Volume 27 Issue 9 - Publication Date: 1 September 2008
Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
S. Suri Department of Computer Science University of California Santa Barbara, USA 95106, E. Vicari and P. Widmayer Institute of Theoretical Computer Science ETH Zurich 8092 Zurich, Switzerland
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 given vertex is convex. Finally, we show that by 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 (n/m) word memory. As a corollary of the triangulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem. A group of n/3 (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.
Return to Contents