Minimum time multi-UGV surveillance, CCO 2008

Minimum time multi-UGV surveillance

David A. Anisi

Optimization and Systems Theory, Royal Institute of Technology (KTH), Stockholm, Sweden

Petter Ögren

Dept. of Autonomous Systems, Swedish Defence Research Agency (FOI), Stockholm, Sweden

ABSTRACT:

This paper addresses the problem of concurrent task- and path planning for a number of surveillance Unmanned Ground Vehicles (UGVs) such that a user defined area of interest is covered by the UGVs' sensors in minimum time.

We first formulate the problem, and show that it is in fact a generalization of the Multiple Traveling Salesmen Problem (MTSP), which is known to be NP-hard. We then propose a solution that decomposes the problem into three subproblems. The first is to find a maximal convex covering of the search area. Most results on static coverage use disjoint partitions of the search area, e.g. triangulation, to convert the continuous sensor positioning problem into a discrete one. However, by a simple example, we show that a highly overlapping set of maximal convex sets is better suited for minimum time coverage.

The second subproblem is a combinatorial assignment and ordering of the sets in the cover. Since Tabu search algorithms are known to perform well on various routing problems, we use it as a part of our proposed solution.

Finally, the third subproblem utilizes a particular shortest path sub-routine in order to find the vehicle paths, and calculate the overall objective function used in the Tabu search. The proposed algorithm is illustrated by a number of simulation examples.