Table of Contents
ToDo:
- Potential function for the complex algo
- Explore neighbors
- Takes a node and returns all its neighbor
- Explore neighbors
- Should this be encapsulated in base Algorithm class?
Preliminary data such as map with obstacle, initial and goal position, common to all algorithms will be provided with node - map_node
Each algorithms can be executed using its own python node.
Complex algorithms which requires functionalities present in simpler can be derived easily as the codebase it OOP based.
PlayGround
bringup.launch.py
Launches rviz2 for visualization of algorithms and
map_node which provided the preliminary datamap_node
Has the preliminary map defined.
Publishes
Map with obstacles
initial and goal pose embedded within the map
map data is first stored in 2d matrix represented as x, y
Instead of adjacency list, the preliminary map is transmitted.
Serves service `get_map` requested by individual algorithms for preliminary map.
Since this wont be changing over time and will be required only once service has been used,
instead of topic.algo_nodes
Waits for the GetMap service and requests the service for map with obstacles with initial and goal pose.
Instead of using sync service, using a flag to wait for the response.
Service callback method converts the data into 2D matrix for manipulation.
Within the timer loop BFS traversal is performed and each node is marked visited denoted in the map itself.
After each iteration of master loop color of visited cells is increased in spectrum for visualization.
Path is back tracked using `parent` attribute and path is generated.-128 to -2 => RED to YELLOW
-1 => GREY
0 => BLACK
1 to 98 => BLUE to RED
99 => CYAN
100 => PINK
101 to 127 => GREENYELLOW => START POINT
BLUE => END POINT
GREEN => GENERATED PATH
Explored area has a gradient from YELLOW to BLUE for each iteration.Breadth First Search
Explores the neighbor nodes first, before moving to the next level of neighbors.
Utilizes queue to store the node yet to be visited.Depth First Search
Plunges depth first into a graph without regard for which edge it take next
until it cannot go further at which point it backtracks and continues.Minimal Spanning Tree
- dijkstra
- greedy
- A*
- D*
- Uniform Cost Search
- Best-First Searching
- A*
- Bidirectional A*
- Anytime Repairing A*
- Learning Real-time A* (LRTA*)
- Real-time Adaptive A* (RTAA*)
- Lifelong Planning A* (LPA*)
- Dynamic A* (D*)
- D* Lite
- Anytime D*
- Dynamic Window Approach.
- Rapidly-Exploring Random Trees RRT
- RRT*
- Probabilistic Roadmap (PRM)
- RRT
- RRT-Connect
- Extended-RRT
- Dynamic-RRT
- RRT*
- Informed RRT*
- RRT* Smart
- Anytime RRT*
- Closed-Loop RRT*
- Spline-RRT*
- Fast Marching Trees (FMT*)
- Batch Informed Trees (BIT*)
- Artificial Potential Field (APF)
- Voronoi Diagrams
- Visibility Graphs:
- Trajectory Optimization
- Model Predictive Control (MPC)
-Probabilistic Graph Search
- Anytime Algorithm
- PRM* (Probabilistic Roadmap Star)
- Informed RRT*
Move into your workspace's src folder
cd ~/ros2_ws/src
Clone the project
git clone
Build the project.
cd ~/ros2_ws && colcon build
Launch rviz2 and map_node using bringup launch file
ros2 launch pathplanners bringup.launch.py
To see individual algorithms in action, run individual scripts.
ros2 run pathplanners <algorithm_name>
Executable list
- bfsReplace these with <algorithm_name> to run the specific algorithm
├── launch
│ └── bringup.launch.py
│
├── media
│ ├── bfs.gif
│ ├── bfs.webm
│ └── playground.png
│
├── pathplanners
│ ├── breadthfirstsearch.py
│ ├── __init__.py
│ ├── map.py
│
├── rviz
│ └── visualizer.rviz
│
├── README.md
│
├── package.xml
├── setup.cfg
└── setup.py