Subhash Suri, Elias Vicari, Peter Widmayer
We consider problems of geometric exploration and self-deployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Even with such a limited sensing, we show that robots can achieve complex geometric reasoning and perform many non-trivial tasks. Specifically, we show that one robot equipped with a single pebble can decide whether the workspace environment is a simply-connected polygon and, if not, it can also count the number of holes in the environment. Highlighting the subtleties of our sensing model, we show that a robot can decide whether the environment is a convex polygon, yet it cannot resolve whether a particular vertex is convex. Finally, we show that using such local and minimal sensing, a robot can compute a proper triangulation of a polygon, and that the triangulation algorithm can be implemented collaboratively by a group of $m$ such robots, each with $\Theta (n/m)$ memory. As a corollary of the triangulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem: a group of $\lfloor n/3 \rfloor$ (bounded memory) robots in our minimal sensing model can self-deploy to achieve visibility coverage of an $n$-vertex art gallery (polygon). This resolves an open question raised recently by Ganguli et al.
Subjects: 17. Robotics; 3.2 Geometric Or Spatial Reasoning
Submitted: Apr 11, 2007