This chapter 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. The authors 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. They 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, they 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 the Tabu search algorithm is known to perform well on various routing problems, they use it as a part of their 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.
Minimum time multi-UGV surveillance
Zeitminimale Überwachung mit mehreren unbemannten Bodenfahrzeugen
2009
15 Seiten, 11 Bilder, 27 Quellen
Conference paper
English