Christos G. Cassandras 

Division of Systems Engineering,
Department of Electrical and Computer Engineering, and
Center for Information and Systems Engineering (CISE)
Boston University
Brookline, MA 02446
cgc@bu.edu, https://christosgcassandras.org

【ABSTRACT】A unifying optimization framework will be presented which encompasses most commonly encountered static and dynamic cooperative multi-agent system problems, including coverage control, consensus, formation control, and persistent monitoring. One of the main challenges in this framework is ensuring that the problems can be solved through distributed algorithms where each agent requires only local information from an appropriately defined neighborhood. Another challenge arises from the fact that most interesting problems involve nonconvex objective functions allowing common gradient-based distributed algorithms to be trapped in poorly preforming local optima.
We first address the fundamental question “when can a multi-agent problem be decentralized?” in the sense that an optimal solution can be fully recovered through a distributed optimization scheme. We will show that this is possible for a large class of problems, while for others we can only achieve this in an “almost distributed” manner.
We next describe a systematic method for escaping a local optimum by exploiting the structure of the objective function and knowledge of an agent’s neighborhood rather than by randomly perturbing controllable variables away from it. This is accomplished through boosting functions applied as transforms of the objective function gradient at an equilibrium point in a way that induces a search for a new equilibrium point. We will show how convergence can be attained through a distributed optimization algorithm with optimally selected step sizes. Examples will be included showing how to improve solutions of some particularly difficult non-convex multi-agent problems.