Here is a primer on how to design and apply this remarkable microcontroller architecture design to your next robotics project. My goal here is to show you the basic concepts, a step by step development process, and ultimately take you through a real application and build a small robot that is completely controlled by this architecture. Since this is a very abstract and complex subject, my goals are to describe the process in simplified everyday terms so you can apply this to your application with a minimal learning curve.
Note: Thanks to members of the Seattle Robotics Club for pointing out how Brooks method of subsumption has been superceeded by a different method of Subsumption in modern times. While Brooks based his architecture on the lower levels having the lowest competence with overlying levels of increasing competence and decreasing priority. Modern Subsumption arranges the layers from bottom to top in increasing PRIORITIES, that can subsume lower levels of less priority. Still, the history of Subsumption Architecture stands firmly on the foundations laid down by Rodney Brooks in 1985.
Background - What is Subsumption Architecture?
In September, 1985 Rodney Brooks of the MIT Mobile Robotics published a landmark paper on a new architecture for constructing and programming robot controllers. (Brains) This concept allows parallel processors to be divided up into Levels of behavior in which the upper levels which perform higher cognitive functions can subsume lower levels and take over control. In plain terms, you have a stack of 2 to 8 layers of processors, the top layers can override (subsume) any commands the lower layers give to for example to the motors, or other output devices so they can perform more advanced behaviors.
An example would be the Level 0 microcontroller can react to external stimulus such as touching the whiskers, or backing off if it detects an approaching object. Otherwise, it just sits there waiting. Level 1 would at periodic intervals, or when it sees fit override the outputs and steer the robot around. The instincts of the lower levels remain intact, if we hit something while in wander mode, the Level 1 module relinquishes the Subsumption and allows the whiskers data used by Level 0 to turn away from the impact. So Layers can be added to achieve increasing levels of machine intelligence and behavior. An interesting aspect of this is that all sensors go into the inputs of all layers simultaneously. Level 0 may interpret the IR proximity of an object as something to back off from, but the upper Levels will subsume it if needed to more closely approach something for study. Upper layers can not only suppress the outputs of lower levels, but can also inhibit the inputs of them as well. You could then for example block the whisker input to Level 0.
This is the basic conceptual drawing, adapted from Brooks original paper. The lowest level drives the motor, based on input stimulus from the sensors. (For example: Whiskers). However, the Wander module at level 1 can "Subsume" or take control of the lowest "Avoid" level when needed to do a more complex action. Similarly, inputs can also be overridden, as the "Explore" module on Level 2 is subsuming the whisker inputs. This is only a representation - the actual wiring does not do this exactly, but is accomplished by accessing the internal registers on lower levels directly.
Layers of Control
- The robot control system can be constructed in functioning groups, each level is a complete working system with a fully competent behavior for survival of the robot.
- Each element of every level is a simplified collection of completely asynchronous Finite State Machines (more on that later)
- Parallel processing of low bandwidth elements can achieve far better performance and realism of achieving an insect like intelligence, and is far easier to program than one huge linear program.
- The simple Muliti-Processor architecture can do as many simultaneous tasks or behaviors simultaneously, using inexpensive "dime a dozen" processors.
Most conventional robot control programs progress in a linear fashion, from sensory input to actuator drive. Multi tasking is not normally an option, and to be able to do dozens of simultaneous operations requires a very fast processor and some horrendous programming methods.
- This is a much more hardware oriented design approach. If you are not comfortable with working with half a dozen microprocessors at the same time, or building a larger board to accommodate a few more elements, than this may not be a viable solution. I've built this architecture before, and used $1.50 PIC processors such as the PIC12F629 or the $2 PIC16F628 with no problems.
- Your brain will spin sometimes trying to think in the abstract subsumptive behavior mode!
The Eight Layers System
Brooks proposed a seven layers of behavior system, which he was able to achieve in the labs at MIT to about the third level in his experiments, starting with Level 0:
Level 0: Avoid - Avoid contacts with objects, both moving and stationary
Level 1: Wander - Wander aimlessly around without hitting things
Level 2: Explore - Identify the most distant reachable goal and go to them.
Level 3: Mapping - Build maps of the environment and plan routes from one place to another.
Level 4: Changes - Notice changes in the environment
Level 5: Reason - Reason about the world and perform tasks related to certain objects
Level 6: Formulate - Change the local environment in some way.
Level 7: Reason 2 - Reason on the behavior of objects in the environment and modify plans accordingly.
Obviously, this gets pretty off the wall near the end of this list, but the idea is to have higher layers of behavior - hence artificial intelligence (A.I.) gradually subsume control of the robot. I can see getting into about layer 4 or 5 in home robotics.
Brooks Idea of one of the modules in each layer is illustrated to the left. Inputs can be either from sensors or data outputs from other modules. Outputs go to other modules that can drive motors, or actuators. Each module contains a reset, for restarting the system, and a critical item - a timer. Think of it as the "attention span" of the behavior. What is difficult to comprehend at first is the inhibit and suppression input circles. Again, remember this is how Brooks theorized control over a module by another. The actual performing of this function is another matter covered later.
Behaviors are Everything
Perhaps the biggest change you will have to make in using this architecture is the way YOU think! Normally, programming bots consists of loops, subroutines and generally continues looping over and over again to keep the robot running. Most robots built by home builders are reactive machines built this way. They simply go forward, until they hit something, then veer away from it traveling until they either get stuck or run out of batteries. From what I've seen, nearly 95 percent of home bots are made this way. How much more work would it be to say thrown in a socket, and a few bucks more in processors and have the next level of AI at your disposal? Now, onto designing an actual working Subsumption robot...
Asynchronous Augumented Finite State Machines
What is a AFSM?
To the right is a simple FSM which can be used in a Sumo Bot, or perhaps some sort of autonomous battle bot. A FSM is an abstraction to help us design a robot control program. The robot can be in one of three behavioral states: Low Battery, Attack, and Wander. There are by definition, NO intermediate stable states. Lines connecting states are the transitions (microsecond type stuff) that cause the state changes. An example would be upon power up, you are in the random Wander state. This for example causes the robot to move about in a random manner, avoiding obstacles. If the battery voltage drops below 8 volts in this case, the state jumps to the Low Batt state, which stops the bot, and woefully calls for help from its master. But if everything is ok with the battery, and the opponent is spotted say by infrared beacon, then we jump to the Attack state, which initiates a full speed charge toward them to push them out of the competition circle. Similarly, if the batteries get low during Attack, then we will jump to the Low Batt state. If the enemy is lost or escapes, then we go from the Attack back to the Wander state.
So what is an Asynchronous AFSM? Each level in a subsumptive architecture consists of chained or parallel FSM's, none sharing a common clock or synchronized in any way. The Augumented part is the added timers. That's the secret of success here, everything can operate independently yet in sequential harmony to achieve a much higher level of behavior.
Testing the States
As with any multi IC project, each and every module in the set will have to be thoroughly debugged and tested before inclusion in each level. Programs for each element or module as Brooks calls them are usually quite simple, and it is only together the complex actions result. We certainly don't want an erratic crazed module subsuming a normally quiet and sane robot!
Physical Construction Considerations
Board size and layout
Consider using a protoboard that is twice to four times the surface area of a conventional project. Multi processors can take up a lot of real estate, with each level using anywhere between 1 and half a dozen small micros. But just keep in mind how much simpler the programming will be in the end. lo
I can't imagine building this with the huge Basic Stamps, with their hefty $50 price tag each and voluptuous mini PCB's, however, one can easily achieve a few levels of Subsumption with only two Basic Stamps, and at a bearable cost. The best solution is to use the dirt cheap PIC processors by Microchip. I program them with PICbasic by Microengineering Labs and can easily get them for under a dollar each for the more basic ones, or a whopping 5 bucks for the really meaty fast ones. For under $20 in processors, which don't need the crystal - use the internal RC oscillator - you can make a really capable architecture in your new system.
The two routes for working with the relatively simple wiring of these devices are conventional proto boards from Radio Shack, with sockets for ALL ICs, and using small 30 gauge solid wire wrap wire to interconnect. Alternately, you can certainly prototype it up on a solderless breadboard (also from RS), and as an additional and more final option, you can for under $20 get circuit boards made by Express PCB.com for some really professional results.
Changing your thinking
You've got to stop thinking in terms of giant endless program loops and one giant complicated program for starters. Were going to be working with small blocks of programs, each an individual finite state machine with simple standard programming each. Lets start by roughing out a basic Subsumption demonstration, using two levels, and only a few components. From this you'll be able to grow and create you own more advanced systems.
Designing for Subsumption
There are many ways to implement a subsumptive architecture. One way is a giant multitasking processor, with hordes of subroutines each representing a FSM. Each sub routine is looped through in a single pass, and the results and place holder are stored in RAM. Then we jump to the next FSM subroutine. After running a dozen or more of these at a high rate of speed, we start over again on each one, taking off from our saved positions in RAM from last time. This is multitasking "almost" parallel architecture. If your a computer genius which I am not, you may go that route to implement SA. Here's how I did it, from a much simpler hardware aspect.
Lets start with the basic Level 0 module, the Avoid module. It consists of one input, a subsume input, and one output. I used a very basic 8 pin PIC12F629 for this. The output which drives an LED normally is set to blink at 1 Hz - or one flash per second. If the subsume input is Low - NOT subsumed, then it runs happily its modest program, (which of course could be anything) and blinks away.The input is ignored unless the subsume goes High. IF the subsume input goes high, an peculiar thing happens, the input = the output. This is easy to do in code with one line. When it goes low again, normal operation occurs.
Now lets consider a simple Level 1 module, the Wander module. Lets say its going to be the highest level, so has no inputs for Subsumption for now. It consists of two outputs, a data out, and subsume output. (Again, were not quite building a robot brain here yet, so hang on) It has an internal timer which can be set for any interval, or can be triggered by an external event such as a sensory input. Its function in our demo is to run its program at the same time as the Level 0 program, independently. It flashes the output on and off at 10 Hz. Every 10 seconds, it makes the Subsume output go high for 10 seconds, then go low again over and over. That's all it does at this point.
The fun begins when we connect the two blocks together. The output of the Level 1 module connects to the input of the Level 0 module. Also the Subsume output connects to the Subsume input of the Level 0. What will happen? Level 0 is running happily along, blinking its LED on its output every second. Then, for no apparent reason, the Level 1 module subsumes the lower one and now the LED on the output of the Level 0 module blinks at 10 Hz! Then after 10 seconds, it goes back to its normal mindless state and blinks happily at 1 Hz.
Considering the Ramifications
This simple experiment which cost me $2 in parts is a very simplified demonstration on how the Subsumption Architecture works. Upper layers taking control of lower layers, asynchronously. If I would have had a third layer - Level 2, it could have say slammed out something more intelligent, such as Morse code of the outside temperature or similar. It just grows and grows.
Creating a simplified robotic demonstration
Now lets make our first robotic demonstration and control a real robot. At left are two levels of a robotic control system similar to our LED flasher example above. Level 0, or the Avoid level reacts to in this case two whisker contact inputs. It then drives two servo motors appropriately. This is a complete functioning system as described below. The upper Level 1 Wander module can subsume the lower level at any time, as set by the timer. We could have also used two infrared proximity sensors as its inputs to have the IR override the whiskers, but I ran out of proto space. Note that ALL modules have the same access to the sensors.
How it works
Keeping in lines with Brooks Hierarchy, Level 0, the Avoid module behaves in the following manner:
- Responds to whisker contact by rotating the other way.
- Touching both whiskers at once yields a backing off behavior.
- No forward movement when not being disturbed.
We do not have the "brains" at this lowest of levels to roam yet. What we have is a core set of reflexes, like the inner brain in our bodies that respond instinctively to external stimuli. You can poke it and it will turn away. You can chase it by grabbing both whiskers and it will continue to run away backwards until you stop.
The Level 1 Module which subsumes Level 0 is also running its little program. Using its on board timer, it subsumes the Avoid module every 10 seconds and generates random headings for it to follow. Then it leaves it alone for another 10 seconds, and lets it run its program. Now here's the great part - while subsumed, and its wandering about if you hit something and activate the whisker sensors it will use the Level 0 functions and turn away or back up from the impact. In other words you are running in subsumed mode unless you hit then the subsume line on the Wander module goes back to low temporarily and when the impact is cleared, you return to normal subsumed operation. This happens because the Wander module has the same inputs as everyone else, in this case when it sees a whisker impact, it stops subsuming until the event is over with. Its crucial to understand that the upper leaves use the lower levels as part of their behavior. Because I don't have to program the higher levels with lower level responses, this GREATLY simplifies the programming.
Ripping the brains out of my old Boe Bot by removing the BS2 was a good place to start. After all, my main purpose was to demonstrate the concept of Subsumption. On the left of the proto board is the Level 0 processor, an PIC12F629. It connects directly with the servos. On the right is the Level 1 Processor, the same part with an LED on the Subsumption line to show the action. You can see the stock whiskers at the top.
Integrating the AFSM into the Architecture
Now to make all this work, lets discuss what is actually going on INSIDE each processor.
Level 0 Finite State Machine
At left is the FSM for the Level 0 PIC processor. Turning on the power puts it in the Initialize state, which sets the processor up. Passing this is a one way trip to the Rest state, where it sits happily running its program doing nothing until a whisker impact causes it to jump state. Then it jumps into the Escape state and tries to move away from the contact. Note again there IS NO FORWARD MOVEMENT STATE. This is simply a set of core reflexes. The fourth state is the Subsume state which is allows the internal registers to be modified by an external data source.
Level 1 Finite State Machine
At right is the FSM for the Level 1 Module. Its quite simple at this point, three distinct states. Wander generates random headings such as Forward, turn right, and turn left. It can look at the whiskers as well. Rest state is what is done when it is not subsuming the lower levels. This could be such complex tasks as gather sensor inputs, or check power levels. For this demo, it does nothing but count to 10 in seconds. The Impact State is where we go at any time from any state if a whisker impact occurs. We must stop what we are doing and respond by letting the lower level 0 handle the situation. Wander will jump to the Rest state under two conditions, when the subsume timer is up, or when a whisker impact occurs. then it relinquishes command to level 0 by jumping to the Impact State.
Connecting it all together
With the appropriate connections made, the power was turned on, and we can see Subsumption in action. Here are some photos and diagrams to illustrate the behavior of such an simple architecture.
Testing with PIC-Bot
Level 0 behavior:
This is a time exposure of the PIC-Bot showing the turn away from the left whisker behavior. As long as you touch the whisker, it will continue to turn. When you stop stimulating the whisker, it jumps to the rest state and sits still.
Another Level 0 behavior:
Another aspect of the Escape state is on this time exposure showing what happens when you touch both whiskers at the same time. PIC-Bot backs up and continues to do so even if you "chase" it. As soon as you stop chasing it, it jumps back to the Rest state.
Level 1 and Level 2 combined behavior:
Finally, by connecting the the two independent levels you get a unique behavior. This diagram shows what PIC-Bot does on the open living room floor. What you see is a random wander which lasts about 10 seconds. Then it stops and goes into the Rest state for another 10 seconds. Then continues on. Note that every time an obstacle is hit in the room, such as a shoe, cat or table leg, the Level 0 Avoid response is allowed by Level 1 to kick in and turns it away.
Processor selection for modules
This simple demonstration used some very inexpensive processors, with only six (yes six) I/O's but resulted in some very complex movements of PIC-Bot. For the next version of a Subsumptive Architecture robot, it would be better to use the $1.80 16F628 processor because of its 16 I/O lines will allow a wider degree of sensory inputs and allow a full 4 bits or more of Subsumption to both inputs and outputs. A key element also here on the PICs is that for this application, most of the processors can be run in the RC time base mode, so no external parts are needed.
Taking it from here
We are currently finishing up our Ostracode project which uses a single processor and only a few timed subroutines for some overriding control. Our next robot in which we are in the parts buying stage at this time will incorporate full Subsumption architecture, and four levels of Subsumption. Stay tuned!