2
$\begingroup$

Context: I am working on a 20 cm x 20 cm indoor robot on a 2D terrain and I need to decide on its path planning algorithm.

Algorithms: A* and Fast marching are two popular (and fundamentally different) approaches for path planning for UAVs in 2D terrain.

A star advantages: A* is faster than fast marching because it runs linear in path length whereas fast marching runs linear in map size. Also it has variants which works with dynamic changes in maps.

Fast marching advantages: Both algorithms discretize the 2D space. Fast marching approximates the geodesic distances better than A* (which suffers due to discretization) and hence its optimal results is closer reality than A*'s optimal results.

Question: Is there any body of literature which compares these two algorithms conceptually and empirically? Are there any other awesome algorithms for 2D terrains?

$\endgroup$
1
$\begingroup$

I'm not sure there's a body of literature exactly, but I was able to find at least one article comparing A* to FMM:

Chiang, Chia Hsun, et al. "A comparative study of implementing Fast Marching Method and A* SEARCH for mobile robot path planning in grid environment: Effect of map resolution." 2007 IEEE Workshop on Advanced Robotics and Its Social Impacts. IEEE, 2007.

If there is a thread of articles on the subject, you can look for it by checking its references, as well as other articles that cite this one.

As for other path planning algorithms, you may want to look into sampling-based motion planning. The OMPL project provides both a number of reference implementations and a nice overview of the approach.

| improve this answer | |
$\endgroup$
  • $\begingroup$ From my reading of the above article and other articles, sampling-based motion planning is used for high dimensional spaces. $\endgroup$ – Vivek Bagaria Apr 8 at 2:43
  • 1
    $\begingroup$ They do excel there, yes, but they are effective in lower-dimensional spaces as well. I have successfully used OMPL sampling-based geometric planners to solve navigation problems in 2D. The advantage is that by adjusting the sampling function, it's possible to detach time performance from the environment's size and resolution. $\endgroup$ – xperroni Apr 8 at 12:28
  • $\begingroup$ I will try the OOMPL library! How would you compare that with using A* on hierarchical map? Map: The overall indoor map is a three level map: The top map connects rooms, the middle map connects different parts of in the room, and the bottom map represents these parts in grids. The robot uses the top map to go between rooms, middle map to between parts of a room and so on. Figure: shorturl.at/kzHP8 $\endgroup$ – Vivek Bagaria Apr 9 at 18:00
  • $\begingroup$ Since you already have a graph structure for the two top levels, I'd use A* there, and reserve sampling-based planning to the bottom one. Alternatively I would take advantage of the scalability of sampling-based planning and get rid of the intermediate level, expanding the grid representation to cover entire rooms. $\endgroup$ – xperroni Apr 9 at 18:45
  • $\begingroup$ By the way, if you think my answer was satisfactory, would you mind accepting it? $\endgroup$ – xperroni Apr 9 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.