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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Minimum time multi-UGV surveillance


    Additional title:

    Zeitminimale Überwachung mit mehreren unbemannten Bodenfahrzeugen


    Contributors:


    Publication date :

    2009


    Size :

    15 Seiten, 11 Bilder, 27 Quellen





    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English




    Real-time vehicle matching for multi-camera tunnel surveillance

    Jelača, Vedran / Niño Castañeda, Jorge / Frias Velazquez, Andres et al. | BASE | 2011

    Free access



    Multi-vehicle surveillance system

    KESAVAN VIJAY SARATHI / LORTZ VICTOR / GUO XINGANG et al. | European Patent Office | 2015

    Free access

    MULTI-VEHICLE SURVEILLANCE SYSTEM

    KESAVAN VIJAY SARATHI / LORTZ VICTOR / GUO XINGANG et al. | European Patent Office | 2016

    Free access