Assignment problems are a classic combinatorial optimization problem in which a group of agents must be assigned to a group of tasks such that maximum utility is achieved while satisfying assignment constraints. Given the utility of each agent completing each task, polynomial-time algorithms exist to solve a single assignment problem in its simplest form. However, in many modern-day applications such as satellite constellations, power grids, and mobile robot scheduling, assignment problems unfold over time, with the utility for a given assignment depending heavily on the state of the system. We apply multi-agent reinforcement learning to this problem, learning the value of assignments by bootstrapping from the known polynomial-time greedy solver and then learning from further experience. We then choose assignments using a distributed optimal assignment mechanism rather than by selecting them directly. We demonstrate that this algorithm is theoretically justified and avoids pitfalls experienced by other RL algorithms in this setting. Finally, we show that our algorithm significantly outperforms other methods in the literature, even while scaling to realistic scenarios with hundreds of agents and tasks.

This paper examines learning the optimal filtering policy, known as the Kalman gain, for a linear system with unknown noise covariance matrices using noisy output data. The learning problem is formulated as a stochastic policy optimiza- tion problem, aiming to minimize the output prediction error. This formulation provides a direct bridge between data-driven optimal control and, its dual, op- timal filtering. Our contributions are twofold. Firstly, we conduct a thorough convergence analysis of the stochastic gradient descent algorithm, adopted for the filtering problem, accounting for biased gradients and stability constraints. Secondly, we carefully leverage a combination of tools from linear system theory and high-dimensional statistics to derive bias-variance error bounds that scale logarithmically with problem dimension, and, in contrast to subspace methods, the length of output trajectories only affects the bias term.

From an optimization point of view, resource allocation is one of the cornerstones of research for addressing problems commonly arising in applications such as power outages and traffic jams. In this paper, we take a data-driven approach to estimate an optimal nodal restoration sequence for immediate recovery of infrastructure networks after natural disasters such as earthquakes. Data is generated from td-INDP, a high-fidelity simulator of optimal restoration strategies for interdependent networks, and employ artificial neural networks to approximate those strategies. Despite the fact that the underlying problem is NP-complete, the restoration sequences obtained by our method are observed to be nearly optimal. In addition, by training multiple models—the so-called estimators—for a variety of resource availability levels, our proposed method balances a tradeoff between resource utilization and restoration time. Decision-makers can use our trained models to allocate resources more efficiently before and after contingencies, and in turn, improve the community resilience. Besides their predictive power, such trained estimators unravel the effect of interdependencies among different nodal functionalities in the restoration strategies. We showcase our methodology by the real-world interdependent infrastructure of Shelby County, TN.

Direct policy gradient methods for reinforcement learning and continuous control problems are a popular approach for a variety of reasons: 1) they are easy to implement without explicit knowledge of the underlying model, 2) they are an “end-to-end” approach, directly optimizing the performance metric of interest, 3) they inherently allow for richly parameterized policies. A notable drawback is that even in the most basic continuous control problem (that of linear quadratic regulators), these methods must solve a non-convex optimization problem, where little is understood about their efficiency from both computational and statistical perspectives. In contrast, system identification and model based planning in optimal control theory have a much more solid theoretical footing, where much is known with regards to their computational and statistical properties. This work bridges this gap showing that (model free) policy gradient methods globally converge to the optimal solution and are efficient (polynomially so in relevant problem dependent quantities) with regards to their sample and computational complexities.

Kronecker product (KP) approximation has recently been applied as a modeling and analysis tool on systems with hierarchical networked structure. In this paper, we propose a tensor product-based approach to the KP approximation problem with arbitrary number of factor matrices. The formulation involves a novel matrix-to-tensor transformation to convert the KP approximation problem to a best rank-(R1, …, RN) tensor product approximation problem. In addition, we develop an algorithm based on higher-order orthogonal iteration to solve the tensor approximation problem. We prove that the proposed approach is equivalent to conventional singular value decomposition-based approach for two matrix factor case proposed by Van Loan. Hence, our work is a generalization of Van Loan's approach to more than two factor matrices. We demonstrate our approach by several experiments and case studies. The results indicate that the tensor product formulation is effective for KP approximation.

The paper considers the efficient selection of leader agents in a swarm running a distributed bearing-compass formation controller. The leaders apply external control which induces translation and scaling of the formation, providing manipulation methods useful to a human operator. The selection algorithm for maximizing translation and scale draws from modularity and submodularity theory. Consequently, the algorithms exhibit guaranteed optimal and suboptimal performance, respectively. For more restricted human-swarm interaction requiring pure translation and scale, a relaxed integer programming algorithm is described to reduce the combinatorial optimization problem to a computationally tractable semidefinite program. The leader selection strategies are supported through demonstration on a swarm testbed.

