Robotics StackExchange | Archived questions

questions about dijkstra algorithm used in navfn package to path planning

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?

  1. 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!

Asked by jxl on 2014-05-14 02:35:19 UTC

Comments

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

Asked by RB on 2015-01-25 12:49:24 UTC

@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.

Asked by jxl on 2015-03-03 02:50:19 UTC

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

Asked by RB on 2015-05-02 00:52:52 UTC

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

Asked by jxl on 2015-05-06 21:12:53 UTC

Answers

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

Asked by indraneel on 2020-06-25 05:38:38 UTC

Comments