×

zbMATH — the first resource for mathematics

The simple grid polygon exploration problem. (English) Zbl 07347223
Summary: This paper considers an on-line exploration problem. We use a mobile robot to explore an unknown simple grid polygon. The robot is assumed to have limited sensing capability that can only detect the four basic cells adjacent to it. The robot’s task is to explore each cell and to return to the start. To explore a cell, the robot has to enter it. We ask for a short exploration tour, that is, minimizing the number of multiple-visit cells. The competitive ratio is used to measure the performance of our strategy. It is the ratio between the length of the on-line exploration path and the length of the shortest path achieved with full knowledge of the polygon. As our main result, we present a new on-line exploration strategy and prove that the robot’s path is at most 7/6 times longer than the shortest path. This matches the previously known lower bound.
MSC:
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Almeida, JPLSD; Nakashima, RT; Neves-Jr, F.; Arruda, LVRD, Bio-inspired on-line path planner for cooperative exploration of unknown environment by a multi-robot system, Robot Auton Syst, 112, 32-48 (2019)
[2] Chalopin, J.; Das, S.; Disser, Y.; Mihalák, M.; Widmayer, P., Mapping simple polygons: The power of telling convex from reflex, ACM Trans Algorithms, 11, 4, 33:1-33:16 (2015) · Zbl 1398.68616
[3] Deng X, Kameda T, Papadimitriou C (1991) How to learn an unknown environment. In: Proceedings 32nd annual symposium of foundations of computer science, pp. 298-303 · Zbl 0904.68115
[4] Dereniowski D, Disser Y, Kosowski A, Paja̧k D, Uznański P (2015) Fast collaborative graph exploration. Inf Comput 243:37-49 · Zbl 1327.68177
[5] Doi K, Yamauchi Y, Kijima S, Yamashita M (2018) Exploration of finite 2d square grid by a metamorphic robotic system. In: Izumi T, Kuznetsov P (eds.) Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science, vol. 11201, pp. 96-110. Springer, Berlin
[6] Foerster, KT; Wattenhofer, R., Lower and upper competitive bounds for online directed graph exploration, Theoret Comput Sci, 655, 15-29 (2016) · Zbl 1359.90141
[7] Gabriely, Y.; Rimon, E., Competitive on-line coverage of grid environments by a mobile robot, Comput Geom, 24, 3, 197-224 (2003) · Zbl 1092.68107
[8] Ghosh, SK; Klein, R., Online algorithms for searching and exploration in the plane, Comput Sci Rev, 4, 4, 189-201 (2010) · Zbl 1298.68280
[9] Hagius R, Icking C, Langetepe E (2004) Lower bounds for the polygon exploration problems. In: 20th European Workshop Computer Geometry, pp. 135-138
[10] Hoffmann, F.; Icking, C.; Klein, R.; Kriegel, K., The polygon exploration problem, SIAM J Comput, 31, 2, 577-600 (2002) · Zbl 0994.68163
[11] Icking C, Kamphans T, Klein R, Langetepe E (2002) On the competitive complexity of navigation tasks. In: Hager GD, Christensen HI, Bunke H, Klein R (eds) Sensor Based Intelligent Robots, vol 2238. Lecture Notes in Computer Science. pp 245-258. Springer, Berlin · Zbl 1053.68847
[12] Icking C, Kamphans T, Klein R, Langetepe E (2005) Exploring simple grid polygons. In: Wang L (ed) Computing and Combinatorics, vol 3595. Lecture Notes in Computer Science. pp 524-533. Springer, Berlin · Zbl 1128.68504
[13] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in l-shaped grid graphs, Theoret Comput Sci, 621, 37-56 (2016) · Zbl 1335.05100
[14] Megow, N.; Mehlhorn, K.; Schweitzer, P., Online graph exploration: New results on old and new algorithms, Theoret Comput Sci, 463, 62-72 (2012) · Zbl 1269.05103
[15] Ortolf C, Schindelhauer C (2012) Online multi-robot exploration of grid graphs with rectangular obstacles. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’12, pp 27-36. ACM, New York, USA
[16] Strom, DP; Bogoslavskyi, I.; Stachniss, C., Robust exploration and homing for autonomous robots, Robot Auton Syst, 90, 125-135 (2017)
[17] Tan X, Wei Q (2015) An improved on-line strategy for exploring unknown polygons. Combinatorial Optimization and Applications, vol 9486. Lecture Notes in Computer Science. pp 163-177. Springer, Berlin · Zbl 06539312
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.