/python_motion_planning

Motion planning and Navigation of AGV/AMR based on python, including A*(A Star), JPS(Jump Point Search), D*(D Star), LPA*, D* Lite, RRT, RRT*, RRT-Connect, Informed RRT*, PID, DWA etc.

Primary LanguagePythonGNU General Public License v3.0GPL-3.0

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 at https://github.com/ai-winter/ros_motion_planning and Matlab Version at https://github.com/ai-winter/matlab_motion_planning

Quick Start

The file structure is shown below

├─gif
├─graph_search
├─sample_search
├─utils
└─main.py

The global planning algorithm implementation is in the folder graph_search and sample_search; The local planning algorithm implementation is in the folder local_planner.

To start simulation, open ./main.py and select the algorithm, for example

if __name__ == '__main__':
    '''
    sample search
    '''
    # build environment
    start = (18, 8)
    goal = (37, 18)
    env = Map(51, 31)

    planner = InformedRRT(start, goal, env, max_dist=0.5, r=12, sample_num=1500)

    # animation
    planner.run()

Version

Global Planner

Planner Version Animation
GBFS Status gbfs_python.png
Dijkstra Status dijkstra_python.png
A* Status a_star_python.png
JPS Status jps_python.png
D* Status d_star_python.png
LPA* Status lpa_star_python.png
D* Lite Status d_star_lite_python.png
RRT Status rrt_python.png
RRT* Status rrt_star_python.png
Informed RRT Status informed_rrt_python.png
RRT-Connect Status rrt_connect_python.png

Local Planner

Planner Version Animation
PID Status Status
APF Status Status
DWA Status Status
TEB Status Status
MPC Status Status
Lattice Status Status

Intelligent Algorithm

Planner Version Animation
ACO Status Status
GA Status Status
PSO Status Status
ABC Status Status

Papers

Search-based 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

Sample-based Planning

  • 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

Local Planning

  • DWA: The Dynamic Window Approach to Collision Avoidance

Acknowledgment