Constraint-based solver for the Military unit path finding problem

Abstract

The authors describe the first phase development of a path finding simulation in a military environment. This concept demonstrator can be used for mission planning by constructing what if scenarios to investigate trade-offs such as location of deployment and mode of transport. The Military Unit Path Finding Problem (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 whilst avoiding threats and obstacles and minimising costs in a digital representation of the real terrain. Although significant research has been done on path finding, the success of a particular technique relies on the environment and existing constraints. The MUPFP is ideal for a constraint-based approach because it requires flexibility in modelling. The authors formulate the MUPFP as a constraint satisfaction problem and a constraint-based extension of the search algorithm. The concept demonstrator uses a provided map, for example taken from Google Earth, on which various obstacles and threats can be manually marked. Our constraint based approach to path finding allows for flexibility and ease of modelling. It has the advantage of modelling new environments or additional constraints with ease, and it produces near optimal solutions if solving is halted prematurely.