ABSTRACT
This chapter presents an algorithm to solve the Dynamic Military Unit Path Finding Problem (DMUPFP) which is based on A. Stentz’s well-known D* algorithm to solve dynamic path finding problems. The MUPFP is the problem of finding a path from a starting point to a destination where a military unit has to move, or be moved, safely while avoiding threats and obstacles and minimising path cost in some digital representation of the actual terrain. The chapter provides an overview of Constraint Programming and Constraint Satisfaction Problems (CSPs). Louise Leenen et al. defined and implemented a modified A* search algorithm to solve the static MUPFP formulated as a CSP. This algorithm maintains a list of potential solutions from the designated start node to the designated destination node. The dynamic version of the MUPFP allows for changes in the graph at any time. The D* algorithm only considers possible changes to edge costs after it has calculated a potential optimal path.
