Escaping from a Labyrinth with One-way Roads forLimited Robots

摘要

In this paper, we consider the problem of navigating a robot with limited abilities concerning computing power, memory, and sensors through a labyrinth with one-way roads. Escaping from a labyrinth is a task which is widely explored. Many algorithms with different advantages and different areas of application are known. Usually, labyrinths are given as polygonal scenes or (directed) graphs. While scenes of the first type preserve the geometry of the 'real' environment, the latter preserve the connectivity, which is crucial if there are passages that can be traversed in only one direction (e.g., one-way roads). Our approach combines both advantages. In this work we present some properties of labyrinths with one-way roads. With the help of these properties, we were able to develop algorithms that allow a robot with very limited abilities to solve any 'fair' labyrinth.