Ergin Sezer

Date of Award


Document Type


Degree Name

Master of Science


Department of Electrical and Computer Engineering

First Advisor

Gary B. Lamont, PhD


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 combinatorial 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.

AFIT Designator


DTIC Accession Number



The author's Vita page is omitted.

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