Robotics: Science and Systems X

Fully Decentralized Task Swaps with Optimized Local Searching

Lantao Liu, Nathan Michael, Dylan Shell


Communication constraints dictated by hardware often require a multi-robot system to make decisions and take actions locally. Unfortunately, local knowledge may impose limits that run antithetical to global optimality in a decentralized optimization problem. This paper redesigns the task-swap mechanism recently introduced in an anytime assignment algorithm to tackle the problem of decentralized task allocation for large scale multi-robot systems. We propose a fully decentralized approach that allows local search processes to execute concurrently while minimizing interactions amongst the processes, needing neither global broadcast nor a multi-hop communication protocol. The formulation is analyzed in a novel way using tools from group theory and the optimization duality theory to show that the convergence of local searching processes is related to a shortest path routing problem on a graph subject to the network topology. Simulation results show that this fully decentralized method converges quickly while sacrificing little optimality.



    AUTHOR    = {Lantao Liu AND Nathan Michael AND Dylan Shell}, 
    TITLE     = {Fully Decentralized Task Swaps with Optimized Local Searching}, 
    BOOKTITLE = {Proceedings of Robotics: Science and Systems}, 
    YEAR      = {2014}, 
    ADDRESS   = {Berkeley, USA}, 
    MONTH     = {July},
    DOI       = {10.15607/RSS.2014.X.021}