An art gallery-based approach to autonomous robot motion planning in global environments
Authors:
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 6 (21530858) , 2079-2084
Abstract
In this paper, we present a novel art gallery-based algorithm for placing a small number of guards to cover a global environment with obstacles for an autonomous robot. The guards are required to cover the entire workspace that is represented as a simple polygon with n vertices and h holes (obstacles). The proposed algorithm efficiently computes a (small) number of guards in simple polygons with holes, which runs in O (n log n) time and requires a linear storage complexity. However, an additional set of connection nodes is computed to form the connectivity graph, which contains all guards. This graph has far less number of vertices when compared to similar data structures used in conventional visibility-based or probabilistic-based motion planning algorithms. The resulting placement of guards and connectors can then be used as control points in the path of an autonomous mobile robot for navigation or inspection tasks. The proposed algorithm is not only offering a better performance in terms of computational cost but also an easy implementation. Simulation results demonstrate the efficiency, robustness, and potential of the proposed algorithm.Keywords
This publication has 15 references indexed in Scilit:
- The art gallery theorem for polygons with holes2002
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- An efficient algorithm for guard placement in polygons with holesDiscrete & Computational Geometry, 1995
- Robot Motion Planning1991
- Computational complexity of art gallery problemsIEEE Transactions on Information Theory, 1986
- Worst-case Analysis of Set Union AlgorithmsJournal of the ACM, 1984
- Triangulating a simple polygonInformation Processing Letters, 1978
- Location of a Point in a Planar Subdivision and Its ApplicationsSIAM Journal on Computing, 1977
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- A note on two problems in connexion with graphsNumerische Mathematik, 1959