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