ROS Resources: Documentation | Support | Discussion Forum | Index | Service Status | ros @ Robotics Stack Exchange
Ask Your Question

navfn algorism

asked 2011-10-01 17:31:12 -0500

haru gravatar image


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.

And I'd like to understand the quadratic approximation.


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;

Thanks in advance!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2011-10-03 02:15:56 -0500

DimitriProsser gravatar image

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 here.

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.

edit flag offensive delete link more



Is 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?

2ROS0 gravatar image 2ROS0  ( 2014-11-14 13:59:33 -0500 )edit

@2ROS0 It is called 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 start

indraneel gravatar image indraneel  ( 2020-06-25 05:18:39 -0500 )edit

I know this is an old question, but I have had the same doubt about the quadratic approximation. Found this

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.

PLui gravatar image PLui  ( 2020-09-10 07:28:32 -0500 )edit

Question Tools

1 follower


Asked: 2011-10-01 17:31:12 -0500

Seen: 7,238 times

Last updated: Oct 03 '11