Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees
KTH, School of Computer Science and Communication (CSC), Robotics, perception and learning, RPL.
KTH, School of Computer Science and Communication (CSC), Robotics, perception and learning, RPL.ORCID iD: 0000-0002-7714-928X
2016 (English)In: IEEE Transactions on robotics, ISSN 1552-3098, E-ISSN 1941-0468Article in journal (Refereed) Published
Place, publisher, year, edition, pages
IEEE, 2016.
National Category
Robotics
Identifiers
URN: urn:nbn:se:kth:diva-202922OAI: oai:DiVA.org:kth-202922DiVA: diva2:1078931
Note

QC 20170307

Available from: 2017-03-07 Created: 2017-03-07 Last updated: 2017-03-07Bibliographically approved
In thesis
1. Behavior Trees in Robotics
Open this publication in new window or tab >>Behavior Trees in Robotics
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Behavior Trees (BTs) are a Control Architecture (CA) that was invented in the video game industry, for controlling non-player characters. In this thesis we investigate the possibilities of using BTs for controlling autonomous robots, from a theoretical as well as practical standpoint. The next generation of robots will need to work, not only in the structured assembly lines of factories, but also in the unpredictable and dynamic environments of homes, shops, and other places where the space is shared with humans, and with different and possibly conflicting objectives. The nature of these environments makes it impossible to first compute the long sequence of actions needed to complete a task, and then blindly execute these actions. One way of addressing this problem is to perform a complete re-planning once a deviation is detected. Another way is to include feedback in the plan, and invoke additional incremental planning only when outside the scope of the feedback built into the plan. However, the feasibility of the latter option depends on the choice of CA, which thereby impacts the way the robot deals with unpredictable environments. In this thesis we address the problem of analyzing BTs as a novel CA for robots. The philosophy of BTs is to create control policies that are both modular and reactive. Modular in the sense that control policies can be separated and recombined, and reactive in the sense that they efficiently respond to events that were not predicted, either caused by external agents, or by unexpected outcomes of robot's own actions. Firstly, we propose a new functional formulation of BTs that allows us to mathematically analyze key system properties using standard tools from robot control theory. In particular we analyze whenever a BT is safe, in terms of avoiding particular parts of the state space; and robust, in terms of having a large domain of operation. This formulation also allows us to compare BTs with other commonly used CAs such as Finite State Machines (FSMs); the Subsumption Architecture; Sequential Behavior Compositions; Decision Trees; AND-OR Trees; and Teleo-Reactive Programs. Then we propose a framework to systematically analyze the efficiency and reliability of a given BT, in terms of expected time to completion and success probability. By including these performance measures in a user defined objective function, we can optimize the order of different fallback options in a given BT for minimizing such function. Finally we show the advantages of using BTs within an Automated Planning framework. In particular we show how to synthesize a policy that is reactive, modular, safe, and fault tolerant with two different approaches: model-based (using planning), and model-free (using learning).

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2017. 63 p.
Series
TRITA-CSC-A, ISSN 1653-5723 ; 2017:07
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-202926 (URN)978-91-7729-283-8 (ISBN)
Public defence
2017-04-11, F3, Lindstedtsvägen 26, Stockholm, 09:30 (English)
Opponent
Supervisors
Note

QC 20170308

Available from: 2017-03-08 Created: 2017-03-07 Last updated: 2017-03-08Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Colledanchise, MicheleÖgren, Petter
By organisation
Robotics, perception and learning, RPL
In the same journal
IEEE Transactions on robotics
Robotics

Search outside of DiVA

GoogleGoogle Scholar

CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf