Optimal Acceleration-Bounded Trajectory Planning in Dynamic Environments Along a Specified Path
Jeff Johnson and Kris Hauser. In ICRA 2012
Abstract. Vehicles that cross lanes of traffic encounter the problem of navigating around dynamic obstacles under actuation constraints. This paper presents an optimal, exact, polynomial-time planner for optimal bounded-acceleration trajectories along a fixed, given path with dynamic obstacles. The planner constructs reachable sets in the path-velocity-time (PVT) space by propagating reachable velocity sets between obstacle tangent points in the path-time (PT) space. The terminal velocities attainable by endpoint-constrained trajectories in the same homotopic class are proven to span a convex interval, so the planner merges contributions from individual homotopic classes to find the exact range of reachable velocities and times at the goal. A reachability analysis proves that running time is polynomial given reasonable assumptions, and empirical tests demonstrate that it scales well in practice and can handle hundreds of dynamic obstacles in a fraction of a second on a standard PC.
Download PDF 
Download Accompanying Video (MP4, 1.3MB): 
Download Planner Library (C++, 331KB): PVTPlanner
UPDATE: We have extended the planning system to generalize construction of PT obstacles and to perform velocity propagation with polygonal PT obstacles. These extensions allow the planner to solve more general path conflicts such as merging and vehicle following. Further information and code here: http://motion.cs.illinois.edu/iv2013/
Other Media
Planner-generated Trajectories in Lane Crossing Scenarios
Our planner is used to plan a safe, time-optimal trajectory across a fixed path (yellow) under dynamic constraints and in the presence of dynamic obstacles. Here the agent traverses 4 lanes of a divided roadway.
MP4, 92KB
Similar to above, here the agent traverses 6 lanes of a divided roadway.
MP4, 251KB
Similar to above, here the agent traverses a 13-lane roadway.
MP4, 523KB
Path-time Space Representations of Lane Crossing Scenarios
The vehicle-centered path-time space view of the 4-lane scenario. The rectangles represent the computed path-time obstacles. The animation displays the contruction of the visibility graph, and the computation of the time-optimal trajectory.
MP4, 118KB
The vehicle-centered path-time view of the 6-lane scenario. The rectangles represent the computed path-time obstacles. The animation displays the contruction of the visibility graph, and the computation of the time-optimal trajectory.
MP4, 125KB
The vehicle-centered path-time view of the 13-lane scenario. The rectangles represent the computed path-time obstacles. The animation displays the contruction of the visibility graph, and the computation of the time-optimal trajectory.
MP4, 127KB
Assisted Collision Avoidance in Lane Crossing Scenario
In this simple scenario the control policy for the vehicle at each time step is full acceleration. Under this control policy collision occurs.
MP4, 26KB
Because our planner is guaranteed to find a safe trajectory if one exists, it can be used to judge whether a given control will result in a goal-reachable, or safe, state. This is the same scenario as above with the addition of a collision avoidance system that utilizes our planner to evaluate a control before it is applied. If the control will result in an unsafe state, the system utilizes information provided by the planner to adjust the control such that the resulting state is safe.
MP4, 47KB
Our planner is here used to provide collision-avoidance assistance to a human operator. In this scenario, a human operator attempts to navigate the fixed path across the lanes of traffic. At each time step, the user control is passed through a filter that utilizes the planner to determine whether the resulting state is safe. If the control is deemed safe, it is executed as-is. If the control is not deemed safe, it is adjusted such that the resulting state will be safe. When the vehicle is under human control, the control block on the GUI is green. When the vehicle is under planner control, the control block is red.
MP4, 766KB
