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.


    Access

    Download


    Export, share and cite



    Title :

    Decentralized Task Allocation Using Local Information Consistency Assumptions


    Contributors:

    Published in:

    Publication date :

    2017-02-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    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


    Asynchronous Decentralized Task Allocation for Dynamic Environments

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


    Decentralized task allocation for multiple UAVs with task execution uncertainties *

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