UC Santa Barbara

Optimization is a prevalent tool in control and estimation. This work explores the theoretical and practical challenges in the design and analysis of distributed algorithms to solve optimization problems related to multi-agent systems.

We begin by considering a problem related to parameter estimation in sensor networks. We show that the maximum likelihood estimation formulation of several localization problems based on inter-sensor measurements reduces to the form of a common constrained optimization. We then design a distributed algorithm that utilizes only the most recent measurements and the estimates from the neighboring sensors, to iteratively compute the optimal solution. Our analysis shows that the solutions obtained from this algorithm converge locally to the maximum likelihood estimates, nevertheless simulations show that this convergence may occur globally. Furthermore, in experimental results using custom ultra-wideband radio frequency devices, this algorithm outperformed other distributed methods tested for a given localization problem.

Next, we consider a multi-agent coordination problem formulated as a finite horizon optimization of the type used in model predictive control. We present two distributed and iterative algorithms, in which each agent is assigned a cost function, which it optimizes to compute its own control action. These cost functions depend on the states and the estimates of the control variables of the agents' neighbors, which are obtained through inter-agent communication. For the first algorithm, the agents are able to receive estimates from 2-hop neighbors, whereas the second algorithm utilizes only 1-hop neighbor information. For the first algorithm, our results show that the local solutions converge to the solution of the original model predictive control problem, regardless of how the algorithm is initialized. Because this convergence is asymptotic, we derive practical conditions for terminating the algorithm in a finite number of iterations, such that the closed-loop system achieves the desired coordination. For the second algorithm, due to more restrictive constraints, the convergence occurs to suboptimal solutions of the model predictive control problem. Nevertheless, simulations demonstrate that the optimality gap is small, and in some cases zero.

A key takeaway from these results is that in many problems of multi-agent systems, the communication between the agents can be leveraged to design distributed algorithms that match the quality of solutions that one would obtain from centralized approaches.