ABUG: A fast Bug-derivative anytime path planner with provable suboptimality bounds

In recent years, anytime algorithms have shown to be a good solution for planning a path in domains with severe restrictions regarding the time for deliberation. They typically operate by quickly finding a highly suboptimal path first, and then improving it until the available time runs out. In this paper, we propose a novel anytime approach called ABUG that performs much more efficiently than the competing strategies. ABUG is based on an improved version of a member of the popular family of algorithms known as Bug. A formal analysis of the planner is provided and several relevant properties of ABUG are identified. Besides, as done in some heuristic-based anytime approaches, we define bounds on the quality / length of the paths returned by the algorithm. Finally, in order to demonstrate the computational savings associated with the proposal, a comparative study involving a set of well-known path-planning techniques is also carried out.