Distributed Multirobot Task Assignment via Consensus ADMM
@article{shorinwa_distributed_2023-1,
title = {Distributed {Multirobot} {Task} {Assignment} via {Consensus} {ADMM}},
volume = {39},
issn = {1552-3098, 1941-0468},
url = {https://ieeexplore.ieee.org/document/10004756/},
abstract = {We present a distributed algorithm to solve a class of multi-robot task assignment problems. We formulate task assignment as a mathematical optimization and solve for optimal solutions with a variant of the consensus Alternating Direction Method of Multipliers (C-ADMM). We provide C-ADMM-based algorithms for both the primal and dual problem formulations, and show the advantages of each form depending on the problem speciļ¬cs. In our algorithm, each robot solves a series of local optimization problems and communicates the results to its local neighbors, ultimately converging to an optimal task assignment in problems with linear objective functions, and an optimal solution of the relaxed problem in convex problems. While many other distributed algorithms require a central station for their implementation, in our algorithm each robot only communicates with its one-hop neighbors. In linear task assignment problems, our algorithm converges to the optimal task assignment, unlike many other distributed algorithms for this problem, which yield sub-optimal solutions. We demonstrate our algorithms in task assignment problems over a variety of communication network topologies, where we show that our inexact dual algorithm is at least 60\% faster than other distributed algorithms which produce an optimal task assignment. In addition, our dual algorithm attains a 69\% speedup in computation time compared to a notable distributed variant of the Hungarian method [1]. We also apply our algorithm to a multi-UAV persistent surveillance problem, showing its suitability for problems involving periodic task assignments.},
language = {en},
number = {3},
urldate = {2023-08-29},
journal = {IEEE Transactions on Robotics},
author = {Shorinwa, Ola and Haksar, Ravi N. and Washington, Patrick and Schwager, Mac},
month = jun,
year = {2023},
pages = {1781--1800},
month_numeric = {6}
}