Online Exploration of Polygons with Holes
This work addresses a specific problem in robotics for autonomous exploration, offering incremental improvements in competitive analysis.
The paper tackles the problem of autonomous mobile robots exploring unknown polygons with holes, presenting an (h+c_0)!-competitive strategy based on a hybrid approach and providing a new lower bound for small h.
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+c_0)!-competitive strategy for such polygons under the assumption that each hole is marked with a special color, where c_0 is a universal constant. The strategy is based on a new hybrid approach. Furthermore, we give a new lower bound construction for small h.