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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$
5
  • $\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, 2020 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, 2020 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, 2020 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, 2020 at 18:45
  • $\begingroup$ By the way, if you think my answer was satisfactory, would you mind accepting it? $\endgroup$
    – xperroni
    Apr 9, 2020 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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