Change search
Link to record
Permanent link

Direct link
BETA
Colledanchise, MicheleORCID iD iconorcid.org/0000-0003-0289-7424
Publications (8 of 8) Show all publications
Ögren, P. & Colledanchise, M. (2018). Behavior Trees in Robotics and AI: An Introduction (Firsted.). CRC Press, Florida, US: CRC Press
Open this publication in new window or tab >>Behavior Trees in Robotics and AI: An Introduction
2018 (English)Book (Refereed)
Abstract [en]

Behavior Trees (BTs) provide a way to structure the behavior of an artificial agent such as a robot or a non-player character in a computer game.  Traditional design methods, such as finite state machines, are known to produce brittle behaviors when complexity increases, making it very hard to add features without breaking existing functionality.  BTs were created to address this very problem, and enables the creation of systems that are both modular and reactive. Behavior Trees in Robotics and AI: An Introduction provides a broad introduction as well as an in-depth exploration of the topic, and is the first comprehensive book on the use of BTs.

Place, publisher, year, edition, pages
CRC Press, Florida, US: CRC Press, 2018. p. 192 Edition: First
Series
Chapman & Hall/CRC artificial intelligence and robotics series ; 6
Keywords
Behavior Trees, AI, Artificial Intelligence, Robotics, Control, Task Switching, Finite State Machine
National Category
Robotics
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-232942 (URN)9781138593732 (ISBN)
Note

QC 20180808

Available from: 2018-08-06 Created: 2018-08-06 Last updated: 2018-09-03Bibliographically approved
Colledanchise, M. (2017). Behavior Trees in Robotics. (Doctoral dissertation). Stockholm: KTH Royal Institute of Technology
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. p. 63
Series
TRITA-CSC-A, ISSN 1653-5723 ; 2017:07
National Category
Computer Sciences
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: 2018-01-13Bibliographically approved
Colledanchise, M. & Ögren, P. (2017). How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees. IEEE Transactions on robotics, 33(2), 372-389
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
Colledanchise, M., Murray, R. M. & Ögren, P. (2017). Synthesis of correct-by-construction behavior trees. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017: . Paper presented at 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, Canada, 24 September 2017 through 28 September 2017 (pp. 6039-6046). Institute of Electrical and Electronics Engineers (IEEE), Article ID 8206502.
Open this publication in new window or tab >>Synthesis of correct-by-construction behavior trees
2017 (English)In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 6039-6046, article id 8206502Conference paper, Oral presentation only (Refereed)
Abstract [en]

In this paper we study the problem of synthesizing correct-by-construction Behavior Trees (BTs) controlling agents in adversarial environments. The proposed approach combines the modularity and reactivity of BTs with the formal guarantees of Linear Temporal Logic (LTL) methods. Given a set of admissible environment specifications, an agent model in form of a Finite Transition System and the desired task in form of an LTL formula, we synthesize a BT in polynomial time, that is guaranteed to correctly execute the desired task. To illustrate the approach, we present three examples of increasing complexity.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2017
Series
IEEE International Conference on Intelligent Robots and Systems, ISSN 2153-0858
National Category
Computer Vision and Robotics (Autonomous Systems)
Identifiers
urn:nbn:se:kth:diva-224272 (URN)10.1109/IROS.2017.8206502 (DOI)2-s2.0-85041952364 (Scopus ID)9781538626825 (ISBN)
Conference
2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, Canada, 24 September 2017 through 28 September 2017
Note

QC 20180315

Available from: 2018-03-15 Created: 2018-03-15 Last updated: 2018-03-15Bibliographically approved
Colledanchise, M., Murray, R. M. & Ögren, P. (2017). Synthesis of Correct-by-Construction Behavior Trees. In: Bicchi, A Okamura, A (Ed.), 2017 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS): . Paper presented at IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), SEP 24-28, 2017, Vancouver, CANADA (pp. 6039-6046). IEEE
Open this publication in new window or tab >>Synthesis of Correct-by-Construction Behavior Trees
2017 (English)In: 2017 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) / [ed] Bicchi, A Okamura, A, IEEE , 2017, p. 6039-6046Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we study the problem of synthesizing correct-by-construction Behavior Trees (BTs) controlling agents in adversarial environments. The proposed approach combines the modularity and reactivity of BTs with the formal guarantees of Linear Temporal Logic (LTL) methods. Given a set of admissible environment specifications, an agent model in form of a Finite Transition System and the desired task in form of an LTL formula, we synthesize a BT in polynomial time, that is guaranteed to correctly execute the desired task. To illustrate the approach, we present three examples of increasing complexity.

Place, publisher, year, edition, pages
IEEE, 2017
Series
IEEE International Conference on Intelligent Robots and Systems, ISSN 2153-0858
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-225808 (URN)000426978205096 ()978-1-5386-2682-5 (ISBN)
Conference
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), SEP 24-28, 2017, Vancouver, CANADA
Note

QC 20180409

Available from: 2018-04-09 Created: 2018-04-09 Last updated: 2018-04-09Bibliographically approved
Colledanchise, M., Parasuraman, R. & Ögren, P. 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
Colledanchise, M., Marzinotto, A. & Ögren, P. 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
Colledanchise, M., Almeid, D. & Ögren, P. 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
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-0289-7424

Search in DiVA

Show all publications