Using eventually consistent compasses to gather memory-less mobile robots with limited visibility

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.

REFERENCES

• 1: Noa Agmon , David Peleg, Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots, SIAM Journal on Computing, v.36 n.1, p.56-82, 2006 [doi>10.1137/050645221]
• 2: 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.
• 3: Balch, T. and Arkin, R. C. 1998. Behavior-based formation control for multi-robot teams. IEEE Trans. Robot. Automat. 14, 6, 926--939.
• 4: 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.
• 5: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 6: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 7: Cieliebak, M. 2004. Gathering non-oblivious mobile robots. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04), 577--588.
• 8: 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.
• 9: 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.
• 10: Reuven Cohen , David Peleg, Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements, SIAM Journal on Computing, v.38 n.1, p.276-302, March 2008 [doi>10.1137/060665257]
• 11: 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.
• 12: 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.
• 13: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 14: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 15: 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.
• 16: Paola Flocchini , Giuseppe Prencipe , Nicola Santoro , Peter Widmayer, Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots, Proceedings of the 10th International Symposium on Algorithms and Computation, p.93-102, December 16-18, 1999
• 17: 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.
• 18: Paola Flocchini , Giuseppe Prencipe , Nicola Santoro , Peter Widmayer, Gathering of asynchronous robots with limited visibility, Theoretical Computer Science, v.337 n.1-3, p.147-168, 9 June 2005 [doi>10.1016/j.tcs.2005.01.001]
• 19: Vincenzo Gervasi , Giuseppe Prencipe, Coordination without communication: the case of the flocking problem, Discrete Applied Mathematics, v.144 n.3, p.324-344, 15 December 2004 [doi>10.1016/j.dam.2003.11.010]
• 20: 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.
• 21: Nobuhiro Inuzuka , Yuichi Tomida , Taisuke Izumi , Yoshiaki Katayama , Koichi Wada, Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses, Proceedings of the 15th international colloquium on Structural Information and Communication Complexity, June 17-20, 2008, Villars-sur-Ollon, Switzerland [doi>10.1007/978-3-540-69355-0_3]
• 22: 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.
• 23: 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.
• 24: 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.
• 25: 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.
• 26: Alcherio Martinoli , Francesco Mondada, Collective and Cooperative Group Behaviors: Biologically Inspired Experiments in Robotics, The 4th International Symposium on Experimental Robotics IV, p.3-10, July 02, 1995
• 27: 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.
• 28: 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.
• 29: Giuseppe Prencipe, Instantaneous Actions vs. Full Asynchronicity: Controlling and Coordinating a Set of Autonomous Mobile Robots, Proceedings of the 7th Italian Conference on Theoretical Computer Science, p.154-171, October 04-06, 2001
• 30: 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.
• 31: 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.
• 32: Souissi, S. 2007. Fault-resilient cooperation of autonomous mobile robots with unreliable compass sensors. Japan Advanced Institute of Science and Technology.
• 33: 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.
• 34: 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.
• 35: Ichiro Suzuki , Masafumi Yamashita, Distributed Anonymous Mobile Robots: Formation of Geometric Patterns, SIAM Journal on Computing, v.28 n.4, p.1347-1363, Aug. 1999 [doi>10.1137/S009753979628292X]
• 36: Y. Uny Cao , Alex S. Fukunaga , Andrew Kahng, Cooperative Mobile Robotics: Antecedents and Directions, Autonomous Robots, v.4 n.1, p.7-27, March 1997 [doi>10.1023/A:1008855018923]
• 37: Masafumi Yamashita , Samia Souissi , Xavier Défago, Gathering two stateless mobile robots using very inaccurate compasses in finite time, Proceedings of the 1st international conference on Robot communication and coordination, October 15-17, 2007, Athens, Greece

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS

General Terms:
Algorithms, Theory

Keywords:
Autonomous Mobile Robots, Cooperation and Control, Point Formation, Self-Organizing Robots, Self-Stabilization, Unreliable Compasses