| ROS Resources: Documentation | Support | Discussion Forum | Index | Service Status | ros @ Robotics Stack Exchange |
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*) ?
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 :)
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
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
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.
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).
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.
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 My hunch is the same: it uses Dijkstra because it was easier to implement, but A* would perform just as good, and likely better.
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
@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?
Asked: 2012-02-23 16:18:59 -0500
Seen: 12,083 times
Last updated: Aug 17 '13
ROS Answers is licensed under Creative Commons Attribution 3.0 Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
