This repository is a part of an assignment in Robot's Control and Navigation Course (2021 Semester B).
Optimal Path Planning Using Generalized Voronoi Graph and Multiple Potential Functions
The main parts of code are located in /src directory.
a_star.py - our simple and generic implementation of A*.
More explanation about the A* implementation can be found
in this repository.
RRT.py - our simple and generic implementation of RRT.
More explanation about the RRT implementation can be also found
in this repository.
main_find_path.py - the main flow of path planning.
The file contains ROS node that responsible to build a path for robot.
We worked with TurtleBot3 robot, Gazebo simulation and Rviz.
| TurtleBot3 | Rviz |
|---|---|
 |
 |
| Gazebo (1) | Gazebo (2) |
|---|---|
 |
 |
We used tuw_voronoi_graph package to create Voronoi graph.
Then, we transferred it to x, y coordinates.
| Map | Graph |
|---|---|
 |
 |
Next, we used a_star.py package to create the shortest path inside Voronoi graph.
| Graph | Graph with path |
|---|---|
|
 |
We used MPFsampling() function inside main_find_path.py
to create the proper distribution that we will use during RRT sampling process.
| Graph with path | Distribution around this path |
|---|---|
|
 |
Then, we used RRT.py to find the desired path to the target
using RRT sampling process with a given MPF distribution.
| Distribution around this path | RRT solution |
|---|---|
|
 |
And finally, we used move2() method inside main_find_path.py
to navigate robot through the found path.
The proposed algorithm can be conveniently implemented on plethora kinds of robots. The calculations do not demand many resources. Easy to understand basic principles.
As an improvements of our implementation, we can suggest:
- Tuning step size ( the length of a branch in RRT) – it is apple to speed up the convergence
- Tuning sampling parameters – better distribution approximation can increase convergence as well
- Adding robot constrains – consider dynamics of a specific robot