README.md

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.

This repository provides the implementation of common Motion Planning algorithms. The theory analysis can be found at motion-planning. Furthermore, we provide ROS C++ and Python version.

Quick Start

The file structure is shown below

├─gif
├─examples
│   ├─simulation_global.mlx
│   ├─simulation_local.mlx
│   ├─simulation_total.mlx
├─global_planner
│   ├─graph_search
│   ├─sample_search
│   └─evolutionary_search
├─local_planner
└─utils

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.

To start simulation, open ./simulation_global.mlx or ./simulation_local.mlx and select the algorithm, for example

clear all;
clc;

% load environment
load("gridmap_20x20_scene1.mat");
map_size = size(grid_map);
G = 1;

% start and goal
start = [3, 2];
goal = [18, 29];

% planner
planner_name = "rrt";

planner = str2func(planner_name);
[path, flag, cost, expand] = planner(grid_map, start, goal);

% visualization
clf;
hold on

% plot grid map
plot_grid(grid_map);
% plot expand zone
plot_expand(expand, map_size, G, planner_name);
% plot path
plot_path(path, G);
% plot start and goal
plot_square(start, map_size, G, "#f00");
plot_square(goal, map_size, G, "#15c");
% title
title([planner_name, "cost:" + num2str(cost)]);

hold off

Version

Global Planner

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

Local Planner

Planner	Version	Animation
PID
LQR
MPC
APF
DWA
RPP
TEB
MPC
Lattice

Intelligent Algorithm

Planner	Version	Animation
ACO
GA
PSO
ABC

Curve Generation

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

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
• Theta*: Theta*: Any-Angle Path Planning on Grids
• Lazy Theta*: Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D

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

Evolutionary-based Planning

• 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
• RPP: Regulated Pure Pursuit for Robot Path Tracking

Curve Generation

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