Wavefront expansion algorithm - Revision history

Josve05a: added orphan tag

2023-09-05T16:02:41Z

added orphan tag

← Previous revision		Revision as of 16:02, 5 September 2023
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 [[~~Motion_planning~~#Sampling-~~based_algorithms~~\|sampling-based algorithm]].		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.

Citation bot: Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2037/3850

2023-03-13T09:17:58Z

Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2037/3850

← Previous revision		Revision as of 09:17, 13 March 2023
Line 5:		Line 5:

	==Motivation==		==Motivation==
	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 ~~\|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a~~ \|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 [[Motion_planning#Sampling-based_algorithms\|sampling-based algorithm]].		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]].

Vozul: removed barely relevant sidebar

2023-02-28T00:12:44Z

removed barely relevant sidebar

← Previous revision		Revision as of 00:12, 28 February 2023
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}}
	{{Tree search algorithm}}
	[[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]]

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T01:37:18Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 01:37, 29 January 2023
Line 6:		Line 6:

	==Motivation==		==Motivation==
	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 \|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a }}</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 \|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a \|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 [[Motion_planning#Sampling-based_algorithms\|sampling-based algorithm]].		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]].

Citation bot: Alter: template type. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 488/563

2022-02-11T00:05:09Z

Alter: template type. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 488/563

← Previous revision		Revision as of 00:05, 11 February 2022
Line 3:		Line 3:
	[[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]]

	The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite ~~arxiv~~ \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019\|class=cs.RO }}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25–33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>		The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arXiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019\|class=cs.RO }}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25–33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>

	==Motivation==		==Motivation==
Line 13:		Line 13:
	A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the [[Spatial network\|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.<ref>{{cite conference \|doi=10.2514/6.2009-6113 \|year=2009 \|publisher=American Institute of Aeronautics and Astronautics \|author=Anjan Chakrabarty and Jack Langelaan \|title=Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs \|conference=AIAA Guidance, Navigation, and Control Conference }}</ref> That means, it uses metrics like distances from obstacles and [[Gradient method\|gradient search]] for the path planning algorithm.		A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the [[Spatial network\|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.<ref>{{cite conference \|doi=10.2514/6.2009-6113 \|year=2009 \|publisher=American Institute of Aeronautics and Astronautics \|author=Anjan Chakrabarty and Jack Langelaan \|title=Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs \|conference=AIAA Guidance, Navigation, and Control Conference }}</ref> That means, it uses metrics like distances from obstacles and [[Gradient method\|gradient search]] for the path planning algorithm.

	The algorithm includes a [[Loss function\|cost function]] as an additional [[Heuristic (computer science)\|heuristic]] for path planning.<ref>{{cite journal \|doi=10.1109/tro.2010.2085790 \|year=2011 \|publisher=Institute of Electrical and Electronics Engineers (IEEE) \|volume=27 \|number=1 \|pages=89–98 \|author=Michaël Soulignac \|title=Feasible and Optimal Path Planning in Strong Current Fields \|journal=IEEE Transactions on Robotics }}</ref>		The algorithm includes a [[Loss function\|cost function]] as an additional [[Heuristic (computer science)\|heuristic]] for path planning.<ref>{{cite journal \|doi=10.1109/tro.2010.2085790 \|year=2011 \|publisher=Institute of Electrical and Electronics Engineers (IEEE) \|volume=27 \|number=1 \|pages=89–98 \|author=Michaël Soulignac \|title=Feasible and Optimal Path Planning in Strong Current Fields \|journal=IEEE Transactions on Robotics \|s2cid=17622757 }}</ref>

	==Implementation==		==Implementation==

Qwerfjkl (bot): Capitalising short description "path planner similar to potential field method with breadth first search modification" per WP:SDFORMAT (via Bandersnatch)

2022-02-10T22:02:21Z

Capitalising short description "path planner similar to potential field method with breadth first search modification" per WP:SDFORMAT (via Bandersnatch)

← Previous revision		Revision as of 22:02, 10 February 2022
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}}
	{{Tree search algorithm}}		{{Tree search algorithm}}
	[[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]]

24spiders: Fixed sentence that was missing a word

2022-02-10T20:12:28Z

Fixed sentence that was missing a word

← Previous revision		Revision as of 20:12, 10 February 2022
Line 18:		Line 18:
	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 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.

	==References==		==References==

Mike Peel: Removing Commons category link that does not match this article (:commons:Category:Breadth-first search) (Commons category belongs at Breadth-first_search)

2021-11-06T21:29:51Z

Removing Commons category link that does not match this article (commons:Category:Breadth-first search) (Commons category belongs at Breadth-first_search)

← Previous revision		Revision as of 21:29, 6 November 2021
Line 2:		Line 2:
	{{Tree search algorithm}}		{{Tree search algorithm}}
	[[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]]
	{{Commons category\|Breadth-first search}}

	The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019\|class=cs.RO }}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25–33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>		The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019\|class=cs.RO }}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25–33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>

