Accession Number : ADA259293


Title :   Solution to a Multicriteria Aircraft Routing Problem Utilizing Parallel Search Techniques


Descriptive Note : Master's thesis,


Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING


Personal Author(s) : Grimm, James J , II


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a259293.pdf


Report Date : Dec 1992


Pagination or Media Count : 247


Abstract : Pilots select routes based on factors such as threats, fuel, time on target, distance, and refueling points. This is a time consuming task. This thesis presents the software engineering synthesis of a software tool, based on a parallelized A* search algorithm, to select routes. For simplicity only threats and distance are used. A centralized open list is used with one processor managing the list while the other processors perform the node expansions. This decomposition result in a dynamically load balanced system. A number of parameters are changed to study their impact on the execution time. The use of a branch and bound technique and its impact on the execution time is studied. Other parameters examined are the size of the supercomputer and granularity of the algorithm. It is important to match the software granularity to the architecture to ensure maximum utilization of the supercomputer and minimize execution time. Tests were run on both an iPSC/2 and iPSC/860 to determine the effects of the architecture upon the execution time. In conjunction with execution time, the efficient usage of the parallel computer was also examined.... Parallel processing, Search algorithms, Heuristic search, Aircraft routing, Mission planning, Software engineering.


Descriptors :   *PARALLEL PROCESSING , *ROUTING , TEST AND EVALUATION , ALGORITHMS , SOFTWARE ENGINEERING , THREATS , TARGETS , TIME , MISSIONS , REFUELING , FLIGHT PATHS , SUPERCOMPUTERS , EXPANSION , COMPUTER APPLICATIONS , PLANNING , NODES , COMPUTERS , PILOTS , COMPUTER ARCHITECTURE , THESES


Subject Categories : Computer Programming and Software
      Air Navigation and Guidance


Distribution Statement : APPROVED FOR PUBLIC RELEASE