Multi-agent Control and Optimization under Uncertainty

Many natural and engineering systems can be characterized as a collection of interacting agents each having access to local information, making local decisions, having local interactions with neighbors, and seeking to optimize local objectives. The analysis and design of such systems falls under the broader framework of “multi-agent control and optimization”. Here depending on the context, “agents” could be animals, autonomous vehicles, power plants, etc. Multi-agent systems have the potential for solving problems that are difficult or impossible for an individual agent or monolithic system to solve. However, the complexity associated with a potentially large number of interacting agents brings about challenging control and optimization problems for system designers and coordinators. Such difficulty is often enhanced by the presence of noise/uncertainty that is pervasive in both biological and engineering systems.

In this dissertation, we focus on the analysis and design of several multi-agent control/optimization algorithms for various problems under uncertainty. Swarming, flocking, schooling and other aggregations of organisms in groups have been studied extensively in biology. Organisms in swarms can exploit several advantages of staying close to each other for more effective foraging. In our first line of work, we develop a mathematical model for analyzing the benefits of social foraging in a noisy environment. We identify conditions on the nutrient profile ensuring that local agent actions will lead to cohesive foraging. For convex, smooth nutrient profiles we formalize the way in which swarming for social foraging is better at handling the effects of noise when compared to the average of individual foraging strategies. Under a swarming discipline, observational noise realizations that induce trajectories differing too much from the group average are likely to be discarded because of each individual’s need to maintain cohesion. As a result, the group trajectories are less affected by noise. Simulation experiments indicate that our theoretical results are also robust to inter-agent communication constraints and non-convex nutrient profiles.

The above results suggest that swarming-like approaches for the control and/or optimization of networked agents may provide an additional level of robustness. This is precisely the gist of our second line of work in which we consider a distributed computing algorithmic scheme for stochastic optimization which relies on modest communication requirements amongst processors and most importantly, does not require synchronization. Specifically, we analyze a scheme with N > 1 independent threads each implementing a stochastic gradient algorithm. The threads are coupled via a perturbation of the gradient (with attractive and repulsive forces) in a similar manner to mathematical models of flocking. We show that a flocking-like approach for distributed stochastic optimization provides a noise reduction effect similar to that of a single-thread stochastic gradient algorithm based upon the average of N gradient samples at each step. When the overhead related to the time needed to gather N samples and synchronization is not negligible, the flocking implementation outperforms the single-thread algorithm.

In our last line of work, we consider one of the most important multi-agent systems in any modern economy: the electric power infrastructure. Specifically, we consider the problem of designing the rules by which market dispatch and payment to participants are gradually adjusted while taking into account network and reliability constraints so as to ensure the market clears with an efficient outcome. We propose a class of iterative mechanisms and show this class exhibits many desirable properties (approximately): incentive compatibility, efficiency, individual rationality and (weak) budget balance. In addition, we analyze an iterative mechanism for stochastic market clearing, a pressing need given the increasing penetration of highly intermittent renewable generation technologies. In this case, the marginal cost of adjustments may only be estimated with some error. We show that truthful reporting is a Nash equilibrium and the resulting dispatch converges almost surely to the efficient dispatch.