Probabilistic Roadmaps for Aerial Relay Path Planning

Unmanned aerial vehicles (UAVs) with on-board relays can be used to establish multi-hop links that deliver high-speed connectivity beyond cell limits. This is of utmost importance e.g. in remote areas and in emergency scenarios. However, jointly designing the trajectories of multiple such flying relays is a complex task since the dimensionality of the underlying configuration space is too large to allow the direct application of traditional shortest-path methods. To bypass this difficulty, this work proposes a probabilistic roadmap algorithm based on a novel heuristic path design which is guaranteed to provide feasible paths for all UAVs under general conditions. This addresses the limitations of existing algorithms, which are typically based on non-linear optimization and, therefore, entail high complexity and cannot readily accommodate the presence of obstacles such as buildings. As corroborated via numerical experiments in an urban environment, the proposed scheme can establish a high-speed link with a user by means of just two aerial relays in a short time.