July
2014
Fully Decentralized Task Swaps with Optimized Local Searching
Authors:
Abstract:
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.
copied = false, 2000);
">
@conference{Liu-2014-17175,
author = {L. Liu And Nathan Michael And D. A. Shell},
title = {Fully Decentralized Task Swaps with Optimized Local Searching},
booktitle = {Proceedings of Robotics: Science and Systems (RSS '14)},
year = {2014},
month = {July},
}
author = {L. Liu And Nathan Michael And D. A. Shell},
title = {Fully Decentralized Task Swaps with Optimized Local Searching},
booktitle = {Proceedings of Robotics: Science and Systems (RSS '14)},
year = {2014},
month = {July},
}