Robotics home pageEach node incorporates an indexed set of buffers for storing a number of LISP-syntax expressions. For convenient reference in programming, the operator can associate a name with a specific buffer at his workstation. Each expression buffer is either active or inactive, and this can be changed under program control, either (a matter of implementation detail) by SETQing the active flag variable or through an explicit activate or deactivate function call. The core SLEEP process merely evaluates the expressions in the active buffers in round-robin sequence (although any of a number of different priority schemes could certainly be added). The message reception process writes an incoming expression into a special buffer and SLEEP executes it one time (the expression can, of course, copy a portion of itself into one of the other regular buffers for repeated processing as part of the active ruleset).
SLEEP provides an indexed set of variables, which are used in three ways. Some point to the variables used by the robot's underlying processing (including memory-mapped sensor inputs and actuator outputs), so that the user can have maximum flexibility in reading the unit's state. Others support SLEEP processing itself, like marking, marked, frozen, and sleeping. The user has complete discretion in using the rest of the variables, associating names with them and using them in expressions.
Functions include basic arithmetic (+, -, *, /, ^, etc.), boolean (AND, OR, NOT), LISP "special forms" [WINS84] (COND, SETQ), SLEEP support (power_down), and pointers to functions in the robot's core software. Randomization functions include (PROB x), which evaluates as TRUE with probability x, and the special form (DICE (x A)(y B)(z C)), which evaluates A with probability x, B with probabilty Y, and C with probability z.
In the initial (very preliminary) exploratory C-based implementation of SLEEP, the range of LISP-expressions has been simplified considerably, and, in fact, expressions are not even represented as conventional linked lists. Instead, an expression, whether in a message or in the rule base, is represented as a sequence of tokens. Each token represents a number, a variable, a function, or an expression in the rule base. So far, numbers have been limited to integers only, but it is clear that floating point numbers will be absolutely required because of the necessity of representing probabilities. The initial set of functions implemented include arithmetic and logical, plus the LISP special forms [WINS84] COND, SETQ, and a variant of SETQ called SETQQ which QUOTEs both its arguments. Moreover, an expression always evaluates to a number, which can, of course, also serve as a boolean. So this is not really LISP, but it captures some relevant desirable features of LISP such as call-by-value parameters, operator prefix notation, and function side effects.
Hoskins' system is comprised of dozens of physically identical mobile vehicles, operating in a plane. All vehicles travel at the same constant speed in straight line paths, each occasionally making a "tumble" -- a turn of about 67 degrees, to the left or right at random. Each vehicle can generate a "ping" which encodes a few bits, and can detect the pings of all the other vehicles. The ping detector can determine the approximate range to the pinger, and just one bit of bearing information -- i.e, whether the ping's origin is in front of it or behind it. A second sensor provides approximate range and and one-bit front/behind bearing to a light source located in the plane. Hoskins divides 50 of these units into 5 castes of 10 units each, encodes the pinger's caste number in each ping, and configures each caste with a set of simple behavioral rules so that the group as a whole manifests the key characteristics of a classic Braitenberg Vehicle [BRAI84] homing toward the light source, including body structure, propulsion, control, and sensing.
SLEEP is well matched to the behavioral rule structure developed by Hoskins. Lower level "core" software is written to implement the following programming model. A ping is represented as variables pRange, pBearing (FRONT or REAR), pCaste, and pFlag (needed for synchronizing the processing of pings as discrete events). The lower level software queues up multiple pings and presents these events one at a time, setting pFlag. The SLEEP ruleset resets pFlag when it has completed processing the event by making one complete pass through the rules. Similarly, the light source is represented by sRange, sBearing, and sFlag. A timer is also necessary to support Poisson processes. The only effector functions are Ping with a numerical argument which will always be set to the value of the variable myCaste, and Tumble, which requires no argument. A typical rule (Hoskins' behavior b4,5) would look like:
(COND ((AND pFlag (EQ pCaste 3) (EQ bBearing FRONT) sFlag (EQ sBearing FRONT) (PROB 0.9)) (PING myCaste))
Receiving elements of caste 4 would store this rule in expression buffer 5 and set its active flag when they received it embedded in:
(COND ((EQ myCaste 4)(SETQ expr5 (QUOTE the-expression-to-be-stored)) (SETQ active5 TRUE)))
What is important is not the details of the LISP syntax; rather it is the fact that the processing of messages broadcast to all nodes is handled by exactly the same simple interpretive execution mechanism that processes the rule base as a whole.
SLEEP becomes especially relevant when we visualize the operations of this system not in simulation but in the laboratory. The robots spend their nights at their electrical "feeding trough" recharging station. To perform an experiment, the researcher activates the robots by turning off the recharging station. The units awake, and their core SLEEP software fires up. The red LED marks any units that wake up sick. The control station starts to transmit keep-alive messages at 10 second intervals, and any units that do not hear the control station turn on their red LEDs in a flashing mode, then turn themselves off after a minute or two. The user initiates downloading of the programs for today's experiment. Different experiments may, of course, require not only different behavioral rule-sets, but also different numbers of castes of robots. The program tells the robots to probabilistically assign themselves to one of the castes, then probes to ensure that each caste is approximately equally represented. (Of course, with a total of only 50 or so elements, it is possible to determine the status of every robot, but SLEEP is designed to work no matter how many there are.) Then the behavior rule sets are downloaded into the units' expression buffers. The user can then command the units to assume the desired initial spatial configuration (e.g., randomly throughout the space). This transit can be made using behaviors and sensors that the experiment itself may not utilize (the issue of collisions, for example, must be dealt with). During the experiment, the positions of the robots are captured by a camera mounted on the ceiling, perhaps bandpass filtered for the desired LED. The units can be reconfigured to perform several experiments in succession, and then, following the day's work (or when power starts to run low) be commanded to return to the recharging station.
Up to Many Robot Systems
Please address all questions and comments to: robo-web@spawar.navy.mil
Last update: 1 December 1998.