Title :
A comparative study between visibility-based roadmap path planning algorithms
Author :
Lulu, Leena ; Elnagar, Ashraf
Author_Institution :
Dept. of Comput. Sci., Sharjah Univ., United Arab Emirates
Abstract :
The aim of this paper is to evaluate the performance of our proposed art gallery-based roadmap algorithm against well-known and frequently cited visibility-based motion planning algorithms: the visibility graph and the visibility-based probabilistic roadmap. The comparison involves several criteria among which are: the cardinality of the graph, the completeness of the algorithm, coverage and connectivity of the free configuration space (CSfree) and computational cost. Our proposed algorithm is robust and fast as it generally covers the whole CSfree, based on the well-known art gallery theorem. It efficiently seeks to construct a roadmap that contains the smallest possible number of nodes (called guards) as opposed to generating a large number of nodes when compared to other motion planning approaches. The simulation results demonstrate that our proposed algorithm outperforms both algorithms and proves to not only combine the attractive features of both algorithms but also eliminate the drawbacks of each one.
Keywords :
graph theory; motion control; path planning; probability; art gallery theorem; art gallery-based roadmap algorithm; graph cardinality; robot motion planning; visibility graph; visibility-based motion planning; visibility-based probabilistic roadmap; visibility-based roadmap path planning; Art; Computational efficiency; Computer science; Joining processes; Motion control; Motion planning; Orbital robotics; Path planning; Robot motion; Robustness; Performance evaluation; art gallery-based roadmap; robot motion planning; visibility graph; visibility-based probabilistic roadmap;
Conference_Titel :
Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on
Print_ISBN :
0-7803-8912-3
DOI :
10.1109/IROS.2005.1545545