A-ePA*SE: Anytime Edge-Based Parallel A* for Slow Evaluations

Hanlan Yang, Shohin Mukherjee, Maxim LikhachevSocs 2023 · DOI

TL;DR

This paper introduces A-ePASE, an anytime extension to the parallel search algorithm ePASE, designed for planning problems with computationally expensive edge evaluations. By combining anytime search principles with parallel edge expansion, A-ePA*SE efficiently finds feasible solutions quickly and then iteratively improves them within a given time budget, outperforming existing anytime search methods.

What Problem Does This Paper Address?

Robotics planning often involves finding the shortest path on a graph representing states and actions. In many real-world scenarios, evaluating the cost or feasibility of an action (an edge in the graph) can be very time-consuming. While parallel search algorithms like ePASE can speed up planning by evaluating edges concurrently, they typically aim for an optimal solution without strict time constraints. However, for real-time applications, it's crucial to have a good solution available within a limited time, even if it's not perfectly optimal. Anytime algorithms address this by providing a feasible solution quickly and then refining it over time. This paper bridges this gap by making ePASE an "anytime" algorithm, allowing it to provide progressively better solutions as time allows, which is essential for dynamic robotic systems.

Methods

The core contribution is the development of A-ePASE, which builds upon the existing ePASE algorithm. ePASE's key innovation is shifting the unit of search from state expansions to edge expansions, enabling asynchronous parallelization of edge evaluations. A-ePASE integrates the "anytime" property by:

  • Iterative Refinement with Decreasing Sub-optimality: Similar to Anytime Repairing A (ARA), A-ePA*SE uses a heuristic inflation factor (w) that is gradually decreased over successive search iterations. This allows the algorithm to start with a relaxed optimality criterion for faster initial solutions and progressively tighten it to approach optimality.
  • Reusing Search Effort: A crucial aspect is how A-ePA*SE reuses previous search efforts. Instead of restarting from scratch with a reduced w, it intelligently re-initializes its search queue (OPEN) by incorporating states that were found to be "inconsistent" (their costs might have been updated) in the previous iteration. This avoids redundant computations.
  • Modified Termination Condition: The search within each iteration is modified to prioritize expanding states whose costs can still be improved or that were marked as inconsistent in prior iterations. This ensures that the algorithm focuses its efforts on promising areas of the search space.

Datasets

The paper evaluates A-ePA*SE on 5 scaled MovingAI 2D maps. These maps represent grid-based environments with a specific agent footprint and action space (moving in 8 directions). The experiments were conducted using two types of cost maps: Euclidean cost and Euclidean cost multiplied by a random factor (between 1 and 100) to introduce varying degrees of gradual improvement.

Key Insights and Ideas

  • Parallelism and Anytime Properties are Synergistic: The paper demonstrates that combining parallel edge evaluation with anytime search strategies can lead to significant performance gains, especially in domains with slow edge evaluations.
  • Intelligent Reuse of Search Effort is Key: The ability to reuse previous search computations by incorporating inconsistent states into subsequent iterations is fundamental to A-ePA*SE's efficiency, distinguishing it from naive sequential execution of anytime algorithms.
  • Anytime Behavior is Crucial for Real-Time Robotics: The experimental results highlight that while ePASE might find optimal solutions faster in a single run, A-ePASE's anytime nature makes it more practical for real-time scenarios where a good solution is needed quickly, and continuous improvement is valuable.
  • Random Cost Maps Reveal Deeper Performance Differences: The random cost maps showed that A-ePASE could discover the optimal solution in hindsight faster than ePASE, suggesting that even if the time budget expires before full optimality, the robot might still execute a near-optimal plan.

Key Results

  • Significant Speedup over ARA*: A-ePASE consistently outperforms ARA in planning time, both for finding initial feasible solutions and for proving optimality.
  • Competitive Initial Solution Quality: A-ePASE and its naive counterpart (A-ePASE-naive) find initial solutions with an optimality ratio of around 0.95, indicating that most of the cost improvement happens in this high-optimality range.
  • Faster Improvement than Naive Anytime: A-ePASE improves the optimality ratio quicker than A-ePASE-naive, especially in the higher optimality ranges, due to its efficient reuse of search effort.
  • Practical Advantage over ePA*SE: While ePASE might be faster for finding a single optimal solution, A-ePASE provides the critical anytime capability, making it more suitable for real-time robotics. In random cost maps, A-ePASE was observed to discover the optimal solution in hindsight faster than ePASE.

Limitations and Future Work

  • Parameter Tuning: The current formulation of A-ePA*SE requires tuning of parameters like the initial heuristic inflation (wo) and the decrement step (Aw).
  • Future Work: The authors suggest extending A-ePA*SE to a non-parametric formulation, which would eliminate the need for manual parameter tuning.

Summary updated

BibTeX
@inproceedings{yang2023epa,
  author = {Hanlan Yang and Shohin Mukherjee and Maxim Likhachev},
  title = {{A-ePA*SE: Anytime Edge-Based Parallel A* for Slow Evaluations}},
  booktitle = {Socs},
  year = {2023},
  doi = {10.1609/socs.v16i1.27297},
}
Figure