A-ePA*SE: 評価に時間がかかる問題のためのいつでも使える並列A*探索
A-ePA*SE: Anytime Edge-Based Parallel A* for Slow Evaluations
辺の評価コストが高い計画問題向けに、並列探索ePA*SEへいつでも解を改善できる性質を加えたA-ePA*SEを提案し、既存のいつでも探索法より効率的であることを示した。
著者: Hanlan Yang, Shohin Mukherjee, Maxim Likhachev
分類: cs.AI, cs.RO
原文アブストラクト
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
