A virtual bug planning technique for 2D robot path planning

Abstract

We present a path planning technique inspired by the bug algorithm to quickly compute paths in an obstacle rich environment (or to report that no such path exists). In our approach, we simulate virtual bugs that upon sensing an obstacle splits into two bugs exploring the obstacle boundary in opposite directions, until the bugs find the goal in the line-of-sight. Then the bug leaves the obstacle and proceeds towards the goal. The process of splitting a bug into two continues until all the bugs reach the goal. The algorithm is simple to implement and it rapidly finds a solution if one exists. We provide worst case bounds on the path length with provable guarantees on convergence and develop heuristics to minimize the number of active bugs in the environment. We compare the performance of our algorithm with different planners from Open Motion Planning Library (OMPL) and visibility graph methods. The results show that the proposed algorithm delivers lower cost paths compared to other planners with lower computational time and rapidly indicates if a path does not exist.