Workshop on Learning, Decision and Control over Networks

Title: Resource-Aware Control for the Design of Accelerated Optimization Algorithms

Abstract: This talk takes a dynamical systems and control approach to the design of fast optimization solvers in machine learning. Recent work in the machine learning and optimization communities seeks to shed light on the behavior of accelerated optimization methods via high-resolution differential equations. These differential equations are continuous-time counterparts of discrete-time optimization algorithms and, remarkably, their convergence properties can be characterized using the powerful tools provided by classical Lyapunov stability analysis. An outstanding open question of pivotal importance is how to discretize these continuous flows while maintaining their convergence rates. We provide an answer to this question by employing ideas from resource-aware control. The main idea is to take advantage of the Lyapunov functions employed to characterize the rate of convergence of high-resolution differential equations to design variable-stepsize discretizations that preserve by design the convergence properties of the original dynamics.

Title: Multi-scale analysis of deployment and coverage control problems

Abstract: As the size of networked systems and swarms dramatically increases, new challenges arise from algorithm performance evaluation and design, and agent-level algorithm implementation. This calls for a consistent, multi-scale approach that can bridge the gap between small and large agent-set cases. In this talk, we outline recent work in this direction while focusing on deployment and coverage control problems.

Title: Distributed Estimation and Learning in Cyber-Physical Networks: A Hierarchical Bayesian Approach

Abstract: Modern cyber-physical networks are characterized by massive, possibly heterogeneous data available at each node. How to infer information from these data is one of the main challenges to be addressed. Moreover, designing distributed protocols allowing agents to learn cooperatively without any central unit is even more challenging. In this talk I will present a general, Bayesian probabilistic framework in which nodes infer a local quantity or learn a local state by means of a two-step procedure. In the “higher-level” step suitable parameters are estimated by means of distributed optimization algorithms. Then, using the estimated parameters, nodes improve their local estimate or classify their local state by means of a suitable local routine.

Title: Physical Flow over Networks: Analysis, Control and Computation

Abstract: Network flow provides a compelling framework to model several civil infrastructure systems, including transportation and power. Traditionally, network flow methodologies have focused predominantly on fast computation of performance metrics in static settings, under only flow conservation. Extensions to additional canonical physical constraints and dynamics underlying civil infrastructure systems, and to robustness analysis and control synthesis have been challenging. This is, in part, due to non-convexity, switched dynamics and hybrid state space. We present recent results that overcome these challenges by exploiting structure through the lens of monotonicity, equivalent relaxation, incremental network reduction, and principled abstraction synthesis. Case studies and examples to illustrate the proposed methodologies will also be presented.

Title: The Impact of Information on Greedy Agents Performing Distributed Submodular Maximization

Abstract: This talk will discuss a distributed maximization problem in which a group of agents must each choose a strategy from their strategy set. The global objective is to maximize a submodular function of the strategies chosen by each agent. Submodular functions capture the notion of diminishing returns; the marginal contribution of an agent to global objective decreases as the number of participating agents increase. This talk will consider the case were each agent has access to only a limited number of other agents’ choices. The goal will be to characterize how the limited information affects the global performance when agents make choices in a greedy manner.

In particular, we will give lower bounds on the performance of greedy algorithms for submodular maximization that depend on the clique number of a graph that captures the information structure. We will then characterize graph- theoretic upper bounds in terms of the chromatic number of the graph. Finally, the talk will show results from applying the results to several common network models and discuss some applications of this work to distributed sensing and resource allocation.

Title: k-Capture in Multiagent Pursuit Evasion, or the Lion and the Hyenas

Abstract: Multiagent pursuit evasion problems have been researched extensively over the past century. With origins in defense applications, these problems also arise in search and rescue and collision avoidance in vehicles among civilian use. This talk is centered on a multiagent pursuit evasion scenario that models asymmetry between the pursuers and the evader in the sense that the evader can hit back! In particular, we will discuss the following generalization of the classical pursuit-evasion problem, which we call k-capture. A group of n pursuers (hyenas) wish to capture an evader (lion) who is free to move in an m-dimensional Euclidean space. The pursuers and the evader can move with the same maximum speed, and at least k pursuers must simultaneously reach the evader’s location to capture it. If fewer than k pursuers reach the evader, then those pursuers get destroyed by the evader. Under what conditions can the evader be k-captured? We study this problem in the discrete time, continuous space model and prove that k-capture is possible if and only if there exists a time when the evader lies in the interior of the pursuers’ k- Hull. When the pursuit occurs inside a compact, convex subset of the Euclidean space, we show through an easy constructive strategy that k-capture is always possible.