Abstract:  

The success of cooperative multi-agent systems rests on our ability to develop control and optimization methods which are scalable, allow for decentralized operation with limited communication in energy-limited environments, and can achieve global optimality. For parametric optimization problems, the goal is to determine an equilibrium for the agent states to optimize a given objective function. We address the question “when is a distributed algorithm feasible?” to achieve this goal and present explicit solutions to the class of optimal coverage problems using such distributed algorithms. Unfortunately, the problem of guaranteeing global optimality for such problems in general remains open. We will present a new approach for systematically escaping local optima using “boosting functions” which induce the distributed agents to explore poorly covered regions of the search space until a new equilibrium point is reached, which is potentially better, but still not guaranteed to be globally optimal. For dynamic optimization problems, the goal is to control the movement of multiple cooperating agents to optimize a given objective. We approach the problem by representing an agent trajectory in terms of general function families characterized by parameters that we can optimize. We then show that the problem of determining optimal parameters for these trajectories can be solved using Infinitesimal Perturbation Analysis (IPA) to determine gradients of the objective function with respect to these parameters evaluated on line so as to adjust them through a standard gradient-based algorithm. We will present results using the family of Lissajous functions as well as a Fourier series representation of an agent trajectory indicating that this scalable approach provides solutions that are near-optimal relative to those obtained through a computationally intensive two point boundary value problem solver. Moreover, the solutions obtained are independent of the stochastic characteristics of the environment.