Characterizing geometric patterns formable by oblivious anonymous mobile robots. (English) Zbl 1208.68222
Summary: In a system in which anonymous mobile robots repeatedly execute a “Look-Compute-Move” cycle, a robot is said to be oblivious if it has no memory to store its observations in the past, and hence its move depends only on the current observation. This paper considers the pattern formation problem in such a system, and shows that oblivious robots can form any pattern that non-oblivious robots can form, except that two oblivious robots cannot form a point while two non-oblivious robots can. Therefore, memory does not help in forming a pattern, except for the case in which two robots attempt to form a point. Related results on the pattern convergence problem are also presented.
Keywords:
distributed algorithms; anonymous robots; convergence; formation; geometric patterns; mobile robots; oblivious robotsReferences:
| [1] | Ando, H.; Oasa, Y.; Suzuki, I.; Yamashita, M., Distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Transactions on Robotics and Automation, 15, 5, 818-828 (1999) |
| [2] | Cieliebak, M.; Flocchini, P.; Prencipe, G.; Santoro, N., Solving the robots gathering problem, (Proc. 30th Int. Colloquium on Automata, Languages and Programming. Proc. 30th Int. Colloquium on Automata, Languages and Programming, ICALP 2003. Proc. 30th Int. Colloquium on Automata, Languages and Programming. Proc. 30th Int. Colloquium on Automata, Languages and Programming, ICALP 2003, LNCS, vol. 2719 (2003)), 1181-1196 · Zbl 1039.68129 |
| [3] | Cohen, R.; Peleg, D., Local algorithms for autonomous robot systems, (Proc. 13th Int. Colloquium on Structural Information and Communication Complexity. Proc. 13th Int. Colloquium on Structural Information and Communication Complexity, SIROCCO 2006. Proc. 13th Int. Colloquium on Structural Information and Communication Complexity. Proc. 13th Int. Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, LNCS, vol. 3221 (2006)), 29-43 · Zbl 1222.68390 |
| [4] | Czyzowicz, J.; Gasieniec, L.; Pelc, A., Gathering few fat mobile robots in the plane, (Proc. 10th Int. Conf. on Principles of Distributed Systems. Proc. 10th Int. Conf. on Principles of Distributed Systems, OPODIS 2006. Proc. 10th Int. Conf. on Principles of Distributed Systems. Proc. 10th Int. Conf. on Principles of Distributed Systems, OPODIS 2006, LNCS, vol. 4288 (2006)), 744-753 |
| [5] | Katayama, Y.; Tomida, Y.; Imazu, H.; Inuzuka, N.; Wada, K., Dynamic compass models and gathering algorithms for autonomous mobile robots, (LNCS, vol. 4474 (2007)), 274-288 · Zbl 1201.68122 |
| [6] | G. Prencipe, Distributed coordination of a set of autonomous mobile robots, Ph.D. Thesis, Università di Pisa, 2002.; G. Prencipe, Distributed coordination of a set of autonomous mobile robots, Ph.D. Thesis, Università di Pisa, 2002. |
| [7] | Prencipe, G., Impossibility of gathering by a set of autonomous mobile robots, Theoretical Computer Science, 384, 222-231 (2007) · Zbl 1125.68124 |
| [8] | G. Prencipe, N. Santoro, Distributed algorithms for mobile robots, in: Proc. 5th IFIP Int. Conf. on Theoretical Computer Science, TCS 2006, pp. 47-62.; G. Prencipe, N. Santoro, Distributed algorithms for mobile robots, in: Proc. 5th IFIP Int. Conf. on Theoretical Computer Science, TCS 2006, pp. 47-62. |
| [9] | Souissi, S.; Defago, X.; Yamashita, M., Gathering asynchronous mobile robots with inaccurate compasses, (Proc. 10th Int. Conf. on Principles of Distributed Systems. Proc. 10th Int. Conf. on Principles of Distributed Systems, OPODIS 2006. Proc. 10th Int. Conf. on Principles of Distributed Systems. Proc. 10th Int. Conf. on Principles of Distributed Systems, OPODIS 2006, LNCS, vol. 4305 (2006)), 333-349 |
| [10] | Suzuki, I.; Yamashita, M., Distributed anonymous mobile robots — formation of geometric patterns, SIAM Journal on Computing, 28, 4, 1347-1363 (1999) · Zbl 0940.68145 |
| [11] | Yamanaka, N.; Ito, N.; Katayama, Y.; Inuzuka, N.; Wada, K., A pattern formation algorithm for distributed autonomous robots without agreements on axis orientations, IEICE Trans. D-I, J88-D-I, 4, 739-750 (2005), (in Japanese) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
