BrainProg and Behaviours
BrainProg is a behavioural language based on the work of the MIT Mobile Robot group. Since 1985, Rodney Brooks and the MIT Mobile Robot group have developed a new way of programming mobile robots called "Subsumption Architecture". For papers to download, see http://www.ai.mit.edu/people/brooks/brooks.html.
Several "Behaviours" are created all of which run in parallel. Each behaviour takes its input from the robot's sensors and controls the robot's motors. For instance, imagine a robot with two antennae at the front left and right corners and two light sensors looking forward-left and forward-right.
The lowest level behaviour might be "if the forward-left light sensor is lighter than the forward-right light sensor then move forward and left otherwise move forward and right".
You would debug this program until the robot reliably heads towards light.
But what if it hits something? The second behaviour might be "if an antenna hits something then back-up and turn away from it".
The first behaviour is working well so you leave it alone. The second behaviour can decide when it's output should override the output from the first behaviour.
Further behaviours might override the output from the first two behaviours or might override the inputs to behaviours.
That is the essence of "Subsumption Architecture". You start with very simple behaviours and get them working. New "higher level" behaviours do not replace your old behaviours, instead, they sometimes override the inputs and outputs of "Lower Level" behaviours.
There are other rules you should try to follow when writing behavioural programs:
- each behaviour should be simple enough to fit on a single computer screen.
- ideally, each behaviour looks at sensor data coming from the real world and tries to control the motors so that the robot moves in the real world; a behaviour which is far removed from the real world probably won't work very well
- behaviours sometimes look at data provided by other behaviours rather than sensor data
- behaviours sometimes override the inputs to another behaviour to provide "fake" sensor data
For instance, let's say you are designing a robot to pick up objects and move them into shade. Behaviour-A makes it drive around randomly but avoiding shade until a sensor senses an object between its jaws. The object triggers Behaviour-B to close the jaws. When Behaviour-C sees that the jaws are closed, it overrides Behaviour-A and heads towards darkness. If the light level is low enough, Behaviour-D opens the jaws. But the robot doesn't "remember" what it's doing at any time, the input from it's senses tells it what it's doing:
- when the jaws are open, Behaviour-A controls the wheels;
-when the jaws are closed, Behaviour-C controls the wheels.
- when the light level is high, Behaviour-B controls the jaws:
if there is an object between the jaws then close them otherwise open them
- when the light level is low, Behaviour-D controls the jaws:
if there is an object between the jaws then open them and back away
What Rodney Brooks says
Our principles of computation are:
- Computation is organized as an asynchronous network of active computational elements (they are augmented finite state machines|see [Brooks 89] for details 1 ), with a fixed topology network of uni-directional connections.
- Messages sent over connections have no implicit semantics|they are small numbers (typically 8 or 16 bits, but on some robots just 1 bit) and their meanings are dependent on the dynamics designed into both the sender and receiver.
- Sensors and actuators are connected to this network, usually through asynchronous two-sided buffers.
These principles lead to certain consequences. In particular:
- The system can certainly have state: it is not at all constrained to be purely reactive.
In all the robots built in the mobile robot lab, the following principles of organization of intelligence have been observed:
- There is no central model maintained of the world. All data is distributed over many computational elements.
- There is no central locus of control.
- There is no separation into perceptual system, central system, and actuation system. Pieces of the network may perform more than one of these functions. More importantly, there is intimate intertwining of aspects of all three of them.
- The behavioral competence of the system is improved by adding more behavior-specific network to the existing network. We call this process layering. This is a simplistic and crude analogy to evolutionary development. As with evolution, at every stage of the development the systems are tested; unlike evolution there is a gentle debugging process available. Each of the layers is a behavior-producing piece of network in its own right, although it may implicitly rely on presence of earlier pieces of network.
- There is no hierarchical arrangement, i.e. there is no notion of one process calling on another as a subroutine. Rather the networks are designed so that needed computations will simply be available on the appropriate input line when needed. There is no explicit synchronization between a producer and a consumer of messages. Message reception buffers can be overwritten by new messages before the consumer has looked at the old one. It is not atypical for a message producer to send 10 messages for every one that is examined by the receiver.
- The layers, or behaviors, all run in parallel. There may need to be a conflict resolution mechanism when different behaviors try to give different actuator commands.
- The world is often a good communication medium for processes or behaviors, within a single robot.
In terms of the BrainProg language,
- each Executable behaviour corresponds to what Brookes calls an "Augmented Finite State Machine".
- each Dataflow behaviour connects Executable behaviours together by routing data from one Executable behaviours
- Dataflow behaviours can be nested so that a Dataflow behaviour can contain other Dataflow behaviours
Augmented Finite State Machines
A Finite State Machine is a very simple kind of program. Consider a simple lift:
The circles represent "states". The arrows represent "transitions"; each transition is labelled with a condition. The Finite State Machine stays in a particular state doing whatever the state says it should until one of the transitions becomes true. It then jumps top the state pointed at by the transition arrow.
But this isn't a very good lift. What if several passengers press buttons on different floors? The lift should stop as it passes the floors to let passengers on or off. We need to remember which buttons have been pressed:
There are now two Finite State Machines, one to move the lift and one to watch for passengers pressing buttons. Both FSMs run at the same time. The FSMs have been "augmented" by adding variables: whether each button has been pressed.
In BrainProg, this would be expressed as
This is a Dataflow behaviour, it specifies how data flows from one Executable behaviour to another.
There are two input behaviours each of which monitors two buttons and there is one output behaviour which controls the motors. These are I/O behaviours and are created automatically when you assign I/O ports to peripherals.
There are four copies of the user defined "Button" behaviour which control whether the buttons are lit. There is one copy of the user defined "Move lift" behaviour which controls the lift motor.
In practice, there would be more user defined and I/O behaviours to measure the lift's current position, to open and close the doors, to control the button lights, etc.
Questions or comments ? E-mail me at firstname.lastname@example.org
No part of this web page may be reproduced in any form or by any means, including photocopying and recording, for any purpose without the express written permission of Analogue Information Systems Ltd.
This web page is copyright © 2008 Analogue Information Systems Ltd., 1 Warrender Park Crescent, Edinburgh EH9 1DX, Scotland, UK, Tel: +44 (0) 131 228 6008. All Rights Reserved