Ask Your Question
1

Dijkstra Global Path Planner

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

Anis gravatar image

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

3 Answers

Sort by » oldest newest most voted
1

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

Dominik gravatar image

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 more

Comments

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

RB gravatar image RB  ( 2015-02-04 23:44:16 -0500 )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 gravatar image ParitoshKelkar  ( 2016-03-27 19:23:11 -0500 )edit
0

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

mortonjt gravatar image

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 more

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.

130s gravatar image 130s  ( 2013-05-25 08:40:36 -0500 )edit

Oops. I must have read that a little hastily. Yeah, your right. They are definitely using Dijkstra's algorithm in the source code.

mortonjt gravatar image mortonjt  ( 2013-05-26 03:31:34 -0500 )edit
0

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

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 more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2013-05-23 08:53:46 -0500

Seen: 1,533 times

Last updated: Feb 04 '15