Priority Arbitration Architecture

  P.A.A.M.I. (PICbot on top for size comparison !)

Here is illustrated the fundamental behavioral programming architecture of our new robot. There are very few robots with this type of programming that have been demonstrated, and when PAAMI is completed, will be a well developed example of this extraordinary subsumption hierarchy.

Fundamental Concepts

A behavior based robot can have numerous programmed behaviors, each operating independently and with no knowledge of the other behavioral levels above or below them. They must be all run simultaneously to take advantage of the layered structure, with the most important behaviors such as crash avoidance taking precedent to such actions as searching for cans, the feeding station, or just cruising. However, with up to dozens of simultaneously running programs running, each with its own view of the world, conflicts of interest in allocation of resources can result. For example, who should get control of the motors, the LCD display or the speaker at any given time? The answer lies in the power of Fixed Priority Arbitration. The hardware builder or programmer (usually one and the same ! ) can decide during the construction and design process which key behavior have more priority over others. We know that if we hit something face on while moving, we MUST perform an escape maneuver and not keep rolling. Similarly, we know we MUST recharge batteries if they are low even if we are just about to reach the can in the corner we have been looking for.

There are two ways to perform priority arbitration. First and more commonly used is a quasi-simultaneous approach, using multitasking programming languages such as Java in which all the behaviors are run quickly and consecutively with a fast processor in a simulation of simultaneous processing. The arbiter is in software, and with crafty programming and some very very long programs, we can achieve a semblance of priority arbitration of behaviors. The second approach is how we have chosen to try it, numerous small and inexpensive processors, each programmed with a separate behavior and running asynchronously. A hardware arbiter is used to share resources.

Advantages of a Hardware approach

A key advantage to a hardware based approach is that rather than one huge program in a big processor, you have many small programs that can be changed easily at will without risking affecting the operation of the robot as a whole. Parallel processing is another huge advantage to a hardware design. The processors are truly running simultaneously and can perform tasks at the same time with lightning speed. A conventional microprocessor can only do one program line at a time, and does not have the flexibility by far of many small cheap processors running all at once. I like to be able to simply swap one chip out in a behavioral section and change the layering structure instantly without worrying about affecting some other part of the operation.

Paami's Architecture

 (Click on the thumbnail for a larger view)

Left: Block diagram of the robots architecture. Behaviors are on the left side, the arbiter is bottom, and this drives the three multiplexers for channeling the digital serial data to the very limited resources.

Our newest robot uses the hardware based architecture to its best advantages. Each level of behavior from the lowest level 1, to the highest level 8 is an inexpensive but extremely powerful PIC processor made by Microchip. They run about $1 to a maximum of $4 each, and run at 10 Mhz for devices that need to be timing accurate, and 4 Mhz for such timing insensitive components such as sensors and the arbiter itself. To add another behavior layer, we simply put in another 18 pin socket, a 50 cent crystal and two 10 cent capacitors. The 16F628 we use has 16 I/O lines, and a good 2k of internal program memory. Behaviors can be simple as the "Cruise" module which has the task of moving the robot simply forward and reporting to the LCD display the sonar distance in inches, to the more complex functions such as "Home" which locates the IR beacon which to drop the target item found such as a tennis ball or soda can off at. Not only is the motor drive decoder shared with all modules, we also arbitrate the LCD display, and the audio driver which at this time is simply a NPN driver and small 16 ohm speaker to make clicks, chirps, beeps and squawks. All of Paami's shared resources are serial data. A data stream consisting of direction, PWM, and motor selection, followed by a check sum for error detection is the main means of controlling the movements of the bot. It is sent at 9600 kbits. The LCD is a Scott Edwards serial display, and is operated at 9600 kb as well. The Audio is generated in each module, and can be beeps and ramping frequencies. To access the resources, all each module has to do is send a subsume request level, high in this case, to the arbiter. It then allows that module to access the resources if and only if it is the highest subsume level present.

The Arbiter

  (Click on the thumbnail for a larger view)

Left: The Arbiter is a small inexpensive microcontroller programed as a priority encoder, putting out the binary equivalent thousands of times per second of the highest requested subsume line.

