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

Paul Breimyer, Peter R. Wurman

Introduction

The A* algorithm is a cornerstone of pathfinding in static environments, widely utilized in robotics, gaming, and navigation systems. However, its fundamental assumption—that an agent will perfectly adhere to the calculated path—is often violated in real-world scenarios. Humans miss exits, robots encounter wheel slippage, and dynamic game environments can push characters off course.

When an agent deviates, standard implementations typically re-run A from the new location. This approach is computationally expensive as it ignores previously explored state space. While dynamic replanning algorithms like D exist, they are often designed for changing environments and carry significant memory overhead. PBA (Plan-B A) addresses this by proactively preparing for deviations in static maps.

Methodology: The Three Phases of PBA*

PBA* enhances the efficiency of recovery by caching a small subset of search history and pre-calculating alternative routes.

Conceptual overview of PBA* showing primary path I and backup paths R and B from deviation points x and y.

The algorithm operates in three distinct phases:

  1. Planning Phase: A standard A* search identifies the optimal path ($I$). All nodes on this path are stored in a KNOWN hash table along with their exact cost-to-goal.
  2. Proactive Phase: PBA* identifies high-probability deviation points along the primary path. It proactively searches for optimal paths from these points to the goal, adding these "Plan B" nodes to the KNOWN table.
  3. Reactive Phase: If a deviation occurs, PBA initiates a new search. Crucially, this search terminates as soon as it intersects any* node in the KNOWN table. Since the table stores true distances to the goal, the algorithm can immediately "stitch" the new path to a pre-calculated one, ensuring optimality without reaching the goal node again.

Experimental Evaluation

The researchers evaluated PBA* using 4-connected square grid worlds with dimensions ranging from 10x10 to 310x310. Edge costs were randomized between 1 and 200. To simulate real-world unpredictability, the algorithm was tested against various deviation models, including Uniform, Normal, and Exponential distributions.

Key Results and Efficiency

The primary advantage of PBA is its dramatic reduction in computational effort during recovery. Experimental data shows that PBA requires searching only a fraction of the state space compared to a full A* restart.

Percentage of state space searched by PBA* compared to standard A* across various grid dimensions.

Key findings include:

  • Search Reduction: PBA searched only 10.1% of the state space required by standard A to recover from deviations.
  • Minimal Overhead: The memory footprint for the KNOWN table was only 0.5% higher than standard A*.
  • Rapid Reconnection: On average, agents reconnected to a known path after traversing just 3% of the total path length.
  • Proactive Cost: The initial proactive planning phase added less than 20% to search time, which is often negligible if run as a background process while the agent begins movement.

Conclusion

PBA* provides a lightweight, human-centric approach to robust pathfinding. By formalizing the intuition of "backup plans," it offers massive efficiency gains for agents operating in static environments where movement is imperfect. Future work may involve integrating real-world GPS data to refine deviation probability models and extending the logic to semi-dynamic environments.

Summary updated

Abstract

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.
BibTeX
@inproceedings{breimyer2008pba,
  author = {Paul Breimyer and Peter R. Wurman},
  title = {{PBA*: Using Proactive Search to Make A* Robust to Unplanned Deviations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure