Approximate 3D Euclidean Shortest Paths for Unmanned Aircraft in Urban Environments.

This paper introduces a fast algorithm that finds collision-free 3D paths for unmanned aircraft in urban environments. These environments are represented by a three-dimensional scenario in which obstacles are vertical polyhedra. This algorithm uses a method to reduce the number of obstacles taken into account in the path finding process. This method is combined with an algorithm that computes approximate Euclidean shortest paths, which has been adapted to suit this kind of scenarios. Instead of focusing on reducing the asymptotic worst-case running time of the algorithm in unrealistic cases, this approach aims to reduce the computation time in a more practical situation. Experimental cases are provided comparing our approach to existing methods in the literature, showing it is very competitive both in terms of speed and solution quality. [ABSTRACT FROM AUTHOR]