A focussed dynamic path finding algorithm with constraints

摘要

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 path cost in some digital representation of the actual terrain [1]. The MUPFP has to be solved in an environment where information can change whilst the optimal path is being calculated, i.e. obstacles and threats can move or appear and path costs can change. In previous work, the authors formulated the MUPFP as a constraint satisfaction problem (CSP) where path costs are minimised whilst threat and obstacle avoidance constraints are satisfied in a dynamic environment [2]. In this paper the previous algorithm is improved by adding a heuristic to focus the search for an optimal path. Existing approaches to solving path planning problems tend to combine path costs with various other criteria such as obstacle avoidance in the objective function which is being optimised. The authors' approach is to optimise only path costs while ensuring that other criteria such as safety requirements, are met through the satisfaction of added constraints. Both the authors' previous algorithm and the improved version presented in this paper are based on dynamic path planning algorithms presented by Stenz [3], [4]. Stenz's original D∗ algorithm solves dynamic path finding problems (by optimising path costs without satisfying additional constraints) and his Focussed D∗ algorithm employs a heuristic function to focus the search. Stenz's algorithms only optimises path costs; no additional factors such as threat and obstacle avoidance are addressed.