Paper Reading - A Review of Motion Planning Techniques for Automated Vehicles

Motion Planning

This note is only a fast review and understanding of the paper, which is more well organized than my note. This note skip every detail of any algorithm, and only focus on the big picture. (As we are doing deep learning, these algorithms are not that important, but the big picture is.)


1. Graph Based Planners

State Space Representation

  • Gird State Space. The graph is constructed by connecting the neighboring cells.
  • State Lattice. It uses a set of predefined paths reffered as state lattice, which is used to discretize the state space. And graph search algorithm such as A* is used.

Graph Search Algorithm

2. Sampling Based Planners

These methods take samples in the state space, and looking for a path connecting the start and goal state. The path is constructed by connecting the samples. The path is not optimal, but it is fast.

  • Probabilistic Roadmap (PRM)
  • Rapidly-exploring Random Tree (RRT)

3. Interpolating Curve Planners

Input: given a set of waypoints

Output: a smoother path - trajectory continuity - vehicle constraints - obstacle avoidance

Methods: - Lines and Circles - Clothoids (improved version of lines and circles with better continuity in curvature) - Polynomial Curves - Bezier Curves (a special case of polynomial curves, better computational efficiency) - Splines (segmented, combined with poly, b-spline, or clothoid)

4. Optimization Based Planners (Numerical Optimization)

Use a cost function to jointly optimize parameters such as speed, steering, lateral acceleration and others.