Static and dynamic optimization problems in cooperative multi-agent systems
MetadataShow full item record
This dissertation focuses on challenging static and dynamic problems encountered in cooperative multi-agent systems. First, a unified optimization framework is proposed for a wide range of tasks including consensus, optimal coverage, and resource allocation problems. It allows gradient-based algorithms to be applied to solve these problems, all of which have been studied in a separate way in the past. Gradient-based algorithms are shown to be distributed for a subclass of problems where objective functions can be decoupled. Second, the issue of global optimality is studied for optimal coverage problems where agents are deployed to maximize the joint detection probability. Objective functions in these problems are non-convex and no global optimum can be guaranteed by gradient-based algorithms developed to date. In order to obtain a solution close to the global optimum, the selection of initial conditions is crucial. The initial state is determined by an additional optimization problem where the objective function is monotone submodular, a class of functions for which the greedy solution performance is guaranteed to be within a provable bound relative to the optimal performance. The bound is known to be within 1 − 1/e of the optimal solution and is improved by exploiting the curvature information of the objective function. The greedy solution is subsequently used as an initial point of a gradient-based algorithm for the original optimal coverage problem. In addition, a novel method is proposed to escape a local optimum in a systematic way instead of randomly perturbing controllable variables away from a local optimum. Finally, optimal dynamic formation control problems are addressed for mobile leader-follower networks. Optimal formations are determined by maximizing a given objective function while continuously preserving communication connectivity in a time-varying environment. It is shown that in a convex mission space, the connectivity constraints can be satisfied by any feasible solution to a Mixed Integer Nonlinear Programming (MINLP) problem. For the class of optimal formation problems where the objective is to maximize coverage, the optimal formation is proven to be a tree which can be efficiently constructed without solving a MINLP problem. In a mission space constrained by obstacles, a minimum-effort reconfiguration approach is designed for obtaining the formation which still optimizes the objective function while avoiding the obstacles and ensuring connectivity.