Fully Decentralized Task Swaps with Optimized Local Searching
Lantao Liu, Nathan Michael, Dylan A. Shell · 2014
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 against 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 multirobot 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.