Intelligent Motion Laboratory at Duke University

Avoiding many moving obstacles in intelligent vehicles

Jeff Johnson, Kris Hauser

Collaborators: Sarah Koskie (IUPUI), Michael Justiss (IUPUI)

Summary

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.

J. Johnson and K. Hauser. Optimal Longitudinal Control Planning with Moving Obstacles. In proceedings of IEEE Int'l Intelligent Vehicles Symposium, May 2013. (oral presentation)
J. Johnson and K. Hauser. Optimal Longitudinal Control Planning with Moving Obstacles. In ICRA 2013 Workshop on Vehicle Autonomy for Urban Transportation Systems. Karlsruhe, Germany, May 2013.
J. Johnson and K. Hauser. Optimal Acceleration-Bounded Trajectory Planning in Dynamic Environments Along a Specified Path. In IEEE Int'l Conference on Robotics and Automation (ICRA), Minneapolis, May 2012.
J. Johnson, Y. Zhang, and K. Hauser. Semiautonomous Longitudinal Collision Avoidance Using a Probabilistic Decision Threshold. In IROS 2011 Workshop on Perception and Navigation for Autonomous Vehicles in Human Environments, September, 2011.

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. Similar to above, here the agent traverses a 13-lane roadway.

MP4, 523KB

A simulated car (red) traveling westward along on Kirkwood Avenue in Bloomington, Indiana on a stretch of road with many restaurants and pubs. Bicyclists often share the road lane and pedestrian traffic is heavy, both at and away from crosswalks.

MP4, 338KB

The visibility graph method represents all safe trajectories that respect velocity and acceleration bounds. Moving obstacles become diagonal forbidden regions in path-time (PT) space. The planner incrementally calculates reachable velocities at each PT obstacle vertex and diagonal edge. The solution is the minimum-time trajectory that reaches the goal (right edge).