大規模並列化された遅延プランニング
MPLP: Massively Parallelized Lazy Planning
グラフ探索と辺評価を完全に非同期並列化した遅延探索アルゴリズムMPLPを提案し、3Dヒューマノイドナビゲーションとロボット組立のタスク・モーションプランニングで既存手法を上回る性能を示した。
著者: Shohin Mukherjee, Sandip Aine, Maxim Likhachev
分類: cs.RO
原文アブストラクト
Lazy search algorithms have been developed to efficiently solve planning problems in domains where the computational effort is dominated by the cost of edge evaluation. The existing algorithms operate by intelligently balancing computational effort between searching the graph and evaluating edges. However, they are designed to run as a single process and do not leverage the multithreading capability of modern processors. In this work, we propose a massively parallelized, bounded suboptimal, lazy search algorithm (MPLP) that harnesses modern multi-core processors. In MPLP, searching of the graph and edge evaluations are performed completely asynchronously in parallel, leading to a drastic improvement in planning time. 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 robotic assembly task. We show that MPLP outperforms the state-of-the-art lazy search as well as parallel search algorithms. The open-source code for MPLP is available here: https://github.com/shohinm/parallel_search
