algorithmgraph-theorypath-finding

Path finding algorithm combining Field D* and Anytime D*


I am looking for a pathfinding algorithm that has a few properties:

  1. Speed is very necessary, and once a goal is selected a suboptimal path needs to be made quickly, and then can be improved upon during motion. This makes me think I need an "anytime algorithm"
  2. The environment has other actors in it, and so changes constantly. This makes me think that an algorithm based on D* or D* Lite, so that the path can be quickly replaced.

These two requirements pointed me to Anytime D*, which seems like it would work fine except for my final requirement:

  1. The returned path must be fast to follow, and direct. Paths produced by Field D* are great examples.

Is there an algorithm that combines the aspects of these two algorithms (Anytime D* and Field D*)? If not, is it possible to include the improvements of Anytime D* in Field D*? Or am I missing something and I already have what I need?


I am writing this later at night in my time, so I won't be able to respond to anything for a few hours. I hope I have enough context.

Thank you for any and all help!


Solution

  • Use Anytime D* and apply path smoothing. Path smoothing has issues where the paths can be suboptimal, but if you're doing an Anytime algorithm it's going to be suboptimal anyways.