A fast algorithm to plan a collision-free path in cluttered 2D environments

Abstract

Planning collision-free paths in 2D environments is not a new problem in the field of robotics. Methods to plan paths which are optimal in the sense of either length or safety tolerance were well reported decades ago. However, most, if not all, of these algorithms require extensive computational resources, i.e. long computing time, large amount of memory or complex data structures to calculate, especially in highly cluttered environments. This paper presented a simple but fast algorithm which provides a close to optimal path between any two points in highly cluttered 2D environments. It can find a path whenever one exists and can indicate when none exists. The cost of pre-processing is relatively light and the data structure is simple. Comparisons have been made against the conventional distance transform and we find that this new algorithm is twenty times faster in average.