Citation bot: Alter: pages. Add: s2cid, class. Formatted dashes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform

2021-05-22T19:58:34Z

Alter: pages. Add: s2cid, class. Formatted dashes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform

← Previous revision		Revision as of 19:58, 22 May 2021
Line 4:		Line 4:
	{{Commons category\|Breadth-first search}}		{{Commons category\|Breadth-first search}}

	The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019}}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=~~25--33~~ \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>		The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019\|class=cs.RO }}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25–33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>

	==Motivation==		==Motivation==
	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\|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a }}</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 \|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a }}</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 [[Motion_planning#Sampling-based_algorithms\|sampling-based algorithm]].		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]].
Line 14:		Line 14:
	A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the [[Spatial network\|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.<ref>{{cite conference \|doi=10.2514/6.2009-6113 \|year=2009 \|publisher=American Institute of Aeronautics and Astronautics \|author=Anjan Chakrabarty and Jack Langelaan \|title=Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs \|conference=AIAA Guidance, Navigation, and Control Conference }}</ref> That means, it uses metrics like distances from obstacles and [[Gradient method\|gradient search]] for the path planning algorithm.		A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the [[Spatial network\|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.<ref>{{cite conference \|doi=10.2514/6.2009-6113 \|year=2009 \|publisher=American Institute of Aeronautics and Astronautics \|author=Anjan Chakrabarty and Jack Langelaan \|title=Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs \|conference=AIAA Guidance, Navigation, and Control Conference }}</ref> That means, it uses metrics like distances from obstacles and [[Gradient method\|gradient search]] for the path planning algorithm.

	The algorithm includes a [[Loss function\|cost function]] as an additional [[Heuristic (computer science)\|heuristic]] for path planning.<ref>{{cite journal \|doi=10.1109/tro.2010.2085790 \|year=2011 \|publisher=Institute of Electrical and Electronics Engineers (IEEE) \|volume=27 \|number=1 \|pages=~~89--98~~ \|author=Michaël Soulignac \|title=Feasible and Optimal Path Planning in Strong Current Fields \|journal=IEEE Transactions on Robotics }}</ref>		The algorithm includes a [[Loss function\|cost function]] as an additional [[Heuristic (computer science)\|heuristic]] for path planning.<ref>{{cite journal \|doi=10.1109/tro.2010.2085790 \|year=2011 \|publisher=Institute of Electrical and Electronics Engineers (IEEE) \|volume=27 \|number=1 \|pages=89–98 \|author=Michaël Soulignac \|title=Feasible and Optimal Path Planning in Strong Current Fields \|journal=IEEE Transactions on Robotics }}</ref>

	==Implementation==		==Implementation==

85.238.91.68: disambiguate potential field to potential method

2020-03-06T07:55:08Z

disambiguate potential field to potential method

← Previous revision		Revision as of 07:55, 6 March 2020
Line 4:		Line 4:
	{{Commons category\|Breadth-first search}}		{{Commons category\|Breadth-first search}}

	The '''wavefront expansion algorithm''' is a specialized [[potential field]]~~{{dn\|date=March 2020}}~~ path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019}}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25--33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>		The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019}}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25--33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>

	==Motivation==		==Motivation==

← Previous revision		Revision as of 19:58, 22 May 2021
Line 4:		Line 4:
	{{Commons category\|Breadth-first search}}		{{Commons category\|Breadth-first search}}

	The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019}}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=~~25--33~~ \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>		The '''wavefront expansion algorithm''' is a specialized [[potential method\|potential field]] path planner with [[breadth-first search]] to avoid local minima.<ref>{{cite arxiv \|title=A Feedback Motion Plan for Vehicles with Bounded Curvature Constraints \|author=Miraglia, Giovanni and Hook, IV \|eprint=1910.06460 \|year=2019\|class=cs.RO }}</ref><ref>{{cite conference \|title=Fast trajectory planning for multiple site surveillance through moving obstacles and wind \|author=Soulignac, Michael and Taillibert, Patrick \|conference=Proceedings of the Workshop of the UK Planning and Scheduling Special Interest Group \|pages=25–33 \|year=2006}}</ref> It uses a growing circle around the robot. The [[Nearest neighbor search\|nearest neighbors]] are analyzed first and then the radius of the circle is extended to distant regions.<ref>{{cite journal \|title=Collective construction of numerical potential fields for the foraging problem \|author=Simonin, Olivier and Charpillet, Francois and Thierry, Eric \|year=2007 \|journal=Research Report RR-6171, Inria-00143302v1}}</ref>

	==Motivation==		==Motivation==
	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\|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a }}</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 \|url=https://semanticscholar.org/paper/f17c71933185cadfc3427200438bcbadc296830a }}</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 [[Motion_planning#Sampling-based_algorithms\|sampling-based algorithm]].		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]].
