Complexity in highly automated robotics systems
Introduction
Automating a drone-in-a-box system turns out to be quite difficult. At mapture.ai we developed our own software to automate the drone-in-a-box operations to a high degree. The software listens to requests from the user and performs the required actions in the correct order. For example, the drone should only take off when the box has been opened and the pre-flight conditions are met. At the same time, the software should be able to deal with unexpected results. For example, when the communication with the user is lost, it should bring back the drone.
The method that we developed at mapture.ai could just as well be applied to other types of robots. Actually a lot of inspiration for the software comes from the gaming industry, where non-player-characters are programmed to display complex behavior.
Challenges
Building a highly automated system means that the user only provides high-level objectives, such as “Fly at coordinate x”, “Standby”, “Sleeping”. The software needs to figure out how to achieve these objectives. For example, if the user sets the objective to “Flying”, the software needs to wake the drone up, open the box, perform pre-flight checks, takeoff and finally fly towards the waypoint. In reality, there are many more steps in between.
The steps that need to be taken also depend on the current state of the system. For example, if the drone is already flying, it does not need to wake up the drone etc. If the drone is currently charging, it should first stop charging before opening the box etc.
It is also very important that every step along the way is abortable. If the user decides to change the objective, the software should change the course of action as soon as possible. What makes this extra difficult is that not every action can be aborted abruptly. For example, disabling the charger takes a couple of seconds. Only after that should the software proceed to open the box.
The user can request any of the following high-level objectives for our mapture.ai drone-in-a-box system:
- Sleeping
- Standby
- Charging
- Flying (at coordinate x)
- Execute waypoint mission
It is also possible to request a sequence of multiple objectives at once. For example, the operator can set objectives “Execute waypoint mission” followed by “Sleeping”. When the waypoint mission is finished, the new objective is automatically set to sleeping. The software then takes all of the steps to get there (return to box, land, close box, charge drone, go to sleep).
Finite State Machines
Since the drone-in-a-box system can be in many different states, the first thing that comes to mind is a Finite State Machine (FSM). Our drone-in-a-box currently runs on a state machine, which works quite well. However, there are some important downsides to this with respect to asynchronous actions and handling objectives.
Simplified State Machine diagram used for our drone-in-a-box system
Asynchronous actions
An asynchronous action is any type of action that takes some time to complete. While waiting for the action to complete, the software should keep doing other things. Because we are dealing with robotics in the real world, almost every action is asynchronous. Even simple commands (i.e. turn on the strobe light) take a little bit of time, because we have to wait a couple of milliseconds for the confirmation from the drone.
State Machines are not very good for asynchronous actions. Fortunately there is an acceptable work-around for this: When a state is entered, it can start running an asynchronous function. The result of the asynchronous function then triggers an event which makes the state machine transition to the next state. However, other events can also trigger a state transition before the asynchronous function is ready. The asynchronous function then keeps running in the background but we lose control of it. This could in some situations result in two conflicting actions to run simultaneously.
In the state machine that we implemented for our drone-in-a-box system, we don’t allow transitions that are directly triggered by an external event (except for error recovery). This limits the usability of the state machine architecture and we still need to be very careful not to accidentally add such a transition.
In our state machine, we recognize two types of states:
- Asynchronous function states: States in which an action is executed
- Passive states: States that observe the objective and initiate a transition if necessary
The disadvantage of this approach is that we cannot easily abort asynchronous functions. We therefore split up some functions into multiple states. This is why we have “charging.starting”, “charging.busy” and “charging.stopping”. “charging.busy” is the only passive state which can be aborted.
Objectives
The other missing aspect in the state machine architecture is the ability to figure out which steps to take to achieve a certain objective. Our approach to this is relatively simple, but it doesn’t scale well and is error-prone.
In every “passive” state, we define the next action required to move towards an objective. For example, in the “standby” state, there are three different possible next actions. Depending on the objective, the state machine transitions to “shutdown”, “charging”, or “box opening”. These lists are now hard-coded for each passive state. This makes it very time-consuming to add new objectives or passive states, because any changes here need to be tripple-checked and tested extensively.
Alternatively, a graph-based pathfinder approach could be implemented to automate this. But such a graph would need to be maintained in parallel to the actual state machine, also risking errors in the process.
Behavior Trees
Although our drone-in-a-box system currently works great using the FSM approach outlined above, it has become increasingly harder to expand the functionality of the system. We have started to explore other architectures that could help us expand the functionality or to develop future software for other drones and robots.
Behavior trees (BTs) are very popular for creating “AI” non-player characters in games, where the behavior is 100% automated. Behavior trees are also widely adapted in robotics and are often used with robots that run on ROS2.
Example of a behavior tree ( source:roboticseabass.com)
Our challenge with asynchronous actions is not directly solved with behavior trees. However, the popular BehaviorTree.CPP library is well documented and has an interesting approach to reactive nodes. This would make it feasible to use abortable asynchronous actions inside behavior trees. This is advantageous compared to the state machine design, where we had to split abortable asynchronous actions into multiple states.
However, the challenge we have with objectives in state machines still persists when working with behavior trees. If we were to implement objectives, each objective would have a separate tree. Parts of the tree could be re-used, but adding new objectives would still be cumbersome. It would also be challenging to recognize that aborting an action is not needed in some situations when the objective is changed.
Goal Oriented Action Planning
Another more complex algorithm for AI in videogames is Goal Oriented Action Planning (GOAP). To achieve a certain goal, a plan is constructed consisting of a series of actions. This could be a very good fit for our drone-in-a-box system, but also for complex robotics in general. The operator would set the goal ( objective), and the GOAP algorithm would find the required series of actions to achieve the goal.
There is not as much literature on GOAP as there is on FSMs and BTs. The use of GOAP for robotics seems limited so far. The original paper on GOAP does not provide a solution for a clean shutdown of abortable asynchronous actions. It also doesn’t know wether to * abort or continue a running action* when the plan is updated.
Although these problems are not solved by GOAP directly, it is possible to extend the algorithm to fulfill our requirements. For the clean shutdown, the running action could simply listen to an abort signal and act accordingly. But when the goal changes, it is not always necessary to abort the current action.
For example: The objective (goal) is changed from “charging” to “sleeping” while the drone is landing. For both goals, the drone needs to land. Instead of aborting the landing and then start the landing again, it should continue the landing action and schedule the next actions from there.
However an other example is when the objective (goal) is set to “charging” while the drone is performing a photo mission. Should it abort the photo mission? By updating the objective, the user essentially tells the system that the outcome of the photo mission is no longer relevant.
One way to decide for abort/continue is to generate two plans and pick the “best”: One path that waits for the action to complete and another path that aborts the current action. Following the original GOAP approach, the decision could be made based on penalties for choosing certain actions over others.
A simpler method would be to re-plan from the state before the current action. If the first action of the plan is still the same, the action is not aborted. For the drone-in-a-box system, this is perfectly suitable.
Conclusion
The state machine and behavior tree methods both have their limitations. The GOAP method with the mentioned extensions seems to be very useful for controlling highly automated robotics systems. Although we are not rewriting the software at this moment, GOAP would definitely be the algorithm of choice for future updates or new robot controllers.