Programming Behaviours

Owned by Daniel Stonier
Oct 30, 2016
4 min read


About

Comparison of three different approaches to handle behavioural logic inside a robot.

  1. Pipes || Delayed Pipes - simply scripted flows (e.g. python coroutines) that yield control from one function to the next, similar to linux command line pipes.
  2. Finite State Machines 
  3. Behaviour Trees - framework that has largely replaced finite state machines for controlling NPC AI's. 

Notes

FSMs & Asynchronicity

FSMs in general do not work well with asynchronicity. A whole state machine is by nature a synchronous entity, and the only place that can be truly asynchronous is inside a single state. Hence smach states are always designed with the creation of pubs, subs and services inside single states. 

FSM Asynchronicity - Rules of Thumb

  • Do not fight the synchronous nature of the state machine, it will just make your head explode.
  • Don't create blackboard/userdata (smach) variables that are shared with the world outside the state machine

Concurrency

None of the approaches handle parallel execution (except inside a behaviour or state). This needs to be managed by something higher.

  • Pipes do not support concurrency at all.
  • Smach has concurrency containers, but use these only for very small blocks (effectively making it a single state) otherwise cross wiring pre-emptive capabilities becomes a nightmare (you are breaking the concept of a state machine).
  • Behaviour trees supports concurrency only to the point of checking conditions, not for parallel execution of behaviours.

Priorities

An example: battery-check-gohome-dock-recharge > move-around-doing-task or wait_for_emergency_zone_to_clear > moving_to_next_point.

  • Pipes have no concept of priority built in.
  • HFSM's enable a certain degree of priority handling to shift between super states.
  • Behaviour trees have formalised the notion and have it built in.

Planning

None of the three methods handle planning. The kind of planning I am thinking about here is to modify the sequence of behaviours to achieve a goal. e.g. inserting subtrees into behaviour trees as a consequence of some GOAP (goal oriented action planning). To be able to reassemble sequences like this is very important, e.g. 

move to A -> wait1 -> move to B -> wait1 -> moveToC -> elevator -> moveToD -> wait2 -> homebase

TicToc

Being able to tic an execution engine, breathe, make some changes and then tic it again seems to be a very strong design pattern. Ecto follows this principle, Jihoon naturally converged to this principle when developing the waiterbot. What are the benefits?

  1. You can stop and reassemble parts of the behaviour jigsaw.
  2. You can periodically introspect on the status of all elements in the subtree.
  3. You can stop and inject updates/parameterisations without having to worry about concurrency complications (namely 'locks')

Support for tic toc:

  • Pipes don't have anything
  • State machines don't have anything
  • Behaviour trees have this built in

Algorithm Comparison

Pipes

Simple to setup, can script something similar in 100 lines or less. The executive_teer package does this in an ideal way with coroutines and also adds preconditions to the pipes, so different preconditions can trigger the start of a pipe flow and kill all others. Not easy to introspect.

Finite State Machines

Give you a structured way to arrange a synchronous flow of events. Synchronous the important thing. I am thinking of them these days as glorified actions - great for when you want a little bit of decision making/interaction inside a task. You can introspect, but only on transition changes which is perhaps not frequent and doesn't give you micro feedback from inside a state.  Trying to scale up from there into a robot manager runs into all kinds of problems - the inability to modify it internally without forcing it to handle concurrency problems, the lack of fast periodic feedback, no ability to handle priorities easily and the usual fsm problem - wiring hell as things get complicated.

Behaviour Trees

Same sort of capabilities as finite state machines but with the advantages of priority handling and the tic toc benefits (periodic parameterisation, updates, feedback). The tic toc thing is huge - especially if we want to handle dynamic changes to goal behaviours.

Resources

Behaviour Trees

Software Packages

Smach

The entrenched official package. Lots of other small packages started up, but hard to get around this one for doing co-ordination since so much is there already.

An interesting observation on how to mix battery readings with waypoint management - it's hard with smach (this probably motivated pi trees).

Source code:

Smach

I like to think of smach engine as a glorified action. They both can be preempted. They both execute something specific. Smach has the power to be alot more complex (via the state machine concept) and the feedback has a formal structure that can be visualised. Trying to get it to do more than this though is like pushing the state machine into a place where state machines just aren't meant to go (e.g. priorities, concurrency, planning).

Executive Teer

Coroutines alternative to smach, stopped in 2012. I like this concept as a purely programming concept. It allows very parallelised and dynamic behaviours (see his tutorials with turtles moving around and pausing/resuming behaviours) constructed along the idea of ‘command line pipes’ via coroutines. It is low level though, need alot of love to build up, but by that token. it's not very constrained either.

Pi Trees

PiRobot's patrick built a simple function based behaviour trees module. He also blogged a really good article about behaviour trees for robotics.

PR Behaviour Trees

pi_trees but with coroutines instead of functions. Built in Jan 2015.

ALMC/Behaviour Trees

C++ implementation of behaviour trees. Quite formalised.

Cogniteam/Decision Making

OWYL

The only reasonably complete behaviour trees package for python, unfortunately docs are no longer public and so I haven't explored at all yet. Stopped development 2-3 years ago.