[back]

Flocking in Embedded Robotic Systems
Adam Hayes, Ian Kelly, Alcherio Martinoli

Abstract. The goal of this project is to implement flocking behavior on real robots, and then study the system to determine what sensory information and behaviors are most important to robust flocking. Our algorithms are inspired by those of Reynolds and Brogan and Hodgins, and are specifically adapted to the sensory and motor constraints of a real robotic platform. Work is ongoing using a sensor-based simulator, Webots, as well as our Moorebot fleet using the overhead camera to emulate additional sensory input. We are in the process of developing sensory hardware for the Moorebots so that they may flock autonomously.

Motivation. Flocking, the formation and maintenance of coherent group movement, has long been studied in natural systems, and more recently efforts have been made to reproduce this type of behavior in artificial systems. The first such work appeared in the context of computer animation [Reynolds87], and since then this behavior has been extensively studied in simulation (e.g. [Brogan97]), and less so on real robots [Mataric9], [Kelly96]. Theoretical treatments of the stability of flocking behavior have also been investigated. The study of flocking is distinct from that of formation control, because the goal of flocking is simply to achieve and maintain coherent group movement rather than to govern specific inter-agent position relationships. As such, flocking is better suited than formation control to implementation on large groups of agents (hundreds to thousands) where the overhead of extensive inter-agent communication and unique agent identification renders formation control inefficient. Also, like formation control, flocking is not an end in itself, but rather can be used as a component of a larger multi-agent system, perhaps simplifying the transport of large numbers of agents or organizing the nodes of a distributed sensing system.

Research. [Reynolds87] identifies three behavior types that lead to simulated flocking: separation, alignment, and cohesion. However, much of the robotic work on flocking relies solely on balanced combinations of separation and cohesion (i.e., flock centering) to produce flocking behavior. It is likely that the inclusion of an alignment term into robotic flocking algorithms will improve performance (particularly by speeding up flock formation times), but there is a cost to making heading information explicitly available within a system.

(a)


(b)

Figiure 1. (a) Simulated flock moving around an obstacle. (b) Flocking Moorebots.

The leaderless distributed algorithm investigated here, LD, is essentially an extension of the flock centering algorithm presented in [Brogans97], incorporating an explicit collision avoidance mechanism (as they suggest) as well as an implicit velocity matching behavior (i.e., an alignment term) via the comparison of sequential flock centering data). Thus LD should exhibit better flocking performance than previous robotic algorithms (though comparative data is unavailable) while not significantly complicating implementation on real robots. Because LD does not explicitly use the alignment of other group members, individual agents need not be able to sense their neighbors' orientation, and range-and-bearing information suffices.

Achievements. We described a leaderless distributed flocking algorithm (LD) that is more conducive to implementation on embodied agents than the established algorithms used in computer animation.

We also used an embodied simulator and reinforcement learning techniques to optimize LD performance in different environments, showing that this method can be used not only to improve performance but also to gain insight into which algorithm components contribute most to system behavior.

We demonstrated that a group of real robots executing LD with emulated sensors can successfully flock and that systematic characterization of real robot flocking parameters is achievable.

We have implemented an initial version of a local IR range, bearing, and communication system necessary to implement LD fully locally, and this will enable full verification of the optimization experiments to be performed on the real robots.

Movies:

Basic Flocking:
Webot Flock Formation (597 KB AVI)
Webot Flocking Around Obstacle (822 KB AVI)
Moorebot Flock Formation (7.8 MB AVI)
Moorebot Flocking Around Obstacle I (3.9 MB AVI)
Moorebot Flocking Around Obstacle II (5.1 MB AVI)

Directed Flocking:
Webot Follow-The-Leader (1.6 KB AVI)
Webot Flee-The-Predator (1.5 KB AVI)

References
"Group Behaviors for Systems with Significant Dynamics". [Brogan97] Brogan, D.C. and Hodgins, J. K.,Autonomous Robots, 1997, Vol. 4, pp. 137-153

"Flocking by the fusion of sonar and active infrared sensors on physical autonomous mobile robots". [Kelly96] Kelly, I.D. and Keating, D.A., The Third Int. Conf. on Mechatronics and Machine Vision in Practice. 1996, Guimaraes, Portugal. Vol. 1, pp 1/1 - 1/4.

Interaction and Intelligent Behavior. [Mataric94] Mataric M., Ph.D Thesis, MIT, Boston, May 1994.

"Flocks, Herds, and Schools: A Distributed Behavioral Model". [Reynolds87] Reynolds, C.W., Computer Graphics, July 1987, Vol. 21(4), pp. 25-34.

"The Application of Wireless Local Area Network Technology to the Control of Mobile Robots". [Winfield00] Winfield A. F. T. and Holland O. E., Microprocessors and Microsystems, 2000, Vol. 23, pp. 597-607.