Autonomous Highway Speeding

Problem Statement:

• Environment

A multi-lane highway with cars moving in one direction at a constant (known) speed.

• Planner

Our car (non-holonomic) is trying to speed through the traffic!  Given a constant velocity that is greater than the traffic’s,  the start location and the goal location, the planner will create a plan (or return that there is no plan) for the car to navigate through the traffic from start to goal.

Sample Visualization on MATLAB

Algorithms & Techniques Involved:

• Explicit Graph, Plan then Execute
• Weighted A* Search
  • Heuristic:  Euclidean Distance
• Motion Primitives
  • Straight, Change Lane To Left, Change Lane To Right

Planner runs a Weighted A* Search on the States defined by (x, y, t).  Successors of each state are found by collision checking each motion primitive.  If no plan is found, the planner will return: “No Plan Found!”

Variables:

• Start Lane, Goal Lane
• Robot Speed
• Traffic Speed
• Percent Traffic
• Number of Lanes
• Road Length

Remaining Issues:

• More Realistic
  • Variable Speed
  • More Motion Primitives
• Safety
• Scalability & Flexibility
  • Be able to scale to different environments
• Precision
  • Increased precision in distance and time
• Move towards Real-Time Planning