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