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

Why navfn is using Dijkstra?

asked 2012-02-23 16:18:59 -0500

130s gravatar image

updated 2013-02-07 08:46:38 -0500

As an algorithm learner, I'm just curious about why navfn was is first equipped with dijkstra search algorith. The answer at this question explains how navfn works using dijkstra, but what is the reason it was selected instead of other algorithms that are equally good (e.g. A*) ?

edit retag flag offensive close merge delete

3 Answers

Sort by ยป oldest newest most voted

answered 2012-05-26 09:08:37 -0500

bhaskara gravatar image

If you look at the navfn code, you'll see that there is in fact an optimized A* algorithm in there. It was not used because there was a bug and nobody had the cycles to fix it. IMO there's a lot of premature optimization here, given that global planning does not need to be happening that often. The right thing to do is to use a principled and efficient A* implementation such as sbpl :)

edit flag offensive delete link more



While Dimitri's answer initiated a meaningful discussion, I thought I have to choose this response as a more direct answer to my particular question.

130s gravatar image 130s  ( 2012-05-26 09:23:01 -0500 )edit

what do you mean by nobody had the "cycles to fix it" ?

2ROS0 gravatar image 2ROS0  ( 2014-11-12 17:54:27 -0500 )edit

I believe it's talking about free time

Void gravatar image Void  ( 2018-11-16 13:55:01 -0500 )edit

Are you sure it is using an Optimized A* ? ROS wiki says "support for an A* heuristic may also be added in the near future". You mean they have already added A* support but never edited their description in ROS wiki?

navid gravatar image navid  ( 2019-10-10 05:17:20 -0500 )edit

answered 2013-08-17 09:29:30 -0500

David Lu gravatar image

For completeness, I had the free cycles and I created an A* version here:

edit flag offensive delete link more

answered 2012-02-24 02:58:35 -0500

DimitriProsser gravatar image

updated 2012-02-24 05:07:06 -0500

Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning.

I have to disagree with @ben, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route.

The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal.

A great way to understand these two algorithms is to look at the wikipedia pages for A* and Dijkstra's and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly.


"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."

Source: this paper

edit flag offensive delete link more



With the risk of sounding pedanitc, isn't A* guaranteed to be optimal when the heuristic does not overestimate the distance to the goal? Euclidean or Manhattan distances should produce optimal paths with A*, on grid maps.

Ivan Dryanovski gravatar image Ivan Dryanovski  ( 2012-02-24 03:10:25 -0500 )edit

A* can certainly produce optimal paths with the correct heuristic. Speaking general terms, however, it's more likely that A* will be sub-optimal than Dijkstra's (if you consider a wide variety of situations).

DimitriProsser gravatar image DimitriProsser  ( 2012-02-24 03:17:43 -0500 )edit

When planning 2D paths for a robot, when would euclidian or manhattan distance heuristics not be admissible? I can't imagine a situation when the straight-lilne distance would be an overestimate.

Dan Lazewatsky gravatar image Dan Lazewatsky  ( 2012-02-24 04:32:19 -0500 )edit

With risk of sounding super-pedantic: A* is guaranteed to be optimal as A* requires an admissible heuristik (otherwise it's not A*). Manhattan and Euclidian are admissible on gridmaps.

dornhege gravatar image dornhege  ( 2012-02-24 05:28:01 -0500 )edit

A* also guarantees minimal number of nodes expanded, so the only reason to be less performant than Dijkstra's would be if the heuristic computation is slowing it down. Maybe the answer to the question is just: Because it was easier to implement and doesn't require heuristics?

dornhege gravatar image dornhege  ( 2012-02-24 05:29:23 -0500 )edit

@dornhege My hunch is the same: it uses Dijkstra because it was easier to implement, but A* would perform just as good, and likely better.

Ivan Dryanovski gravatar image Ivan Dryanovski  ( 2012-02-24 05:50:14 -0500 )edit

Thanks. Btw it seems to me that A* is also implemented and not just in use (navfn::NavFn Class). It's just NavfnROS::computePotential calls the one that's associated with Dijkstra (navfn_ros.cpp), although I've not found if A* function is tested. I opened a ticket

130s gravatar image 130s  ( 2012-03-14 05:31:49 -0500 )edit

@DimitriProsser: The paper you linked to does not claim that Dijkstra's outperforms A*. Instead, it says that A* (and, thus, Dijkstra's) may perform too slowly to use in a game. @IsaacSaito: Since A* will always outperform Dijkstra's, why not remove Dijkstra's from navfn entirely?

mkoval gravatar image mkoval  ( 2012-05-26 04:45:49 -0500 )edit

Question Tools



Asked: 2012-02-23 16:18:59 -0500

Seen: 12,332 times

Last updated: Aug 17 '13