[Review] Behaviour Trees for Modular UAV Control

October 29, 2018 ยท 3 minute read

Paper Review 29-10-2018

Increasing Modularity of UAV Control Systems using Computer Game Behaviour Trees

Petter Ogren, 2012 AIAA Guidance, Navigation, and Control Conference, Minneapolis, Minnesota.

Aims of paper

The author outlines his argument for the adoptation of the method of Behaviour Trees (BT) as a replacement to Hybrid Dynamical Systems (HDS) for UAV Control. In this paper

  1. Both HDS and Behaviour Trees are broken down and explained.
  2. Examples and Advantages of BTs are presented.
  3. It is shown that all HDSs can be formulated as BTs.

Paper summary

The author tackles the problem of how to choose the correct task (designing the control architecture) for UAV control. This problem is almost identical to (non playable character) NPC control in video games where there has been much work in using Behaviour Trees.

HDSs are problematic for applications with large numbers of discrete states (e.g. robotics and drone control). The discrete dynamics of the HDS is explicitly encoded into the transition functions which effect the modularity of HDS systems. If a state is removed all transitions must be adjusted to ensure HDSs are valid.

BTs, however, are created of a tree structure where any subtree block can be moved to anywhere else in the tree, or removed, and still be valid. The Behaviour Tree is made up of 4 different nodes and 2 different types of leaf from which we can design the behaviour of an agent in certain situations. When a node is processed it returns either success, failure or running in response to the returns of its child nodes.

  1. Selectors - “OR” nodes which return success if one of its children succeed
  2. Sequence - “AND” nodes which exectue all children and fail if one of its children fails
  3. Parallel - If some number of its children succeed when the children are all run in parallel
  4. Dectorator - Special alterations to the returns of its children e.g. time delays

We also have the following leaves

  1. Action - Some prespecified action which returns success if completed
  2. Condition - As expected. Often used in conjunction with a sequence and a sibling action for condition actions.

The benefits of using BTs then are that the transition functions are implicitly encoded d by the tree structure rather than the explicit transition functions within the HDS technique. The combination of the Selector and Sequence operators provide a complete system with which to specify control. The author uses a programming language analogy to motivate the advantages of using implict transitions as they allow greater freedom and flexibility (two-way communication) vs previous methods.

Paper Review

This paper appears to serve to teach readers about the concept of behaviour trees with an addendum which is to why they should be used. A large portion of this paper is devoted to explaining what a behaviour tree is with many theoretical examples given which is good. As expected the author appears to be biased towards adopting game behaviour trees as much of the paper is describing how BTs theoretically improve upon HDSs, but it is a somwhat unfair comparison with no disadvatages being mentioned and no real experimental evidence is presented to back up their claim (although it does mention that UAV trials are in the works). This paper is worth reading if you wish to find out how behaviour trees work (although I imagine there is more complete literature from video game researchers) but much of it seems to be more of an opinion piece on why HDSs are bad and BTs are good.