[Paper Notes] Practical Search Techniques in Path Planning for Autonomous Driving

San Francisco, May 15, 2022
  • Application: high-performance path planning involving both forward and reverse motion, such as navigating parking lots, executing U-turns and dealing with blocked roads and intersections.
  • Related work:
    - Discrete state space search, which leads to paths that are non-smooth or do no generally satisfy non-holonomic constraints.
    - Non-linear optimization in the space of controls or parameterized curves, which may not guarantee fast convergence due to local optima.
  • Two phases:
    - Generate a kinematically feasible trajectory through heuristic search in continuous coordinates.
    - Improve the quality of the trajectory using conjugate gradient descent.
  • How does hybrid-state A* generate drivable paths?
    - Discretize the search space (x, y, theta), but associate with each grid cell a continuous 3D state instead of just the center of the cell, so that the path is not piece-wise linear as in standard A*.
  • Take the maximum of two admissible heuristics:
    - One heuristic ignores obstacles but takes into account the non-holonomic constraint.
    - Another ignores the non-holonomic constraint and takes account of the obstacle map.
  • Two types of state expansions:
    - By applying control actions selected from a discretized space, whereby the search may never reach the continuous coordinate goal state.
    - Analytic expansions on one of every N nodes, which computes an optimal Reed-and-Shepp path from the current state to the goal.
  • Two-stage optimization for post-processing the hybrid-state A* solution:
    - Non-linear optimization using CG to improve the path length and smoothness.
    - Non-parametric interpolation, which minimizes curvature of the path using another iteration of CG.
  • Cost formulation that balances obstacle avoidance, non-holonomic constraint and smoothness:
Cost function, cited from the original paper¹.
  • The Voronoi field (the first term in the cost function):
    - Penalizes proximity to obstacles as any other potential field.
    - Rescales the field based on the geometry of the workspace to address untraversable narrow passages in ordinary potential fields.
Voronoi field, cited from the original paper¹.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Devin Z

Devin Z

认识世界,改造世界 (Seek truth and solve problems)