Robotics Research Lab
CRES
USC Computer Science
USC Engineering
USC
/ Research / Projects / Ethologically Insipired Group Foraging and Robust Behavior-Based Control

Introduction Task and Robots Approach Publications

Introduction

Social structure plays an important role in the performance of a group, whether it consist of biological or synthetic individuals. In a synthetic approach, such as mobile robotics, which is the focus of our work, it may is difficult to determine an appropriate social structure for a group performing a specific task. Issues to be considered include how many robots to use, and how the task should be divided both temporally and spatially among the individuals in order to allow completion of the task and provide a desired level of performance.

Suppose one has a group of robots and a particual task in mind. How many robots should be used for the task? What is the most efficient way for the robots to perform this task? Should they all have identical behavioral repetoirs, or different? How will they communicate? How will the robots cooperate or interfere with each other given decisions to the previous questions?

More formally, these questions translate to the following issues (Brooks 1991):

A pragmatic, principled approach to guide the resolution of these issues is desirable. We have explored such an approach based on the analysis and manipulation of physical interference (i.e., collisions) a readily measurable property of mobile robotic systems. Our approach involves a controller refinement methodology that is motivated by biological evolution and based on the application of ethologically inspired arbitration schemes, i.e., modifications to social structure, or the multi-robot controller. We have applied our approach to the task of foraging on a group of four robots. Before describing the approach, we first present the task and the robots that performed it.

The Task and Robots

We define the collection task as a two-step repetitive process in which: robots search designated regions of space for certain objects, which once found are brought to a goal region using some form of navigation.

The specific configuration we used is shown in the diagram. The experiments were performed in an 11 by 14 foot rectangular enclosure (the Corrall) containing 27 small metal cylinders (pucks) that the four robots had to collect and bring to the goal local (Home) in one corner of the Corrall.

exp

The robots were programmed to wander around the Corrall, using their IR and bump sensors to avoid obstacles. When the IR sensors at the tips of the fingers detected an object, the robot entered into a ``puck detection'' mode. It raised its gripper five or six inches to determine whether or not it could ``see'' over the object. If it could not, the object was either a wall or another robot. In such a case, the robot entered an avoid mode, leaving the vicinity of that object. If it could see over the object, then it was considered to be a puck which the robot slowly approached and grabbed.

Once a robot had a puck, it raised its gripper and started a homing behavior, which brought it near Home. Raising the lift while homing serves two purposes. First, while the robot was homing it also avoided all obstacles. Any pucks lying in the robot's path were too small to be considered obstacles. Second, due to the shape of the robots, raising the lift allowed the robots to collect and push any pucks in their path to Home.

When a robot carrying a puck entered the Buffer, it slowed down and performed a more refined version of the homing behavior to get to Home. Upon entering Home, the robot dropped the puck, backed up, lowered its lift, closed the gripper, and left Home in search of more pucks. The closed gripper ensured that the robot did not mistakenly pick up pucks that were near Home.

The Boundary served a repelling function, to keep robots without pucks from taking the pucks already at Home.

r2s

Four IS Robotics R2e robots were used. Each is a differentially-steered base equipped with two drive motors and a two-fingered gripper. The sensing capabilities of each robot include piezo-electric contact (bump) sensors around the base and in the gripper, five infrared (IR) sensors around the chasis and one on each finger for proximity detection, a color sensor in the gripper, a radio transmitter/receiver for communication and data gathering, and an ultrasound/radio triangulation system for positioning.

The Approach and Experiments

In our approach, the first multi-robot controller that is constructed for a desire task is homogeneous, loosely analogous to the herd phenomenon exhibited by certain animal species. In such a controller, the robots are behaviorally identical, each capable of independently completing the entire task. Since the robots function independently of each other, there is no need for explicit communication. The homogeneous controller enables a base-case analysis of interference characteristics. This initial controller is refined by modifying its interference characteristics through the employment of pack arbitration or caste arbitration.

homo pack caste

Pack arbitration is modeled after the phenomenon of the pack observed in wolf and other animal societies. In these, any individual is physically and behaviorally capable of performing most functions necessary to the group. In order to minimize aggressive behavior which, if not controlled, can jeopardize the pack, a form of dominance hierarchy exists among the individuals. Similar to animal packs, in pack arbitration, all of the individuals of the robot group are physically and behaviorally capable of performing any of the functions necessary for the group to complete the task (as is also true for the herd scheme). To avoid interference (collisions) between individuals, the controller is modified so that the robots take turns entering regions where interference was high in the homogeneous case, with the most dominant robot going first. This form of arbitration contains some implicit assumptions about communication. The robots must be able to communicate their rank and intention to enter a region of potentially high interference. In addition, they must be able to determine when a dominant robot has failed so as not to wait indefinitely for it to complete its objective.

Caste arbitration is modeled after the structure apparent in many social insect societies. In these, individuals are behaviorally heterogeneous and are not capable of accomplishing all of the tasks that the group requires. Individuals may also be physically differentiated. As an example, consider many ant species whose colonies include worker, drone, possibly warrior castes, and at least one queen. Each individual is a member of one of these castes and has associated physical and behavioral characteristics. No one caste can maintain the colony without the others.

In caste arbitration, physical interference between robots is modified through the use of territoriality, with different castes occupying different regions of the task space and potentially having different behavioral repetoirs. This limits destructive interactions such as collisions. Robustness in caste arbitration is achieved by allowing members to change castes when necessary. If, for example, all the members of one caste fail, a member of some other caste must be able to take over. Some form of communication is needed to determine the number (or density) of individuals in each caste. Such caste switching is observed in honey-bee societies (McFarland87).

We have demonstrated our interference-modifying approach to controller refinement by implementing homogeneous, pack, and caste behavior-based controllers for the foraging task, a prototype for various applications including distributed solutions to de-mining, toxic waste clean-up, and terrain mapping. We evaluated and compared the controllers according to three performance criteria: time-to-completion, inter-robot collisions (interference), and energy expenditure. An important component of this analysis was the comparison of internal behavior activations to the externally observed interference. This initial study of behavior activations inspired our later efforts in modeling interaction dynamics using behavior activations and augmented Markov models. A parallel effort in our work on ethologically-inspired foraging aimed at demonstrating the ease with which robust, easily modifiable behavior-based controllers may be designed, implemented, and evaluated.

Publications

[1] Dani Goldberg and Maja J Mataric, (2000) "Robust Behavior-Based Control for Distributed Multi-Robot Collection Tasks," USC Institute for Robotics and Intelligent Systems Technical Report IRIS-00-387. [PS version], [PDF version]

[2] Dani Goldberg and Maja J Mataric, (1997) "Interference as a Tool for Designing and Evaluating Multi-Robot Controllers," Proceedings, AAAI-97, Providence, Rhode Island, July 27-31. [PS version], [PDF version]