Multiple UAVs trajectory generation and waypoint assignment in urban environment based on DOP maps

This paper tackles strategic path planning for a multi-UAV routing problem in low altitude urban environment, where GNSS coverage challenges typically affect navigation performance and thus autonomous flight capabilities. These issues are addressed with a multi-step strategy that includes automated definition of GNSS-challenging volumes based on a georeferenced three-dimensional environment model, derivation of candidate obstacle-free paths between waypoints, waypoint assignment and definition of time-tagged trajectories for all UAVs. In all the steps, attention is paid to limiting the computational burden, thus ensuring applicability in real mission scenarios. Going beyond binary logics which consider GNSS-challenging volumes as obstacles, a discrete number of dilution of precision levels is considered, leading to different three-dimensional maps of the environment defined as "DOP layers". Then, the basic idea to ensure that the designed trajectories are "flyable" with given positioning accuracy requirements is to take navigation performance into account at waypoint assignment level, using propagated covariance as a metric. The approach thus combines "navigation aware" planning with multi-vehicle task assignment, generating a solution that depends on the sensors embarked onboard the UAVs, and can be naturally extended to account for multi-sensor-based navigation architectures and ground-infrastructure support. The algorithm is tested in simulations based on a real world scenario, considering a wide combination of input parameters in terms of positioning error threshold, maximum UAV velocity, number of UAVs, navigation sensors performance, and mission epoch. (C) 2021 Published by Elsevier Masson SAS.