ROS Answers: Open Source Q&A Forum - RSS feedhttps://answers.ros.org/questions/Open source question and answer forum written in Python and DjangoenROS Answers is licensed under Creative Commons Attribution 3.0Thu, 10 Sep 2020 07:28:32 -0500navfn algorismhttps://answers.ros.org/question/11388/navfn-algorism/Hi!
I am using the navfn. The algorithm works perfectly for me, but I would like to know whether there is any documentation about how it works.<p>
And I'd like to understand the quadratic approximation.<p>
<BLOCKQUOTE>
link: [http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473](http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473 "http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473") <p>
00507 // use quadratic approximation
00508 // might speed this up through table lookup, but still have to
00509 // do the divide
00510 float d = dc/hf;
00511 **float v = -0.2301 * d * d + 0.5307 * d + 0.7040;**
00512 pot = ta + hf * v;
</BLOCKQUOTE>
Thanks in advance!
Sat, 01 Oct 2011 17:31:12 -0500https://answers.ros.org/question/11388/navfn-algorism/Answer by DimitriProsser for <p>Hi!</p>
<p>I am using the navfn. The algorithm works perfectly for me, but I would like to know whether there is any documentation about how it works.</p><p></p>
<p>And I'd like to understand the quadratic approximation.</p><p></p>
<p></p><blockquote>
link: <a href="http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473" title="<a href=">http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473</a>"><a href="http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473">http://www.ros.org/doc/diamondback/api/navfn/html/navfn_8cpp_source.html#l00473</a> <p>
00507 // use quadratic approximation <br>
00508 // might speed this up through table lookup, but still have to <br>
00509 // do the divide <br>
00510 float d = dc/hf; <br>
00511 <strong>float v = -0.2301 * d * d + 0.5307 * d + 0.7040;</strong> <br>
00512 pot = ta + hf * v; </p>
<p></p></blockquote>
Thanks in advance!<p></p>
https://answers.ros.org/question/11388/navfn-algorism/?answer=16891#post-id-16891Navfn uses Dijkstra's algorithm to search through the available working area and find the best path. What this means is that navfn uses breadth-first search to check the costmap cells for the optimal path. It begins at the robot's origin and radiates outward, checking each non-obstacle cell in turn until the goal is reached. You can find a primer on Dijkstra's algorithm [here](http://en.wikipedia.org/wiki/Dijkstra's_algorithm).
Navfn's optimal path is based on a path's "potential". The potential is the relative cost of a path based on the distance from the goal and from the existing path itself. It must be noted that Navfn update's each cell's potential in the potential map, or potarr as it's called in navfn, as it checks that cell. This way, it can step back through the potential array to find the best possible path. The potential is determined by the cost of traversing a cell (traversability factor, hf) and the distance away that the next cell is from the previous cell.
The section of code that you posted occurs during the update of a given cell during traversal. The quadratic approximation is used to overcome the limitation that navfn's potential array is four-connected, i.e. it only checks it's top, right, left, and bottom neighbors and not the diagonals. For example, in the section of code that you posted, `tc` is defined as the cell with the lowest of either the left cell or the right cell, and `ta` is the lowest of the top cell or the bottom cell. It then calculates the relative cost between these two cells. Then, the algorithm checks to see if the relative cost of traversing **through** a cell is less than the cost of going around it. If the cost of going around a cell is less than going through it, the algorithm uses the quadratic estimation to determine an approximate cost. Mon, 03 Oct 2011 02:15:56 -0500https://answers.ros.org/question/11388/navfn-algorism/?answer=16891#post-id-16891Comment by PLui for <p>Navfn uses Dijkstra's algorithm to search through the available working area and find the best path. What this means is that navfn uses breadth-first search to check the costmap cells for the optimal path. It begins at the robot's origin and radiates outward, checking each non-obstacle cell in turn until the goal is reached. You can find a primer on Dijkstra's algorithm <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">here</a>.</p>
<p>Navfn's optimal path is based on a path's "potential". The potential is the relative cost of a path based on the distance from the goal and from the existing path itself. It must be noted that Navfn update's each cell's potential in the potential map, or potarr as it's called in navfn, as it checks that cell. This way, it can step back through the potential array to find the best possible path. The potential is determined by the cost of traversing a cell (traversability factor, hf) and the distance away that the next cell is from the previous cell.</p>
<p>The section of code that you posted occurs during the update of a given cell during traversal. The quadratic approximation is used to overcome the limitation that navfn's potential array is four-connected, i.e. it only checks it's top, right, left, and bottom neighbors and not the diagonals. For example, in the section of code that you posted, <code>tc</code> is defined as the cell with the lowest of either the left cell or the right cell, and <code>ta</code> is the lowest of the top cell or the bottom cell. It then calculates the relative cost between these two cells. Then, the algorithm checks to see if the relative cost of traversing <strong>through</strong> a cell is less than the cost of going around it. If the cost of going around a cell is less than going through it, the algorithm uses the quadratic estimation to determine an approximate cost. </p>
https://answers.ros.org/question/11388/navfn-algorism/?comment=361290#post-id-361290I know this is an old question, but I have had the same doubt about the quadratic approximation. Found this https://github.com/locusrobotics/robot_navigation/tree/master/dlux_global_planner#the-kernel
There it explains where the calculation comes from. How does it relate to the ideia of going around the cell in the answer? I mean, the potential is still assigned to the expanded node n, so for me, it is not clear how the algorithm "knows" it should go around instead of trasnversing through the cell.Thu, 10 Sep 2020 07:28:32 -0500https://answers.ros.org/question/11388/navfn-algorism/?comment=361290#post-id-361290Comment by indraneel for <p>Navfn uses Dijkstra's algorithm to search through the available working area and find the best path. What this means is that navfn uses breadth-first search to check the costmap cells for the optimal path. It begins at the robot's origin and radiates outward, checking each non-obstacle cell in turn until the goal is reached. You can find a primer on Dijkstra's algorithm <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">here</a>.</p>
<p>Navfn's optimal path is based on a path's "potential". The potential is the relative cost of a path based on the distance from the goal and from the existing path itself. It must be noted that Navfn update's each cell's potential in the potential map, or potarr as it's called in navfn, as it checks that cell. This way, it can step back through the potential array to find the best possible path. The potential is determined by the cost of traversing a cell (traversability factor, hf) and the distance away that the next cell is from the previous cell.</p>
<p>The section of code that you posted occurs during the update of a given cell during traversal. The quadratic approximation is used to overcome the limitation that navfn's potential array is four-connected, i.e. it only checks it's top, right, left, and bottom neighbors and not the diagonals. For example, in the section of code that you posted, <code>tc</code> is defined as the cell with the lowest of either the left cell or the right cell, and <code>ta</code> is the lowest of the top cell or the bottom cell. It then calculates the relative cost between these two cells. Then, the algorithm checks to see if the relative cost of traversing <strong>through</strong> a cell is less than the cost of going around it. If the cost of going around a cell is less than going through it, the algorithm uses the quadratic estimation to determine an approximate cost. </p>
https://answers.ros.org/question/11388/navfn-algorism/?comment=355781#post-id-355781@2ROS0 It is called Wavefront expansion algorithm https://en.wikipedia.org/wiki/Wavefront_expansion_algorithm but it essentially has the same breadth first search propogation as the conventional dijkstras algorithm, the only difference is instead of constructing a tree of neighbours based on cost traversal, it assumes initially that all cells are at high potential except the start which is at zero potential, assigns finite potential values to each cell during traversal and then uses gradient descent to trace path back from end to startThu, 25 Jun 2020 05:18:39 -0500https://answers.ros.org/question/11388/navfn-algorism/?comment=355781#post-id-355781Comment by 2ROS0 for <p>Navfn uses Dijkstra's algorithm to search through the available working area and find the best path. What this means is that navfn uses breadth-first search to check the costmap cells for the optimal path. It begins at the robot's origin and radiates outward, checking each non-obstacle cell in turn until the goal is reached. You can find a primer on Dijkstra's algorithm <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">here</a>.</p>
<p>Navfn's optimal path is based on a path's "potential". The potential is the relative cost of a path based on the distance from the goal and from the existing path itself. It must be noted that Navfn update's each cell's potential in the potential map, or potarr as it's called in navfn, as it checks that cell. This way, it can step back through the potential array to find the best possible path. The potential is determined by the cost of traversing a cell (traversability factor, hf) and the distance away that the next cell is from the previous cell.</p>
<p>The section of code that you posted occurs during the update of a given cell during traversal. The quadratic approximation is used to overcome the limitation that navfn's potential array is four-connected, i.e. it only checks it's top, right, left, and bottom neighbors and not the diagonals. For example, in the section of code that you posted, <code>tc</code> is defined as the cell with the lowest of either the left cell or the right cell, and <code>ta</code> is the lowest of the top cell or the bottom cell. It then calculates the relative cost between these two cells. Then, the algorithm checks to see if the relative cost of traversing <strong>through</strong> a cell is less than the cost of going around it. If the cost of going around a cell is less than going through it, the algorithm uses the quadratic estimation to determine an approximate cost. </p>
https://answers.ros.org/question/11388/navfn-algorism/?comment=197474#post-id-197474Is there a name for this particular method? Like in the normal Dijkstra's algorithm (taking Euclidean distance from start & goal to be the metric), there is no need to have the potential field with the traversabilitiy factor and the lowest neighbor and all that. What's this particular method called?Fri, 14 Nov 2014 13:59:33 -0600https://answers.ros.org/question/11388/navfn-algorism/?comment=197474#post-id-197474