This paper deals with the large-scale task allocation problem for Unmanned Aerial Vehicle (UAV) swarms in surveillance missions. The task allocation problem is proven to be NP-hard which means that finding the optimal solution requires exponential time. This paper presents a practically efficient decentralized task allocation algorithm for UAV swarms based on lazy sample greedy. The proposed algorithm can provide a solution with an expected optimality ratio of at least ${p}$ for monotone submodular objective functions and of ${p}(1 - p)$ for non-monotone submodular objective functions. The individual computational complexity for each UAV is ${O}(pr^{2})$, where ${p}\,\in \,(0,0.5]$ is the sampling probability, ${r}$ is the number of tasks. The performance of the proposed algorithm is testified through digital simulations of a multi-target surveillance mission. Simulation results indicate that the proposed algorithm achieves a comparable solution quality to state-of-the-art algorithms with dramatically less running time. Moreover, a trade-off between the solution quality and the running time is obtained by adjusting the sampling probability.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Efficient Decentralized Task Allocation for UAV Swarms in Multi-target Surveillance Missions


    Beteiligte:
    Li, Teng (Autor:in) / Shin, Hyo-Sang (Autor:in) / Tsourdos, Antonios (Autor:in)


    Erscheinungsdatum :

    01.06.2019


    Format / Umfang :

    441741 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Swarms in Space Missions

    Truszkowski, Walt / Hallock, Harold L. / Rouff, Christopher et al. | Springer Verlag | 2009


    Decentralized Control of UAV Swarms for Bandwidth-Aware Video Surveillance Using NMPC

    Rezaei, Mohammad Amin / Manfredi, Gioacchino / Racanelli, Vito Andrea et al. | IEEE | 2024