Behavior Trees

Description: Behavior Trees Intro

Keywords: decision_making

Tutorial Level: BEGINNER

Next Tutorial: decision_making/Tutorials/BehaviorTree(C++)

Introduction

We would like a system that is more general the FSMs,more structured than programs, and lighter weight than planners. Behavior trees were developed by Geoff Dromey in the mid-2000s in the field of software engineering, which provides a modular way to define software in terms of actions and preconditions. They were first used in Halo 2 and were adopted by a number of other games such as Spore.

HTN + HSM = Behavior tree

• HTN - Hierarchical task network (planning)
  • Goal directed but ignores execution
• HSM - Hierarchical finite state machines
  • Reactive (state oriented) but not goal oriented
  • Intuitive but worksome
• Behavior tree
  • Task-oriented rather than state-oriented
  • Modular, reusable behaviours
  • Can easily be built up into hierarchies

Behavior tree building blocks

• Tasks [boxes] - A preemptive task. Can be a local function or an actionLib call, will return true, false or error code.
• Sequencer [right arrow] - all tasks until one fails
• Selector [circle] - all tasks until one succeed
• Parallel [parallelogram] - do in parallel all tasks connected
• Decorator [text on the edges] - filters on return values (and execution)

The behavior tree snippet above reads:

• Goto car and in parallel plan paths while doing the mission
• During the mission first stand up and then in parallel monitor not to fall while searching for an object and going towards it
• The object is first validated by an operator, and then tracked while the robot approaches it... etc...
• !L! is a while decorator. It continues as long as the task returns false. It is used in the scenario above to assure that if the mission fails if will be re-run, if the object serch and go failed it will be re-run, and if the operator did not respond the rutine will be executed again.

Reading material

1. FSM, HSM and Behavior treeshttp://www.cs.umd.edu/class/spring2013/cmsc425/Lects/lect20.pdf

2. Behavior trees http://aigamedev.com/insider/-presentations/behavior-trees/