Autonomous Drone Flight with Behavior Trees, AirSim-js and Nodejs
Recently I needed to define and execute several missions for a multirotor drone in the AirSim simulation environment. My plan, use Nodejs and the open-source AirSim-js client library to connect with and control autonomous drones hosted in an AirSim session. That was the easy part. Next I needed a strategy for defining and executing mission flight plans. Initially I considered finite state machines (FSM). But then I remembered reading about behavior trees to implement AI in gaming and robotics. Bingo! In this article I will share how behavior trees greatly simplified my development of drone mission plans and their execution.
Initially I considered finite state machines (FSM). But then I remembered reading about behavior trees. Bingo!
Brief Introduction to Behavior Trees
To provide some context for this article here is a video of a drone flying a short mission in a neighborhood environment. The mission is implemented and executed as a behavior tree.
So what is a behavior tree?
According to Wikipedia:
A behavior tree is a mathematical model of plan execution used in computer science, robotics, control systems and video games. They describe switching between a finite set of tasks in a modular fashion. Their strength comes from their ability to create very complex tasks composed of simple tasks, without worrying how the simple tasks are implemented. … Its ease of human understanding that make behavior trees less error prone and very popular in the game developer community.
If you’re familiar with tree data structures, behavior trees are pretty easy to grasp.
For my application of a behavior tree, each step in a mission flight plan is implemented as either an action node or a control flow node. Sequences of actions and flow control are ordered to create behaviors. Behaviors are structured hierarchically in the form of a tree that are executed in depth-first order.
For a deeper dive into behavior trees check out the follow resources:
Behavior trees for ai: How they work
What is a Behavior Tree
Behavior Trees in Robotics and AI
Blueshell TypeScript Behavior Trees
A number of JavaScript implementations of behavior trees can be found in the npm library. I reviewed several of them and settled on the open-source Blueshell TypeScript behavior tree library.
Blueshell provides a comprehensive collection of action, conditional, composite and decorator node types.
To make Blueshell easier to learn I forked the Github repo and used typedoc to publish the api online at https://ros2jsguy.github.io/blueshell-docs
For this article we will be using the Blueshell node types:
- RunningAction — used to wrap promise-based AirSim-js api.
- Sequence (latched option) — an ordered list of behavior nodes that only succeeds when all of it’s child nodes succeed. Think of this node like an AND logic operator over all it’s children nodes.
- Selector (latched option) — similar to a Sequence except this node succeeds upon it’s first successful child node. Think of this node like an OR logic operator over all of it’s children nodes.
A behavior tree propagates events from a root node down through the tree to be handled by it’s child nodes. The path that events flow is typically a depth-first traversal. At the bottom of the tree are the Action nodes, a.k.a. Tasks nodes. Actions do most of the work within the tree. The nodes above the Action nodes are either control-flow nodes or decorator nodes. Decorator nodes usually perform a transform of some type on either events or results flowing up and down through the tree respectively.
/**
* Handles the event by processing it directly
* or dispatching to child nodes.
*/
public handleEvent(state: S, event: E): ResultCode {
...
}The latched option for Sequence and Selector configures the node to preserve an execution history such that future invocations of the node will resume execution at the child node that running in the most recent execution.
Drone Mission Behavior Trees
The mission behavior tree is designed with 2 main subtrees of behaviors, the main FlightPath subtree and an emergency AbortSequence subtree.
The Mission node is a Selector that only needs one of it’s child nodes to succeed. Since events flow downward from the Mission node to its child nodes in a depth-first order, FlightPath is the main path to which events will flow. If all of it’s child nodes succeed the flight has completed successfully. The AbortSequence subtree will only be invoked if the FlightPath tree fails for some reason. At the bottom of the tree are custom Action nodes that are designed to support long-running behaviors, e.g., 1 second to minutes.
Following is a snippet of the mission code:
A special note aboutFlightPlanSequence. It is a subclass of LatchedSequence that persists in a FAILURE state once it has seen an ‘abort’ event. The effect is to fail-fast and force the flow of events to the AbortProcedure behaviors.
Actions
In a behavior tree, Action nodes do most of the work. The following class diagram illustrates actions available for creating a Mission behavior tree. Notice the AirSimAction class which maintains references to an AirSim-js session and drone vehicle. It uses Promises to execute long running api calls to AirSim.
Tic’ing and Abort Events
Blueshell requires an external event source to drive a behavior tree. For this, generictic events are sent to the Mission node every 500 milliseconds (2 Hz). On each tic event, the Mission node passes the event to the FlightPath node. In the nominal case, FlightPath will pass the event to it’s most recent running child node, e.g., MoveToPos to be processed. When invoked with an event, a node returns a result of either SUCCESS, FAILURE, ERROR or RUNNING. Since we are using long running Actions the RUNNING result is most frequently observed result returned by Mission.
If FlightPath has previously processed an ‘abort’ event it will immediately return a FAILURE result to the Mission node. Being a Selector node, Mission will next send the event to the AbortSequence subtree. This process will continue until the Mission returns any result other than RUNNING.
Putting it all together
At the heart of the program is the MissionControl class. MissionControl is instantiated with a Mission behavior tree. When launched an internal timer generates tic events which are dispatched to the Mission tree. If the a mission anomally is detected an abort method is available to generate and dispatch an ‘abort’ event to the tree to initiate the abort procedure. Frequently actions need to adapt to the state of the mission. For this a MissionState data object containing configuration properties and current state information is passed into the behavior tree on each tic.
Wrapping Up
I found behavior trees simple to learn and apply. Their power is derived from their ability to create complex yet intuitive behaviors from smaller simpler hierarchies of behaviors. The Blueshell behavior tree library took me a little more time than it should have to get started. But once I got my head around the node types and their api I was up and running. The AirSim-js of which I’m the author is simple to use and was easily integrate into custom Blueshell Action nodes.
If you have interest in learning more about AirSim-js or Blueshell check out the links below. And finally you can find the code for the full demo here.
Thanks for checking out this AirSim-js introduction. If you liked this article please give it a Thumbs Up and a share on twitter. You can reach me on Twitter at @ros2jsguy and find code that I’ve developed or working on at my GitHub account: https://github.com/ros2jsguy
Resources
Introducing AirSim-js
airsim-js-drone-mission Github repo
Blueshell API docs
Blueshell npm
Blueshell Github repo
