Approaches to a Dynamic Pathfinding Algorithm

Question

My A* implementation works well for my static environment. If I would now like to work with a dynamic environment, i.e. certain costs between my nodes change while we are traversing from the start to the finish.

From my reading so far I have found the LPA*, D* and D* Lite algorithm that could help me. Well my worst case scenario would be to implement all and see what works best.

Is there any research done on comparing the capabilities of these algorithms? The papers that I have read so far just focus on a single algorithm at a time and since their experiment environments are different, it is hard to make a comparison.

**Some background information: I'm using C++ and my environment is a 3d scene with my search graph being represented using navmeshes.

Answer 1

Maybe this paper could help you, Reactive Deformation Roadmaps: Motion Planning of Multiple Robots in Dynamic Environments by Russell Gayle Avneesh Sud Ming C. Lin Dinesh Manocha; The abstract goes like this:

We present a novel algorithm for motion planning of multiple robots amongst dynamic obstacles. Our approach is based on a new roadmap representation that uses deformable links and dynamically retracts to capture the connectivity of the free space. We use Newtonian Physics and Hooke’s Law to update the position of the milestones and deform the links in response to the motion of other robots and the obstacles. Based on this roadmap representation, we describe our planning algorithms that can compute collision-free paths for tens of robots in complex dynamic environments.

They present an algorithm that is physically-based, adaptive roadmap representation that retracts and changes its topology as a function of the dynamic environment. Iit can be used to plan the motion of a single robot or multiple robots among dynamic obstacles.