Introduction

Motion planning plans the state sequence of the robot without conflict between the start and goal.

Motion planning mainly includes Path planning and Trajectory planning.

• Path Planning: It's based on path constraints (such as obstacles), planning the optimal path sequence for the robot to travel without conflict between the start and goal.
• Trajectory planning: It plans the motion state to approach the global path based on kinematics, dynamics constraints and path sequence.

This repository provides the implement of common Motion planning algorithm, welcome your star & fork & PR.

The theory analysis can be found at motion-planning

We also provide ROS C++ version and Matlab version.

Quick Start

The file structure is shown below

python_motion_planning
├─gif
├─example
├─global_planner
│   ├─graph_search
│   ├─sample_search
│   └─evolutionary_search
├─local_planner
├─curve_generation
├─utils
└─main.py

• The global planning algorithm implementation is in the folder global_planner with graph_search, sample_search and evolutionary search.
• The local planning algorithm implementation is in the folder local_planner.
• The curve generation algorithm implementation is in the folder curve_generation.

To start simulation, open the folder example and select the algorithm, for example

if __name__ == '__main__':
    '''
    path searcher constructor
    '''
    search_factory = SearchFactory()
    
    '''
    graph search
    '''
    # build environment
    start = (5, 5)
    goal = (45, 25)
    env = Grid(51, 31)

    # creat planner
    planner = search_factory("a_star", start=start, goal=goal, env=env)
    # animation
    planner.run()

Version

Global Planner

Planner	Version	Animation
GBFS
Dijkstra
A*
JPS
D*
LPA*
D* Lite
Theta*
Lazy Theta*
Voronoi
RRT
RRT*
Informed RRT
RRT-Connect
ACO
GA
PSO

Local Planner

Planner	Version	Animation
PID
APF
DWA
TEB
MPC
Lattice

Curve Generation

Planner	Version	Animation
Polynomia
Bezier
Cubic Spline
BSpline
Dubins
Reeds-Shepp

Papers

Global Planning

• A*: A Formal Basis for the heuristic Determination of Minimum Cost Paths
• JPS: Online Graph Pruning for Pathfinding On Grid Maps
• Lifelong Planning A*: Lifelong Planning A*
• D*: Optimal and Efficient Path Planning for Partially-Known Environments
• D* Lite: D* Lite
• Theta*: Theta*: Any-Angle Path Planning on Grids
• Lazy Theta*: Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D
• RRT: Rapidly-Exploring Random Trees: A New Tool for Path Planning
• RRT-Connect: RRT-Connect: An Efficient Approach to Single-Query Path Planning
• RRT*: Sampling-based algorithms for optimal motion planning
• Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal heuristic
• ACO: Ant Colony Optimization: A New Meta-Heuristic

Local Planning

• DWA: The Dynamic Window Approach to Collision Avoidance
• APF: Real-time obstacle avoidance for manipulators and mobile robots

Curve Generation

• Dubins: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents

Acknowledgment

• Our visualization and animation framework of Python Version refers to https://github.com/zhm-real/PathPlanning. Thanks sincerely.