Consensus-based ADMM for Task Assignment in Multi-Robot Teams

Ravi N. Haksar, Olaoluwa Shorinwa, Patrick Washington, Mac Schwager

2019 International Symposium on Robotics Research, 2019

Abstract

In this work, we leverage the alternating direction method of multipliers (ADMM) framework to solve task assignment for a multirobot team. While ADMM is a well-established method, it has yet to be utilized in multi-robot problems as the standard formulation requires a centralized update step, a paradigm that conﬂicts with decentralization as a means of robustness. Therefore, we describe the formulation of separable optimizations in order to produce decentralized ADMM algorithms. Here, our aim is to provide an additional tool for solving cooperative team-based problems in robotics. For the decentralized algorithms, we discuss the conditions for convergence to the optimal centralized solution. We present simulation results for task assignment to demonstrate the beneﬁts of ADMM compared to state-of-the-art methods.

BibTeX

@inproceedings{haksar_consensus-based_2019,
  address = {Hanoi, Vietnam},
  title = {Consensus-based {ADMM} for {Task} {Assignment} in {Multi}-{Robot} {Teams}},
  abstract = {In this work, we leverage the alternating direction method of multipliers (ADMM) framework to solve task assignment for a multirobot team. While ADMM is a well-established method, it has yet to be utilized in multi-robot problems as the standard formulation requires a centralized update step, a paradigm that conﬂicts with decentralization as a means of robustness. Therefore, we describe the formulation of separable optimizations in order to produce decentralized ADMM algorithms. Here, our aim is to provide an additional tool for solving cooperative team-based problems in robotics. For the decentralized algorithms, we discuss the conditions for convergence to the optimal centralized solution. We present simulation results for task assignment to demonstrate the beneﬁts of ADMM compared to state-of-the-art methods.},
  language = {en},
  booktitle = {2019 {International} {Symposium} on {Robotics} {Research}},
  publisher = {Springer},
  author = {Haksar, Ravi N. and Shorinwa, Olaoluwa and Washington, Patrick and Schwager, Mac},
  month = oct,
  year = {2019},
  keywords = {multi-robot, optimization, planning},
  month_numeric = {10}
}