This paper studies the multi-vehicle task assignment problem where several dispersed vehicles need to visit a set of target locations in a time-invariant drift field while trying to minimize the total travel time. Using optimal control theory, we first design a path planning algorithm to minimize the time for each vehicle to travel between two given locations in the drift field. The path planning algorithm provides the cost matrix for the target assignment, and generates routes once the target locations are assigned to a vehicle. Then, we propose several clustering strategies to assign the targets, and we use two metrics to determine the visiting sequence of the targets clustered to each vehicle. Mainly used to specify the minimum time for a vehicle to travel between any two target locations, the cost matrix is obtained using the path planning algorithm, and is in general asymmetric due to time-invariant currents of the drift field. We show that one of the clustering strategies can obtain a min-cost arborescence of the asymmetric target vehicle graph where the weight of a directed edge between two vertices is the minimum travel time from one vertex to the other respecting the orientation. Using tools from graph theory, a lower bound on the optimal solution is found, which can be used to measure the proximity of a solution from the optimal. Furthermore, by integrating the target clustering strategies with the target visiting metrics, we obtain several task assignment algorithms. Among them, two algorithms guarantee that all the target locations will be visited within a computable maximal travel time, which is at most twice of the optimal when the cost matrix is symmetric. Finally, numerical simulations show that the algorithms can quickly lead to a solution that is close to the optimal.


    Access

    Download


    Export, share and cite



    Title :

    Clustering-based algorithms for multi-vehicle task assignment in a time-invariant drift field


    Contributors:
    Bai, Xiaoshan (author) / Yan, Weisheng (author) / Cao, Ming (author)

    Publication date :

    2017-10-20


    Remarks:

    Bai , X , Yan , W & Cao , M 2017 , ' Clustering-based algorithms for multi-vehicle task assignment in a time-invariant drift field ' , IEEE Robotics and Automation Letters , vol. 2 , no. 4 , pp. 2166-2173 . https://doi.org/10.1109/LRA.2017.2722541



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629



    Distributed multi-vehicle task assignment in a time-invariant drift field with obstacles

    Bai, Xiaoshan / Yan, Weisheng / Cao, Ming et al. | BASE | 2019

    Free access

    An integrated multi-population genetic algorithm for multi-vehicle task assignment in a drift field

    Bai, Xiaoshan / Yan, Weisheng / Ge, Shuzhi Sam et al. | BASE | 2018

    Free access

    Hierarchical Task Assignment and Communication Algorithms for Unmanned Aerial Vehicle Flocks

    Ben-Asher, Yosi / Feldman, Sharoni / Gurfil, Pini et al. | AIAA | 2008


    Adjustable Fully Adaptive Cross-Entropy Algorithms for Task Assignment of Multi-UAVs

    Kehao Wang / Xun Zhang / Xuyang Qiao et al. | DOAJ | 2023

    Free access

    Increasing UAV Task Assignment Performance through Parallelized Genetic Algorithms

    Darrah, Marjorie / Niland, William / Stolarik, Brian | AIAA | 2007