Wavefront expansion algorithm
Template:Tree search algorithm
The wavefront expansion algorithm is a specialized potential field path planner which is working with breadth-first search to avoid local minima.[1][2] It is using a growing circle around the robot. The nearest neighbors are analyzed first and then the radius of the circle is extended to distant regions.[3]
Motivation
Before a robot is able to navigate in a map he needs a plan.[4] The plan is equal to a trajectory from start to goal and describes for each moment in time and each position in 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 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 determines for each cell a direction for the robot. The direction field is shown as an overlay to the map which contains of the robot and the obstacles. The open question for the potential field algorithm is: which cell is labeled with which direction?. This can be answered with an sampling-based algorithm.
Wavefront expansion
A sampling based planner is working with a search in the graph. In the case of pathplanning, the graph contains of spatial nodes which can be observed by the robot. The wavefront expansion is increasing the performance of graph search by analyzing only nodes which have a small distance to the robot. The decision is made on a geometrical level which is equal to breadth-first search.[5] That means, the map isn't interpreted as a Linguistic map which contains of sub paths, but the idea is to utilize mathematical objectives like distances from obstacles and gradient search for the pathplanning algorithm.
The sliding wavefront expansion algorithm includes a cost function as an additional heuristic for path planning.[6]
Implementation
Practical implementations of the wavefront expansion algorithm are available at github. The map of the world is provided as an array. Obstacles and the start position of the robot are given by special characters in the array. The solver determines the goal direction in the imagined wave. The existing repositories are using a queue to store a wave datastructure which is created around the robot. The 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 the Python programming language.
References
- ^ 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) - ^ 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.
- ^ Anjan Chakrabarty and Jack Langelaan (2009). Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs. AIAA Guidance, Navigation, and Control Conference. American Institute of Aeronautics and Astronautics. doi:10.2514/6.2009-6113.
- ^ 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.
Category:Routing algorithms