This is a collection of my implementation of robotic 2D path planning algorithms in c++.
This repo shows each algo individually.
For a more complete navigation module, please check my this repo navigation_package_V1 .
Using only C++ standard libraries for algorithms, and OpenCV for visulization.
Methods in progress:
- LPA*
- Reeds-shepp (code done, need to make GIF)
- Potential field
update some of the GIFs, since they were recorded with a very early version of code, which may casue non-optimal solution.
(The code has been updated, but GIFs need re-recording)
Each of the demo contains 5 samples played in sequence.
They are using tasks with identical start/goal position.
![BFS search BFS showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/BFS/bfs.gif)
![DFS search BFS showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/DFS/dfs.gif)
![Dijkstra search BFS showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/Dijkstra/dijkstra.gif)
After the first path is found, the robot starts moveing along the path.
The path is shown as orange line.
Some obstacles are added into the map while the robot is moving.
When the next step is blocked, it stops and looks for a new path to the goal.
The green line is the path during replanning; the new valid path is orange line.
![D-Star search dstar showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/D_star/d_star.gif)
This sample is using Manhattan distance as h-cost.
(I will update the GIF later)
![A-Star search BFS showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/A_star/astar.gif)
This sample is using Euclidean distance as the primary source of h-cost.
Then modify the h-cost based on the motion direction, steer, and priximity to obstacle.
The g-cost is the same as A-star.
Both position and direction are considered.
![BFS search Hybrid A-Star showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/hybrid_A_star/hybrid_a_star.gif)
This sample assume that the motion model contains only forward motion.
This algo is based on the paper
"Classification of the Dubins set"
by Andrei M. Shkel, Vladimir Lumelsky.
The types of curves being tried are listed at the top left corner of gif; and their costs are printed as well.
Those 2 black shart lines are the current pose and target pose.
![Dubins search Dubins showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/Dubins_curve/dubins.gif)
![BFS search PRM showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/PRM/prm.gif)
![RRT search RRT showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/RRT/rrt.gif)
Max sample number: 1000
The final path is much smoother than RRT above.
![RRTstar search RRTstar showcase gif](https://github.com/hanmmmmm/robot-path-planning/raw/main/RRT_star/rrt_star.gif)