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

arXiv: https://arxiv.org/abs/2305.04408 · HTML: https://mlsanity.com/paper/2305.04408/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 8 May 2023.

## Builds on (most cited first, 8 of 8)

- [Search-Based Task Planning with Learned Skill Effect Models for Lifelong Robotic Manipulation](https://mlsanity.com/paper/2109.08771/) (2021)
- [A Planning Framework for Persistent, Multi-UAV Coverage with Global Deconfliction](https://mlsanity.com/paper/1908.09236/) (2019)
- [Reactive Long Horizon Task Execution via Visual Skill and Precondition Models](https://mlsanity.com/paper/2011.08694/) (2020)
- [ePA*SE: Edge-based Parallel A* for Slow Evaluations](https://mlsanity.com/paper/2203.01369/) (2022)
- [MPLP: Massively Parallelized Lazy Planning](https://mlsanity.com/paper/2107.02826/) (2021)
- [AMRA*: Anytime Multi-Resolution Multi-Heuristic A*](https://mlsanity.com/paper/2110.05328/) (2021)
- [GePA*SE: Generalized Edge-Based Parallel A* for Slow Evaluations](https://mlsanity.com/paper/2301.10347/) (2023)
- [Best-First Heuristic Search for Multicore Machines](https://mlsanity.com/paper/1401.3861/) (2014)

## Built on by (most cited first, 1 of 1)

- [Parallel Heuristic Search as Inference for Actor-Critic Reinforcement Learning Models](https://mlsanity.com/paper/2509.25402/) (2025)

## Abstract (arXiv)

Anytime search algorithms are useful for planning problems where a solution is desired under a limited time budget. Anytime algorithms first aim to provide a feasible solution quickly and then attempt to improve it until the time budget expires. On the other hand, parallel search algorithms utilize the multithreading capability of modern processors to speed up the search. One such algorithm, ePA*SE (Edge-Based Parallel A* for Slow Evaluations), parallelizes edge evaluations to achieve faster planning and is especially useful in domains with expensive-to-compute edges. In this work, we propose an extension that brings the anytime property to ePA*SE, resulting in A-ePA*SE. We evaluate A-ePA*SE experimentally and show that it is significantly more efficient than other anytime search methods. The open-source code for A-ePA*SE, along with the baselines, is available here: https://github.com/shohinm/parallel_search