Ask Your Question

Why navfn is using Dijkstra?

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 close merge delete

3 Answers

Sort by ยป oldest newest most voted

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 :)

more

Comments

2

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.

( 2012-05-26 09:23:01 -0500 )edit
1

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

( 2014-11-12 17:54:27 -0500 )edit
1

I believe it's talking about free time

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

For completeness, I had the free cycles and I created an A* version here: https://github.com/ros-planning/navigation/tree/hydro-devel/global_planner

more

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.

EDIT:

"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

more

Comments

8

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.

( 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).

( 2012-02-24 03:17:43 -0500 )edit
3

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.

( 2012-02-24 04:32:19 -0500 )edit
3

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.

( 2012-02-24 05:28:01 -0500 )edit
5

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?

( 2012-02-24 05:29:23 -0500 )edit
1

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

( 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 http://goo.gl/0pJzd

( 2012-03-14 05:31:49 -0500 )edit
1

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

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Stats

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

Seen: 7,439 times

Last updated: Aug 17 '13