So how do we arbitrate all those modules running simultaneously, each wanting control of the motors, LCD and audio at the same time? The arbiter is a very simple program. The processor consists of a single PIC, a 16F628 processor running of course asynchronously to everything else. I use the internal clock, and run it at 4Mhz with is plenty zippy enough to do its job. The arbiter module works in the following way:

8 subsume lines from all the modules are input, with each subsume line assigned a level, from 0 to the lowest priority to 7 for the highest. The software scans the input lines from the top down. The highest subsume line then latches the output of the arbiter to its equivalent parallel binary code. Thats it. Takes about half a page of PIC Basic code. So for example, if the Avoid module is triggered by an IR impact, its subsume line goes high. IF the current level was cruise for standard straight line running which has a subsume line of 0, it is then now superseded by the level 5 avoid module. The binary code of 5, which is 101 is output on the arbiter.

Multiplexing shared Resources

Now that we have a binary code representative of the highest subsumption line, what do we do with it? Using 74HC151 multiplexers, we can select its eight inputs into one input. So its an 8 to 1 multiplexer. If the Avoid module is triggered, line 5 will go high, subsuming cruise at level 0, and putting out 101 into the inputs of ALL multiplexers. That means not only will the motor drive MUX get the code, so will the LCD, and Audio Muxes. Now any motor serial commands, LCD or sounds that are made with the Avoid module will be running the robot. When the subsume line goes low, the highest up subsume is now back to 0, and the cruise module dominates. The LCD now reads the sonar, and the bot goes on its way ready for the next event in its life.

Priority Arbitration in Action!

Here are some images and movies of this procedure working. Obviously at this point, having only three levels installed - Cruise, IR Avoid, and Bumper Impact, the behaviors are not too different from a single processor bot. But wait -- as more layers are added the behaviors will get much more interesting and intelligent as emergent behaviors start appearing.

Sonar - Cruise: The first module we installed. Its function is to move the robot forward straight ahead, while monitoring the sonar data. The speed of the robot will be dependent on how far ahead it has room. If the sonar indicates 5 feet for example, the speed is faster forward. It displays the distance in inches on the LCD on the top. The audio is a series of sonar like pips, which get higher in pitch as it approaches an object. The other easily subsumable feature is the sonar is set to do a slight 10 degree right or left veering off, if the detection of an object dead ahead and less than a foot away.

Movie 1 (367kB) - Turn up your sound, and hear the sonar report the distance ahead.

Movie 2 (228kB) - Direct travel toward wall causes the sonar to initiate an escape maneuver at 12 inches.

Impact: This module is quite high on the priority scale, 6. It causes a controlled ballistic reaction with rear bumper feedback when the frontal bumper shields are touched. The Audio pips from the Cruise Sonar are subsumed, and specific beeps, and rolling frequency sounds are made briefly when the bumpers are hit.

Movie 3 (326kB) - Manual operation of the bumpers, causing an avoidance behavior.

IR Avoid: Frontal and Rear IS417 proximity detector arrays cause either veering off, or a complete ballistic escape action with rear bumper feedback. Range is bout 6 to 8 inches. This overrides Sonar-Cruise, but not Impact.

Movie 4 (367kB) - Standard avoidance from frontal sensor initiating a random escape maneuver. The Outer pair of IR does a very different thing, it veers to avoid, rather than a ballistic escape.

Movie 5 (425kB) - Avoiding the EVIL rocking chair, always a high challenge for all our bots!

Where do we go from here?

I can add 5 more layers of behaviors at this time. Thats how many arbiter lines I have left. That should be plenty for some very interesting behaviors to be implemented. Next is "Charge/Cruise", which will of course initiate a hunger response and cause the bot to seek out the battery charger, a docking station with an IR beacon to home in on. Then Paami will be much more independent to roam 24 hours a day, or until she gets stuck under a chair or something. A stasis sensor similar to that in Ostracode will be implemented to take care of these types of conditions. After that, the main goal will be to develop behaviors for collecting things of a specific attribute. Pop Cans, Tennis balls, cat toys, etc.

Robotics Main Page HOME

You are visitor number since June 17, 2001

FastCounter by bCentral