Samia Souissi
Skip Abstract Section
Abstract
Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not determined in advance, and without the help of some global coordinate system. While very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it has been proved that the gathering problem is solvable in asynchronous model with oblivious (i.e., memory-less) robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass, or when they cannot detect multiplicity.
In this article, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in the semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, we show that our algorithm solves the gathering problem for at most three robots in the asynchronous model. Our algorithm is intrinsically self-stabilizing.
- Agmon, N. and Peleg, D. 2006. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36, 1, 56--82. Google Scholar
Digital Library
- Ando, H., Oasa, Y., Suzuki, I., and Yamashita, M. 1999. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Automat. 15, 5, 818--828.Google ScholarCross Ref
- Balch, T. and Arkin, R. C. 1998. Behavior-based formation control for multi-robot teams. IEEE Trans. Robot. Automat. 14, 6, 926--939.Google ScholarCross Ref
- Beni, G. and Hackwood, S. 1992. Coherent swarm motion under distributed control. In Proceedings of the International Symposium on Distributed Autonomous Robotic Systems (DARS'92), 39--52.Google Scholar
- Bonabeau, E., Dorigo, M., and Theraulaz, G. 1999. Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press. Google ScholarCross Ref
- Chandra, T. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2, 225--267. Google ScholarDigital Library
- Cieliebak, M. 2004. Gathering non-oblivious mobile robots. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04), 577--588.Google ScholarCross Ref
- Cieliebak, M., Flocchini, P., Prencipe, G., and Santoro, N. 2003. Solving the robots gathering problem. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'03), 1181--1196.Google Scholar
- Cohen, R. and Peleg, D. 2004. Robot convergence via center of gravity algorithms. In Proceedings of the Colloquium on Structural Information and Communication Complexity (SIROCCO'04). Lecture Notes in Computer Science, vol. 3104. 79--88.Google ScholarCross Ref
- Cohen, R. and Peleg, D. 2008. Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38, 1, 276--302. Google ScholarDigital Library
- Czyzowicz, J., Gasieniec, L., and Pelc, A. 2006. Gathering few fat mobile robots in the plane. In Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS'06). Lecture Notes in Computer Science, vol. 4305. 350--364.Google ScholarDigital Library
- Défago, X., Gradinariu, M., Messika, S., and Raipin-Parvédy, P. 2006. Fault-tolerant and self-stabilizing mobile robots gathering. In Proceedings of the 20th International Symposium on Distributed Computing (DISC'06). Lecture Notes in Computer Science, vol. 4167, 46--60.Google ScholarDigital Library
- Dolev, S. 2000. Self-Stabilization. MIT Press. Google ScholarDigital Library
- Dwork, C., Lynch, N., and Stockmeyer, L. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2, 288--323. Google ScholarDigital Library
- Fishkin, A. V. 2004. Disk graphs: A short survey. Proceedings of the Workshop on Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 2909, 260--264.Google ScholarCross Ref
- Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 1999. Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC'99). Lecture Notes in Computer Science, vol. 1741, 93--102. Google ScholarDigital Library
- Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 2001. Pattern formation by autonomous robots without chirality. In Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'01). 147--162.Google Scholar
- Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 2005. Gathering of asynchronous robots with limited visibility. Theoret. Comput. Sci. 337, 1--3, 147--168. Google ScholarDigital Library
- Gervasi, V. and Prencipe, G. 2004. Coordination without communication: the case of the flocking problem. Discr. Appl. Math. 143, 1-3, 203--223. Google ScholarDigital Library
- Imazu, H., Itoh, N., Katayama, Y., Inuzuka, N., and Wada, K. 2005. A gathering problem for autonomous mobile robots with disagreement in compasses (in Japanese). In Proceedings of the 1st Workshop on Theoretical Computer Science. 43--46.Google Scholar
- Inuzuka, N., Tomida, Y., Izumi, T., Katayama, Y., and Wada, K. 2008. Gathering problem of two asynchronous mobile robots with semi-dynamic compasses. In Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO'08). Lecture Notes in Computer Science, vol. 5058, 5--19. Google ScholarDigital Library
- Izumi, T., Katayama, Y., Inuzuka, N., and Wada, K. 2007. Gathering autonomous mobile robots with dynamic compasses: An optimal result. In Proceedings of the 21st International Symposium on Distributed Computing (DISC'07). Lecture Notes in Computer Science, vol. 4731, 298--312.Google ScholarCross Ref
- Katayama, Y., Tomida, Y., Imazu, H., Inuzuka, N., and Wada, K. 2007. Dynamic compass models and gathering algorithms for autonomous mobile robots. In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO'07). Lecture Notes in Computer Science, vol. 4474, 274--288.Google ScholarCross Ref
- Kawauchi, Y., Inaba, M., and Fukuda, T. 1993. A principle of distributed decision making of cellular robotic system (cebot). In Proceedings of the IEEE International Conference on Robotics and Automation. Lecture Notes in Computer Science, vol. 3, 833--838.Google Scholar
- Krieger, M. J. B., Billeter, J.-B., and Keller, L. 2000. Ant-like task allocation and recruitment in cooperative robots. Nature 406, 6799, 992--995.Google Scholar
- Martinoli, A. and Mondada, F. 1995. Collective and cooperative group behaviours: Biologically inspired experiments in robotics. In Proceedings of the 4th Symposium on Experimental Robotics. 3--10. Google ScholarDigital Library
- Matarić, M. J. 1995. From local interactions to collective intelligence. In Proceedings of Biology and Technology of Intelligent Autonomous Agents. Lecture Notes in Computer Science, vol. 144, 275--295.Google Scholar
- Peleg, D. 2005. Distributed coordination algorithms for mobile robot swarms: New directions and challenges. In Proceedings of the 7th International Workshop on Distributed Computing (IWDC'05). 1--12.Google ScholarDigital Library
- Prencipe, G. 2001a. Instantaneous actions vs. full asynchronicity: Controlling and coordinating a set of autonomous mobile robots. In Proceedings of the 7th Italian Conference on Theoretical Computer Science (ICTCS'01). 154--171. Google ScholarDigital Library
- Prencipe, G. 2001b. Corda: Distributed coordination of a set of autonomous mobile robots. In Proceedings of the 4th European Research Seminar on Advances in Distributed Systems and Dependable Systems (ERSADS'01). 185--190.Google Scholar
- Prencipe, G. 2005. On the feasibility of gathering by autonomous mobile robots. In Proceedings of the Colloquium on Structural Information and Communication Complexity (SIROCCO'05). 246--261.Google ScholarDigital Library
- Souissi, S. 2007. Fault-resilient cooperation of autonomous mobile robots with unreliable compass sensors. Japan Advanced Institute of Science and Technology.Google Scholar
- Souissi, S., Défago, X., and Yamashita, M. 2006a. Gathering asynchronous mobile robots with inaccurate compasses. In Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS'06). Lecture Notes in Computer Science, vol. 4305, 333--349.Google ScholarDigital Library
- Souissi, S., Défago, X., and Yamashita, M. 2006b. Using eventually consistent compasses to gather oblivious mobile robots with limited visibility. In Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'06). Lecture Notes in Computer Science, vol. 4280, 471--487.Google Scholar
- Suzuki, I. and Yamashita, M. 1999. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28, 4, 1347--1363. Google ScholarDigital Library
- Uny Cao, Y., Fukunaga, A. S., and Kahng, A. B. 1997. Cooperative mobile robotics: Antecedents and directions. Auton. Robots 4, 1--23. Google ScholarDigital Library
- Yamashita, M., Souissi, S., and Défago, X. 2007. Gathering two stateless mobile robots using very inaccurate compasses in finite time. In Proceedings of the 1st International Conference on Robot Communication and Coordination (ROBOCOMM'07). Athens, Greece. Google ScholarDigital Library
Index Terms
- Using eventually consistent compasses to gather memory-less mobile robots with limited visibility
Recommendations
Gathering of asynchronous robots with limited visibility
In this paper we study the problem of gathering a collection of identical oblivious mobile robots in the same location of the plane. Previous investigations have focused mostly on the unlimited visibility setting, where each robot can always see all the ...
Design and implementation of a navigation system for autonomous mobile robots
In this paper, a navigation system for autonomous mobile robots is proposed. Our navigation system is a hybrid of behaviour-based and model-based navigation systems. In our system, a behaviour-based subsystem is in charge of low-level reactive actions, ...
Using eventually consistent compasses to gather oblivious mobile robots with limited visibility
SSS'06: Proceedings of the 8th international conference on Stabilization, safety, and security of distributed systemsReaching agreement between a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some (not predetermined) ...
Comments