A Lower Bounding Framework for Motion Planning Amid Dynamic Obstacles in 2D

Zhongqiang Ren, Sivakumar Rathinam, Howie Choset

TL;DR

This paper introduces a novel framework to calculate tight lower bounds for the minimum arrival time in motion planning problems involving dynamic obstacles. By using a bi-level discretization approach and a specialized A algorithm (LB-A), the researchers provide a way to measure exactly how close a "feasible" robot path is to the theoretical optimum, even when the optimum itself is unknown.

What Problem Does This Paper Address?

In robotics, the Motion Planning Problem with Dynamic Obstacles (MPDO) is notoriously difficult—specifically, it is NP-Hard. While we have many algorithms (like SIPP or RRT) that can find a feasible path to avoid moving obstacles, we rarely know how "good" that path actually is. Is it 5% slower than the perfect path, or 50%?

To answer this, you need to know the optimal cost ($C^*$). However, finding $C^*$ for arbitrary moving obstacles is computationally impractical. The authors address this gap by developing a framework that calculates a lower bound—a "theoretical floor" for the arrival time. If your planner finds a path that takes 40 seconds, and this framework says the absolute best possible time is 38 seconds, you know your solution is nearly optimal.

Methods

The authors propose a two-part framework:

  1. Bi-Level Discretization:
    • Higher Level: The 2D workspace is divided into a grid of cells (size $w$).
  2. Lower Level: The boundaries of these cells are further divided into $k$ smaller sub-segments.
  3. The Graph: Each sub-segment becomes a node in a graph. Edges are created between sub-segments on different boundaries of the same cell. The cost of an edge is the minimum possible travel time between those segments at maximum robot speed.
  4. Relaxed Constraints: To ensure the result is a true lower bound (an underestimate), the authors introduce two key relaxations:
  5. Relaxation-1: Collisions are only checked at the cell boundaries (vertices), ignoring potential collisions while the robot is traversing the interior of a cell.
  6. Relaxation-2: If a robot reaches a vertex while it is free, it is allowed to "wait" there indefinitely, even if an obstacle moves over that spot later (treating the vertex as a safe harbor).
  7. LB-A* Algorithm: A modified version of the A* search algorithm designed to handle "reachable time intervals"—specific windows of time when a vertex is not occupied by an obstacle.

Datasets

The paper does not use standard public datasets, as is common in theoretical motion planning research. Instead, the authors evaluated their framework using three synthetic experimental setups:

  • Experiment 1: A simple environment with two static bar-like obstacles to verify convergence.
  • Experiment 2: A single circular obstacle moving across the robot's path.
  • Experiment 3: A complex environment with two static bars and ten circular obstacles moving on random trajectories.

Key Insights and Ideas

  • The Proxy for Optimum: Since $C^*$ is unknown, the lower bound acts as a proxy. This allows researchers to calculate an "optimality gap" (e.g., "this path is at most 8% away from the optimum").
  • Resolution Matters: The tightness of the lower bound is directly controlled by the hyper-parameters $w$ (cell size) and $k$ (number of sub-segments). Increasing $k$ makes the bound tighter but increases the computational cost.
  • Wait Actions as Self-Loops: The algorithm treats waiting at a vertex as a special "self-loop" edge, allowing the robot to stay in place to let an obstacle pass, provided the arrival time falls within a "reachable" window.
  • The Duplication Trick: To handle the edge case where a robot passes through a corner shared by four cells, the authors use a "duplication" method to ensure the graph remains connected and the lower bound remains valid.

Key Results

  • Convergence: In static environments where the true optimum is known, the framework's lower bound converged toward the optimal cost as the number of sub-segments ($k$) increased.
  • Tighter Bounds: In dynamic scenarios, the proposed LB-A* provided significantly tighter bounds than the "baseline" (which simply ignores dynamic obstacles).
  • Quantifiable Quality: In one experiment with a moving obstacle, the baseline suggested a feasible solution was 16.5% away from the optimum. The authors' framework proved it was actually within 8.1% of the optimum—effectively halving the uncertainty about the solution's quality.
  • Complexity: The number of vertices in the graph scales as $O(kn^2)$, representing a manageable trade-off between search efficiency and bound tightness.

Limitations and Future Work

  • Computational Burden: High-resolution discretization (large $n$ and $k$) requires significant memory and search time. The authors note a clear trade-off between how "tight" the bound is and how long it takes to calculate.
  • Heuristic Design: Currently, the algorithm uses a simple zero-heuristic (Dijkstra-like), which is admissible but slow. Developing more "informative" heuristics could speed up the search.
  • Simple Robot Models: The work assumes a point robot with a maximum speed. Future work could extend this to robots with complex shapes or non-Euclidean movement constraints (like cars that can't turn in place).
  • Discretization Strategy: The current grid is uniform. The authors suggest that non-uniform or adaptive discretization (focusing resolution near obstacles) could improve performance.

Summary updated

Abstract

This work considers a Motion Planning Problem with Dynamic Obstacles (MPDO) in 2D that requires finding a minimum-arrival-time collision-free trajectory for a point robot between its start and goal locations amid dynamic obstacles moving along known trajectories. Existing methods, such as continuous Dijkstra paradigm, can find an optimal solution by restricting the shape of the obstacles or the motion of the robot, while this work makes no such assumptions. Other methods, such as search-based planners and sampling-based approaches can compute a feasible solution to this problem but do not provide approximation bounds. Since finding the optimum is challenging for MPDO, this paper develops a framework that can provide tight lower bounds to the optimum. These bounds act as proxies for the optimum which can then be used to bound the deviation of a feasible solution from the optimum. To accomplish this, we develop a framework that consists of (i) a bi-level discretization approach that converts the MPDO to a relaxed path planning problem, and (ii) an algorithm that can solve the relaxed problem to obtain lower bounds. We also present numerical results to corroborate the performance of the proposed framework. These results show that the bounds obtained by our approach for some instances are up to twice tighter than a baseline approach showcasing potential advantages of the proposed approach.
BibTeX
@inproceedings{ren2022lower,
  author = {Zhongqiang Ren and Sivakumar Rathinam and Howie Choset},
  title = {{A Lower Bounding Framework for Motion Planning Amid Dynamic Obstacles in 2D}},
  booktitle = {WAFR},
  year = {2022},
  url = {https://openreview.net/forum?id=w4GPyKO8oAg},
}

Loading related content...

Figure