I recently caught sight of the article Subsumption for the SR04 and jBot Robots over at the Dallas Personal Robotics Group's webpage. What is sad is that the first thing that David Anderson goes into is technical details regarding their timing loop. Sadly, timing has nothing to do with implementing the subsumption architecture. Our recent explorations on the SRV-1 demonstrate this nicely, I think.
At AAAI, Jon and I implemented code for the mini-robotics-challenge that was hosted in our session. We had to program a robot that would:
This is a trivial task, but all the participants were using robotics platforms they had never seen before, and had roughly 1.5 hours to implement their solutions. Having first seen the SRV-1 just a day before, we had ported the Transterpreter to it, and had basic motor control and access to the IR sensors. Using this, we looked at the problem, and tackled it by implementing a three-layer subsumption architecture.
At the lowest level, we wanted our robot to go forward. We wanted a higher-level behavior that would avoid obstacles, and a third, even higher level behavior that would (after 30 seconds) replay the motor commands that had been generated in the previous 30 seconds (causing the robot to retrace its steps). This is a bit odd as subsumption architectures go (having a layer that suppresses everything below it simply to replay previous actions), but it yielded a very clean implementation.
What follows is the network, and a step-by-step decomposition of how it worked.
Each orange box represents an occam-pi process; in some languages, you might call these "threads". However, in occam-pi, processes have certain properties. First, they are completely sealed, and therefore, no other process can manipulate their state; for example, anything in the "forward" process is completely isolated from the "avoid" process, and visa versa. Also, occam-pi processes are incredibly light-weight: we can run hundreds of these processes on robots the size of a LEGO Mindstorms or the SRV-1, and therefore casually write highly concurrent programs for very small robots.
The arrows in this diagram are channels; they carry data from one process to another. In fact, channels are the only way two processes can communicate with each-other. First, they are unidirectional; you can only talk in one direction down a channel. Second, they are blocking, meaning that once committed to a communication (either a send or a receive), the communicating process deschedules, and waits until the other half of the communication is carried out. This explicit synchronization makes it easy to reason about many different processes taking turns doing computation and communicating between each-other.
With this brief background in occam-pi, you can begin to piece together the network. The forward process sends motor commands to a suppressor process (S1), which communicates on to another suppressor process (S2). This then communicates to a delta process (which copies its input to two outputs). One of those outputs flows to the motors, and the other to a process called record, which records all the motor commands sent to it. In the common case, both suppressors are inactive, and motor commands flow around the network as depicted below:
When an object is detected, the avoid process kicks in. Note that it does not "turn off" or "disable" the forward process---both are always running concurrently. However, suppressor S1 becomes active when the avoid process goes active. It does this when it detects something in front of the robot using the IR sensor. It then begins sending commands to pivot the robot to the left. (This is a pretty dumb robot, really.) These new commands are routed through S1 instead of the commands from forward, and the robot pivots away from the obstacle (and records the pivot as well).
The trickiest bit of work comes when we begin replaying our movements after 30 seconds have passed. The live portions of the network look like this:
The replay module suppresses the output of both the forward and avoid processes. It also inhibits communications between the delta process and the record process; this is because we definitely do not want to be recording the playback! (We made this error, initially; it yielded very strange robot behaviors, and usually ended in both a crash of hardware and software.)
The replay module requests actions from the record process, and then plays each of those actions down the channel it has to S2; these are routed through to the run.motor process. The end result is that our robot replays all of the actions that were recorded over the previous thirty seconds.
It may, or it may not---it depends on how you like to think about control systems for embedded devices (like little robots). I prefer this model, where nowhere in my code am I worrying about timing---instead, I'm just worrying about where my data is flowing. In this case, I'm flowing motor commands from one process to another, and I've written special processes (the suppressors and inhibitor) to control how that data flows through the network. The language and runtime are responsible for handling the concurrency---not me.
For a C programmer, this is a completely foreign idea. However, it is (I believe) the case that C is generally useful only for very specific tasks, like hardware interfacing. Handling complex data structures, complex data flows, and any kind of concurrency or parallelism is something that should be left to the compiler, not the programmer. Put another way, we as programmers are too error prone to be left on our own writing complex control loops, and languages like occam-pi are a first step towards managing that complexity.
As always, we encourage you to take a look at RoboDeb if you're interested in the intersection between robotics and concurrent programming languages. We're very, very close to releasing the newly revised LEGO Mindstorms runtime, which will let you explore occam-pi on your Mindstorms as well. (Our NXT port will follow that release.)
Most of the code for this was written in the twenty minutes before the robotics competition. I could go into the code here, but for the moment will beg off (it is a beautiful day, and I'd rather be outside). However, you can see the code online in our Subversion repository.
If you want to know more about the code, drop me an email (matt at transterpreter dot org), and I'll put together a post that goes through it in more detail. You might start with Jon Simpson's paper Mobile Robot Control: The Subsumption Architecture and occam-pi (PDF), as it goes through a similar process network, and includes code for the inhibitor and suppressor processes. (It will be more readable than anything I hack into the 'blog, anyway.)