2012/07/01 by Robert Georges, Georges, Robert, Frank Hoffmann +3
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO) #cs.CG #cs.DS #cs.RO
paper · pdf · doi:10.48550/arxiv.1207.0240
16 pages, 9 figures, submitted to WAOA 2012
arxiv created 2012/07/01 · openalex publication_date 2012/07/01 · arxiv updated 2012/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study online strategies for autonomous mobile robots with vision to explore unknown polygons with at most h holes. Our main contribution is an (h+c0)!-competitive strategy for such polygons under the assumption that each hole is marked with a special color, where c0 is a universal constant. The strategy is based on a new hybrid approach. Furthermore, we give a new lower bound construction for small h.