Self-stabilizing Localization of the Middle Point of a Line Segment by an Oblivious Robot with Limited Visibility

This paper poses a question about a simple localization problem, which is arisen from self-stabilizing location problems by oblivious mobile autonomous robots with limited visibility. The question is if an oblivious mobile robot on a line-segment can localize the middle point of the line-segment in finite steps observing the direction (i.e., Left or Right) and distance to the nearest end point. This problem is also akin to (a continuous version of) binary search, and could be closely related to computable real functions. Contrary to appearances, it is far from trivial if this simple problem is solvable or not, and unsettled yet. This paper is concerned with three variants of the original problem, minimally relaxing, and presents self-stabilizing algorithms for them. We also show an easy impossibility theorem for bilaterally symmetric algorithms.

• Publication year

  2017

• Venue

  Safety-critical Systems Symposium

• Publication date

  2017-07-20

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/978-3-319-69084-1_12arXiv 1707.06398
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Uniform Deployment of Mobile Agents in Asynchronous Rings

  2016cited by this paper
• Pattern Formation by Oblivious Asynchronous Mobile Robots

  2015cited by this paper
• Plane Formation by Synchronous Mobile Robots in the Three-Dimensional Euclidean Space

  2015cited by this paper
• Distributed Barrier Coverage with Relocatable Sensors

  2014influential reference
• Pattern Formation by Mobile Robots with Limited Visibility

  2013cited by this paper
• Distributed algorithms for barrier coverage using relocatable sensors

  2013influential reference
• Computing by Mobile Robotic Sensors

  2011cited by this paper
• Characterizing geometric patterns formable by oblivious anonymous mobile robots

  2010cited by this paper
• Uniform scattering of autonomous mobile robots in a grid

  2009cited by this paper
• Local spreading algorithms for autonomous robot systems

  2008cited by this paper
• Self-deployment of mobile sensors on a ring

  2008cited by this paper
• Self-deployment Algorithms for Mobile Sensors on a Ring

  2006influential reference
• Local Algorithms for Autonomous Robot Systems

  2006cited by this paper
• Eventually consistent compasses for robust gathering of asynchronous mobile robots with limited visibility

  2005cited by this paper
• Gathering of asynchronous robots with limited visibility

  2005cited by this paper
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems

  2004cited by this paper
• Circle formation for oblivious anonymous mobile robots with no common sense of orientation

  2002influential reference
• The development of prime number theory

  2000cited by this paper
• Distributed memoryless point convergence algorithm for mobile robots with limited visibility

  1999cited by this paper
• Distributed Anonymous Mobile Robots

  1996cited by this paper
• Field and Galois theory

  1996cited by this paper
• Formation and agreement problems for synchronous mobile robots with limited visibility

  1995cited by this paper
• The localization problem for mobile robots

  1994cited by this paper

• Can a Skywalker Localize the Midpoint of a Rope?

  2021cites this paper
• Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots

  2020cites this paper
• Can Walker Localize The Middle Point of A Line-segment?.

  2017cites this paper