ePA*SE: Edge-based Parallel A* for Slow Evaluations

Parallel search algorithms harness the multithreading capability of modern processors to achieve faster planning. One such algorithm is PASE (Parallel A for Slow Expansions), which parallelizes state expansions to achieve faster planning in domains where state expansions are slow. In this work, we propose ePASE (Edge-based Parallel A for Slow Evaluations) that improves on PASE by parallelizing edge evaluations instead of state expansions. This makes ePASE more efficient in domains where edge evaluations are expensive and need varying amounts of computational effort, which is often the case in robotics. On the theoretical front, we show that ePASE provides rigorous optimality guarantees. In addition, ePASE can be trivially extended to handle an inflation weight on the heuristic resulting in a bounded suboptimal algorithm w-ePASE (Weighted ePASE) that trades off optimality for faster planning. On the experimental front, we validate the proposed algorithm in two different planning domains: 1) motion planning for 3D humanoid navigation and 2) task and motion planning for a dual-arm robotic assembly task. We show that ePASE can be significantly more efficient than PASE and other alternatives. The open-source code for ePA*SE along with the baselines is available here: https://github.com/shohinm/parallel_search