| 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. |
