A comparative study between visibility-based roadmap path planning algorithms

摘要

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 (CS_free) and computational cost. Our proposed algorithm is robust and fast as it generally covers the whole CS_free, 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.