Charles B. McVey, David P. Clements, Barton C. Massey, and Andrew J. Parkes, University of Oregon
We consider the common problem of calculating routes from a starting point to a destination through a given space. This process typically involves discretizing the navigational space into a graph of intermediate waypoints linked together through transitions. A search for a solution that fits desired criteria can then be performed. Typical criteria include: minimum distance, minimum transit time, minimum fuel use, and maximum agent safety. Our work in this area focuses on the rapid determination of minimal fuel routes for aircraft to fly from any source point to any destination point on the earth. The Worldwide Aeronautical Route Planner (WARP) is our prototype demonstration of technology developed to perform optimal real-time (under one minute per route) flight planning. WARP uses high-fidelity aircraft flight models, standard rules of flight operation, actual time-dependent worldwide weather data, and a variant of A* (Multi-Pass A*) which retains A*’s completeness and optimality properties. WARP discovers the flight plan that guarantees minimal use of fuel. Typical routes are generated by WARP in under thirty seconds, with fuel savings on the order of one to eight percent compared to great circle (minimum distance) routes.