Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Teamwork, territoriality, and congestion: on the role of scale in mobile multi-agent systems

A very active research area today addresses coordination of several autonomous robots: robotic teams and large-scale swarms are being considered for a broad class of applications, ranging from environmental monitoring to national security. While these concepts are undoubtedly fascinating, it is not clear what are the benefits of scale in such systems. In this seminar, I will present some recent work on several related classes of problems involving the coordination of possibly large numbers of robots. The underlying theme of this work is the investigation of the relation between the number of robots and the collective performance, given realistic constraints on their motion and on their ability to collect and exchange information. As an additional outcome, we design scalable coordination algorithms with provable performance guarantees. In particular, we will focus on the following class of problems. Consider a number of robots free to move within a convex and bounded region in the plane. Assume that "service requests" are generated within the region by a stochastic point process; a service request is fulfilled when one of the robots visits the corresponding point. We present algorithms that provably minimize the expected waiting time between the issuance and fulfillment of a service request, in the asymptotic cases of light and heavy load (i.e., when the service requests are issued very rarely or very often), and under a variety of assumptions on the robots' dynamics (holonomic vs. non-holonomic vehicles), and on the nature of their interaction (cooperative vs. non-cooperative strategies). The proposed algorithms are spatially decentralized, and combine tools and results from geometric optimization, combinatorial optimization, and nonlinear control theory. Interestingly, our results provide novel insight into the observed behavior of large groups of animals. We will also address the other face of the coin, showing how traffic congestion imposes severe limitations on the performance of large multi-robot systems. More specifically, we will address the following basic problem: Given n robots and n origin- destination pairs in the plane, what is the minimum time needed to transfer each robot from its origin to its destination, avoiding conflicts with other robots? We show that the average velocity of any robot must decrease at least as 1/sqrt(n), and present algorithms providing constant-factor approximations to safe, minimum-time vehicle routing strategies. This yields a formal framework for the rigorous analysis of the effects of traffic volume on traffic congestion, and we will discuss some implications regarding current and envisioned mass transportation systems.
Type of Seminar:
Public Seminar
Ass. Professor Emilio Frazzoli
University of California, Los Angeles, USA
Dec 21, 2005   08:30

ETH-Zentrum, Main Building Room HG F 33.1 , Rämistrasse 101, Zurich
Contact Person:

Prof. L. Guzzella
No downloadable files available.
Biographical Sketch: