Abstract
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 the vertex among them which it came from in its last move, i.e. the robot can look back. Other than that the robot has no means of distinguishing distant vertices. We assume that an upper bound on n is known to the robot beforehand and show that it can always uniquely reconstruct the visibility graph of the polygon. Additionally, we show that multiple identical and deterministic robots can always solve the weak rendezvous problem in which the robots need to position themselves such that all of them are mutually visible to each other.
Our results are tight in the sense that the strong rendezvous problem, where robots need to gather at a vertex, cannot be solved in general, and, without knowing a bound beforehand, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic, Dordrecht (2003)
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)
Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 82–93 (1980)
Bilò, D., Disser, Y., Mihalák, M., Suri, S., Vicari, E., Widmayer, P.: Reconstructing visibility graphs with simple robots. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity, pp. 87–99 (2009)
Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Proceedings of the 15th International Conference on Distributed Computing, pp. 33–47 (2001)
Brunner, J., Mihalák, M., Suri, S., Vicari, E., Widmayer, P.: Simple robots in polygonal environments: a hierarchy. In: Proceedings of the Fourth International Workshop on Algorithmic Aspects of Wireless Sensor Networks, pp. 111–124 (2008)
Chalopin, J., Das, S., Disser, Y., Mihalák, M., Widmayer, P.: How simple robots benefit from looking back. In: Proceedings of the 7th International Conference on Algorithms and Complexity, pp. 229–239 (2010)
Chalopin, J., Godard, E., Métivier, Y., Ossamy, R.: Mobile agent algorithms versus message passing algorithms. In: Proceedings of the 10th International Conference on the Principles of Distributed Systems, pp. 187–201 (2006)
Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38(1), 276–302 (2008)
Disser, Y., Mihalák, M., Widmayer, P.: Reconstructing a simple polygon from its angles. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 13–24 (2010)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1–3), 147–168 (2005)
Ganguli, A., Cortés, J., Bullo, F.: Distributed deployment of asynchronous guards in art galleries. In: Proceedings of the 2006 American Control Conference, pp. 1416–1421 (2006)
Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge (2007)
Kranakis, E., Krizanc, D., Rajsbaum, S.: Mobile agent rendezvous: a survey. In: Proceedings of the 13th International Colloquium Structural Information and Communication Complexity, pp. 1–9 (2006)
Norris, N.: Universal covers of graphs: isomorphism to depth n−1 implies isomorphism to all depths. Discrete Appl. Math. 56(1), 61–74 (1995)
Suri, S., Vicari, E., Widmayer, P.: Simple robots with minimal sensing: from local visibility to global geometry. Int. J. Robot. Res. 27(9), 1055–1067 (2008)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)
Yamashita, M., Kameda, T.: Computing on anonymous networks: Part I—characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69–89 (1996)
Yershova, A., Tovar, B., Ghrist, R., LaValle, S.M.: Bitbots: Simple robots solving complex tasks. In: Proceedings of the 20th National Conference on Artificial Intelligence, vol. 3, pp. 1336–1341 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in the Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC 2010) [7].
Rights and permissions
About this article
Cite this article
Chalopin, J., Das, S., Disser, Y. et al. Mapping Simple Polygons: How Robots Benefit from Looking Back. Algorithmica 65, 43–59 (2013). https://doi.org/10.1007/s00453-011-9572-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9572-8