PBA*: Using Proactive Search to Make A* Robust to Unplanned Deviations

Paul Breimyer, Peter R. Wurman

Many path planning algorithms leverage A* to determine optimal paths. However, when an actor deviates from the optimal path, a typical application of A* executes a new search from the deviation point to the goal. This approach redundantly calculates paths that may have been examined during the initial search, rather than leveraging previous information. We introduce Plan-B A* (PBA*), which uses A* for the initial search, and substantially reduces the number of searched states during all subsequent searches, while incurring minimal space overhead. PBA* not only remembers certain states it has examined, it proactively creates solution paths for the most likely deviations. In our experiments, PBA* searches only 10% of the A* search space when recovering from execution errors by storing a limited amount of search history.

Subjects: 15.7 Search; 1.11 Planning

Submitted: Apr 15, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.