Comparison of Flight-Planning Algorithms in View of Certification Requirements
Pavel Pačes, Vitek Udatny · 2019
In this paper, a comparison of flight path planning algorithms is presented to solve three-dimensional planning problem for a typical flight path scenario for UAV indoor and outdoor applications with oversight into general aviation and paid transport. The algorithms consider the performance of the navigation sensors and expected departure and arrival procedures which use the existing navigation means (VOR, NDB, ILS, GPS). The cruise situation is simplified to GPS navigation and obstacle avoidance. We choose to analyze the selected algorithms from the point of view of the certification issues according to the existing HW and SW requirements on determinism and time consumption. The analysis is made from the point of view of DO-178 standard. We describe the Artificial Intelligence phenomena and discuss the determinism of the currently used algorithms for flight-path panning. Within our work we focus on and summarize advantages and disadvantages of Breadth First Search, A*, Iterative Deepening A*, Theta*, and RRT* algorithms. Their reasoning process and path selection methodology with perspective of aerospace requirements are evaluated. Our main focus will be on the randomization element and uncertainty of these algorithms. We will also describe selected evaluation parameters required by FAA and EASA Technical Standard Order (TSO) documents on electronic systems and what are the conflicts between these requirements and the natural principle of the existing path-planning algorithms.