RRT Guided Model Predictive Path Integral Method

Chuyuan Tao, Hunmin Kim, Naira HovakimyanarXiv 2023 · DOI · arXiv

Introduction

Motion planning remains a cornerstone challenge in robotics, typically bifurcated into two distinct methodologies: global planners and local optimal controllers. Global planners, such as Rapid-exploring Random Trees (RRT), are adept at navigating complex geometries but often yield non-optimal, jerky trajectories. Conversely, local controllers like Model Predictive Path Integral (MPPI) generate smooth, optimal controls through extensive sampling but are highly sensitive to initial conditions. If the "mean" control input is poorly initialized, MPPI may fail to explore viable regions of the state space without an impractical number of samples.

This paper introduces RRT-MPPI, a hybrid framework that leverages RRT to provide a global "prior" for MPPI's sampling distribution. By guiding local optimization with global reach, the system achieves robust navigation in dynamic environments with significantly improved computational efficiency.

Methodology: The RRT-MPPI Framework

The RRT-MPPI algorithm operates through a three-stage synergy designed to handle both static complexity and dynamic changes:

  1. Offline Global Guidance: Initially, an RRT algorithm identifies a feasible path to the goal, providing a rough topological map of the environment.
  2. Guided Sampling: Instead of sampling around a zero or arbitrary mean, MPPI derives its nominal control input from the RRT path using a Lyapunov or PD controller. This ensures that the sampling distribution is centered on a promising region of the search space.
  3. Dynamic Replanning: To handle environmental changes, such as moving or expanding obstacles, the system employs a "Replanning RRT." If the robot deviates significantly from its path or the path becomes obstructed, the RRT quickly updates the global guidance without a full restart.
The impact of different mean control inputs on the resulting MPPI trajectory.

Key Insights: The Importance of the Mean

A critical insight of this work is that the performance of MPPI is a function of its sampling mean. A conservative mean limits exploration, while an aggressive mean increases the "optimality gap"—the discrepancy between the sampled result and the true mathematical optimum.

The authors provide a formal Sample Size Analysis using Chebyshev’s inequality. They demonstrate that the required number of samples $K$ to reach a target accuracy is directly proportional to the magnitude of the control mean. By using RRT to provide a "sensible" mean, the algorithm reduces the variance of the samples, thereby lowering the hardware requirements for real-time execution.

Experimental Results

The RRT-MPPI method was evaluated in synthetic 2D environments featuring static and dynamic obstacles, such as circular obstacles that expand over time to simulate a changing workspace.

Performance comparison between RRT-MPPI (orange) and standard RRT (blue) across static and dynamic environments.

The results demonstrate significant gains over standard approaches:

  • Efficiency: In dynamic scenarios, RRT-MPPI completed navigation tasks in 14.56 seconds, compared to 21.81 seconds for a fixed-mean MPPI baseline.
  • Computational Load: To maintain equivalent error bounds, RRT-MPPI required only 6,122 samples, a near 50% reduction from the 11,413 samples required by the standard method.
  • Robustness: While standard MPPI often became trapped by growing obstacles, the RRT-guided version successfully replanned its trajectory to maintain a safe and optimal path to the goal.

Conclusion

The RRT-MPPI method effectively bridges the gap between global connectivity and local optimality. By using RRT as a prior for MPPI's sampling distribution, the authors have created a planner that is both robust to dynamic changes and computationally efficient. Future work will focus on reducing the latency of the replanning phase for high-speed applications and validating the framework on high-dimensional robotic systems.

Summary updated

BibTeX
@misc{tao2023rrt,
  author = {Chuyuan Tao and Hunmin Kim and Naira Hovakimyan},
  title = {{RRT Guided Model Predictive Path Integral Method}},
  year = {2023},
  eprint = {2301.13143},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.13143},
}
Figure