Planning Algorithm

1. How to Use

1.1 Environment config

Ubuntu20.04(recommend) or Ubunt18.04
CMake
OpenCV(OpenCV4 recommend)

1.2 Build program

mkdir build
cd build
cmake ..
make -j10
./a_star
./rrt

1.3 Supplementary Instruction

The rightward direction is the positive direction of the X-axis
The downward direction is the positive direction of the Y-axis.

2. Taxonomy of motion planning techniques applied in automated driving scenarios

Algorithm group Technique Technique description
Graph search based planners Dijkstra's Algorithm Known nodes/cells search space with associated weights
Grid and node/cells weights computation according to the environment
A* algorithm family Anytime D* with Voronoi cost functions Hybrid-heuristics A*
A* with Voronoi/Lattice enviroment represeantation. PAO*
State Lattices Enviroment decomposed in a local variable grid, depending on the complexity of the maneuver
Spatio-temporal lattices(considering time and velocity dimensions)
Sampling based planners RRT Physical and logical bias are used to generate the random-tree
Anytime planning with RRT*
Trajectory coordination with RRT
Interpolating curve planners Line and circle Road fitting and interpolation of known waypoints
Clothoid Curves Piecewise trajectory generation with straight, clothoid and circular segments
Off-line generation of clothoid primitives from which the best will be taken in on-line evaluation
Polynomial Curves Cubic order polynomial curves
Higher order polynomial curves
Bezier Curves Selection of the optimal control points location for the situation in hand
Rational Bezier curves impletation
Spline Curves Polynomial piecewise implementation Basis splines(b-splines)
Numerical optimization approaches Function optimization Trajectory generation optimizing parameters such as speed, steering speed, rollover constraints, lateral accelerations, jerk(lateral comort optimization), among others