Context
For example, patrolling in an industrial warehouse, environmental monitoring, mapping, surface cleaning, urban search and rescue, planet exploration, intelligence activities, and many other hazardous tasks can be solved by robot swarms. Designing distributed algorithms allowing the coordination of robots without central control remains a challenging task [3].
Distributed computing for robot swarms mainly considers problems such as exploration [2], gathering [5], or scattering [1]. Exploration problem has two variants: terminating and perpetual exploration. Terminating exploration requires that every location of a discrete environment is visited by at least one robot. Perpetual exploration requires that every location is visited infinitely often by a robot. Starting from arbitrary positions, gathering consists in assembling all robots in the same place. On the contrary, the goal of the scattering is to place all robots in different positions.
We focus on robots equipped with few lights of different colors that can be seen by the surrounding robots [4]. Other than those lights, robots do not have any persistent memory or communication abilities.
Goals
After some bibliographic study in order to get familiar with the computational models considered in mobile robot distributed computing, the intern will design distributed algorithms for swarm of robots equipped with lights. The objective will be to minimize the number of lights used by the robots. The intern will perform the correction and complexity analysis of the designed algorithms and might be required to prove impossibility results or lower bounds.
Successful work is expected to lead to a paper submission and continuation towards a PhD on related topics is possible.
References
[1] L. Barrière, P. Flocchini, E. M. Barrameda, and N. Santoro. Uniform scattering of autonomous mobile robots in a grid. Inter. Journal of Foundations of Computer Science, 22(3):679–697, 2011.
[2] F. Bonnet, A. Milani, M. Potop-Butucaru, and S. Tixeuil. Asynchronous exclusive perpetual grid exploration without sense of direction. In Inter. Conference on the Principles of Distributed Systems (OPODIS’11), pages 251–265, 2011.
[3] P. Flocchini, G. Prencipe, and N. Santoro. Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2012.
[4] D. Peleg. Distributed coordination algorithms for mobile robot swarms: New directions and challenges. In Inter. Workshop on Distributed Computing (IWDC’05), pages 1–12, 2005.
[5] G. D. Stefano and A. Navarra. Gathering of oblivious robots on infinite grids with minimum traveled distance. Information and Computation, 254:377–391, 2017.
Leave your comments
Post comment as a guest