Can a Skywalker Localize the Midpoint of a Rope?
Article No.: 17, Pages 1 - 23
Abstract
This article poses a question about a simple localization problem. The question is if an oblivious walker on a line segment can localize the midpoint of the line segment in a finite number of steps observing the direction (i.e., Left or Right) and the distance to the nearest end point. This problem arises from self-stabilizing location problems by autonomous mobile robots with limited visibility, which is an abstract model attracting a wide interest in distributed computing. Contrary to appearances, it is far from trivial whether this simple problem is solvable, and it is not settled yet. This article is concerned with three variants of the problem with a minimal relaxation and presents self-stabilizing algorithms for them. We also show an easy impossibility theorem for bilaterally symmetric algorithms.
References
[1]
Hideki Ando, Yoshinobu Oasa, Ichiro Suzuki, and Masafumi Yamashita. 1999. Distributed memoryless point convergence algorithm for mobile robots. IEEE Trans. Robot. Autom. 15, 5, (Oct. 1999), 818–828.
[2]
Hideki Ando, Ichiro Suzuki, and Masafumi Yamashita. 1995. Formation and agreement problems for synchronous mobile robots with limited visibility. In Proceedings of the 10th IEEE Symposium of Intelligent Control (ISIC’95).453–460.
[3]
Lali Barriere, Paola Flocchini, Eduardo Mesa-Barrameda, and Nicola Santoro. 2011. Uniforming scattering of autonomous mobile robots in a grid. Int. J. Found. Comput. Sci. 22, 3, (2011), 679–697.
[4]
Reuven Cohen and David Peleg. 2005. Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 6, (2005), 1516–1528.
[5]
Reuven Cohen and David Peleg. 2006. Local algorithms for autonomous robot systems. In Proceedings of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO’06).29–43.
[6]
Reuven Cohen and David Peleg. 2008. Local spreading algorithms for autonomous robot systems. Theor. Comput. Sci. 399, 1–2, (June 2008), 71–82.
[7]
Xavier Défago and Akihiko Konagaya. 2002. Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In Proceedings of the ACM Workshop on Principles of Mobile Computing (POMC’02).97–104.
[8]
Edsger W. Dijkstra. 1974. Self-stabilizing systems in spite of distributed control. Commun. ACM 17, 11 (Nov. 1974), 643–644.
[9]
Leonhard Euler. 1737. Variae observationes circa series infinitas. Commentarii academiae scientiarum Petropolitanae 9, (1744), 160–188.
[10]
Mohsen Eftekhari, Paola Flocchini, Lata Narayanan, Jaroslav Opatrny, and Nicola Santoro. 2014. Distributed barrier coverage with relocatable sensors. In Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO’14).235–249.
[11]
Mohsen Eftekhari, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. 2016. Distributed algorithms for barrier coverage using relocatable sensors. Distrib. Comput. 29, (Apr. 2016), 361–376.
[12]
Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2008. Self-deployment algorithms for mobile sensors on a ring. Theor. Comput. Sci. 402, 1, (July 2008), 67–80.
[13]
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. 2005. Gathering of asynchronous mobile robots with limited visibility. Theor. Comput. Sci. 337, 1-3, (June 2005), 147–168.
[14]
Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2011. Computing by Mobile Robotic Sensors.Springer, Berlin.
[15]
Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. 2015. Pattern formation by oblivious asynchronous mobile robots. SIAM J. Comput. 44, 3, (2015). 740–785.
[16]
Jon Michael Kleinberg. 1994. The localization problem for mobile robots. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS’94).521–531.
[17]
Akihiro Monde, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. 2017. Self-stabilizing localization of the middle point of a line segment by an oblivious robot with limited visibility. In Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS’17).172–186.
[18]
Władysław Narkiewicz. 2000. The Development of Prime Number Theory.Springer-Verlag, Berlin.
[19]
Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. 2018. Uniform deployment of mobile agents in asynchronous rings. J. Parallel Distrib. Comput. 119, (Sept. 2018), 92–106.
[20]
Ichiro Suzuki and Masafumi Yamashita. 1999. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28, 4, (1999), 1347–1363.
[21]
Masafumi Yamashita and Ichiro Suzuki. 2010. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci. 411, 26–28, (2010), 2433–2453.
[22]
Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, and Masafumi Yamashita. 2017. Plane formation by synchronous mobile robots in the three dimensional Euclidean space. J. ACM 64, 3 (June 2017).
[23]
Yukiko Yamauchi and Masafumi Yamashita. 2013. Pattern formation by mobile robots with limited visibility. In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO’13).201–212.
Index Terms
- Can a Skywalker Localize the Midpoint of a Rope?
Recommendations
Task Oriented Behavior-Based State-Adaptive PID (Proportional Integral Derivative) Control for Low-Cost Mobile Robot
ICCEA '10: Proceedings of the 2010 Second International Conference on Computer Engineering and Applications - Volume 01This paper describes how state-adaptive PID (Proportional Integral Derivative) control can be applied to a low-cost mobile robot. Behavior-based state-adaptive control for this mobile robot behaviors was designed using only three infrared sensors, a low-...
Autonomous mobile robot that can read
The ability to read would surely contribute to increased autonomy of mobile robots operating in the real world. The process seems fairly simple: the robot must be capable of acquiring an image of a message to read, extract the characters, and recognize ...
Experimental investigation on coverage performance of a chaotic autonomous mobile robot
In many autonomous mobile robotic missions the complete and fast coverage of the workspace, scanned by an unpredictable trajectory, plays a crucial role. To satisfy these special demands in the design of an autonomous mobile robot, a motion controller, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2021
146 pages
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 July 2021
Accepted: 01 March 2021
Revised: 01 September 2020
Received: 01 March 2019
Published in TOCT Volume 13, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 62Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format