ROS Motion Planning

Robot Motion planning is a computational problem that involves finding a sequence of valid configurations to move the robot from the source to the destination. Generally, it includes Path Searching and Trajectory Optimization.

• Path Searching: Based on path constraints, such as obstacles, to find the optimal sequence for the robot to travel from the source to the destination without any collisions.

• Trajectory Planning: Based on kinematics, dynamics and obstacles, it optimizes the trajectory of the motion state from the source to the destination according to the path.

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

Your stars, forks and PRs are welcome!

Contents

• Quick Start within 3 Minutes
• Document
• Tool Chains
• Version
• Acknowledgments
• License
• Maintenance

0. Quick Start within 3 Minutes

Tested on ubuntu 20.04 LTS with ROS Noetic.

1. Install ROS (Desktop-Full suggested).

2. Install git.

   sudo apt install git

3. Install dependence

   • OSQP

   git clone -b release-0.6.3 --recursive https://github.com/oxfordcontrol/osqp
   cd osqp && mkdir build && cd build
   cmake .. -DBUILD_SHARED_LIBS=ON
   make -j6
   sudo make install
   sudo cp /usr/local/include/osqp/* /usr/local/include

   • OSQP-Eigen

   git clone https://github.com/robotology/osqp-eigen.git
   cd osqp-eigen && mkdir build && cd build
   cmake ..
   make
   sudo make install

   • Other dependence.

   sudo apt install python-is-python3 \
   ros-noetic-amcl \
   ros-noetic-base-local-planner \
   ros-noetic-map-server \
   ros-noetic-move-base \
   ros-noetic-navfn

4. Compile the code. go to the workspace

   NOTE: Please refer to #48 if you meet libignition dependency error.

   cd ros_motion_planning/
   catkin_make
   # or catkin build
   # you may need to install it by: sudo apt install python-catkin-tools

5. Execute the code.

   cd scripts/
   ./main.sh

   NOTE: Modifying launch files may not have any effect, because they are regenerated by a Python script based on src/user_config/user_config.yaml when you run main.sh. Therefore, you should modify configurations in user_config.yaml instead of launch files.

6. You can use the other script to shutdown them rapidly.

   ./killpro.sh

1. Document

The overall file structure is shown below.

ros_motion_planner
├── assets
├── scripts
└── src
    ├── core
    │   ├── global_planner
    │   ├── local_planner
    │   ├── curve_generation
    │   └── utils
    ├── sim_env             # simulation environment
    │   ├── config
    │   ├── launch
    │   ├── maps
    │   ├── meshes
    │   ├── models
    │   ├── rviz
    │   ├── urdf
    │   └── worlds
    ├── third_party
    │   ├── dynamic_rviz_config
    │   ├── dynamic_xml_config
    │   ├── gazebo_plugins
    │   └── rviz_plugins
    └── user_config         # user configure file

To better understand the project code, detailed interface documentation can be generated using the doxygen tool. First install doxygen and graphviz.

sudo apt-get install doxygen graphviz

Then start the doxygen and you can find the documentation in ./docs/html/index.html.

doxygen

For more information about the project usage, please refer to the following table.

Index	Document	Introduction
0		Introduce how to dynamically configure parameters such as robot types, planning algorithms, environmental obstacles, etc.
1		Introduce how to use Docker to conveniently build the project environment and simulate it.
2		Introduce how to build a real robot application based on the algorithms provided in this repository.
3		Important updates.

02. Tool Chains

For the efficient operation of the motion planning system, we provide a series of user-friendly simulation tools that allow for on-demand selection of these lightweight repositories.

Tool Version	Introduction
	This is a Gazebo plugin for pedestians with collision property. You can construct a dynamic environment in ROS easily using plugin.
	This repository provides a ROS-based visualization Rviz plugins for path planning and curve generation algorithms.

03. Version

Global Planner

Planner	Version	Animation	Papers
GBFS			-
Dijkstra			-
A*			A Formal Basis for the heuristic Determination of Minimum Cost Paths
JPS			Online Graph Pruning for Pathfinding On Grid Maps
D*			Optimal and Efficient Path Planning for Partially-Known Environments
LPA*			Lifelong Planning A*
D* Lite			D* Lite
Voronoi			-
Theta*			Theta*: Any-Angle Path Planning on Grids, Any-angle path planning on non-uniform costmaps
Lazy Theta*			Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D
S-Theta*			S-Theta*: low steering path-planning algorithm
Hybrid A*			Practical search techniques in path planning for autonomous driving
RRT			Rapidly-Exploring Random Trees: A New Tool for 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
RRT-Connect			RRT-Connect: An Efficient Approach to Single-Query Path Planning
ACO			Ant Colony Optimization: A New Meta-Heuristic
GA			Adaptation in Natural and Artificial Systems
PSO			Particle Swarm Optimization

Local Planner

Planner	Version	Animation	Paper
PID			Mapping Single-Integrator Dynamics to Unicycle Control Commands p. 14
LQR			-
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
TEB
MPC			-
Lattice

Curve Generation

Planner	Version	Animation	Paper
Polynomia			-
Bezier			-
Cubic Spline			-
BSpline			-
Dubins			On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents
Reeds-Shepp			Optimal paths for a car that goes both forwards and backwards

04. Acknowledgments

• Our robot and world models are from Dataset-of-Gazebo-Worlds-Models-and-Maps and aws-robomaker-small-warehouse-world. Thanks for these open source models sincerely.

• Pedestrians in this environment are using social force model(sfm), which comes from https://github.com/robotics-upo/lightsfm.

• A ROS costmap plugin for dynamicvoronoi presented by Boris Lau.

05. License

The source code is released under GPLv3 license.

06. Maintenance

Feel free to contact us if you have any question.