Distributed Multirobot Task Assignment via Consensus ADMM

doi:10.1109/TRO.2022.3228132

Distributed Multirobot Task Assignment via Consensus ADMM

2023-06-01

9

PRE

AI

Patrick H. Washington

M

Mac Schwager

DOI：10.1109/TRO.2022.3228132

原文链接

原文求助

摘要

En 中文

In this article, we present a distributed algorithm to solve a class of multirobot 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 specifics. 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 suboptimal 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 (Chopra et al., 2017). We also apply our algorithm to a multi-unmanned-aerial-vehicle persistent surveillance problem, showing its suitability for problems involving periodic task assignments.

Keyword:

Task analysis

Robots

Multi-robot systems

Optimization

Linear programming

Costs

Distributed algorithms

Distributed mathematical programming

distributed optimization

distributed task assignment

multirobot systems

Distributed Multirobot Task Assignment via Consensus ADMM

摘要

期刊

机构

引用论文