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 Generalize the Teleo-Reactive Paradigm and And-Or-Trees
KTH, School of Computer Science and Communication (CSC), Computer Vision and Active Perception, CVAP.ORCID iD: 0000-0003-0289-7424
KTH, School of Computer Science and Communication (CSC), Computer Vision and Active Perception, CVAP.ORCID iD: 0000-0002-7714-928X
2016 (English)Conference paper (Refereed)
Abstract [en]

Behavior Trees (BTs) is a way of organizing the switching structure of a control system, that was originally developed in the computer gaming industry but is now also being used in robotics. The Teleo-Reactive programs (TRs) is a highly cited reactive hierarchical robot control approach suggested by Nilsson and And-Or-Trees are trees used for heuristic problems solving. In this paper, we show that BTs generalize TRs as well as And-Or-Trees, even though the two concepts are quite different. And-Or-Trees are trees of conditions, and we show that they transform into a feedback execution plan when written as a BT. TRs are hierarchical control structures, and we show how every TR can be written as a BT. Furthermore, we show that so-called Universal TRs, guaranteeing that the goal will be reached, are a special case of so-called Finite Time Successful BTs. This implies that many designs and theoretical results developed for TRs can be applied to BTs.

Place, publisher, year, edition, pages
2016.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-194179ISI: 000391921700063ScopusID: 2-s2.0-85006371530OAI: oai:DiVA.org:kth-194179DiVA: diva2:1038488
Conference
Intelligent Robots and Systems (IROS), 2016 IEEE/RSJ International Conference on, 2016
Note

QC 20161019

Available from: 2016-10-18 Created: 2016-10-18 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

fulltext(424 kB)29 downloads
File information
File name FULLTEXT02.pdfFile size 424 kBChecksum SHA-512
410adb55fccdbabb18d1c03ad010ad79d97981f8a4f908c2d1ad4e4aedede8cf430fbb2d9b4416f463c0541778da8f9c6169199db6e96304b9330ade6b6face1
Type fulltextMimetype application/pdf

Other links

ScopusConference web page

Search in DiVA

By author/editor
Colledanchise, MicheleÖgren, Petter
By organisation
Computer Vision and Active Perception, CVAP
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 49 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 129 hits
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