Mission Route Planning with Multiple Aircraft and Targets Using Parallel A* Algorithm

The general Mission Route Planning (MRP) Problem is the process of selecting an aircraft flight path in order to fly from a starting point through defended terrain to target(s), and return to a safe destination. MRP is a three-dimensional, multi-criteria path search. Planning of aircraft routes involves an elaborate search through numerous possibilities, which can severely task the resources of the system being used to compute the routes. Operational systems can take up to a day to arrive at a solution due to the combinatoric nature of the problem, which is not acceptable, because time is critical in aviation. Also, the information that the software is using to solve the MRP may become invalid during the computation. An effective and efficient way of solving the MRP with multiple aircraft and multiple targets is desired using parallel computing techniques. Processors find the optimal solution by exploring in parallel the MRP search space. With this distributed decomposition the time required for an optimal solution is reduced as compared to a sequential version. We have designed an effective and scalable MRP solution using a parallelized version of the A* search algorithm. Efficient implementation and extensive testing was done using MPI on clusters of workstations and PCs.