Pathfinding with Dynamic Obstacles

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 in 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 behaviour with these algorithms?

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

---

You might be better to consider breaking the problem into two parts than trying to solve it using a single algorithm.

Character movement has two components: high-level goal selection and pathfinding, and local steering. Pathfinding solves the problem of "I'm here, and I need to know how to get there". Local steering solves the problem of "I'm on my way there and someone just got in my way".

Keep your pathfinding as it is now. What you need to add is the ability for characters to detect obstacles as they are moving along that path and then adjust that local portion of the path to avoid the obstacle.

The book Artificial Intelligence for Games (author site: http://ai4g.com/ and Amazon: http://amzn.to/k9K62F) details several ways to combine pathfinding with collision avoidance. This paper also covers steering algorithms fairly well at a high level. A highly effective technique I've implemented is a steering pipeline, also known as cooperative arbitration.

Any complete answer will depend on your world representation and other factors specific to your implementation, but I hope this helps.

---

This article has great ideas about dynamic A*, which could be usuful 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.

---

You can see a dynamic scene such a static scene that is regularly updated and where you have to recompute the pathfinding at each step/modification of the scene

Cf. regularly update the map with new positions of yours moving objets and recompute the pathfinding at each step

For moving obstacles/objects, add for exemple a marging of one or two "pixels" around moving obstacles/objects on your updated map for to easily handle the fact that they can move to a "random but very near" position during the time of the step

Better, mark the trajectories of the maximum of moving obstacles at the begining and only update on real time specials trajectories such as doors, stairs or moving objects for exemples