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.

This paper presents Reduced State Value Iteration (RSVI), an algorithm to compute policies for Markov Decision Processes (MDPs) that have natural checkpoints, allowing for a solution based on a reduced state space. The algorithm is applied to find policies for multiple drones to persistently surveil an environment subject to charging constraints. RSVI leverages the structure of the true MDP to build an MDP with a smaller state-action space. Monte Carlo simulations are used to estimate transitions between the states in the reduced MDP, which are used in value iteration to compute a policy for the reduced MDP. States in the true MDP are mapped to reduced states. Actions in the reduced space from the policy are then mapped to actions in the full space for execution on the true MDP. Performance of the RSVI policy improves as the state discretization becomes finer, but with increasing computational requirements, thus giving a natural trade-off between computational resources and policy suboptimality. Results of simulated persistent surveillance experiments show that our RSVI policy outperforms a baseline heuristic.