Special Lecture

Scheduled Talk - February 12, 2010 - [ 3:00PM in DH 1064 ]

Oleg Burdakov
Department of Mathematics
Linköping University

"Optimal Positioning of Unmanned Aerial Vehicles for Surveillance"

Relay chains of unmanned aerial vehicles (UAVs) are often used to survey some target located in one point and convey the gathered information back to a base station located in another point. Optimal positioning of UAVs is an important problem. The objective function here could access, for instance, the communication and surveillance quality, or it could make favored the positions which are well distant from obstacles over those which are closer to obstacles.

The placement of UAVs is restricted not only by the presence of obstacles, but also by the free line of sight requirement for every consecutive pair of UAVs in the chain, a limited communication range, and a limited number of available UAVs. For any fixed number of UAVs, the feasible set of placements is typically disjoint, and the number of disjoint subsets may grow exponentially with the number of obstacles. This makes the optimal positioning a difficult multi-extremal problem which is required to be solved in real time mode almost immediately after the target position becomes available.

We present here a dynamic programming approach which allows solving efficiently this global optimization problem. In the framework of this approach, we have developed two label correcting algorithms which return for each target position all Pareto optimal solutions of the multiextremal problem of minimizing both the original objective function and the number of UAVs. We present results of numerical 3D experiments which demonstrate the efficiency of our approach.

We extend our approach to the case of multi-target surveillance. Since it is far more difficult than the one-target case, some heuristics are offered.