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.
Introduction
In robotics, the Motion Planning Problem with Dynamic Obstacles (MPDO) is notoriously difficult—specifically, it is NP-Hard. While many algorithms (like SIPP or RRT) can find a feasible path to avoid moving obstacles, it is often impossible to know how close that path is to the theoretical optimum. To determine the quality of a solution, one needs the optimal cost ($C^*$), which is computationally impractical to find for arbitrary moving obstacles.
This research addresses this gap by developing a framework that calculates a lower bound—a theoretical floor for the arrival time. By establishing this proxy for the optimum, researchers can calculate an "optimality gap," providing a quantifiable measure of a planner's performance.
Methodology
Bi-Level Discretization
The proposed framework utilizes a two-part discretization strategy to transform the continuous 2D workspace into a searchable graph.
- Higher Level: The workspace is divided into a grid of cells of size $w$.
- Lower Level: The boundaries of these cells are further divided into $k$ smaller sub-segments.
- Graph Construction: 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 defined as the minimum possible travel time between those segments at the robot's maximum speed.
Relaxed Constraints and LB-A*
To ensure the resulting path cost is a true lower bound (an underestimate), the framework introduces two key relaxations:
- Relaxation-1: Collisions are only checked at the cell boundaries (vertices), ignoring potential collisions while the robot traverses the interior of a cell.
- 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.
The LB-A* Algorithm is a modified version of A* designed to handle "reachable time intervals"—specific windows of time when a vertex is not occupied by an obstacle. 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 valid window.
Results and Discussion
Numerical results corroborate the performance of the proposed framework across several synthetic experimental setups, including complex environments with multiple moving obstacles.
- 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, LB-A* provided significantly tighter bounds than baseline approaches that simply ignore dynamic obstacles. In one instance, the framework proved a feasible solution was within 8.1% of the optimum, whereas a baseline suggested it was 16.5% away—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.
Conclusion
This framework provides a robust method for evaluating motion planners in dynamic environments. While high-resolution discretization requires significant computational resources, the ability to calculate tight lower bounds offers a critical benchmark for robotic path optimality. Future work may involve developing more informative heuristics to speed up the LB-A* search and extending the model to accommodate non-Euclidean movement constraints and complex robot shapes.
Summary updated