Ask Your Question
1

questions about dijkstra algorithm used in navfn package to path planning

asked 2014-05-14 02:35:19 -0500

jxl gravatar image

Hello,everyone

i am a student from xi’an of China, also a freshman to ROS. when i learning the path planning algorithm of 2d_navigation ,locating in navfn package. like other people ,i found it use Dijkstra algorithm to do it, here are some my questions :

  1. in the navfn/include/navfn/navfn.h (because my karma is insufficient to publish the link,sorry )

    * line 161,what does “ *float *potarr ” mean, What it is used for? What is the difference between “potarr array”and “cost array”?

    * line 167*,what does “ int *curp , int *nextp ,int *overp ”mean,what are they used for?

  2. in the navfn/include/navfn/navfn.cpp, I think like Astar algorithm (basically understand its principle), in the code ,there are two lists, OPEN and CLOSED,where are they ,how does the "updateCell function"line 472,update ?

Any suggestions will be appreciated,thank you very much!

edit retag flag offensive close merge delete

Comments

Have you got the answer? I am also looking for the answer.

RB gravatar image RB  ( 2015-01-25 11:49:24 -0500 )edit

@RB,sorry,i didn't got the answer.i found it was very difficult for me when i took many hours on it .now i am learning other ROS knowledge,if possible ,maybe we can exchange some ideas about ROS.

jxl gravatar image jxl  ( 2015-03-03 01:50:19 -0500 )edit

@jxl, Hi..Sorry to reply late!! No problem, we can discuss ideas about ROS.

RB gravatar image RB  ( 2015-05-02 00:52:52 -0500 )edit

@RB,Hi...Did you know how to save the path published by the global path planner ,link is here

jxl gravatar image jxl  ( 2015-05-06 21:12:53 -0500 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2020-06-25 05:38:38 -0500

indraneel gravatar image

Attempting to answer the questions for whoever that might find them useful :

* line 161,what does “ *float *potarr ” mean, What it is used for? What is the difference between “potarr array”and “cost array”?

Literally speaking, Cost array are the raw cost values for each cell from the 2D cost map and Potarr is the potential that the navfn propogation function assigns to each cell during traversal which can be later used to find the final path using gradient descent.

 line 167*,what does “ int *curp , int *nextp ,int *overp ”mean,what are they used for?

The propogation function uses three priority buffers namely current buffer, next buffer and over buffers, these three pointer variables that you have mentioned point to elements inside the three buffers

n the navfn/include/navfn/navfn.cpp, I think like Astar algorithm (basically understand its principle), in the code ,there are two lists, OPEN and CLOSED,where are they ,how does the "updateCell function"line 472,update ?

Update cell function in navfn has the following steps in brief :

  1. ensure cell does not have lethal obstacle cost
  2. Find potentials of the four neighbouring cells from potarr (potarr is initialised to inifinity by default) and find the lowest potential among them
  3. Calculate new potential of the cell using this lowest potential and the traversibility factor
  4. If this calculated potential is lower than the existing potential of the cell in potarr, assign this potential then use this to calculate the new potentials for neighbouring cells as well and push the neighbours to next/over buffer accordingly
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

1 follower

Stats

Asked: 2014-05-14 02:35:19 -0500

Seen: 391 times

Last updated: Jun 25 '20