Lazy Lifelong Planning for Efficient Replanning in Graphs with Expensive Edge Evaluation

Jaein Lim, Siddhartha S Srinivasa, Panagiotis Tsiotras

TL;DR

Lifelong-GLS (L-GLS) is a new incremental search algorithm that solves the "expensive edge" problem in robot path replanning. By combining the vertex-reuse efficiency of Lifelong Planning A (LPA) with the lazy evaluation strategy of Generalized Lazy Search (GLS), it drastically reduces the number of costly collision checks needed to update a path when the environment changes.

What Problem Does This Paper Address?

In robotics, "replanning" is the art of updating a path when the world changes—like when a door closes or a person moves into a robot's way. Standard algorithms like LPA* are great at this because they reuse previous search results to fix only the "broken" parts of a path.

However, LPA has a major weakness: it assumes checking if an edge is traversable (e.g., a collision check) is cheap. In reality, for high-dimensional robots (like a 7-DOF arm), checking a single edge can involve complex geometry math that dominates the total computation time. LPA often evaluates many changed edges that aren't even relevant to the final path. Conversely, Lazy Search methods avoid these checks until necessary but usually start from scratch every time the graph changes, losing the benefits of previous work.

Methods

The authors introduce Lifelong-GLS (L-GLS), which bridges the gap between incremental and lazy search.

  1. Lazy LPA* Core: L-GLS maintains a search tree similar to LPA*, but instead of using actual edge costs for every changed edge, it uses "lazy" estimates (admissible heuristics).
  2. Two-Loop Structure:
    • Inner Loop: It runs a "lazy" version of the search to find the potential shortest path to the goal based on estimates. It then evaluates only the edges on that specific path. If an edge is blocked, it updates the tree and tries again.
  3. Outer Loop: It monitors the environment for external changes. When changes occur, it doesn't immediately validate them; it simply marks the affected edges as "unevaluated" and lets the inner loop decide if they are worth checking.
  4. Event-Based Toggles: Borrowing from the GLS framework, L-GLS uses "events" to decide when to stop repairing the tree and start evaluating edges. This allows the algorithm to behave like Lifelong-LazySP (checking the whole path) or Lifelong-LRA* (checking edges step-by-step), depending on the problem's needs.

Datasets

The algorithm was evaluated using the Open Motion Planning Library (OMPL) on three distinct benchmarks:

  • 2D Grid World: A simple visualization of path repair with moving obstacles.
  • 3D Piano Movers (Apartment Scenario): A complex 3D environment where a large object must be maneuvered through tight spaces with 8,000 vertices and over 34,000 edges.
  • 7D PR2 Manipulator: A high-dimensional robot arm task in a dynamic environment, utilizing a prebuilt graph of 30,000 vertices and nearly 169,000 edges.

Key Insights and Ideas

  • Relevance is King: The core "aha" moment is that you don't need to know the exact cost of a changed edge unless that edge is a candidate for the optimal path. L-GLS ignores "irrelevant" changes in the environment entirely.
  • Vertex vs. Edge Efficiency: There is a fundamental trade-off between expanding vertices (logic) and evaluating edges (physics/collision checks). L-GLS is the first to systematically minimize both by being both incremental and lazy.
  • Bounded Suboptimality: The authors prove that if you use "inflated" heuristics (to speed up the search) or truncate the tree repair early, L-GLS still provides a solution within a guaranteed factor of the optimal cost.

Key Results

The experiments showed that L-GLS outperforms both its "parents" (LPA* and GLS) in dynamic scenarios:

  • Massive Speedups: In the 3D Piano Movers task, L-GLS found a new path in 0.626 seconds, while standard LPA took 9.46 seconds and GLS took 38.8 seconds*.
  • Edge Evaluation Reduction: In the PR2 manipulator test, L-GLS evaluated only 7 to 52 edges to find a new path, whereas LPA was forced to evaluate between 10,000 and 49,000 edges*.
  • Consistency: Unlike GLS, which can vary wildly in time because it starts from scratch, L-GLS remains consistently fast across consecutive search episodes because it reuses the "consistent" parts of the previous search tree.

Limitations and Future Work

  • Heuristic Dependency: Like all A*-based methods, the performance of L-GLS relies heavily on having a "good" (admissible and consistent) heuristic. In very complex spaces where heuristics are weak, the "lazy" path might be frequently invalid, leading to many iterations.
  • Graph Representation: The current work assumes a discrete graph. Extending this to continuous, sampling-based planners (like RRT*) in a way that maintains the "lifelong" property is a logical next step.
  • Multi-Agent Scaling: While the paper mentions multi-agent coordination in the introduction, the specific experiments focus on single-agent replanning. Testing how L-GLS handles the rapid graph changes inherent in multi-robot systems remains an open area.

Summary updated

Abstract

We present an incremental search algorithm, called Lifelong-GLS, which combines the vertex efficiency of Lifelong Planning A* (LPA*) and the edge efficiency of Generalized Lazy Search (GLS) for efficient replanning on dynamic graphs where edge evaluation is expensive. We use a lazily evaluated LPA* to repair the cost-to-come inconsistencies of the relevant region of the current search tree based on the previous search results, and then we restrict the expensive edge evaluations only to the current shortest subpath as in the GLS framework. The proposed algorithm is complete and correct in finding the optimal solution in the current graph, if one exists. We also show that the search returns a bounded suboptimal solution, if an inflated heuristic edge weight is used and the tree repairing propagation is truncated early for faster search. Finally, we show the efficiency of the proposed algorithm compared to the standard LPA* and the GLS algorithms over consecutive search episodes in a dynamic environment. For each search, the proposed algorithm reduces the edge evaluations by a significant amount compared to the LPA*. Both the number of vertex expansions and the number of edge evaluations are reduced substantially compared to GLS, as the proposed algorithm utilizes previous search results to facilitate the new search.
BibTeX
@inproceedings{lim2022lazy,
  author = {Jaein Lim and Siddhartha S Srinivasa and Panagiotis Tsiotras},
  title = {{Lazy Lifelong Planning for Efficient Replanning in Graphs with Expensive Edge Evaluation}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2022},
  doi = {10.1109/iros47612.2022.9981389},
}
Figure