--- _id: '20710' author: - first_name: Andreas full_name: Cord-Landwehr, Andreas last_name: Cord-Landwehr - first_name: Bastian full_name: Degener, Bastian last_name: Degener - first_name: Matthias full_name: Fischer, Matthias last_name: Fischer - first_name: Martina full_name: Hüllmann, Martina last_name: Hüllmann - first_name: Barbara full_name: Kempkes, Barbara last_name: Kempkes - first_name: Alexander full_name: Klaas, Alexander last_name: Klaas - first_name: Peter full_name: Kling, Peter last_name: Kling - first_name: Sven full_name: Kurras, Sven last_name: Kurras - first_name: Marcus full_name: Märtens, Marcus last_name: Märtens - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm last_name: Meyer auf der Heide - first_name: Christoph full_name: Raupach, Christoph last_name: Raupach - first_name: Kamil full_name: Swierkot, Kamil last_name: Swierkot - first_name: Daniel full_name: Warner, Daniel id: '3902' last_name: Warner - first_name: Christoph full_name: Weddemann, Christoph last_name: Weddemann - first_name: Daniel full_name: Wonisch, Daniel last_name: Wonisch citation: ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. A New Approach for Analyzing Convergence Algorithms for Mobile Robots. In: Automata, Languages and Programming. Berlin, Heidelberg; 2011. doi:10.1007/978-3-642-22012-8_52' apa: Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas, A., … Wonisch, D. (2011). A New Approach for Analyzing Convergence Algorithms for Mobile Robots. In Automata, Languages and Programming. Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22012-8_52 bibtex: '@inbook{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_Meyer auf der Heide_et al._2011, place={Berlin, Heidelberg}, title={A New Approach for Analyzing Convergence Algorithms for Mobile Robots}, DOI={10.1007/978-3-642-22012-8_52}, booktitle={Automata, Languages and Programming}, author={Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and Meyer auf der Heide, Friedhelm and et al.}, year={2011} }' chicago: Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “A New Approach for Analyzing Convergence Algorithms for Mobile Robots.” In Automata, Languages and Programming. Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-22012-8_52. ieee: A. Cord-Landwehr et al., “A New Approach for Analyzing Convergence Algorithms for Mobile Robots,” in Automata, Languages and Programming, Berlin, Heidelberg, 2011. mla: Cord-Landwehr, Andreas, et al. “A New Approach for Analyzing Convergence Algorithms for Mobile Robots.” Automata, Languages and Programming, 2011, doi:10.1007/978-3-642-22012-8_52. short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas, P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Weddemann, D. Wonisch, in: Automata, Languages and Programming, Berlin, Heidelberg, 2011.' date_created: 2020-12-12T12:22:41Z date_updated: 2022-01-06T06:54:33Z department: - _id: '63' doi: 10.1007/978-3-642-22012-8_52 language: - iso: eng place: Berlin, Heidelberg publication: Automata, Languages and Programming publication_identifier: isbn: - '9783642220111' - '9783642220128' issn: - 0302-9743 - 1611-3349 publication_status: published status: public title: A New Approach for Analyzing Convergence Algorithms for Mobile Robots type: book_chapter user_id: '3902' year: '2011' ... --- _id: '16409' abstract: - lang: eng text: "Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.\r\n" author: - first_name: Andreas full_name: Cord-Landwehr, Andreas last_name: Cord-Landwehr - first_name: Bastian full_name: Degener, Bastian last_name: Degener - first_name: Matthias full_name: Fischer, Matthias id: '146' last_name: Fischer - first_name: Martina full_name: Hüllmann, Martina last_name: Hüllmann - first_name: Barbara full_name: Kempkes, Barbara last_name: Kempkes - first_name: Alexander full_name: Klaas, Alexander last_name: Klaas - first_name: Peter full_name: Kling, Peter last_name: Kling - first_name: Sven full_name: Kurras, Sven last_name: Kurras - first_name: Marcus full_name: Märtens, Marcus last_name: Märtens - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Christoph full_name: Raupach, Christoph last_name: Raupach - first_name: Kamil full_name: Swierkot, Kamil last_name: Swierkot - first_name: Daniel full_name: Warner, Daniel last_name: Warner - first_name: Christoph full_name: Weddemann, Christoph last_name: Weddemann - first_name: Daniel full_name: Wonisch, Daniel last_name: Wonisch citation: ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. A New Approach for Analyzing Convergence Algorithms for Mobile Robots. In: Automata, Languages and Programming. Berlin, Heidelberg; 2011. doi:10.1007/978-3-642-22012-8_52' apa: Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas, A., … Wonisch, D. (2011). A New Approach for Analyzing Convergence Algorithms for Mobile Robots. In Automata, Languages and Programming. Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22012-8_52 bibtex: '@inbook{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_Meyer auf der Heide_et al._2011, place={Berlin, Heidelberg}, title={A New Approach for Analyzing Convergence Algorithms for Mobile Robots}, DOI={10.1007/978-3-642-22012-8_52}, booktitle={Automata, Languages and Programming}, author={Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and Meyer auf der Heide, Friedhelm and et al.}, year={2011} }' chicago: Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “A New Approach for Analyzing Convergence Algorithms for Mobile Robots.” In Automata, Languages and Programming. Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-22012-8_52. ieee: A. Cord-Landwehr et al., “A New Approach for Analyzing Convergence Algorithms for Mobile Robots,” in Automata, Languages and Programming, Berlin, Heidelberg, 2011. mla: Cord-Landwehr, Andreas, et al. “A New Approach for Analyzing Convergence Algorithms for Mobile Robots.” Automata, Languages and Programming, 2011, doi:10.1007/978-3-642-22012-8_52. short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas, P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Weddemann, D. Wonisch, in: Automata, Languages and Programming, Berlin, Heidelberg, 2011.' date_created: 2020-04-06T07:47:55Z date_updated: 2022-01-06T06:52:50Z department: - _id: '63' doi: 10.1007/978-3-642-22012-8_52 language: - iso: eng place: Berlin, Heidelberg publication: Automata, Languages and Programming publication_identifier: isbn: - '9783642220111' - '9783642220128' issn: - 0302-9743 - 1611-3349 publication_status: published status: public title: A New Approach for Analyzing Convergence Algorithms for Mobile Robots type: book_chapter user_id: '15415' year: '2011' ...