MPLP: Massively Parallelized Lazy Planning

Shohin Mukherjee, Sandip Aine, Maxim LikhachevIEEE RA-L 2022 · DOI

TL;DR

This paper introduces MPLP, a novel massively parallelized lazy planning algorithm that achieves significant speedups by asynchronously executing graph search and expensive edge evaluations across multiple CPU cores. By decoupling these operations, MPLP dramatically improves planning efficiency in domains where edge evaluation is the bottleneck, outperforming existing lazy and parallel search methods.

What Problem Does This Paper Address?

Robotics planning problems, especially those involving motion planning, often translate to finding the shortest path on a graph representing the state space. A critical bottleneck in these problems is the evaluation of edges, which can involve computationally intensive tasks like collision checking. Traditional lazy search algorithms address this by deferring edge evaluations, but they are typically designed for single-threaded execution and cannot leverage the power of modern multi-core processors. Existing parallel search methods also struggle with efficiently handling the asynchronous nature of expensive edge evaluations. This paper aims to bridge this gap by developing a planning algorithm that can effectively utilize multi-core CPUs for both graph traversal and edge evaluation simultaneously.

Methods

The core innovation of MPLP (Massively Parallelized Lazy Planning) lies in its asynchronous, parallel execution of search and edge evaluation. Instead of a single thread toggling between these tasks, MPLP dedicates separate threads:

  • Optimistic Search (Thread T0): This thread performs a weighted A* search using optimistic (underestimated) costs for unevaluated edges and true costs for evaluated ones. When new edges are discovered, they are added to a priority queue for evaluation.
  • Edge Evaluation (Threads T3-TNt): A pool of threads is responsible for evaluating edges from the priority queue. These threads work in parallel, fetching edges, computing their true costs, and updating the graph.
  • Path Monitoring (Thread T1): This thread monitors paths found by the optimistic search. It checks if a path is fully evaluated and meets a suboptimality bound before declaring it a solution.

This asynchronous approach allows the search to proceed without waiting for edge evaluations, and edge evaluations to happen concurrently with the search. MPLP also incorporates a priority inflation mechanism for edges on discovered paths, further prioritizing their evaluation.

Datasets

Not discussed in the paper. The paper focuses on evaluating MPLP on two distinct planning domains:

  • 3D Navigation: Motion planning for a PR2 robot in an indoor environment.
  • Assembly Task: Task and motion planning for a PR2 robot to assemble blocks.

Key Insights and Ideas

  • Asynchronous Parallelism is Key: The most significant insight is that decoupling search and edge evaluation into asynchronous parallel processes, rather than trying to balance them within a single thread, unlocks substantial performance gains on multi-core processors.
  • Edge Evaluation as a Bottleneck: The paper strongly emphasizes that in many robotics domains, the cost of edge evaluation (e.g., collision checking) far outweighs the cost of graph traversal, making it the primary target for optimization.
  • Leveraging CPU Parallelism: MPLP effectively utilizes the MIMD (multiple-instruction, multiple-data) capabilities of CPUs, allowing for the parallel evaluation of potentially dissimilar edges, unlike SIMD-based GPU approaches.
  • Priority Inflation for Path Edges: Dynamically increasing the evaluation priority of edges that lie on discovered paths helps MPLP converge to a solution faster by focusing computational resources on promising routes.

Key Results

MPLP demonstrated significant performance improvements across various scenarios:

  • Navigation Domain:
    • MPLP-90 (using 90 threads) achieved substantial speedups over weighted A and lazy search baselines (LwA, LSP), especially as the collision checking interval (dcc) decreased (making edge evaluation more expensive). For instance, with dcc = 0.5cm and w=50, MPLP-90 was up to 16x faster than LSP.
  • Compared to parallel search baselines (PwA, PASE), MPLP also showed superior speedups, particularly when edge evaluation costs were high.
  • Assembly Task Domain:
    • MPLP-40 achieved a 5.9x speedup over wA* and a 1.6x speedup over LSP.
  • General Observation: The performance gains of MPLP were more pronounced in domains with higher edge evaluation costs.

Limitations and Future Work

  • Limitations:
    • MPLP's effectiveness is tied to domains where edge evaluation is expensive. In scenarios with inexpensive edges, its advantage diminishes.
  • The current priority inflation strategy is described as "naive," suggesting room for improvement.
  • The paper notes that for the assembly task, increasing threads beyond 40 did not yield further performance improvements, indicating potential saturation points.
  • Future Work:
    • Developing more intelligent strategies for edge priority assignment, potentially incorporating domain-specific "edge-existence priors."
    • Exploring adaptive strategies for search, potentially switching between incremental methods (like LPA*) and scratch-based searches based on the number of updated edges.
  • Investigating the integration of GPU acceleration for edge evaluation while maintaining the CPU-based parallel search architecture.

Summary updated

BibTeX
@article{mukherjee2022mplp,
  author = {Shohin Mukherjee and Sandip Aine and Maxim Likhachev},
  title = {{MPLP: Massively Parallelized Lazy Planning}},
  journal = {IEEE RA-L},
  year = {2022},
  doi = {10.1109/lra.2022.3157544},
}
Figure