Technical Report PHD-2010-02

Title: Fundamental Problems in the Theory of Multi-Agent Robotics
Authors: Noam Gordon
Supervisors: Alfred M. Bruckstein and Israel A. Wagner
Abstract: The theory of Multi-Agent Robotic Systems (MARS) is a specialized and fascinating branch of distributed systems theory and robotics. The mobility of the agents, their autonomy, as well as the limitations of their sensing, communication, and computation capabilities give rise to new and interesting challenges. We investigate several problems in modeling and analyzing such systems under the ant-robotic paradigm, which emphasizes the individual agent limitations and the homogeneity and anonymity of the swarm. Our methods and results revolve around three fundamental problems in distributed robotics - agreement, spatial formation, and gathering. In our swarm model, the agents have no explicit means of communications, and therefore must rely exclusively on movement and mutual observation of their locations in order to coordinate their actions. This severe limitation imposes great difficulties in attaining sustainable consensus and at the same time enable the robots to perform other tasks. We develop a general theory of terminating protocols for agreement, which defines the basic anatomy of the agreement process in a way that is useful for design and analysis of agreement protocols, as we demonstrate by presenting and analyzing protocols for agreement on a common coordinate system and formation of arbitrary spatial patterns. Symmetry breaking is a commonly mentioned fundamental problem in the literature. Tasks such as formation of arbitrary patterns have been proven to be impossible, due to this problem. The basic argument is that if the agents, which are all identical, work in synchrony and reach a symmetric configuration, they will be trapped indefinitely in symmetry. We argue that in the context of systems of multiple real autonomous and asynchronous robots this problem has limited significance. Therefore, we consider an asynchronous model and supplement it with a new assumption termed strong asynchronicity, which ensures that symmetries are eventually broken. This assumption has made possible the design of the aforementioned agreement and formation protocols. Ant-robots typically have limited myopic sensing of the environment. This makes even seemingly simple problems such as gathering in a small region challenging. While several known works consider range-limited sensing, the ability to sense the distance from visible agents is usually assumed. Inspired by experiments with actual ant-robots built from LEGO Mindstorm bricks in our laboratory, which cannot sense distances reliably, we devise algorithms for gathering, which utilize little or no distance-sensing ability. We examine the interesting global behaviors that arise, and prove the convergence of our algorithms.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2010
To the main CS technical reports page

Computer science department, Technion