.
└── Search-based Planning
├── Breadth-First Searching (BFS)
├── Depth-First Searching (DFS)
├── Best-First Searching
├── Dijkstra's
├── A*
├── Bidirectional A*
├── Anytime Repairing A*
├── Learning Real-time A* (LRTA*)
├── Real-time Adaptive A* (RTAA*)
├── Lifelong Planning A* (LPA*)
├── Dynamic A* (D*)
├── D* Lite
└── Anytime D*
└── Sampling-based Planning
├── RRT
├── RRT-Connect
├── Extended-RRT
├── Dynamic-RRT
├── RRT*
├── Informed RRT*
├── RRT* Smart
├── Anytime RRT*
├── Closed-Loop RRT*
├── Spline-RRT*
├── Fast Marching Trees (FMT*)
└── Batch Informed Trees (BIT*)
└── Papers
This repository implemented some common motion planners used on autonomous vehicles, including
- Hybrid A* Planner
- Frenet Optimal Trajectory
- Hierarchical Optimization-Based Collision Avoidance (H-OBCA) (Incomplete)
Also, this repository provides some controllers for path tracking, including
- Pure Pursuit + PID
- Rear-Wheel Feedback + PID
- Front-Wheel Feedback / Stanley + PID
- LQR + PID
- Linear MPC
- Python 3.6 or above
- SciPy
- cvxpy
- Reeds-Shepp Curves
- pycubicspline
This repository uses two models: simple car model and car pulling trailers model.
- Basic Path Planning Algorithms: PathPlanning
- Baidu Apollo Planning module: Recommended Materials
- Survey of Planning and Control algos: A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles
- Hybrid A* Planner: Practical Search Techniques in Path Planning for Autonomous Driving
- Frenet Optimal Trajectory: Optimal Trajectory Generation for Dynamic Street Scenarios in a Frenet Frame
- Baidu Apollo Control module: Recommended Materials
- Pure Pursuit: Implementation of the Pure Pursuit Path Tracking Algorithm
- Rear-Wheel Feedback: Automatic Steering Methods for Autonomous Automobile Path Tracking
- Front-Wheel Feedback / Stanley: Stanley: The Robot that Won the DARPA Grand Challenge
- LQR: ApolloAuto/apollo: An open autonomous driving platform
- Linear MPC: MPC-Based Approach to Active Steering for Autonomous Vehicle Systems
- HybridAStarTrailer (Julia): by AtsushiSakai
- Hybrid Path Planner (C++): by KTH Research Concept Vehicle
- A*: A Formal Basis for the heuristic Determination of Minimum Cost Paths
- Learning Real-Time A*: Learning in Real-Time Search: A Unifying Framework
- Real-Time Adaptive A*: Real-Time Adaptive A*
- Lifelong Planning A*: Lifelong Planning A*
- Anytime Repairing A*: ARA*: Anytime A* with Provable Bounds on Sub-Optimality
- D*: Optimal and Efficient Path Planning for Partially-Known Environments
- D* Lite: D* Lite
- Field D*: Field D*: An Interpolation-based Path Planner and Replanner
- Anytime D*: Anytime Dynamic A*: An Anytime, Replanning Algorithm
- Focussed D*: The Focussed D* Algorithm for Real-Time Replanning
- Potential Field, [PPT]: Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
- Hybrid A*: Practical Search Techniques in Path Planning for Autonomous Driving
- RRT: Rapidly-Exploring Random Trees: A New Tool for Path Planning
- RRT-Connect: RRT-Connect: An Efficient Approach to Single-Query Path Planning
- Extended-RRT: Real-Time Randomized Path Planning for Robot Navigation
- Dynamic-RRT: Replanning with RRTs
- RRT*: Sampling-based algorithms for optimal motion planning
- Anytime-RRT*: Anytime Motion Planning using the RRT*
- Closed-loop RRT* (CL-RRT*): Real-time Motion Planning with Applications to Autonomous Urban Driving
- Spline-RRT*: Optimal path planning based on spline-RRT* for fixed-wing UAVs operating in three-dimensional environments
- LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically Derived Extension Heuristics
- RRT#: Use of Relaxation Methods in Sampling-Based Algorithms for Optimal Motion Planning
- RRT*-Smart: Rapid convergence implementation of RRT* towards optimal solution
- Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal heuristic
- Fast Marching Trees (FMT*): a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions
- Motion Planning using Lower Bounds (MPLB): Asymptotically-optimal Motion Planning using lower bounds on cost
- Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs
- Advanced Batch Informed Trees (ABIT*): Sampling-Based Planning with Advanced Graph-Search Techniques ((ICRA) 2020)
- Adaptively Informed Trees (AIT*): Fast Asymptotically Optimal Path Planning through Adaptive Heuristics ((ICRA) 2020)