Dijkstra Global Path Planner

asked 2013-05-23 08:53:46 -0600

Anis
253 ●22 ●26 ●34

Hello

I wonder whether there is any document that describes the implementation of the Dijkstra algorithm using ROS. I read the navfn API documentation but the code is not clear to me.

My main concern is whether the Dijkstra algorithm make a complete search on all the cells of the grid or a subset. It was indicated that an interpolated version is implemented by I did not see how interpolation can be used with Dijkstra. Any clarification will be very appreciated.

Furthermore, when the global planner navfn computes a path, how this path is expressed? Is it a sequence of cell coordinate in the grid (row ID, Column ID) or sequence of position? Which topic published the path output by navfn?

Thanks for any help

Anis

edit retag flag offensive close merge delete

add a comment

1

answered 2013-06-11 06:33:53 -0600

Dominik
68 ●3 ●5 ●10 http://www.dobots.nl/

I have been trying to make sense of the NavFn code as well but I haven't come to a total understanding yet either. I would be very much interested in a documentation of the NavFn code as well, or at least somebody that can give some more insight to the code. However, I can try to express what I understood so far to give you some help.

The Dijkstra algorithm operates on a potential matrix which is computed from the global costmap. How it is calculated I don't know yet either, it seems to be a function of the distance from the goal, the distance from the start and the distance from obstacles. The potential matrix can be displayed in rviz over the topic ~<name>/potential as a PointCloud by setting the NavFn parameter visualize_potential to true. The potential matrix is expanded in a circular fashion until the goal point is reached. For a detailed description of the Dijkstra algorithm check wikipedia.

The path is then computed using a gradient descent on the potential matrix and is published as a nav_msg/Path on the topic ~<name>/plan. The plan is basically a list of Poses (position and orientation) expressed in your global frame.

edit flag offensive delete link

Comments

Is there any material related to complete understanding of navfn package? Thanks!!

RB ( 2015-02-04 23:44:16 -0600 )edit

I am not able to figure out how the path(grid cells) returned by Dijkstra is used by the gradient descent algorithm. Any thoughts? I thought that gradient descent alone could be used to generate required path.

ParitoshKelkar ( 2016-03-27 19:23:11 -0600 )edit

add a comment

0

answered 2015-02-04 04:51:42 -0600

Martin Günther

11816 ●82 ●159 ●198 https://www.dfki.de/en...

If you're using Hydro or later, you could switch to David Lu's global_planner. It has implementations of several algorithms (A*, Dijkstra) and can also emulate the old navfn behavior, if you wish. Looks like the source code is much easier to digest than navfn.

edit flag offensive delete link

add a comment

0

answered 2013-05-25 03:22:37 -0600

mortonjt
217 ●7 ●8 ●15

I don't think that there is a ROS package that implements Dijkstra's algorithm.

However, I do know that navfn and sbpl_lattice_planner both implement variants of the A* search algorithm. In fact, there is a parameter in sbpl_lattice_planner that demands that the path must be optimal. You may want to check out that package.

edit flag offensive delete link

Comments

navfn employs dijkstra and not A* as of early 2012. See this thread. Since I don't know things have changed since then I'm sorry if you're correct now.