The program supports the creation of up to ten independently controllable behavior groups of elements (robots), with up to 200 elements total. The program user creates clusters of elements by specifying how many elements are to be created in each cluster, in what pattern (random distribution within a circle or rectangle of specified size and location), with what initial velocities (random distribution within ranges of speed and course), and with what behavior (zero acceleration, specified speed and course, rendezvous at specified time and position, or one of several sensor-based flocking algorithms). The simulation navigates each individual element in terms of speed and course; realizing the requested speed and course in terms of throttle and steering is allocated to an unsimulated lower level controller, which also navigates around point obstacles, such as other elements. The behaviors of the different groups of elements can be changed by user command as the simulation progresses. A simulation run can be saved as a file containing a succession of kinematic frames, and replayed later.
Figure 1 presents a sequence of several frames from a simulation run, showing a group of 40 elements executing a "condensation" behavior, coming together from an initially dispersed configuration. The actual algorithm is very simple: if the minimum azimuthal angle subtended by all an element's neighbors is less than 180 degrees (i.e., if it is possible to draw a line through the element so that all its neighbors fall on the same side of the line), then the element knows that it is "on the edge" of the group. Elements "on the edge" move at fixed speed down the bisector of the subtended angle; elements not "on the edge" remain stationary. Thus, the configuration "implodes", with the "outer" elements "sweeping" the remaining nodes insward as the condensation continues. The angle-bisecting component of this algorithm has been previously described by Sugihara and Suzuki [SUGI90], whose paper discusses a number of other interesting motion coordination algorithms. In a real application, a complementary (or in some implementations, "competing") behavior would halt the condensation process as the desired element density is achieved.
The condensation algorithm and its simulation present some interesting features for discussion. First, the algorithm is highly robust, in the sense that, even if the sensor range is much smaller than the initial diameter of the configuration, the algorithm will produce a single compact group, as long as the sensor detections produce a connected graph. (If the graph consists of disjoint pieces, each piece will condense to form a separate group.) This is true because any element in motion is moving closer to the positions of all other elements that it can see. The second point is that the condensation process requires no global position information of any sort; the command to the group is not "condense to position LATLONG", it is just "condense". The third point is that the algorithm makes use of only azimuthal information from sensors, and has no requirement for range data. However, algorithms generally similar in effect can also be designed using range data only, or a mix of range and azimuth data, and this is an area of exploration for the continuing simulation effort. The fourth point is that, in its initial instantiation, with a discontinuity in element motion based on a binary decision of "on the edge" or "not on the edge", the time-step simulation introduces an artifact of clustering at the "corners" of the configuration, as the different elements in a "corner cluster" play leapfrog, taking turns being "on the edge". It is possible, however, that the concentration of forces introduced by this "artifact" might be considered a desirable feature in some combat situations, and the algorithm could be time-quantized to produce it with real (vice simulated) robots.
Up to Many Robot Systems
Please address all questions and comments to: robo-web@spawar.navy.mil
Last update: 1 December 1998.
Robotics home page