| Previous | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
¡@
Leena Lulu and Ashraf Elnagar+
Intelligent Systems and Infrastructure Group
Department of Computer Science
University of Sharjah
P O Box 27272, Sharjah, UAE
+E-mail: ashraf@ieee.org
In this paper, we use an efficient art gallery-based algorithm for placing a small
number of guards to inspect a 2D environment. The gallery models a 2D workspace for
an autonomous robot. The proposed algorithm efficiently computes a near-optimal
(small) number of guards in O(n log n) time and requires a linear storage complexity. An
additional set of connection nodes are 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 along 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 ease of implementation.
Received July 8, 2004; revised October 20, 2004; accepted January 13, 2005.
Communicated by Chin-Teng Lin.
* A preliminary version ¡§Guarding polygons with holes for robot motion planning applications,¡¨ has been
appeared in Proceedings of the International IEEE Conference on Systems, Man and Cybernetics, 2004, pp. 923-928.