×

Coordination without communication: the case of the flocking problem. (English) Zbl 1161.90336

Summary: We study the distributed coordination and control of a set of asynchronous, anonymous, memoryless mobile vehicles that can freely move on a two-dimensional plane but cannot communicate among themselves. In particular, we analyze the problem of forming a certain pattern and following a designated vehicle, referred to as the leader, while maintaining the pattern: the flocking problem. We provide an algorithm to solve the flocking problem, together with theoretical considerations on its correctness and applicability, and numerical simulation showing the actual behavior of the algorithm. We also propose two variants of the algorithm sporting a more stable convergence, and analyze how different conditions on the equipment available to the vehicles and on the amount of knowledge they share affect the kind of patterns that can be formed.

MSC:

90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ando, H.; Oasa, Y.; Suzuki, I.; Yamashita, M., A distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Trans. Robot. Automat, 15, 5, 818-828 (1999)
[2] Arkin, R. C., Motor schema-based mobile robot navigation, Int. J. Robot. Res, 8, 4, 92-112 (1989)
[3] Arkin, R. C.; Balch, T., Cooperative multiagent robotic systems, (Kortenkamp, D.; Bonasso, R. P.; Murphy, R., Artificial Intelligence and Mobile Robots (1998), MIT/AAAI Press: MIT/AAAI Press Cambridge, MA/New York)
[4] Balch, T.; Arkin, R. C., Behavior-based formation control for multi-robot teams, IEEE Trans. Robot. Automat, 14, 6, 926-939 (1998)
[5] Bonabeau, E.; Dorigo, M.; Theraulaz, G., Swarm Intelligence (1999), Oxford University Press: Oxford University Press Oxford · Zbl 1003.68123
[6] Y.U. Cao, A.S. Fukunaga, A.B. Kahng, F. Meng, Cooperative mobile robotics: antecedents and directions, in: IEEE/TSJ International Conference on Intelligent Robots and Systems, Yokohama, Japan, 1995, pp. 226-234.; Y.U. Cao, A.S. Fukunaga, A.B. Kahng, F. Meng, Cooperative mobile robotics: antecedents and directions, in: IEEE/TSJ International Conference on Intelligent Robots and Systems, Yokohama, Japan, 1995, pp. 226-234.
[7] Q. Chen, J.Y.S. Luh, Coordination and control of a group of small mobile robots, in: Proceedings of IEEE International Conference on Robotics and Automation, San Diego, CA, 1994, pp. 2315-2320.; Q. Chen, J.Y.S. Luh, Coordination and control of a group of small mobile robots, in: Proceedings of IEEE International Conference on Robotics and Automation, San Diego, CA, 1994, pp. 2315-2320.
[8] Dijkstra, E. W., Self-stabilizing systems in spite of distributed control, Comm. ACM, 17, 11, 643-644 (1974) · Zbl 0305.68048
[9] Dolev, S., Self-Stabilization (2000), The MIT Press: The MIT Press Cambridge, MA · Zbl 1026.93001
[10] B.R. Donald, J. Jennings, D. Rus, Analyzing teams of cooperating mobile robots, Technical Report TR 94-1429, Department of Computer Science, Cornell University, 1994.; B.R. Donald, J. Jennings, D. Rus, Analyzing teams of cooperating mobile robots, Technical Report TR 94-1429, Department of Computer Science, Cornell University, 1994.
[11] E.H. Durfee, Blissful ignorance: knowing just enough to coordinate well, in: International Conference on Multi Agent Systems (ICMAS), 1995, pp. 406-413.; E.H. Durfee, Blissful ignorance: knowing just enough to coordinate well, in: International Conference on Multi Agent Systems (ICMAS), 1995, pp. 406-413.
[12] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Hard tasks for weak robots: the role of common knowledge in pattern formation by autonomous mobile robots, in: Proceedings 10th Annual International Symposium on Algorithms and Computation (ISAAC’99), Lecture Notes in Computer Science, Vol. 1741, 1999, pp. 93-102.; P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Hard tasks for weak robots: the role of common knowledge in pattern formation by autonomous mobile robots, in: Proceedings 10th Annual International Symposium on Algorithms and Computation (ISAAC’99), Lecture Notes in Computer Science, Vol. 1741, 1999, pp. 93-102. · Zbl 0970.68700
[13] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Distributed coordination of a set of autonomous mobile robots, in: IEEE Intelligent Vehicle Symposium (IV 2000), 2000, pp. 480-485.; P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Distributed coordination of a set of autonomous mobile robots, in: IEEE Intelligent Vehicle Symposium (IV 2000), 2000, pp. 480-485.
[14] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Gathering of autonomous mobile robots with limited visibility, in: Proceedings 18th International Symposium on Theoretical Aspects of Computer Science (STACS 2001), Lecture Notes in Computer Science, Vol. 2010, 2001, pp. 247-258.; P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Gathering of autonomous mobile robots with limited visibility, in: Proceedings 18th International Symposium on Theoretical Aspects of Computer Science (STACS 2001), Lecture Notes in Computer Science, Vol. 2010, 2001, pp. 247-258. · Zbl 0976.68550
[15] J. Halpern, Y. Moses, Knowledge and common knowledge in a distributed environment, in: Proceedings of the Third ACM Symposium on Principles of Distributed Computing, 1984, pp. 50-61.; J. Halpern, Y. Moses, Knowledge and common knowledge in a distributed environment, in: Proceedings of the Third ACM Symposium on Principles of Distributed Computing, 1984, pp. 50-61.
[16] D. Jung, G. Cheng, A. Zelinsky, Experiments in realising cooperation between autonomous mobile robots, in: Fifth International Symposium on Experimental Robotics (ISER), Barcelona, Catalonia, 1997, pp. 609-620.; D. Jung, G. Cheng, A. Zelinsky, Experiments in realising cooperation between autonomous mobile robots, in: Fifth International Symposium on Experimental Robotics (ISER), Barcelona, Catalonia, 1997, pp. 609-620. · Zbl 0947.70507
[17] M.J. Matarić, Interaction and intelligent behavior, Ph.D. Thesis, MIT Press, Cambridge, MA, 1994.; M.J. Matarić, Interaction and intelligent behavior, Ph.D. Thesis, MIT Press, Cambridge, MA, 1994.
[18] F.R. Noreils, Toward a robot architecture integrating cooperation between mobile robots: application to indoor environment, Int. J. Robot. Res. (1993) 79-98.; F.R. Noreils, Toward a robot architecture integrating cooperation between mobile robots: application to indoor environment, Int. J. Robot. Res. (1993) 79-98.
[19] L.E. Parker, Adaptive action selection for cooperative agent teams, in: Proceedings of Second International Conference on Simulation of Adaptive Behavior, MIT Press, Cambridge, MA, 1992, pp. 442-450.; L.E. Parker, Adaptive action selection for cooperative agent teams, in: Proceedings of Second International Conference on Simulation of Adaptive Behavior, MIT Press, Cambridge, MA, 1992, pp. 442-450.
[20] G. Prencipe, CORDA: distributed coordination of a set of autonomous mobile robots, in: Proceedings Fourth European Research Seminar on Advances in Distributed Systems (ERSADS 2001), 2001, pp. 185-190.; G. Prencipe, CORDA: distributed coordination of a set of autonomous mobile robots, in: Proceedings Fourth European Research Seminar on Advances in Distributed Systems (ERSADS 2001), 2001, pp. 185-190.
[21] 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.
[22] Suzuki, I.; Yamashita, M., Distributed anonymous mobile robotsformation of geometric patterns, SIAM J. Comput, 28, 4, 1347-1363 (1999) · Zbl 0940.68145
[23] Wang, P. K.C., Navigation strategies for multiple autonomous mobile robots moving in formation, J. Robot. Systems, 8, 2, 177-195 (1991) · Zbl 0716.70035
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.