A tree-based algorithm with two wavefronts for path-planning in an unknown discrete environment. The two fronts simultaneously exist and expand. In this version, there is no prior knowledge of the position of goal, therefore, no heuristics can be used.
For a more in-depth overview of the work carried out, check the following pdf report: Dual Wavefront Algorithm
To run this project you will need installed: python 3, numpy, matplotlib, scipy, tkinter, math, subprocess.
python3 main.py
Some demos of the output generated are shown in the following animations (created with Matplotlib).
A simple block scenario simulation is carried out.
In this simulation, it is explicitly shown the tree as it expands. Note that optimum paths are being expanded on-the-go. Therefore, once both "waves" meet, it is only a matter of backtracking through the parent nodes back to the original root.
A more complex layout is proposed by randomly distributing block obstacles in the search space.
A grid of uniformly distributed blocks is input to the dual wavefront planner.
A plan view search space is proposed.
Laberynths are constructed to test the limits of the planner. Firstly, a simple labyrinth is constructed.
A more challenging labyrinth follows.
A labyrinth with multiple holes and simultaneously open tree branches.
A huge laberynth of 99x99 cells grid.
Laberynths generation is taken from:
This project is licensed under the MIT License - see the LICENSE.md file for details.