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

Quick Start

The file structure is shown below

├─animation
│  └─video
├─env
│  └─map
├─gif
├─graph_search
├─local_planner
├─sample_search
├─utils
├─simulation_global.mlx
└─simulation_local.mlx

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 ./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
D*
LPA*
D* Lite
RRT
RRT*
Informed RRT
RRT-Connect

Local Planner

Planner	Version	Animation
PID
APF
DWA
TEB
MPC
Lattice

Intelligent Algorithm

Planner	Version	Animation
ACO
GA
PSO
ABC

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