2. BACKGROUND

Herding, flocking, and schooling behaviors of animals have been studied extensively over the past century, and this research has stimulated attempts to create robots and simulated characters with similar skills. Biologists have found that groupings in animals are created through an attraction that modulates the desire of each member to join the group with the desire to maintain a sufficient distance from nearby characters. 3 As an example of this attraction, Cullen, Shaw, and Baldwin4 report that the density of fish is approximately equal in all planes of a school, as if each fish had a sphere around its head with which it wished to contact the spheres of other fish. Biologists have found that herding benefits group members by limiting the average number of encounters with predators (data summarized in Veherencamp5 ). Group behaviors also allow animals to hunt more powerful animals than those they could overpower as individuals. The success of behaviors such as these in biological systems argues the merit of exploring their use in robotic systems. An understanding of these behaviors is essential for realistic characters in virtual environments.

Early progress in the simulation of group behaviors was made by Reynolds. 6 Actors in his system are birdlike objects similar to the point masses used in particle systems except that each bird also has an orientation. The birds maintain proper position and orientation within the flock by balancing their desire to avoid collisions with neighbors, to match the velocity of nearby neighbors, and to move towards the center of the flock. Each bird uses only information about nearby neighbors. This localization of information simulates one aspect of perception and reaction in biological systems and helps to balance the three flocking tendencies. Reynolds's work demonstrates that realistic-looking animations of group formations can be created by applying simple rules to determine the behaviors of the individuals in the flock.

Sugihara and Suzuki demonstrated that multiple simulated robots can form stable formations when each robot executes an identical algorithm for position determination within the group. 7 Each robot perceives the relative positions of all other robots and has the ability to move one grid position during each unit of time. By adjusting their position relative to either the most distant or the closest neighbor, the robots can form a regular geometric shape such as a circle. By carefully constructing the algorithm that each robot uses in determining intragroup position, formations will emerge without a priori knowledge about the total number of robots or their initial positions. Designation of leaders allows the simple rules of the group to create leader-follower algorithms and to demonstrate the division of a formation into smaller groups.

Arkin explored the question of communication in a group of interacting mobile robots in the laboratory using schema-based reactive control. (reference to Bibliography item #8) Example schemas are move-to-goal, move-ahead, and avoid-static-obstacle. Each behavior computes a velocity vector that is combined with the velocity vectors from the other behaviors. The combined velocity vector is used to control the robot. Arkin demonstrated that multiple robots can effectively complete group tasks such as foraging and can retrieve large quantities of goal items with little or no explicit communication.

Mataric explored emergent behavior and group dynamics for 20 wheeled vehicles in the laboratory. These robots, like Arkin's, do not explicitly communicate state or goals and the system has no leaders. This work demonstrated that combinations of such simple behaviors as aggregation and dispersion can produce such complex relationships as flocking in physical robots in the laboratory.(reference to Bibliography item #9) The robots utilize the knowledge that they are all identical when executing behaviors, but an extension to these results found that heterogeneous agents, where robots moved in a predetermined order, do not perform significantly better than homogeneous ones in aggregation and dispersion experiments.(reference to Bibliography item #10) In these experiments, a hierarchy is created in which an ordering between the agents determines which agent will move first in completing such tasks as grouping and dispersing.

Tan and Lewis developed control algorithms for groups of non-holonomic simulated robots moving in formation. 11 The formation is defined by a virtual structure, a polygon with vertices that specify robot positions, which can be translated and rotated, but cannot shift, skew, or scale. Successful group formation navigation requires the robots maintain a rigid geometric relationship to each other by following the points of the virtual structure lattice. The goal of the control algorithm is to specify the virtual structure's trajectory to a destination position while minimizing the sum of distances between each robot and its assigned point on the virtual structure. A model of the robot's dynamic abilities estimates the positions each robot can reach at the next time step and provides an accurate penalty value for all spots the robot cannot reach. The evaluation function uses this model of a robot's reachable positions when evaluating the numerous translations and rotations that could be applied to the virtual structure. The distance between the virtual structure and the goal position is also used when evaluating new positions. The Davidson-Fletcher-Powell method is used to search the space of virtual structure transformations. This paper produces interesting results because the formation algorithm adjusts to robots with different locomotion capabilities. Likewise, the algorithm is robust to robot failure as the virtual structure adjusts to minimize the distance between the group and the failing robot while simultaneously moving towards the goal.