2010/12/23 by Christian Icking, Icking, Christian, Tom Kamphans +5 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #I.2.9 #I.3.5 #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO) #cs.CG #cs.RO
paper · pdf · doi:10.48550/arxiv.1012.5240
49 pages, 45 figures
arxiv created 2010/12/23 · openalex publication_date 2010/12/23 · arxiv updated 2010/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the exploration problem of a short-sighted mobile robot moving in an unknown cellular room. To explore a cell, the robot must enter it. Once inside, the robot knows which of the 4 adjacent cells exist and which are boundary edges. The robot starts from a specified cell adjacent to the room's outer wall; it visits each cell, and returns to the start. Our interest is in a short exploration tour; that is, in keeping the number of multiple cell visits small. For abitrary environments containing no obstacles we provide a strategy producing tours of length S <= C + 1/2 E - 3, and for environments containing obstacles we provide a strategy, that is bound by S <= C + 1/2 E + 3H + WCW - 2, where C denotes the number of cells-the area-, E denotes the number of boundary edges-the perimeter-, and H is the number of obstacles, and WCW is a measure for the sinuosity of the given environment.