2 January 2023 in IEEE Transactions on Robotics
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.
18 February 2020 in IEEE Robotics and Automation Letters
In this work, we develop a novel decentralized coordination algorithm for a team of autonomous unmanned aerial vehicles (UAVs) to surveil an aggressive forest wildfire. For dangerous environmental processes that occur over very large areas, like forest wildfires, multi-agent systems cannot rely on long-range communication networks. Therefore, our framework is formulated for very restrictive communication constraints: UAVs are only able to communicate when they are physically close to each other. To accommodate this constraint, the UAVs schedule a time and place to meet in the future to guarantee that they will be able to meet up again and share their belief of the wildfire state. In contrast with prior work, we allow for a discrete time, discrete space Markov model with a large state space as well as restrictive communication constraints. We demonstrate the effectiveness of our approach using simulations of a wildfire model that has $10^{298}$ total states.
6 February 2023 in IEEE Transactions on Automatic Control
We consider controlling a graph-based Markov decision process (GMDP) with a control capacity constraint given only uncertain measurements of the underlying state. We also consider two special structural properties of GMDPs, called Anonymous Influence and Symmetry. Large-scale spatial processes such as forest wildfires, disease epidemics, opinion dynamics, and robot swarms are well-modeled by GMDPs with these properties. We adopt a certainty-equivalence approach and derive efficient and scalable algorithms for estimating the GMDP state given uncertain measurements, and for computing approximately optimal control policies given a maximum-likelihood state estimate. We also derive sub-optimality bounds for our estimation and control algorithms. Unlike prior work, our methods scale to GMDPs with large state-spaces and explicitly enforce a control constraint. We demonstrate the effectiveness of our estimation and control approach in simulations of controlling a forest wildfire using a model with $10^{1192}$ total states.