Ask Your Question
16

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
12

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

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.

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

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

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

I believe it's talking about free time

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

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: https://github.com/ros-planning/navigation/tree/hydro-devel/global_planner

edit flag offensive delete link more
4

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.

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

edit flag offensive delete link 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.

Ivan Dryanovski gravatar imageIvan 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 imageDimitriProsser ( 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.

Dan Lazewatsky gravatar imageDan Lazewatsky ( 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.

dornhege gravatar imagedornhege ( 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?

dornhege gravatar imagedornhege ( 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.

Ivan Dryanovski gravatar imageIvan 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 http://goo.gl/0pJzd

130s gravatar image130s ( 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?

mkoval gravatar imagemkoval ( 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

Question Tools

5 followers

Stats

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

Seen: 7,439 times

Last updated: Aug 17 '13