Communication constrained task allocation with optimized local task swaps

October 2015

Communication constrained task allocation with optimized local task swaps

Authors:

L. Liu, N. 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 ultimately impede global optimality in a decentralized optimization problem. This paper enhances a recent anytime optimal assignment method based on a task-swap mechanism, redesigning the algorithm to address task allocation problems in a decentralized fashion. 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 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.
@article{Liu-2015-120047,
author = {L. Liu And N. Michael And D. A. Shell},
title = {Communication constrained task allocation with optimized local task swaps},
journal = {Proceedings of Autonomous Robots},
year = {2015},
month = {October},
volume = {39},
number = {3},
pages = {429 - 444},
}
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.