Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Behavior Trees in Robotics
KTH, School of Computer Science and Communication (CSC), Robotics, perception and learning, RPL.ORCID iD: 0000-0003-0289-7424
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. , p. 63
Series
TRITA-CSC-A, ISSN 1653-5723 ; 2017:07
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-202926ISBN: 978-91-7729-283-8 (print)OAI: oai:DiVA.org:kth-202926DiVA, id: diva2:1078940
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: 2018-01-13Bibliographically approved
List of papers
1. How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees
Open this publication in new window or tab >>How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees
2017 (English)In: IEEE Transactions on robotics, ISSN 1552-3098, E-ISSN 1941-0468, Vol. 33, no 2, p. 372-389Article in journal (Refereed) Published
Place, publisher, year, edition, pages
IEEE, 2017
National Category
Robotics
Identifiers
urn:nbn:se:kth:diva-202922 (URN)10.1109/TRO.2016.2633567 (DOI)000399348900009 ()2-s2.0-85007048891 (Scopus ID)
Note

QC 20170307

Available from: 2017-03-07 Created: 2017-03-07 Last updated: 2017-10-23Bibliographically approved
2. How Behavior Trees Generalize the Teleo-Reactive Paradigm and And-Or-Trees
Open this publication in new window or tab >>How Behavior Trees Generalize the Teleo-Reactive Paradigm and And-Or-Trees
2016 (English)Conference paper, Published 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.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-194179 (URN)000391921700063 ()2-s2.0-85006371530 (Scopus ID)
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
3. Towards Blended Planning and Acting using Behavior Trees. A Reactive, Safe and Fault Tolerant Approach.
Open this publication in new window or tab >>Towards Blended Planning and Acting using Behavior Trees. A Reactive, Safe and Fault Tolerant Approach.
(English)Article in journal (Refereed) Submitted
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-202923 (URN)
Note

QCR 20170307

Available from: 2017-03-07 Created: 2017-03-07 Last updated: 2017-03-07Bibliographically approved
4. Stochastic Behavior Trees for Estimating and Optimizing the Performance of Reactive Plan Executions
Open this publication in new window or tab >>Stochastic Behavior Trees for Estimating and Optimizing the Performance of Reactive Plan Executions
(English)Article in journal (Refereed) Submitted
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-202924 (URN)
Note

QCR 20170307

Available from: 2017-03-07 Created: 2017-03-07 Last updated: 2017-06-02Bibliographically approved
5. Learning of Behavior Trees for Autonomous Agents.
Open this publication in new window or tab >>Learning of Behavior Trees for Autonomous Agents.
(English)Article in journal (Refereed) Submitted
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-202925 (URN)
Note

QCR 20170307

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

Open Access in DiVA

Colledanchise(7989 kB)267 downloads
File information
File name FULLTEXT01.pdfFile size 7989 kBChecksum SHA-512
c8086870273aa6906b355963947e97d0738916a9e86e38722666cac3b73dcbf3f0c5d74f981e7c55ce772d414d3703e9601b805f5a3a38e3d6a38844b23a4d15
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Colledanchise, Michele
By organisation
Robotics, perception and learning, RPL
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 267 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 722 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
v. 2.34-SNAPSHOT
|