Wavefront expansion algorithm
 | This article, Wavefront expansion algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
Before a robot is able to navigate in a map he needs a plan.[1] The plan is equal to a trajectory from start to goal and describes for each moment in time and each position on the map, what the next action for the robot will be. The topic of pathplanning is addressed with many different algorithms, which can be divided into sampling based and heuristics based approaches.
Before a path planning can be realized, the map is discretized into a grid. The vector information are converted into a 2d array and stored in the RAM of the computer. The potential field pathplanning algorithm is determine for each of the cell a direction for the robot. The direction field is shown as an overlay to the map which contains of the robot and the obstacle. The open question for the potential field algorithm is: which cell is labeled with which direction?. In most cases this is answered with a sampling based planner.
Sampling based motion planning has the problem to utilize a large amount of cpu-ressources and it will stuck in local minima. To overcome the issues, the wavefront expansion was introduced as an advanced form of a potential field path planning algorithm.[2][3] It is working by a growing circle around the robot which is realized as a breadth first search algorithm.[4] That means, the Nearest neighbor around the robot are analyzed first and then the radius of the circle is extended to far distances.
The sliding wavefront expansion algorithm includes of a cost function as an additional heuristics for path planning.[5] Like other sampling based motion planner the main disadvantage is, that it's working on pure geometrical level. That means, the map isn't interpreted as a semantic one which contains of sub paths, but the idea is to utilize mathematical objectives like distances from obstacles and gradient search for the pathplanning algorithm.
Implementation
The existing practical implementation of the wavefront expansion algorithm at github are using a queue to store virtual waves which are build around the robot. The wave datastructure is utilized by the overall planner to determine the path of the robot. A typical implementation can be realized in 200 lines of code in Python programming language.
References
- ^ Chytra Pawashe and Metin Sitti (2006). "Two-dimensional vision-based autonomous microparticle manipulation using a nanoprobe". Journal of Micromechatronics. 3 (3). Brill: 285–306. doi:10.1163/156856306777924671.
- ^ Miraglia, Giovanni and Hook, IV (2019). "A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints". arXiv:1910.06460.
{{cite arXiv}}: CS1 maint: multiple names: authors list (link) - ^ Soulignac, Michael and Taillibert, Patrick (2006). Fast trajectory planning for multiple site surveillance through moving obstacles and wind. Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group. pp. 25--33.
{{cite conference}}: CS1 maint: multiple names: authors list (link) - ^ Simonin, Olivier and Charpillet, Francois and Thierry, Eric (2007). "Collective construction of numerical potential fields for the foraging problem". Research Report RR-6171, Inria-00143302v1.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ Michaël Soulignac (2011). "Feasible and Optimal Path Planning in Strong Current Fields". IEEE Transactions on Robotics. 27 (1). Institute of Electrical and Electronics Engineers (IEEE): 89--98. doi:10.1109/tro.2010.2085790.