Optimization-based Motion Planning in Dynamic Environments

Chonhyon Park, Jia Pan and Dinesh Manocha
University of North Carolina at Chapel Hill



We present a novel optimization-based algorithm for motion planning in dynamic environments. Our approach uses a stochastic trajectory optimization framework to avoid collisions and satisfy smoothness and dynamics constraints. Our algorithm does not require a priori knowledge about global motion or trajectories of dynamic obstacles. Rather, we compute a conservative local bound on the position or trajectory of each obstacle over a short time and use the bound to compute a collision-free trajectory for the robot in an incremental manner. Moreover, we interleave planning and execution of the robot in an adaptive manner to balance between the planning horizon and responsiveness to obstacle. We highlight the performance of our planner in a simulated dynamic environment with the 7-DOF PR2 robot arm and dynamic obstacles.


Dynamically Balanced and Plausible Trajectory Planning for Human-Like Characters (PDF) [Video]
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D), 2016

Simulating High-DOF Human-like Agents using Hierarchical Feedback Planner (PDF) [Video]
The ACM Symposium on Virtual Reality Software and Technology (VRST), 2015

Smooth and Dynamically Stable Navigation of Multiple Human-Like Robots (PDF)
[Video 1][Video 2] [Video 3][Video 4]
The Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2014

Fast and Dynamically Stable Optimization-based Planning for High-DOF Human-like Robots (PDF) [Video 1][Video 2][Video 3]
IEEE International Conference on Humanoid Robots (HUMANOIDS), 2014

High-DOF Robots in Dynamic Environments using Incremental Trajectory Optimization (PDF)
International Journal of Humanoid Robotics (IJHR), 2014

Real-time Optimization-based Planning in Dynamic Environments using GPUs (PDF) [Video]
IEEE International Conference on Robotics and Automation (ICRA), 2013

ITOMP: Incremental Trajectory Optimization for Real-time Replanning in Dynamic Environments (PDF)
International Conference on Automated Planning and Scheduling (ICAPS), 2012


Dynamically Balanced and Plausible Trajectory Planning for Human-Like Characters

Performance Comparison of ITOMP and OMPL for Amazon Picking Challenge [MP4]

Multi-Robot Planning

Stable Optimizaton-based Planning for High-DOF Human-like Robots

Hierarchical Optimization-based Planning

Optimization-based Planning in Dynamic Environments


(a) Success rates

(b) Average cost of planned trajectories

Success rate and trajectory cost results obtained from the replanning in dynamic environments on a multi-core CPU and a many-core GPU. The success rate and trajectory cost is measured for each planner. The use of multiple trajectories in our replanning algorithm results in higher success rates and trajectories with lower costs and thereby, improved quality.

Related Links

GAMMA Research Group
Motion Planning Research at GAMMA