Real-time optimization-based planning in dynamic environments using GPUs

We present a novel algorithm to compute collision-free trajectories in dynamic environments. Our approach is general and does not require a priori knowledge about the obstacles or their motion. We use a replanning framework that interleaves optimization-based planning with execution. Furthermore, we describe a parallel formulation that exploits a high number of cores on commodity graphics processors (GPUs) to compute a high-quality path in a given time interval. We derive bounds on how parallelization can improve the responsiveness of the planner and the quality of the trajectory.

Authors

• Chonhyon Park
• Jia Pan 0001
• Dinesh Manocha

Keywords

• Trajectory
• Dynamic Environment
• Graphics Processing Unit
• Optimization-based Planning
• Time Interval
• Collision-free Trajectory
• Probability Density Function
• Global Optimization
• Local Optimum
• Path Planning
• Configuration Space
• Trajectory Optimization
• Noise Vector
• Order Statistics
• Number Of Trajectories
• Collision Detection
• Planning Algorithm
• Parallel Algorithm
• Time Budget
• Multiple Trajectories
• Dynamic Scenes
• Static Obstacles
• Dynamic Obstacles
• Parallel Optimization
• Conservative Bound
• Parallel Trajectories
• Solution Trajectory
• Multiple Threads
• Optimization Algorithm
• Sensor Data
• State Space