motionplanning

Motion planning algorithm implementation in Python and C++

Table of Contents

• C++ useage
• a* algorithm
• theta* algorithm
• Probabilistic Roadmaps algorithm
• Rapidly-exploring random tree algorithm
  • rrt
  • rrt_connect
  • rrt*
  • rrt*-smart
• Dubins path algorithm
  • shortest dubins path with different end point
  • 6 types of dubins path with same end point
  • RRT-Dubins
  • RRT*-Dubins
• Reeds Shepp path algorithm
  • shortest Reeds Shepp path with different end point
  • different types of Reeds Shepp path with same end point
  • Hybrid A* algorithm

C++ useage

C++11 standard, use Rviz to show algorithm, so you should install ROS.

1. put this package in your ros workspace, e.g. ~/catkin_ws/src/
2. cd ~/catkin_ws and catkin_make
3. source devel/setup.bash
4. launch script, e.g. roslaunch cpp_rviz a_star.launch

a* algorithm

theta* algorithm

Probabilistic Roadmaps algorithm

Rapidly-exploring random tree algorithm

rrt

rrt_connect

rrt*

rrt*-smart

Dubins path algorithm

Dubins algorithm have 6 types path as below.

shortest dubins path with different end point

6 types of dubins path with same end point

RRT-Dubins

RRT*-Dubins

Reeds Shepp path algorithm

The difference of Reeds Shepp path and Dubins path is that Reeds Sheep path have both forwards and backwards. So Dubins path is a subset of Reeds Shepp path.

shortest Reeds Shepp path with different end point

different types of Reeds Shepp path with same end point

Hybrid A* algorithm

based A* algorithm and Reeds Shepp path algorithm