File:Weighted A star with eps 5.gif
Summary
Illustration of <a href="https://en.wikipedia.org/wiki/A*_search_algorithm#Weighted_A.2A" class="extiw" title="w:A* search algorithm">weighted A* search</a> with <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eda109510699d97ff1fc07e22d12f038cb271da9" class="mwe-math-fallback-image-inline mw-math-element" aria-hidden="true" style="vertical-align: -0.338ex; width:7.067ex; height:2.176ex;" alt="{\displaystyle \epsilon =5.0}">, for faster, but sub-optimal path planning. The <a href="https://en.wikipedia.org/wiki/Graph_(mathematics)" class="extiw" title="w:Graph (mathematics)">graph</a> is created by uniform square discretization of a 2-dimensional planar region, placing a node in each discretized cell, and connecting each node with its 8 neighbors using bidirectional edges. Cost of edges are same as their Euclidean lengths. The gray shape represents an obstacle. The filled circles in red & green represent expanded nodes (nodes in closed set). The color indicate the g-score (red:lower g-score, green: higher g-score). The empty nodes with blue boundary are the ones in open set. The nodes of the graph are generated on the fly, and nodes falling inside the obstacle are discarded as inaccessible. The <a href="https://en.wikipedia.org/wiki/Heuristic" class="extiw" title="w:Heuristic">heuristic</a> used by a node is 5 times its <a href="https://en.wikipedia.org/wiki/Euclidean_distance" class="extiw" title="w:Euclidean distance">Euclidean distance</a> to goal (note that <a href="https://en.wikipedia.org/wiki/Euclidean_distance" class="extiw" title="w:Euclidean distance">Euclidean distance</a> to goal is a <a href="https://en.wikipedia.org/wiki/Consistent_heuristic" class="extiw" title="w:Consistent heuristic">consistent heuristic</a>). The final path obtained is suboptimal when compared to the ones obtained using <a href="//commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif" title="File:Dijkstras progress animation.gif">Dijkstra's algorithm</a> or <a href="//commons.wikimedia.org/wiki/File:Astar_progress_animation.gif" title="File:Astar progress animation.gif">A* search algorithm</a>, but the search is significantly faster. Created using <a rel="nofollow" class="external text" href="http://code.google.com/p/yagsbpl/">YGSBPL graph-search library</a> and <a href="https://en.wikipedia.org/wiki/OpenCV" class="extiw" title="w:OpenCV">OpenCV</a>.
Licensing
Lua error in package.lua at line 80: module 'strict' not found.
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 06:13, 13 January 2017 | | 210 × 210 (6 KB) | 127.0.0.1 (talk) | Illustration of <a href="https://en.wikipedia.org/wiki/A*_search_algorithm#Weighted_A.2A" class="extiw" title="w:A* search algorithm">weighted A* search</a> with <span><span class="mwe-math-mathml-inline mwe-math-mathml-a11y mw-math-element" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi>ϵ<!-- ϵ --></mi><mo>=</mo><mn>5.0</mn></mstyle></mrow><annotation encoding="application/x-tex">{\displaystyle \epsilon =5.0}</annotation></semantics></math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eda109510699d97ff1fc07e22d12f038cb271da9" class="mwe-math-fallback-image-inline mw-math-element" aria-hidden="true" style="vertical-align: -0.338ex; width:7.067ex; height:2.176ex;" alt="{\displaystyle \epsilon =5.0}"></span>, for faster, but sub-optimal path planning. The <a href="https://en.wikipedia.org/wiki/Graph_(mathematics)" class="extiw" title="w:Graph (mathematics)">graph</a> is created by uniform square discretization of a 2-dimensional planar region, placing a node in each discretized cell, and connecting each node with its 8 neighbors using bidirectional edges. Cost of edges are same as their Euclidean lengths. The gray shape represents an obstacle. The filled circles in red & green represent expanded nodes (nodes in closed set). The color indicate the g-score (red:lower g-score, green: higher g-score). The empty nodes with blue boundary are the ones in open set. The nodes of the graph are generated on the fly, and nodes falling inside the obstacle are discarded as inaccessible. The <a href="https://en.wikipedia.org/wiki/Heuristic" class="extiw" title="w:Heuristic">heuristic</a> used by a node is 5 times its <a href="https://en.wikipedia.org/wiki/Euclidean_distance" class="extiw" title="w:Euclidean distance">Euclidean distance</a> to goal (note that <a href="https://en.wikipedia.org/wiki/Euclidean_distance" class="extiw" title="w:Euclidean distance">Euclidean distance</a> to goal is a <a href="https://en.wikipedia.org/wiki/Consistent_heuristic" class="extiw" title="w:Consistent heuristic">consistent heuristic</a>). The final path obtained is suboptimal when compared to the ones obtained using <a href="//commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif" title="File:Dijkstras progress animation.gif">Dijkstra's algorithm</a> or <a href="//commons.wikimedia.org/wiki/File:Astar_progress_animation.gif" title="File:Astar progress animation.gif">A* search algorithm</a>, but the search is significantly faster. Created using <a rel="nofollow" class="external text" href="http://code.google.com/p/yagsbpl/">YGSBPL graph-search library</a> and <a href="https://en.wikipedia.org/wiki/OpenCV" class="extiw" title="w:OpenCV">OpenCV</a>. |
- You cannot overwrite this file.
File usage
The following page links to this file:
