Solving the Multi Observer 3D Visual Area Coverage Scheduling Problem by Decomposition

Abstract

This paper presents two solution methodologies for the Visual Area Coverage Scheduling problem. The objective is to schedule a number of dynamic observers over a given 3D terrain such that the total visual area covered (viewed) over a planning horizon is maximal. This problem is a more complicated extension of the Set Covering Problem, known to be Np-Hard. We present two decomposition based heuristic methods each containing three stages. The first methodology finds a set of area covering points, and then partitions them into routes (cover first, partition second). The second methodology partitions the area into a region for each observer, and then finds the best covering points and routes (partition first, cover second). In each, a last stage determines dwell (view) times so as to maximize the visible coverage smoothly over the terrain. Comparative tests were made for the two methods on real terrains for several scenarios. When comparing the best solutions of both methods the CF-PS method was slightly better. However, because of the increased computation time we suggest that the PF-CS method with a fine terrain approximation be used. This method is faster as partitioning the terrain into separate regions for each observer results in smaller coverage and routing problems. A sensitivity analysis of the number of observation points to the total number of terrain points covered depicted the classical notion of decreasing returns to scale, increasing in a convex manner as the number of observation points was increased. The best method achieved 100 percent coverage of the terrain by using only 2.7 percent of its points as observation points. Experts stated that the computer based solutions can save precious time and help plan observation missions with satisfying results.