Exploring Polygonal Environments by Simple Robots with Faulty Combinatorial Vision

摘要

We study robustness issues of basic exploration tasks of simple robots inside a polygon P when sensors provide possibly faulty information about the unlabelled environment P. Ideally, the simple robot we consider is able to sense the number and the order of visible vertices, and can move to any such visible vertex. Additionally, the robot senses whether two visible vertices form an edge of P. We call this sensing a combinatorial vision. The robot can use pebbles to mark vertices. If there is a visible vertex with a pebble, the robot knows (senses) the index of this vertex in the list of visible vertices in counterclockwise order. It has been shown [1] that such a simple robot, using one pebble, can virtually label the visible vertices with their global indices, and navigate consistently in P. This allows, for example, to compute the map or a triangulation of P. In this paper we revisit some of these computational tasks in a faulty environment, in that we model situations where the sensors "see" two visible vertices as one vertex. In such a situation, we show that a simple robot with one pebble cannot even compute the number of vertices of P. We conjecture (and discuss) that this is neither possible with two pebbles. We then present an algorithm that uses three pebbles of two types, and allows the simple robot to count the vertices of P. Using this algorithm as a subroutine, we present algorithms that reconstruct the map of P, as well as the correct visibility at every vertex of P.