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 and include examples
showing how to improve solutions of some particularly difficult multi-agent problems.