Time-bounded lattice for efficient planning in dynamic environments

Aleksandr Kushleyev, Maxim LikhachevICRA 2009 · DOI

TL;DR

This paper introduces a "time-bounded lattice" approach for robot path planning in environments with dynamic obstacles. It efficiently merges short-term, time-aware planning with long-term, time-agnostic planning, adapting the planning horizon based on obstacle uncertainty to achieve real-time performance and robust collision avoidance.

What Problem Does This Paper Address?

Navigating in environments with moving objects (like other robots, pedestrians, or cars) is a significant challenge for autonomous systems. Traditional methods often treat dynamic obstacles as static, leading to inefficient or even impossible paths. While some approaches plan for time-dependent trajectories, these can be computationally expensive, especially when dealing with uncertainty in obstacle movements. This paper tackles the problem of planning dynamically-feasible paths in real-time, even with numerous, uncertain, and moving obstacles, aiming for near-optimal solutions rather than just feasible ones.

Methods

The core contribution is the time-bounded lattice data structure. This approach combines two planning paradigms:

  • Six-Dimensional (6D) Time-Parameterized Planning: This handles the dynamic nature of the environment and the robot's own dynamics (position, orientation, velocity, angular velocity, and time). It's used for short-term planning.
  • Two-Dimensional (2D) Kinematic Planning: This is a faster, time-agnostic planning method used for longer-term navigation.

The key innovation is how these are merged:

  1. Dynamic Obstacle Representation: Obstacles are modeled as a set of predicted time-parameterized trajectories, each with an associated uncertainty (represented by Gaussian distributions). This allows for handling noisy sensor data and multiple possible future paths for each obstacle.
  2. Time-Bounding: The algorithm determines a "bounding time" ($T_{bound}$) for each dynamic obstacle. Beyond this time, the obstacle's uncertainty is so high that it's effectively ignored for planning purposes. This $T_{bound}$ is dynamically calculated based on the obstacle's predicted trajectory and its uncertainty.
  3. Time-Bounded Lattice Construction: A graph is built where states are either 6D (for time-aware planning up to $T_{bound}$) or 2D (for time-agnostic planning beyond $T_{bound}$). Transitions between states are short motion primitives.
  4. Weighted A* Search: A modified A* search algorithm is used to find the optimal path within this time-bounded lattice, with a restriction to ensure efficient expansion.

This adaptive approach allows the planner to focus computational effort on the immediate, uncertain future while relying on faster, less precise planning for the distant future.

Datasets

Not discussed in the paper. The experiments were conducted in simulation (using Gazebo and Player) and on real robots.

Key Insights and Ideas

  • Uncertainty is Key: The paper emphasizes that accurately modeling and leveraging uncertainty in obstacle predictions is crucial for robust and efficient planning. High uncertainty allows the planner to "ignore" obstacles beyond a certain time horizon.
  • Bridging Time-Aware and Time-Agnostic Planning: The time-bounded lattice elegantly combines the strengths of both approaches, providing a principled way to manage the computational complexity of dynamic environments.
  • Real-Time Performance through Bounding: By dynamically limiting the time horizon for explicit time-parameterized planning, the system achieves real-time replanning capabilities, essential for dynamic environments.
  • Adaptability: The graph structure automatically adapts. If there are no dynamic obstacles or they are far away, it effectively reduces to a standard 2D grid search.

Key Results

  • Efficiency: The time-bounded lattice approach significantly outperforms full 6D time-parameterized planning in terms of speed. In one experiment, the time-bounded lattice achieved an average planning time of 34 msecs, compared to 230 msecs for full 6D planning.
  • Robustness: The planner successfully navigated environments with up to 30 dynamic obstacles in simulation and demonstrated effective collision avoidance on real robots.
  • Goal Achievement: The time-bounded lattice approach led to more goals achieved (69 vs. 25) in a long-duration experiment compared to full 6D planning, likely due to its faster replanning times preventing the robot from getting stuck or missing opportunities.
  • Collision Avoidance: The system showed good performance in avoiding collisions, with only 12 collisions in an experiment where some obstacles were not programmed to avoid collisions themselves.

Limitations and Future Work

  • Stationary Dynamic Obstacles: The paper acknowledges that the current approach might struggle with "stationary dynamic obstacles" (obstacles that are dynamic but don't move, potentially causing deadlocks). Future work aims to find a principled way to resolve these, possibly by declaring them as static at a higher level.
  • Incremental Planning: The authors intend to extend the approach to incremental planning, which would further speed up replanning in response to map updates.
  • Obstacle Model Improvement: The current obstacle model doesn't fully account for the influence of static obstacles on dynamic obstacle trajectories. Future work will refine this by adjusting uncertainty distributions based on the static environment.
  • TMAX Parameter: The choice of the hard threshold $T_{MAX}$ is critical. It needs to be large enough for the robot to react but small enough to maintain real-time performance. The paper notes that if $T_{MAX}$ is too small, the robot might fail to avoid collisions due to its dynamic constraints.

Summary updated

BibTeX
@inproceedings{kushleyev2009time,
  author = {Aleksandr Kushleyev and Maxim Likhachev},
  title = {{Time-bounded lattice for efficient planning in dynamic environments}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2009},
  doi = {10.1109/robot.2009.5152860},
}
Figure