Line 14:		Line 14:
	A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the [[Spatial network\|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.<ref>{{cite conference \|doi=10.2514/6.2009-6113 \|year=2009 \|publisher=American Institute of Aeronautics and Astronautics \|author=Anjan Chakrabarty and Jack Langelaan \|title=Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs \|conference=AIAA Guidance, Navigation, and Control Conference }}</ref> That means, it uses metrics like distances from obstacles and [[Gradient method\|gradient search]] for the path planning algorithm.		A sampling-based planner works by searching the graph. In the case of path planning, the graph contains the [[Spatial network\|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.<ref>{{cite conference \|doi=10.2514/6.2009-6113 \|year=2009 \|publisher=American Institute of Aeronautics and Astronautics \|author=Anjan Chakrabarty and Jack Langelaan \|title=Energy Maps for Long-Range Path Planning for Small- and Micro- UAVs \|conference=AIAA Guidance, Navigation, and Control Conference }}</ref> That means, it uses metrics like distances from obstacles and [[Gradient method\|gradient search]] for the path planning algorithm.

	The algorithm includes a [[Loss function\|cost function]] as an additional [[Heuristic (computer science)\|heuristic]] for path planning.<ref>{{cite journal \|doi=10.1109/tro.2010.2085790 \|year=2011 \|publisher=Institute of Electrical and Electronics Engineers (IEEE) \|volume=27 \|number=1 \|pages=~~89--98~~ \|author=Michaël Soulignac \|title=Feasible and Optimal Path Planning in Strong Current Fields \|journal=IEEE Transactions on Robotics }}</ref>		The algorithm includes a [[Loss function\|cost function]] as an additional [[Heuristic (computer science)\|heuristic]] for path planning.<ref>{{cite journal \|doi=10.1109/tro.2010.2085790 \|year=2011 \|publisher=Institute of Electrical and Electronics Engineers (IEEE) \|volume=27 \|number=1 \|pages=89–98 \|author=Michaël Soulignac \|title=Feasible and Optimal Path Planning in Strong Current Fields \|journal=IEEE Transactions on Robotics }}</ref>

	==Implementation==		==Implementation==