Abstract
In this paper, we survey recent results regarding the Gathering problem in the research area of distributed computing by mobile robots. We assume a simple, standard model of robots: they are point-shaped, live in a d- dimensional Euclidean space, are disoriented (do not agree on common directions or orientations), and have limited visibility (can only observe other robots up to a constant distance). The goal of Gathering is to gather all robots at a single, not predefined point. Our focus lies on unifying and extending existing work on gathering in the above model. For this, we derive core properties of protocols that guarantee Gathering and prove runtime bounds that improve upon previous work. This paper surveys results presented in [2, 3, 11] in which such core properties are derived in two different time models: a discrete, round-based time model and a continuous time model.
This work was partially supported by the German Research Foundation (DFG) under the project number ME 872/14-1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Autom. 15(5), 818–828 (1999)
Braun, M., Castenow, J., Meyer auf der Heide, F.: Local gathering of mobile robots in three dimensions. In: Richa, A.W., Scheideler, C. (eds.) SIROCCO 2020. LNCS, vol. 12156, pp. 63–79. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-54921-3_4
Castenow, J., Harbig, J., Jung, D., Kling, P., Knollmann, T., Meyer auf der Heide, F.: A unifying approach to efficient (near)-gathering of disoriented robots with limited visibility. In: OPODIS. LIPIcs, vol. 253, pp. 15:1–15:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516–1528 (2005)
Degener, B., Kempkes, B., Kling, P., Meyer auf der Heide, F.: Linear and competitive strategies for continuous robot formation problems. ACM Trans. Parallel Comput. 2(1), 2:1–2:18 (2015)
Degener, B., Kempkes, B., Langner, T., Meyer auf der Heide, F., Pietrzyk, P., Wattenhofer, R.: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: SPAA, pp. 139–148. ACM (2011)
Elzinga, D.J., Hearn, D.W.: The minimum covering sphere problem. Manage. Sci. 19(1), 96–104 (1972)
Flocchini, P., Prencipe, G., Santoro, N.: Moving and computing models: Robots. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. Lecture Notes in Computer Science, vol. 11340, pp. 3–14. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_1
Gordon, N., Wagner, I.A., Bruckstein, A.M.: Gathering multiple robotic a(ge)nts with limited sensing capabilities. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 142–153. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28646-2_13
Kling, P., Meyer auf der Heide, F.: Continuous protocols for swarm robotics. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. Lecture Notes in Computer Science, vol. 11340, pp. 317–334. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_13
Li, S., Markarian, C., Meyer auf der Heide, F., Podlipyan, P.: A continuous strategy for collisionless gathering. Theor. Comput. Sci. 852, 41–60 (2021)
Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384(2–3), 222–231 (2007)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Castenow, J., Harbig, J., Meyer auf der Heide, F. (2023). Unifying Gathering Protocols for Swarms of Mobile Robots. In: Mavronicolas, M. (eds) Algorithms and Complexity. CIAC 2023. Lecture Notes in Computer Science, vol 13898. Springer, Cham. https://doi.org/10.1007/978-3-031-30448-4_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-30448-4_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30447-7
Online ISBN: 978-3-031-30448-4
eBook Packages: Computer ScienceComputer Science (R0)