lijian8 / hybrid_a_star

Path Planning with Visualization using Hybrid A*

Hybrid A* Path Planning

This project implements Hybrid-A* Path Planning algorithm for a non-holonomic vehicle, which is inspired by this Demo Video.

The Hybrid-A* algorithm is described here, Practical Search Techniques in Path Planning for Autonomous Driving.

The code is ready to run a real Autonomous Vehicle with minor modifications, although it runs standalone as a demo in this repository.

Algorithm Description

• A 3D discrete search space is used but unlike traditional A*, hybrid-A* associates with each grid cell a continuous 3D state of the vehicle. The resulting path is guaranteed to be drivable (standard A* can only produce piece-wise linear paths).
• The search algorithm is guided by two heuristics -
  • 'non-holonomic-without-obstacles' uses Dubin's path length ignoring obstacles
  • 'holonomic-with-obstacles' uses shortest path in 2D computed using A* (or Dijkstra's) ignoring holonomic constraints of vehicle
• To improve search speed, the algorithm analytically expands nodes closer to goal using dubins path and checks it for collision with current obstacle map.

Parameters

• map
• initial
• goal
• velocity

Path Planning Visualization

Result Images

Future Work

• Path Smoothing
• Reverse Motion (Done)
• User Interaction
• Viusalization Optimization
• Motion Control

Resources

• Practical Search Techniques in Path Planning for Autonomous Driving