The Taub Faculty of Computer Science Events and Talks

Multi-agent systems are a fascinating, multidisciplinary field with applications to robotics, distributed systems, biology, and social dynamics. A multi-agent system is a distributed system composed of several interacting, autonomous agents that cooperate to achieve some desired behavior. The topic of this talk is the way in which local interactions between extremely simple agents can result in desirable global states. We study this topic from two perspectives: the perspective of an observer of the natural world, and the perspective of a designer of swarm-robotic systems. In the natural world, living swarms of organisms seem to effortlessly and autonomously coordinate their motion. How do swarms of locusts converge to a single direction of motion? Why are trails of ants so straight and nice? As observers, our goal is to study the principles underlying these kinds of phenomena, learning what we can from Mother Nature's algorithms. As designers, on the other hand, our goal is to create and guarantee the performance of swarm-robotic systems. We seek to establish that even severely myopic and computationally limited robots can be remarkably effective when working together. We shall show that, with the right local algorithm, such robots can explore unknown environments, recover from crashes, split workloads, and optimize traffic systems. Almost all mathematical models we work with assume the agents move in a space that is finite and discrete; namely, a graph environment, where spatial locations are indicated by vertices and the connections between them by edges. From a theoretical standpoint, the study of these types of multi-agent models is often ad hoc, and relatively few general techniques are known. A main goal of ours is to highlight a number of techniques that have proven repeatedly useful in the analysis of such models, including exchangeability, coupling, potential (``Lyapunov'') functions, interacting particle systems, and stationary distributions.