Robotics: Science and Systems X
Fully Decentralized Task Swaps with Optimized Local Searching
Lantao Liu, Nathan Michael, Dylan ShellAbstract:
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.
Bibtex:
@INPROCEEDINGS{Liu-RSS-14, 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} }