  Autonomous unmanned aerial vehicles (UAVs) can be utilized as aerial relays
to serve users far from terrestrial infrastructure. Existing algorithms for
planning the paths of multiple aerial relays cannot generally accommodate
flight constraints. These are imposed by the presence of obstacles, such as
buildings, and by regulations, which include altitude limits, minimum distance
to people, and no-fly zones to name a few. Existing schemes for UAV path
planning typically handle these constraints via shortest-path algorithms.
However, in the context of aerial relays, the large number of degrees of
freedom renders such an approach unaffordable. To bypass this difficulty, this
work develops a framework built upon the notion of probabilistic roadmaps that
allows the optimization of different communication performance metrics while
preserving connectivity between the relays and the base station throughout the
trajectory. To counteract the large number of configuration points required by
conventional probabilistic roadmaps, a novel node generation scheme is
developed based on two heuristics with theoretical guarantees, one for static
users and another for moving users. Numerical experiments demonstrate that the
proposed scheme can effectively serve the user by means of just two aerial
relays.
