Gathering two stateless mobile robots using very inaccurate compasses in finite time

ABSTRACT

This paper considers two asynchronous identical mobile robots in an environment devoid of any landmarks or common coordinate system. The robots, executing their own instance of the same algorithm, must cooperate to end up at the exact same location (not predetermined) within a finite time.

The problem, known as gathering, is the simplest form of spontaneous agreement that can be reached between the robots. This simple problem is however notoriously impossible with two such robots. Surprisingly, the problem was shown to be solvable for three robots or more, adding a weak assumption to help break any potential symmetry in the system. Prior work has shown that the problem could be solved by letting each robot have access to some compass, provided that the divergence between the compasses is at most 45°. The question remained open, however, as to whether the problem could still be solved with a larger divergence.

In this paper, we present a distributed algorithm that solves the gathering problem with two asynchronous robots, when their compasses can differ by any angle less than 180°, which is obviously the largest divergence for which the compasses can still bring any useful information.

REFERENCES

• 1: Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Proc. Intl. Colloquium on Automata, Languages and Programming (ICALP'03). (2003) 1181--1196
• 2: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 3: 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]
• 4: Imazu, H., Itoh, N., Katayama, Y., Inuzuka, N., Wada, K.: A Gathering Problem for Autonomous Mobile Robots with Disagreement in Compasses (in Japanese). In: 1st Workshop on Theoretical Computer Science in Izumo, Japan (2005) 43--46
• 5: Prencipe, G.: Corda: Distributed coordination of a set of autonomous mobile robots. In: Proc. 4th European Research Seminar on Advances in Distributed Systems (ERSADS'01), Bertinoro, Italy (2001) 185--190
• 6: Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Proc. Colloquium on Structural Information and Communication Complexity (SIROCCO'05). (2005) 246--261
• 7: Souissi, S., Défago, X., Yamashita, M.: Gathering Asynchronous Mobile Robots with Inaccurate Compasses. In: Proc. 10th International Conference On Principles Of Distributed Systems (OPODIS '06). LNCS. 4305 (2006) 333--349
• 8: 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]
• 9: Beni, G., Hackwood, S.: Coherent Swarm Motion under Distributed Control. In: Proc. International Symposium on Distributed Autonomous Robotic Systems (DARS'92). (1992) 39--52
• 10: 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
• 11: Balch, T., Arkin, R. C.: Behavior-based Formation Control for Multi-robot Teams. IEEE Trans. on Robotics and Automation, 14 (6) (1998) 926--939
• 12: 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]
• 13: Kawauchi, Y., Inaba, M., Fukuda, T.: A principle of distributed decision making of Cellular Robotic System (CEBOT). In: Proc. IEEE International Conference on Robotics and Automation. 3 (1993) 833--838
• 14: Dias, M. B., Stentz, A.: A Free Market Architecture for Distributed Control of a Multirobot System. Proc. of the 6th Intl. Conf. on Intelligent Autonomous Systems (IAS--6). (2000) 115--122
• 15: Edgar Nett , Stefan Schemmer, Reliable Real-Time Communication in Cooperative Mobile Applications, IEEE Transactions on Computers, v.52 n.2, p.166-180, February 2003 [doi>10.1109/TC.2003.1176984]
• 16: Jennifer E. Walter , Jennifer L. Welch , Nancy M. Amato, Distributed reconfiguration of metamorphic robot chains, Distributed Computing, v.17 n.2, p.171-189, August 2004 [doi>10.1007/s00446-003-0103-y]
• 17: C. Belta, C., Bicchi, A., Egerstedt, M., Frazzoli, E., Klavins, E., Pappas. G. J.: Symbolic Planning and Control of Robot Motion. IEEE Robotics and Automation Magazine. 14(1) (2007) 61--70
• 18: Yamashita, M., Souissi, S., Défago, X.,: Tight bound on the gathering of two oblivious mobile robots with inconsistent compasses. Research Report IS-RR-2007-006, Japan Advanced Institute of Science and Technology, Ishikawa, Japan, April (2007).