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.
Originally posted by DimitriProsser with karma: 11163 on 2011-10-03
This answer was ACCEPTED on the original site
Post score: 11
Original comments
Comment by 2ROS0 on 2014-11-14:
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?
Comment by indraneel on 2020-06-25:
@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 start
Comment by PLui on 2020-09-10:
I 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.