SOFSEM 2001 28th Annual Conference on Current Trends in Theory and Practice of Informatics November 24 - December 1, 2001 Piestany, Slovak Republic, Europe

Distributed Computations by Autonomous Mobile Robots

by Nicola Santoro

In robotic research, the current trend in both the AI, the software and the engineering communities, has been increasingly moving towards the design of a large number of simple, generic robots, with very limited capabilities but together able to perform rather complex tasks.

In such a setting, the crucial problem is the analysis of the minimum level of capabilities (sensorial, computational, and motorial) these robots must have to collectively solve a given task. In this talk I will discuss some fundamental problems (e.g., gathering, pattern formation, election,...). I will describe different distributed algorithms to perform the tasks, depending on a variety of assumptions on the capabilities of the robots and on the availability (or lack of) a common coordinate system. These algorithms are provably correct and terminate in finite time. They do so even if the robots are identical (anonymous), have no memory of the past (oblivious), cannot explicitly communicate, and are totally asynchronous in their actions, computations, and movements.