Wavefront expansion algorithm: Difference between revisions
Citation bot (talk | contribs) Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2037/3850 |
m added orphan tag |
||
| Line 1: | Line 1: | ||
{{Short description|Path planner similar to potential field method with breadth first search modification}} |
{{Short description|Path planner similar to potential field method with breadth first search modification}} |
||
{{Orphan|date=September 2023}} |
|||
[[File:Rapid-parallel-path-planning-by-propagating-wavefronts-of-spiking-neural-activity-Movie1.ogv|thumb|Path planning is realized with propagating wavefronts]] |
[[File:Rapid-parallel-path-planning-by-propagating-wavefronts-of-spiking-neural-activity-Movie1.ogv|thumb|Path planning is realized with propagating wavefronts]] |
||
| Line 7: | Line 9: | ||
Before a robot is able to navigate a map it needs a plan.<ref>{{cite journal |doi=10.1163/156856306777924671 |year=2006 |publisher=Brill |volume=3 |number=3 |pages=285–306 |author=Chytra Pawashe and Metin Sitti |title=Two-dimensional vision-based autonomous microparticle manipulation using a nanoprobe |journal=Journal of Micromechatronics|s2cid=18241136 |doi-access=free }}</ref> The plan is a trajectory from start to goal and describes, for each moment in time and each position in the map, the robot's next action. [[Pathfinding|Path planning]] is solved by many different algorithms, which can be categorised as sampling-based and heuristics-based approaches. |
Before a robot is able to navigate a map it needs a plan.<ref>{{cite journal |doi=10.1163/156856306777924671 |year=2006 |publisher=Brill |volume=3 |number=3 |pages=285–306 |author=Chytra Pawashe and Metin Sitti |title=Two-dimensional vision-based autonomous microparticle manipulation using a nanoprobe |journal=Journal of Micromechatronics|s2cid=18241136 |doi-access=free }}</ref> The plan is a trajectory from start to goal and describes, for each moment in time and each position in the map, the robot's next action. [[Pathfinding|Path planning]] is solved by many different algorithms, which can be categorised as sampling-based and heuristics-based approaches. |
||
Before path planning, the map is [[Discretization|discretized]] into a grid. The vector information is converted into a 2D array and stored in memory. The potential field path planning algorithm determines the direction of the robot for each cell. This direction field is shown overlaid on the [[Robotic mapping|robotic map]] containing the robot and the obstacles. The question for the potential field algorithm is: which cell is labeled with which direction? This can be answered with a [[ |
Before path planning, the map is [[Discretization|discretized]] into a grid. The vector information is converted into a 2D array and stored in memory. The potential field path planning algorithm determines the direction of the robot for each cell. This direction field is shown overlaid on the [[Robotic mapping|robotic map]] containing the robot and the obstacles. The question for the potential field algorithm is: which cell is labeled with which direction? This can be answered with a [[Motion planning#Sampling-based algorithms|sampling-based algorithm]]. |
||
==Wavefront expansion== |
==Wavefront expansion== |
||
| Line 15: | Line 17: | ||
==Implementation== |
==Implementation== |
||
Practical open-source implementations of the algorithm are available. The map of the world is provided as an array. Obstacles and the start position of the robot are given by special values in the array. The solver determines the goal direction in the imagined wave. |
Practical open-source implementations of the algorithm are available. The map of the world is provided as an array. Obstacles and the start position of the robot are given by special values in the array. The solver determines the goal direction in the imagined wave. |
||
Existing implementations use a [[Queue (abstract data type)|queue]] to store a wave data structure created around the robot. A typical implementation in [[Python (programming language)|Python]] can be realized in around 200 lines of code. |
Existing implementations use a [[Queue (abstract data type)|queue]] to store a wave data structure created around the robot. A typical implementation in [[Python (programming language)|Python]] can be realized in around 200 lines of code. |
||
Latest revision as of 16:02, 5 September 2023
The wavefront expansion algorithm is a specialized potential field path planner with breadth-first search to avoid local minima.[1][2] It uses 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
[edit]Before a robot is able to navigate a map it needs a plan.[4] The plan is a trajectory from start to goal and describes, for each moment in time and each position in the map, the robot's next action. Path planning is solved by many different algorithms, which can be categorised as sampling-based and heuristics-based approaches.
Before path planning, the map is discretized into a grid. The vector information is converted into a 2D array and stored in memory. The potential field path planning algorithm determines the direction of the robot for each cell. This direction field is shown overlaid on the robotic map containing the robot and the obstacles. The question for the potential field algorithm is: which cell is labeled with which direction? This can be answered with a sampling-based algorithm.
Wavefront expansion
[edit]A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the spatial nodes which can be observed by the robot. The wavefront expansion increases the performance of the search by analyzing only nodes near the robot. The decision is made on a geometrical level which is equal to breadth-first search.[5] That means, it uses metrics like distances from obstacles and gradient search for the path planning algorithm.
The algorithm includes a cost function as an additional heuristic for path planning.[6]
Implementation
[edit]Practical open-source implementations of the algorithm are available. The map of the world is provided as an array. Obstacles and the start position of the robot are given by special values in the array. The solver determines the goal direction in the imagined wave.
Existing implementations use a queue to store a wave data structure created around the robot. A typical implementation in Python can be realized in around 200 lines of code.
References
[edit]- ^ Miraglia, Giovanni and Hook, IV (2019). "A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints". arXiv:1910.06460 [cs.RO].
{{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. S2CID 18241136.
- ^ 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. S2CID 17622757.