Fully Decentralized Task Swaps with Optimized Local Searching

July 2014

Fully Decentralized Task Swaps with Optimized Local Searching

Authors:

L. Liu, Nathan Michael, and D. A. Shell

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.
@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},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.