JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]


Journal of Information Science and Engineering, Vol. 22 No. 6, pp. 1355-1366


Efficient and Complete Coverage of 2D Environments by Connectivity Graphs for Motion Planning Algorithms


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


Keywords: simple polygons with holes, connectivity graph, visibility graph, free path, collision avoidance, motion planning

  Retrieve PDF document (JISE_200606_04.pdf)