Automated Path and Mission Planning for Aerial Platforms under Dynamic Conditions and Constraints

The proposal herein merges two novel and different algorithms for unmanned platform dynamic path-planning in obstacle fields. The first employs a recently published technique, Focused Dynamic Programming [1], which offers the benefits of both the LAO* algorithm [2] (LAO* subsumes Dijkstra's algorithm) and the Prioritized Sweeping algorithm [3]. Focused Dynamic Programming uses heuristics to limit the number of states examined during the value iteration so that the value updates are used most effectively. The second algorithm formulates the path optimization as a Mixed Integer Linear Programming problem. This approach is particularly convenient because (i) it allows a wide range of operationally relevant elements to be accounted for in the optimization and (ii) the formulated problem can be immediately solved by existing commercial or non-commercial optimization software. Both of the proposed algorithms appear well-suited to account for multi-objective cost functions and incorporate constraints driven by platform dynamics and rules of engagement. Additionally, the algorithms have been selected because of their potential to produce solutions for rapidly changing battlespace conditions. MIT has already applied Mixed Integer Linear Programming to solve the path planning problem for a highly maneuverable UAV helicopter.