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:

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

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:

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

• algorithm
• graph-theory
• path-finding

• l'll use this. Thank you! If you put your comment in a answer I will accept it. – Elijah Crum Commented 18 hours ago

1 Answer 1

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.