Abstract
We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that is, if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counterclockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (⩽ π) or reflex ( > π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known.
We obtain the general result that a robot exploring any locally oriented, arc-labeled graph G can always determine the base graph of G. Roughly speaking, this is the smallest graph that cannot be distinguished by a robot from G by its observations alone, no matter how it moves. Combining this result with various other techniques allows the ability to show that a robot exploring a polygon P with the preceding capabilities is always capable of reconstructing the visibility graph of P. We also show that multiple identical, indistinguishable, and deterministic robots of this kind can always solve the weak rendezvous problem in which they need to position themselves such that they mutually see each other—for instance, such that they form a clique in the visibility graph.
- N. Agmon and D. Peleg. 2007. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing 36, 1, 56--82. Google ScholarDigital Library
- H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. 1999. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation 15, 5, 818--828.Google ScholarCross Ref
- D. Angluin. 1980. Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing. 82--93. Google ScholarDigital Library
- D. Bilò, Y. Disser, M. Mihalák, S. Suri, E. Vicari, and P. Widmayer. 2012. Reconstructing visibility graphs with simple robots. Theoretical Computer Science 444, 52--59. Google ScholarDigital Library
- P. Boldi and S. Vigna. 2002. Fibrations of graphs. Discrete Mathematics 243, 1--3, 21--66. Google ScholarDigital Library
- J. Brunner, M. Mihalák, S. Suri, E. Vicari, and P. Widmayer. 2008. Simple robots in polygonal environments: A hierarchy. In Proceedings of the 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks. 111--124. Google ScholarDigital Library
- J. Chalopin, S. Das, Y. Disser, M. Mihalák, and P. Widmayer. 2011. Mapping simple polygons: How robots benefit from looking back. Algorithmica 65, 1, 43--59.Google ScholarDigital Library
- J. Chalopin, E. Godard, Y. Métivier, and R. Ossamy. 2006. Mobile agent algorithms versus message passing algorithms. In Proceedings of the 10th International Conference on the Principles of Distributed Systems. 187--201. Google ScholarDigital Library
- R. Cohen and D. Peleg. 2008. Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM Journal on Computing 38, 1, 276--302. Google ScholarDigital Library
- S Das, P. Flocchini, S. Kutten, A. Nayak, and N. Santoro. 2007. Map construction of unknown graphs by multiple agents. Theoretical Computer Science 385, 1--3, 34--48. Google ScholarDigital Library
- D. Dereniowski and A. Pelc. 2012. Drawing maps with advice. Journal of Parallel and Distributed Computing 72, 2, 132--143. Google ScholarDigital Library
- Y. Disser, S. K. Ghosh, M. Mihalák, and P. Widmayer. 2013a. Mapping a polygon with holes using a compass. Theoretical Computer Science 553, 106--113. Google ScholarDigital Library
- Y. Disser, M. Mihalák, and P. Widmayer. 2011. A polygon is determined by its angles. Computational Geometry: Theory and Applications 44, 418--426. Google ScholarDigital Library
- Y. Disser, M. Mihalák, and P. Widmayer. 2013b. Mapping polygons with agents that measure angles. In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics (WAFR). 415--425.Google Scholar
- A. Ganguli, J. Cortés, and F. Bullo. 2006. Distributed deployment of asynchronous guards in art galleries. In Proceedings of the 2006 American Control Conference. 1416--1421.Google Scholar
- M. Katsev, A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle. 2011. Mapping and pursuit-evasion strategies for a simple wall-following robot. IEEE Transactions on Robotics 27, 1, 113--128. Google ScholarDigital Library
- D.-T. Lee and F. P. Preparata. 1984. Euclidean shortest paths in the presence of rectilinear barriers. Networks 14, 3, 393--410.Google ScholarCross Ref
- J. Lin, A. Morse, and B. Anderson. 2007a. The multi-agent rendezvous problem. Part 1: The synchronous case. SIAM Journal on Control and Optimization 46, 6, 2096--2119. Google ScholarDigital Library
- J. Lin, A. Morse, and B. Anderson. 2007b. The multi-agent rendezvous problem. Part 2: The asynchronous case. SIAM Journal on Control and Optimization 46, 6, 2120--2147. Google ScholarDigital Library
- P. Panaite and A. Pelc. 1999. Exploring unknown undirected graphs. Journal of Algorithms 33, 281--295. Google ScholarDigital Library
- S. Suri, E. Vicari, and P. Widmayer. 2008. Simple robots with minimal sensing: From local visibility to global geometry. International Journal of Robotics Research 27, 9, 1055--1067. Google ScholarDigital Library
- I. Suzuki and M. Yamashita. 1999. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing 28, 4, 1347--1363. Google ScholarDigital Library
- M. Yamashita and T. Kameda. 1996. Computing on anonymous networks: Part—characterizing the solvable cases. IEEE Transactions on Parallel and Distributed Systems 7, 1, 69--89. Google ScholarDigital Library
Index Terms
- Mapping Simple Polygons: The Power of Telling Convex from Reflex
Recommendations
Mapping Simple Polygons: How Robots Benefit from Looking Back
We consider the problem of mapping an initially unknown polygon of size n with a simple robot that moves inside the polygon along straight lines between the vertices. The robot sees distant vertices in counter-clockwise order and is able to recognize ...
Unsolved problems in visibility graphs of points, segments, and polygons
In this survey article, we present open problems and conjectures on visibility graphs of points, segments, and polygons along with necessary backgrounds for understanding them.
Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryLet P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment inside P. We present a 3-approximation algorithm for the problem of finding a ...
Comments