This study investigates the task assignment problem where a fleet of dispersed vehicles needs to visit multiple target locations in a time-invariant drift field with obstacles while trying to minimise the vehicles' total travel time. The vehicles have different capabilities, and each kind of vehicles can visit a certain type of the target locations; each target location might require to be visited more than once by different kinds of vehicles. The task assignment problem has been proven to be NP-hard. A path planning algorithm is first designed to minimise the time for a vehicle to travel between two given locations through the drift field while avoiding any obstacle. The path planning algorithm provides the travel cost matrix for the target assignment, and generates routes once the target locations are assigned to the vehicles. Then, a distributed algorithm is proposed to assign the target locations to the vehicles using only local communication. The algorithm guarantees that all the visiting demands of every target will be satisfied within a total travel time that is at worst twice of the optimal when the travel cost matrix is symmetric. Numerical simulations show that the algorithm can lead to solutions close to the optimal.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Bai, Xiaoshan (Autor:in) / Yan, Weisheng (Autor:in) / Cao, Ming (Autor:in) / Xue, Dong (Autor:in)

    Erscheinungsdatum :

    2019-11-26


    Anmerkungen:

    Bai , X , Yan , W , Cao , M & Xue , D 2019 , ' Distributed multi-vehicle task assignment in a time-invariant drift field with obstacles ' , IET Control Theory and Applications , vol. 13 , no. 17 , pp. 2886-2893 . https://doi.org/10.1049/iet-cta.2018.6125



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



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

    Bai, Xiaoshan / Yan, Weisheng / Cao, Ming | BASE | 2017

    Freier Zugriff

    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

    Freier Zugriff

    Distributed on-line dynamic task assignment for multi-robot patrolling

    Farinelli, Alessandro / IOCCHI, Luca / NARDI, Daniele | BASE | 2017

    Freier Zugriff

    Task Assignment and Motion Planning in the Presence of Obstacles and Prioritized Targets

    Gottlieb, Y. / Shima, T. / Tekhniyon, Makhon tekhnologi le-Yisra'el | British Library Conference Proceedings | 2014


    Distributed on-line dynamic task assignment for multi-robot patrolling

    Farinelli, A. | British Library Online Contents | 2017