Distributed Algorithms via Saddle-Point Dynamics for Multi-Robot Task Assignment

Abstract

This letter develops two distributed algorithms to solve multi-robot task assignment problems (MTAP). We first describe MTAP as an integer linear programming (ILP) problem and then reformulate it as a relaxed convex optimization problem. Based on the saddle-point dynamics, we propose two distributed optimization algorithms using optimistic gradient decent ascent (OGDA) and extra-gradient (EG) methods, which achieve exact convergence to an optimal solution of the relaxed problem. In most cases, such an solution reflects the optimality of the original ILP problems. For some special ILP problems, we provide a perturbation-based distributed method to avoid the inconsistency phenomenon, such that an optimal solution to any ILP problem is obtained. Compared with some decentralized algorithms requiring a central robot that communicates with the other robots, our developed algorithms are fully distributed, in which each robot only communicates with the nearest neighbors for an arbitrary connected graph. We evaluate the developed algorithms in terms of computation, communication, and data storage complexities, and compare them with some typical algorithms. It is shown that the developed algorithms have low computational and communication complexities. We also verify the effectiveness of our algorithms via numerical examples.