MPLP: Massively Parallelized Lazy Planning
This work addresses the problem of slow planning times in robotics and AI domains by leveraging parallel processing, offering a significant speedup for researchers and practitioners in these fields.
The paper tackles the inefficiency of existing lazy search algorithms in planning problems by proposing MPLP, a massively parallelized algorithm that runs searching and edge evaluations asynchronously, resulting in a drastic improvement in planning time and outperforming state-of-the-art methods in domains like 3D humanoid navigation and robotic assembly.
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