Fast Graph-Search Algorithms for General-Aviation Flight Trajectory Generation
Eran Rippel, A. Bar-Gill, Nahum Shimkin · Journal of Guidance Control and Dynamics · 2005
We consider numerical algorithms for on-board flight trajectory generation and optimization in three dimensional space. Our approach relies on graph search algorithms, which perform a global search over the set of feasible trajectories. We start by formulating a simplified kinematic model that is appropriate for General Aviation aircraft. The cost function to be optimized includes, the cost function to be optimized accounts for position-dependent criteria such as the flight altitude and terrain clearance. Additional “dynamic” components that involve the angular velocities are introduced to account for riding qualities and pilot workload. Using an approximate grid-based discretization scheme, we transform the continuous optimization problem into a search problem over a finite graph, and apply Dijkstra’s shortest-path algorithm to this problem. To reduce the computation time to acceptable levels, we introduce a novel state reduction technique that leads to sub-optimal search. Further speedup is achieved by heuristic search techniques and hierarchical methods. Performance of the proposed algorithms is evaluated for a trajectory optimization problem with terrain following over a 100 × 100 kilometer area. Our experiments demonstrate the potential of these algorithms, when combined, to provide an on-board solution to realistic flight trajectory generation problems. ∗Graduate student, Department of Electrical Engineering, Technion—Israel Institute of Technology, Haifa, Israel †Department of Aeronautical Engineering, Technion—Israel Institute of Technology, Haifa, Israel ‡Department of Electrical Engineering, Technion—Israel Institute of Technology, Haifa, Israel