The information available to agents using decentralized task allocation algorithms plays an important role in how assignments can be constructed. The requirement that information be globally consistent across all agents can be leveraged to allow cooperation on coupled objectives. In environments where global information consistency assumptions are difficult to enforce, the alternative is to rely only on a local best estimate of the global information state, which is referred to here as local information consistency. Algorithms that assume only this local information consistency will have reduced optimization capabilities compared to their global information assumption counterparts. Specifically, if objective functions are non-submodular, local information algorithms may produce arbitrarily bad allocations or, in the case of many algorithms, may not even converge. The key contribution of this paper is an algorithm termed bid warped consensus-based bundle algorithm that converges for all deterministic objective functions and has nontrivial performance guarantees for submodular and some non-submodular objective functions. Included in this paper is an analytical analysis of both convergence and performance of the algorithm, as well as a numerical comparison to several other competing local and global information approaches.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Decentralized Task Allocation Using Local Information Consistency Assumptions


    Beteiligte:
    Johnson, Luke B. (Autor:in) / Choi, Han-Lim (Autor:in) / Ponda, Sameera S. (Autor:in) / How, Jonathan P. (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    2017-01-24


    Format / Umfang :

    20 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Asynchronous Decentralized Task Allocation for Dynamic Environments

    Johnson, Luke / Ponda, Sameera / Choi, Han-Lim et al. | AIAA | 2011


    Minimizing Communications in Decentralized Greedy Task Allocation

    Kim, Keum-Seong / Kim, Ho-Yeon / Choi, Han-Lim | AIAA | 2019


    Asynchronous Decentralized Task Allocation for Dynamic Environments

    Johnson, L. / Ponda, S. / Choi, H.-L. et al. | British Library Conference Proceedings | 2011


    Partial Replanning for Decentralized Dynamic Task Allocation

    Buckman, Noam / Choi, Han-Lim / How, Jonathan P. | AIAA | 2019


    Decentralized task allocation for multiple UAVs with task execution uncertainties *

    Liu, Ruifan / Seo, Minguk / Yan, Binbin et al. | IEEE | 2020