BugFlood: A bug inspired algorithm for efficient path planning in an obstacle rich environment

Abstract

Given a source location and a goal location, a robot needs to find a collision-free path in an obstacle rich environment. Determining a near-optimal collision-free path in realtime is a difficult problem. In this paper, we propose a novel fast path planning algorithm inspired from the classic bug algorithm. The path planner uses line-of-sight with respect to the goal as a mechanism to drive the bug towards the goal. When the bug detects an obstacle, it splits into two bugs exploring the obstacle in opposite directions with the aim of moving towards the goal. The process of moving towards the goal and splitting upon detection of an obstacle continues until all the bugs reach the goal. Thus forming a binary tree structure dynamically. To minimize the number of branches exploring the area, we also present some heuristics. The proposed algorithm performance in terms of time to determine the path and the length of the path for different obstacle densities is compared against standard path planning algorithms, namely, visibility graph, RRT and RRT*. The results show that the proposed algorithm outperforms all the algorithms in terms of computational time required while determining a path length similar to that of visibility graph which is the shortest path.