# GePA*SE: Generalized Edge-Based Parallel A* for Slow Evaluations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 24 Jan 2023.

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

- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [Search-Based Task Planning with Learned Skill Effect Models for Lifelong Robotic Manipulation](https://mlsanity.com/paper/2109.08771/) (2021)
- [Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles](https://mlsanity.com/paper/1904.02795/) (2019)
- [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)

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

- [A-ePA*SE: Anytime Edge-Based Parallel A* for Slow Evaluations](https://mlsanity.com/paper/2305.04408/) (2023)
- [Parallel Heuristic Search as Inference for Actor-Critic Reinforcement Learning Models](https://mlsanity.com/paper/2509.25402/) (2025)

## Abstract (arXiv)

Parallel search algorithms have been shown to improve planning speed by harnessing the multithreading capability of modern processors. One such algorithm PA*SE achieves this by parallelizing state expansions, whereas another algorithm ePA*SE achieves this by effectively parallelizing edge evaluations. ePA*SE targets domains in which the action space comprises actions with expensive but similar evaluation times. However, in a number of robotics domains, the action space is heterogenous in the computational effort required to evaluate the cost of an action and its outcome. Motivated by this, we introduce GePA*SE: Generalized Edge-based Parallel A* for Slow Evaluations, which generalizes the key ideas of PA*SE and ePA*SE i.e. parallelization of state expansions and edge evaluations respectively. This extends its applicability to domains that have actions requiring varying computational effort to evaluate them. The open-source code for GePA*SE along with the baselines is available here: https://github.com/shohinm/parallel_search