ABUG: A fast Bug-derivative anytime path planner with provable suboptimality bounds
2009
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
1
Citations
NaN
KQI