Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry

Abstract

We consider problems of geometric exploration and self-deployment for simple robots that can only sense the combinatorial (non-metric) features of their sur roundings. 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 or not; with sufficiently many peb bles, it can also count the number of holes in the en vironment. Highlighting the subtleties of our sens ing model, we show that a robot can decide whether the environment is a convex polygon, yet it cannot re solve 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 poly gon, and that the triangulation algorithm can be imple mented collaboratively by a group of m such robots, each with Θ(n/m) memory. As a corollary of the tri angulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem [1]: 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 in [4].