Pathfinding with Dynamic Obstacles

Question

I am implementing a simulation that requires me to have some pathfinding.

A* works fine for me when my environment does not change.

LPA* and D* Lite work fine for me when I encounter a static obstacle that is not on my original map.

However, how do I handle the situation when these obstacles are moving at a certain velocity?

Is there a variant of the LPA* or D* Lite algorithm that handles this?

OR Do I have to combine some form of steering behavior with these algorithms?

Ultimately in my simulation, I want to have my 'agent' move from a start point to an endpoint in an environment in which there will be obstacles that move.

Answer 1

Listed below are some criteria that could be used for determining when a recalculation is needed:

1. Every N steps: this guarantees that the information used to calculate the path is not more than N steps old.

2. Whenever extra CPU time is available: this permits dynamic adjustment of path quality; as more units are deployed, or if the game is running on a slower computer, CPU usage per unit can be decreased.

3. Whenever the unit turns a corner or passes a waypoint.

4. Whenever the world near the unit has changed.

This article has great ideas about dynamic A*, which could be useful to you

Anytime Dynamic A*: An Anytime, Replanning Algorithm Maxim Likhachev, Dave Ferguson† Geoff Gordon†, Anthony Stentz†, and Sebastian Thrun Also this article, Randomized Kinodynamic Motion Planning with Moving Obstacles by David Hsu Robert, Kindel Jean-Claude Latombe, Stephen Rock

They should be a good start.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial and Artificial Intelligence Course. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.