| Sign In to gain access to subscriptions and/or personal tools. |
Simple Robots with Minimal Sensing: From Local Visibility to Global GeometryDepartment of Computer Science University of California Santa Barbara, USA 95106
Institute of Theoretical Computer Science ETH Zurich 8092 Zurich, Switzerland, vicariel{at}inf.ethz.ch
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
Key Words: robot navigation • robot sensing • art gallery problems
The International Journal of Robotics Research, Vol. 27, No. 9,
1055-1067 (2008) |
|||
 |
|
|
 |
|
Sign In to gain access to subscriptions and/or personal tools.
(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.