Sage Journals: Discover world-class research

Abstract

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.

Keywords

robot navigation robot sensing art gallery problems

Get full access to this article

View all access options for this article.

References

Brunner, J. , Mihalak, M. , Suri, S. , Vicari, E. , and Widmayer, P. (2008). Simple robots in polygonal environments: A hierarchy . In Algorithmic Aspects of Wireless Sensor Networks, Fourth International Workshop, ALGOSENSORS 2008, Reykjavik , Iceland (To Appear).

Chvátal, V. (1975). A combinatorial theorem in plane geometry . Journal of Combinatorial Theory, 18: 39-41.

de Berg, M. , van Kreveld, M. , Overmars, M. , and Schwarzkopf, O. (1997). Computational geometry: algorithms and applications . Heidelberg, Springer-Verlag.

Fisk, S. (1978). A short proof of Chvatal's watchman theorem . Journal of Combinatorial Theory, 24(B): 374 .

Ganguli, A. , Cortes, J. , and Bullo, F. (2006). Distributed deployment of asynchronous guards in art galleries . In Proceedings of the American Control Conference, pp. 1416- 1421.

Gfeller, B. , Mihalak, M. , Suri, S. , Vicari, E. , and Widmayer, P. (2007). Counting targets with mobile sensors in an unknown environment . In Algorithmic Aspects of Wireless Sensor Networks , Third International Workshop, ALGOSENSORS 2007 , Wroclaw, Poland, July 14, 2007, Revised Selected Papers, Volume 4837 of Lecture Notes in Computer Science, pp. 32-45. Springer.

Ghosh, S. (2007). Visibility Algorithms in the Plane. New York: Cambridge University Press.

Guibas, L.J. , Latombe, J.-C. , LaValle, S.M. , Lin, D. , and Motwani, R. (1999). Visibility-based pursuit-evasion in a polygonal environment . International Journal of Computational Geometry and Applications, 9(5): 471-494.

Latombe, J.-C. (1991). Robot Motion Planning. Norwell, MA: Kluwer Academic Publishers.

10.

LaValle, S.M. (2006). Planning Algorithms. Cambridge : Cambridge University Press.

11.

Pottie, G.J. and Kaiser, W.J. (2000). Wireless integrated network sensors . Communications of the ACM, 43(5): 51-58.

12.

Sachs, S. , Rajko, S. , and LaValle, S.M. (2004). Visibility-based pursuit-evasion in an unknown planar environment . International Journal of Robotics Research , 23(1): 3-26.

13.

Tovar, B. , Freda, L. , and LaValle, S.M. (2007). Using a robot to learn geometric information from permutations of landmarks . Contemporary Mathematics, 438: 33-45.

14.

Yershova, A. , Tovar, B. , Christ, R. , and LaValle, S.M. (2005). Bitbots: Simple robots solving complex tasks . In Proceedings of AAAI National Conference on Artificial Intelligence, pp. 1336-1342.

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

Abstract

Keywords

Get full access to this article

References