Séminaire REGAL : Gathering Oblivious Mobile Robots in Finite Time.
Thursday, September 28, 2006Xavier Défago JAIST Japon
Gathering Oblivious Mobile Robots in Finite Time.
Just like any distributed system, reaching agreement among a set of mobile robots is a fundamental issue in distributed robotic systems. However, unlike traditional distributed systems, the physical location of the nodes is of primary importance. Reaching agreement in this context is often illustrated by the gathering problem. Namely, starting from any initial configuration, a group of robots sharing no knowledge of a global coordinate system must move to meet at a non-predetermined location. While being very simple to express, the gathering problem retains the inherent difficulty of agreement, namely the question of breaking symmetry between robots.
In this presentation, I will give a general overview of the difficulties surrounding gathering, as well as a report on some of our most recent results. More specifically, I will first discuss the use of a compass to solve the gathering problem deterministically in a system with limited visibility and little synchrony. In particular, we have focussed on the case where the compasses of the robots are either unstable or make bounded errors. After that, I will briefly report on the solvability of the gathering problem in the presence of faults, using synchrony or randomization.
Maria.Gradinariu (at) nulllip6.fr