This paper examines an advection-based protocol for the coordination of a networked, multi-agent system. Diffusion forms the basis of the popular consensus dynamics and is closely related to advection. It is with this motivation that we examine a discretized version of advection over a network with the flow field realized through directed graph edges. We endeavor to demonstrate that the subsequent advection protocol forms an attractive set of system dynamics for coordinated control. This paper includes a formulation of the advection dynamics on directed graphs and a presentation of some of its characteristics. We also demonstrate the versatility of the advection dynamics with a decentralized load balancing application.

Cell function manifests through intricately controlled dynamic processes that both interact amongst each other—in a network—and also respond to external signals, e.g., transcription factors, etc. Recently, controllability of complex networks has received considerable attention for its potential to influence the behavior of dynamically interacting nodes of interest in biological, social, and engineered networks. For example, Liu et al. recently used the notion of structural controllability to provide insights into the percentage of nodes required to control the evolution of the state of the nodes in a network in response to external stimuli [1]–[3]. However, when applying the notion of controllability in biology, we must consider the dynamical nature of biological systems as well as the timing of the external input. Here, we provide a parallel yet distinct approach to the problem of network controllability in the context of cell differentiation and highlight the importance of network controllability and its applications in dynamical biological systems [4]. Cellular differentiation is the process via which the nucleus achieves a new function. After many years of intensive investigation, we are just scratching the surface of how the cell nucleus functions on a global level to produce specialized cell types. The relationship between nuclear form and function will be critical to understanding the dynamics of the nucleus during cell differentiation [5], [6]. We argue that feedback between form and function during differentiation fine-tunes a cell-specific form, leading to the desired function [7]. In this venue, we first define form as a geometric network that reflects the physical configuration of chromosomes in the interphase nucleus and function as the transcriptional network. Adopting this geometric point of view allows us to consider the evolution of a concrete, physically realizable network during differentiation, and assess how essential features of this network evolve over time. The basic question is thus how network geometry with a particular initial configuration evolves toward a specific cell type with its own unique configuration and how essential features of the network evolve with this geometry. Two constructs form the basic premise in addressing this question. First, cell fate is guided by transcription factors that have broad influence on cell differentiation and reprogramming [8]. An example of this type of influence is the well-studied transcription factor MyoD, which can convert fibroblasts into skeletal muscle cells by activating the skeletal muscle differentiation program [9]. Another example is the recently discovered set of transcription factors that can reprogram cells to pluripotency [10]. Second, we pose that the essential features of the network that evolve to allow for efficient reprogramming fall in the realm of control theory. One of the basic concepts in control theory is—to no surprise—controllability. Essentially, controllability is a feature of a dynamic system with inputs, allowing its states to be steered towards desirable target states. If we now consider the physical configuration of the chromosomes, the form, as the dynamic state during differentiation, and transcription factors such as MyoD as the external signals, the natural idea is to examine the differentiation dynamics from the point of view of its controllability. What would such a point of view offer? It provides a systematic means of quantifying directions that the network can most efficiently be steered towards, given how the transcription factor binds and interacts with various parts of the chromosomal network. This can be accomplished by not only considering whether the network is controllable from the input, but also examining how controllable each direction in the configuration space of the chromosomal network is. And since the network is dynamic—after all, that is what differentiation is all about—a static, parameterized notion of controllability, such as structural controllability, turns out to be unsuitable for assessing network controllability. In the structural controllability approach, the weights on the interactions are of little consequence—as long as they are zero and non-zero—for assessing whether the network is steerable to a particular configuration or not. However, in networks such as the chromosomal network during cellular differentiation, there is intriguing evidence that two nodes interact more if their pairwise physical distance is less. Thus, as the nodes in the chromosomal network come closer, they have a higher interaction with each other, and it is well-conceivable that the network becomes less controllable by an external signal such as a transcription factor. We have proposed a framework to examine this notion of controllability via the controllability gramian, a matrix that captures how directions in the nodes' configuration space are attainable with a given external input [11]. The controllability gramian not only reveals the efficiency and time critical nature of steering the network, but also has a statistical significance in terms of its connection with measurement covariances and their determinant, the network entropy. Thus, we can estimate the entropy from the determinant of the covariance matrix, and interpret it as a measure of network controllability. Using this approach, we have proposed a diffusion-driven network with dynamics that is parameterized by the relative distances between the nodes, for which the evolution of the controllability gramian not only matches the experimentally determined covariances in terms of their algebraic properties, but also offers a control theoretic parallel for a highly entropic intermediate network as the cell transitions between two highly ordered states during differentiation (Figure 1). Figure 1 Dynamics of network controllability and entropy. The dynamical properties of a cell are hardwired in the genome, but both environmental and epigenetic factors influence how this information is accessed and applied [12], [13]. Thus, a cell is naturally receptive to external influence, and this gives us an opportunity by which to manipulate a cell to achieve a desired function or outcome. To best take advantage of this property, we require a deeper understanding of when and where to apply external influences. The application of network controllability theory may be the key to systematic reasoning about which nodes to target to achieve global impact toward a desired outcome, and when to target them in a perturbed system, such as cancer. This may lead to novel strategies for redirecting cancer cells along new trajectories that avoid further pathology. However, the dynamic nature of the network, as well as the efficiency and timing of the control mechanism, should be an integral part of such a network controllability research.

