Using Computer Game Behaviour Trees in UAVs – Paper Review

Introduction

As part of my PhD I have to review related scientific papers every week.  To keep me in the momentum and to share what I’m doing I thought it might be a good idea to make a video about each paper and also to post my basic summary and review to my blog along with a copy of the abstract from the paper itself.  So here it goes for my first ever paper review.

You can get this paper from the author’s website at http://www.csc.kth.se/~petter/Publications/ogren2012bt.pdf even without a subscription.

Abstract

Ogren, P. (2014). Increasing Modularity of UAV Control Systems using Computer Game Behavior Trees. In AIAA Guidance, Navigation, and Control Conference (2012) (pp. 13–16).

In this paper, we argue that the modularity, re-usability and complexity of Unmanned Aerial Vehicle (UAV) guidance and control systems might be improved by using a Behavior Tree (BT) architecture. BTs are a particular kind of Hybrid Dynamical Systems (HDS), where the state transitions of the HDS are implicitly encoded in a tree structure, instead of explicitly stated in transition maps. In the gaming industry, BTs have gained a lot of interest, and are now replacing HDS in the control architecture of many automated in-game opponents. Below, we explore the relationship between HDS and BTs. We show that any HDS can be written as a BT and that many common UAV control constructs are quite naturally formulated as BTs. Finally, we discuss the positive implications of making the above mentioned state transitions implicit in the BTs.

Review

This conference paper looks at the the use of behaviour trees (BTs) and their use in UAV control systems.  The paper starts with a basic introduction to BTs and moves through to a pseudo implementation of a combat-ready system and directly looks at the how existing control systems can be best remodelled as behaviour trees.

Behaviour trees (in the context of this paper at least) can be traced back to modern computer games where non-playable characters have had their rules defined by behaviour trees since the mid 2000s in many games.  Within computer games BTs solve the problem of how to manage extremely complex states that define the interactions and behaviour of AI within the game.  Unlike robotics one can argue that computer game design is a mature, rather than research, field that is highly commercialised and as such a consequence of this is the need for reusable and maintainable software that can be supported for a long period of time.  BTs are designed to provide a number of benefits in this scenario:

Modularity of behaviour in particular allowing for easy changes of behaviour when new flows are either added, removed or changed

No explicit requirement to code the transition between behaviours thus reducing the complexity of the problem – this transition is, instead, implicit

A two-way rather than one-way transition making the code more maintainable and allowing for it to be more easily managed and for a better capability to determine how far through processing it is at any point in time

The paper suggests that UAV work has been predominantly focused on the technical challenges that need to be solved (such as the control systems themselves) rather than how best to actually structure them architecturally.  It appears as though the author’s implication (although not directly stated) is that the software currently running many UAV systems does not follow good software architecture practices and that UAV software should learn lessons from existing commercial software used in other sectors.

Behaviour trees are described as a tree structure consisting of nodes and edges.  Nodes are defined with a parent/child relation where a node with no parents is a root node and a node with no children is a leaf node.  Nodes can be one of six different node types depending on whether or not they are a leaf or a non-leaf node.  The different node types allow different types of operations to be performed – be they condition checks, custom actions (depending on the problem domain), sequences of serial actions, parallel actions or decorators (which change the output of child nodes – for example negating another node’s output or adding a timeouts requirement).  The tree is represented graphically with the root node at the top and leaves bottom-most in the tree.  The control loop in the application starts processing from the root node, working down and then back up according to the specific nodes within an individual tree.  This action of the control loop is called a “tick”.  The different structure of BTs allows for switching between tasks in a highly modular fashion depending on the control flow requirements of a particular problem domain.  You could directly encapsulate existing HDS within a single “action” node or design a completely new tree to mirror the functionality.  The paper goes on to give an example of a number of UAV control system tasks expressed as BTs.

The tree structure itself defines the transition between nodes – meaning that there is no explicit requirement for the control software to manage these transitions thus reducing the complexity.  It is the types of node, rather than explicit state management, that defines how they are processed and how transitions are made.  The tree structure also makes it far easier for changes in the structure.  As long as all nodes are connected to children/parents then there is a flow – this makes it very easily to reconnect or move functionality as well as to add or delete it with an obvious immediate impact and a visual confirmation of the change.

This paper is easily readable to those with a basic understanding of algorithms and goes in to detail about BTs even if HDS are not covered in much detail.  Whilst I personally enjoyed this paper I did not feel it added much to the discipline.  This is a paper that is, in effect, just stating “as systems become more complex use tried and tested software architectures rather than trying to overly complicate the issue”.  The paper draws the parallel to the use of “GOTO” statements in antiquated BASIC code saying that these make software unreadable and difficult to navigate and that BTs are equivalent to using functions in modern language.  This is a valid point but an entire paper dedicated to “do not use GOTO statements” for every single problem domain covered by software systems would not add much to the sum of human knowledge.  I feel that there was not much in this paper that expressly concerned UAVs as the same paper could have been as true for a building-wide heating and ventilation control system for a skyscraper as it was for UAVs.  The robotics (and consequentially UAV) area is extremely complex and this presents problems with testability and safety.  BTs potentially offer a way to test discrete functionality that can guarantee behaviour of the whole whereas this possibility wasn’t covered at all in the paper.  Additionally, the paper did not look at any negatives that may come from BTs and why, or where, more traditional approaches may still have merit.  The topics within this paper were certainly interesting and are applicable to many areas of robotics and computer science but other than advertising existing facts to those that may not have known about them did not really look at the true benefits to this domain.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s