论文标题
EPA* SE：基于边缘的平行A*用于缓慢评估
ePA*SE: Edge-based Parallel A* for Slow Evaluations
论文作者
论文摘要
并行搜索算法利用现代处理器的多线程功能来实现更快的计划。一种这样的算法是Pa* se（用于缓慢扩展的平行a*），该算法与状态扩展并行，以在状态扩展缓慢的域中实现更快的计划。在这项工作中，我们提出了通过并行化边缘评估而不是状态扩展来改善PA*SE的EPA*SE（用于缓慢评估的边缘平行A*）。这使EPA*SE在边缘评估昂贵且需要不同数量的计算工作的领域中更有效，这在机器人技术中通常是这种情况。在理论方面，我们表明EPA*SE提供了严格的最佳保证。此外，EPA*se可以琐碎地扩展以处理启发式的通货膨胀率，从而导致有界的次优算法W-EPA*SE（加权EPA*SE），该算法将最佳交易以提供更快的计划。在实验方面，我们在两个不同的计划域中验证了所提出的算法：1）3D类人体导航的运动计划和2）双臂机器人组装任务的任务和运动计划。我们表明，EPA*SE可以比Pa*se和其他替代方案更有效。可在此处提供EPA*SE的开源代码以及基线：https：//github.com/shohinm/parallel_search
Parallel search algorithms harness the multithreading capability of modern processors to achieve faster planning. One such algorithm is PA*SE (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 ePA*SE (Edge-based Parallel A* for Slow Evaluations) that improves on PA*SE by parallelizing edge evaluations instead of state expansions. This makes ePA*SE 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 ePA*SE provides rigorous optimality guarantees. In addition, ePA*SE can be trivially extended to handle an inflation weight on the heuristic resulting in a bounded suboptimal algorithm w-ePA*SE (Weighted ePA*SE) 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 ePA*SE can be significantly more efficient than PA*SE and other alternatives. The open-source code for ePA*SE along with the baselines is available here: https://github.com/shohinm/parallel_search
