The problem of offline path planning for unmanned autonomous vehicles (UAVs) is discussed in this paper. More specifically, the concern is to provide communication links via such vehicles. The paper uses as an illustrative example the case where it is desired to maintain communication between two land-based (fixed) sites using two UAVs to provide the intermediate links. The problem takes into account a number of constraints that arise in real-life situations. First, there is the “fuel penalty,” which incorporates both the costs of remaining aloft and the costs of moving at higher speeds. Second are constraints on position and speed; there may be no-fly zones that must be taken into account. Third are the connectivity constraints that deal with the ability of stations and UAVs to communicate along the chain. It is to be noted that the model does not assume symmetry here. Finally, there are the constraints associated with the geography of the terrain. The problem is set up as a mixed integer linear programing (MILP) problem. Several of the constraints are represented by binary variables (such as the ability to communicate). The problem can be somewhat simplified by using the initial positions to determine the values of some of the binary variables. The MILP problem is solved using either the Gurobi or CPLEX optimization packages.

For the specific example configuration mentioned above, the authors investigate the effect on performance of using various modifications to the pure MILP solutions. They conclude that pre-processing the communication constraints is not in fact worthwhile, whereas pre-processing the terrain constraints does have a positive effect. The paper has enough detail so that the algorithms can be understood with relatively little effort on the reader’s part.