This paper examines the system dynamics of a networked multi-agent system, operating with a consensus-type algorithm, that can be influenced by external agents. We refer to this class of networks as semi-autonomous. We introduce a control scheme for such semi-autonomous networks, involving excitation of the network by the external agents, with the objective of manipulating or steering the network. In this context, we consider the situation where the external agents deliver a constant mean control signal. We proceed to examine the resultant mean and covariance of the network output and relate these quantities to circuit-theoretic notions of the network, quantifying the network's amenability to external signals. Four protocols for tree graphs, to promote and deter convergence and to increase and reduce average variance within the network are then presented. These protocols involve decentralized local edge swaps that can be performed in parallel and asynchronously.

Formation flying (FF) is a critical element in NASA's future deep-space missions. Terrestrial Planet Finder (TPF), NASA's first space-based mission to directly observe planets outside our own solar system, will rely on FF to achieve the functionality and benefits of a large instrument using multiple lower cost smaller spacecraft. Many key network design problems for such FF missions can be formulated as optimization problems with local and global constraints. We develop a topology control algorithm that can be used for many network problems in the presence of local constraints, such as collision avoidance, and global constraints, such as network connectivity. The presence of contradictory objectives in topology control problems motivated a game-theoretic approach. We demonstrated that a game-theoretic technique could provide a framework for design and analysis of many topology control problems in dynamic networks. In particular, the problem of motion planning for formation reconfiguration in the presence of constraints on network connectivity and inter-spacecraft collisions is studied.

In this paper, we consider the problem of distributed linear parameter estimation in static and dynamic sensor networks. We propose iterative averaging algorithms based on Laplacian dynamics which converge to the centralized least squares solution asymptotically. In the first part of this paper, we consider the case of unclustered (flat architecture) sensor networks and analyze convergence of the iterative algorithm, for both static and dynamic topologies. Subsequently, we extend our analysis to static but clustered sensor networks with pulsed inter-cluster updates. In this scheme, we assume that all inter-cluster communications occur every H time steps, H > 1, and the corresponding updates are held till the next update instant. Depending on the sensor locations and the topology formation algorithm used, it may be the case that inter-cluster communications require higher transmitter power support than intra-cluster communications. From a power efficiency (or alternately, network lifetime) point of view, it may therefore be beneficial to limit the extent of inter-cluster communication, without significantly enhancing the convergence time of the distributed estimation algorithm. We anticipate that a pulsed inter-cluster update scheme will also be beneficial for applications such as military sensor networks, where low probability of detection and interception is essential. Our analysis provides sufficient conditions under which the distributed algorithm operating on a pulsed inter-cluster update scheme converges. Simulation results are provided which illustrate the dependence of the convergence rate of the algorithm on H

We consider the problem of survivable minimum power bidirectional topology optimization in wireless networks. Two optimization problems are considered, minimization of the total transmit power and minimization of the maximum transmit power, subject to arbitrary K-node connectivity constraints. In this paper, we take an algebraic view of graph connectivity which is defined as the second smallest eigenvalue of the Laplacian matrix of a graph. Since the algebraic connectivity of a graph is known to be a lower bound on its node and edge connectivities, we impose a constraint on the algebraic connectivity to ensure that the solution is K-connected. Given the special properties of the Laplacian matrix of a graph, it is possible to express the algebraic connectivity requirement as a positive semidefinite constraint. Using this result, we show how the optimization problems can be formulated as 0/1 semidefinite programs (SDP's), which can be solved exactly using an SDP solver within a branch-and-bound framework. Linear and semidefinite relaxations of the 0/1 constraints are also discussed. These relaxations are useful for generating lower bounds on the exact 0/1 SDP models.