M.Sc Thesis

M.Sc StudentRippel Eran
SubjectReal-Time Digital-Map-Based Algorithms for General Aviation
Flight Trajectory Generation
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Nahum Shimkin
PROF. Aharon Bar-Gill


We consider numerical algorithms for real-time flight trajectory generation and optimization. The proposed approach relies on fast single-pass (Dijkstra) algorithms, that solve the shortest-path problem over finite graphs. The cost function to be optimized includes both standard criteria, such as minimal time and height requirements as well as terrain following costs and additional components quantifying pilot workload and riding qualities. Using a grid-based discretization scheme, we transform the continuous optimization problem into an approximate search problem over a finite graph. This is the breakthrough that enables real-time performance. Each vertex in this graph corresponds to two consecutive spatial points, which allows to account for angular acceleration components in the link costs. To obtain the optimal path for the discretized problem, we apply Dijkstra's shortest path algorithm, and indicate certain modifications that are required to account for flight constraints. Further significant speedup is achieved through state-reduction and hierarchical methods. Combined, these methods yield a real-time solution to realistic flight trajectory generation problems. The proposed algorithms are simulated and compared using digital map data over a 100km2 terrain. We also explore briefly the applicability of more elaborate discretization schemes that lead to numerically consistent search algorithms, such as Fast Marching, albeit their use is restricted to highly simplified cost functions.