Search

This paper presents a time-constrained model predictive control strategy for the six degree-of-freedom autonomous rendezvous, proximity, operations and docking problem between a controllable "deputy" satellite and an uncontrolled "chief" satellite. The objective is to achieve a docking configuration defined by both the translational and attitudinal states of the deputy relative to the chief, whose dynamics are respectively governed by both the Clohessy-Wiltshire equations and Euler's second law of motion. The proposed control strategy explicitly addresses computational time constraints that are common to state-of-the-art space vehicles. Thus, a time-constrained model predictive control strategy is implemented on a space-grade processor. Although suboptimal with regards to energy consumption when compared to conventional optimal RPO trajectories, it is empirically demonstrated via numerical simulations that the deputy spacecraft still achieves a successful docking configuration while subject to computational time constraints., Comment: arXiv admin note: text overlap with arXiv:2211.11653

The study of spreading processes often analyzes networks at different resolutions, e.g., at the level of individuals or countries, but it is not always clear how properties at one resolution can carry over to another. Accordingly, in this work we use dissipativity theory from control system analysis to characterize composite spreading networks that are comprised by many interacting subnetworks. We first develop a method to represent spreading networks that have inputs and outputs. Then we define a composition operation for composing multiple spreading networks into a larger composite spreading network. Next, we develop storage and supply rate functions that can be used to demonstrate that spreading dynamics are dissipative. We then derive conditions under which a composite spreading network will converge to a disease-free equilibrium as long as its constituent spreading networks are dissipative with respect to those storage and supply rate functions. To illustrate these results, we use simulations of an influenza outbreak in a primary school, and we show that an outbreak can be prevented by decreasing the average interaction time between any pair of classes to less than 79% of the original interaction time.

We present a totally asynchronous algorithm for convex optimization that is based on a novel generalization of Nesterov's accelerated gradient method. This algorithm is developed for fast convergence under "total asynchrony," i.e., allowing arbitrarily long delays between agents' computations and communications without assuming any form of delay bound. These conditions may arise, for example, due to jamming by adversaries. Our framework is block-based, in the sense that each agent is only responsible for computing updates to (and communicating the values of) a small subset of the network-level decision variables. In our main result, we present bounds on the algorithm's parameters that guarantee linear convergence to an optimizer. Then, we quantify the relationship between (i) the total number of computations and communications executed by the agents and (ii) the agents' collective distance to an optimum. Numerical simulations show that this algorithm requires 28% fewer iterations than the heavy ball algorithm and 61% fewer iterations than gradient descent under total asynchrony., Comment: 11 pages, 1 figure

Modeling epidemic spread is critical for informing policy decisions aimed at mitigation. Accordingly, in this work we present a new data-driven method based on Gaussian process regression (GPR) to model epidemic spread through the difference on the logarithmic scale of the infected cases. We bound the variance of the predictions made by GPR, which quantifies the impact of epidemic data on the proposed model. Next, we derive a high-probability error bound on the prediction error in terms of the distance between the training points and a testing point, the posterior variance, and the level of change in the spreading process, and we assess how the characteristics of the epidemic spread and infection data influence this error bound. We present examples that use GPR to model and predict epidemic spread by using real-world infection data gathered in the UK during the COVID-19 epidemic. These examples illustrate that, under typical conditions, the prediction for the next twenty days has 94.29% of the noisy data located within the 95% confidence interval, validating these predictions. We further compare the modeling and prediction results with other methods, such as polynomial regression, k-nearest neighbors (KNN) regression, and neural networks, to demonstrate the benefits of leveraging GPR in disease spread modeling., Comment: The code for the analyses is available at https://github.com/baikeshe/GPR_Epi_Modeling

Markov decision processes often seek to maximize a reward function, but onlookers may infer reward functions by observing the states and actions of such systems, revealing sensitive information. Therefore, in this paper we introduce and compare two methods for privatizing reward functions in policy synthesis for multi-agent Markov decision processes, which generalize Markov decision processes. Reward functions are privatized using differential privacy, a statistical framework for protecting sensitive data. The methods we develop perturb either (1) each agent's individual reward function or (2) the joint reward function shared by all agents. We show that approach (1) provides better performance. We then develop a polynomial-time algorithm for the numerical computation of the performance loss due to privacy on a case-by-case basis. Next, using approach (1), we develop guidelines for selecting reward function values to preserve ``goal" and ``avoid" states while still remaining private, and we quantify the increase in computational complexity needed to compute policies from privatized rewards. Numerical simulations are performed on three classes of systems and they reveal a surprising compatibility with privacy: using reasonably strong privacy ($\epsilon =1.3$) on average induces as little as a~$5\%$ decrease in total accumulated reward and a $0.016\%$ increase in computation time., Comment: 16 Pages, 11 figures

Composing systems is a fundamental concept in modern control systems, yet it remains challenging to formally analyze how controllers designed for individual subsystems can differ from controllers designed for the composition of those subsystems. To address this challenge, we propose a novel approach to composing control systems based on resource sharing machines, a concept from applied category theory. We use resource sharing machines to investigate the differences between (i) the linear-quadratic regulator (LQR) designed directly for a composite system and (ii) the LQR that is attained through the composition of LQRs designed for each subsystem. We first establish novel formalisms to compose LQR control designs using resource sharing machines. Then we develop new sufficient conditions to guarantee that the LQR designed for a composite system is equal to the LQR attained through composition of LQRs for its subsystems. In addition, we reduce the developed condition to that of checking the controllability and observability of a certain linear, time-invariant system, which provides a simple, computationally efficient procedure for evaluating the equivalence of controllers for composed systems.

Reproduction numbers are widely used for the estimation and prediction of epidemic spreading processes over networks. However, reproduction numbers do not enable estimation and prediction in individual communities within networks, and they can be difficult to compute due to the aggregation of infection data that is required to do so. Therefore, in this work we propose a novel concept of distributed reproduction numbers to capture the spreading behaviors of each entity in the network, and we show how to compute them using certain parameters in networked SIS and SIR epidemic models. We use distributed reproduction numbers to derive new conditions under which an outbreak can occur. These conditions are then used to derive new conditions for the existence, uniqueness, and stability of equilibrium states. Finally, in simulation we use synthetic infection data to illustrate how distributed reproduction numbers provide more fine-grained analyses of networked spreading processes than ordinary reproduction numbers.

Control barrier functions are a popular method of ensuring system safety, and these functions can be used to enforce invariance of a set under the dynamics of a system. A control barrier function must have certain properties, and one must both formulate a candidate control barrier function and verify that it does indeed satisfy the required properties. Targeting the latter problem, this paper presents a method of verifying any finite number of candidate control barrier functions with linear programming. We first apply techniques from real algebraic geometry to formulate verification problem statements that are solvable numerically. Typically, semidefinite programming is used to verify candidate control barrier functions, but this does not always scale well. Therefore, we next apply a method of inner-approximating the set of sums of squares polynomials that significantly reduces the computational complexity of these verification problems by transcribing them to linear programs. We give explicit forms for the resulting linear programs, and simulation results for a satellite inspection problem show that the computation time needed for verification can be reduced by more than 95%., Comment: 8 pages, 1 figure

Data-driven systems are gathering increasing amounts of data from users, and sensitive user data requires privacy protections. In some cases, the data gathered is non-numerical or symbolic, and conventional approaches to privacy, e.g., adding noise, do not apply, though such systems still require privacy protections. Accordingly, we present a novel differential privacy framework for protecting trajectories generated by symbolic systems. These trajectories can be represented as words or strings over a finite alphabet. We develop new differential privacy mechanisms that approximate a sensitive word using a random word that is likely to be near it. An offline mechanism is implemented efficiently using a Modified Hamming Distance Automaton to generate whole privatized output words over a finite time horizon. Then, an online mechanism is implemented by taking in a sensitive symbol and generating a randomized output symbol at each timestep. This work is extended to Markov chains to generate differentially private state sequences that a given Markov chain could have produced. Statistical accuracy bounds are developed to quantify the accuracy of these mechanisms, and numerical results validate the accuracy of these techniques for strings of English words., Comment: 16 pages, 9 figures, submitted to Automatica

Graphs are the dominant formalism for modeling multi-agent systems. The algebraic connectivity of a graph is particularly important because it provides the convergence rates of consensus algorithms that underlie many multi-agent control and optimization techniques. However, sharing the value of algebraic connectivity can inadvertently reveal sensitive information about the topology of a graph, such as connections in social networks. Therefore, in this work we present a method to release a graph's algebraic connectivity under a graph-theoretic form of differential privacy, called edge differential privacy. Edge differential privacy obfuscates differences among graphs' edge sets and thus conceals the absence or presence of sensitive connections therein. We provide privacy with bounded Laplace noise, which improves accuracy relative to conventional unbounded noise. The private algebraic connectivity values are analytically shown to provide accurate estimates of consensus convergence rates, as well as accurate bounds on the diameter of a graph and the mean distance between its nodes. Simulation results confirm the utility of private algebraic connectivity in these contexts., Comment: 8 pages, 5 figures, submitted to 60th IEEE Conference on Decision and Control 2021

Loads that can vary their power consumption without violating their Quality of service (QoS), that is flexible loads, are an invaluable resource for grid operators. Utilizing flexible loads as a resource requires the grid operator to incorporate them into a resource allocation problem. Since flexible loads are often consumers, for concerns of privacy it is desirable for this problem to have a distributed implementation. Technically, this distributed implementation manifests itself as a time varying convex optimization problem constrained by the QoS of each load. In the literature, a time invariant form of this problem without all of the necessary QoS metrics for the flexible loads is often considered. Moving to a more realistic setup introduces additional technical challenges, due to the problems' time-varying nature. In this work, we develop an algorithm to account for the challenges introduced when considering a time varying setup with appropriate QoS metrics., Comment: 8 pages, 3 figures

In decision-making problems, the actions of an agent may reveal sensitive information that drives its decisions. For instance, a corporation's investment decisions may reveal its sensitive knowledge about market dynamics. To prevent this type of information leakage, we introduce a policy synthesis algorithm that protects the privacy of the transition probabilities in a Markov decision process. We use differential privacy as the mathematical definition of privacy. The algorithm first perturbs the transition probabilities using a mechanism that provides differential privacy. Then, based on the privatized transition probabilities, we synthesize a policy using dynamic programming. Our main contribution is to bound the "cost of privacy," i.e., the difference between the expected total rewards with privacy and the expected total rewards without privacy. We also show that computing the cost of privacy has time complexity that is polynomial in the parameters of the problem. Moreover, we establish that the cost of privacy increases with the strength of differential privacy protections, and we quantify this increase. Finally, numerical experiments on two example environments validate the established relationship between the cost of privacy and the strength of data privacy protections., Comment: Submitted to the Conference on Decision and Control (CDC) 2020

Multi-agent optimization problems with many objective functions have drawn much interest over the past two decades. Many works on the subject minimize the sum of objective functions, which implicitly carries a decision about the problem formulation. Indeed, it represents a special case of a multi-objective problem, in which all objectives are prioritized equally. To the best of our knowledge, multi-objective optimization applied to multi-agent systems remains largely unexplored. Therefore, we propose a distributed algorithm that allows the exploration of Pareto optimal solutions for the non-homogeneously weighted sum of objective functions. In the problems we consider, each agent has one objective function to minimize based on a gradient method. Agents update their decision variables by exchanging information with other agents in the network. Information exchanges are weighted by each agent's individual weights that encode the extent to which they prioritize other agents' objectives. This paper provides a proof of convergence, performance bounds, and explicit limits for the results of agents' computations. Simulation results with different sizes of networks demonstrate the efficiency of the proposed approach and how the choice of weights impacts the agents' final result.

Privacy is an important concern in various multiagent systems in which data collected from the agents are sensitive. We propose a differentially private controller synthesis approach for multi-agent systems subject to high-level specifications expressed in metric temporal logic (MTL). We consider a setting where each agent sends data to a cloud (computing station) through a set of local hubs and the cloud is responsible for computing the control inputs of the agents. Specifically, each agent adds privacy noise (e.g., Gaussian noise) point-wise in time to its own outputs before sharing them with a local hub. Each local hub runs a Kalman filter to estimate the state of the corresponding agent and periodically sends such state estimates to the cloud. The cloud computes the optimal inputs for each agent subject to an MTL specification. While guaranteeing differential privacy of each agent, the controller is also synthesized to ensure a probabilistic guarantee for satisfying the MTL specification.We provide an implementation of the proposed method on a simulation case study with two Baxter-On-Wheels robots as the agents.

Differential privacy has emerged as a formal framework for protecting sensitive information in control systems. One key feature is that it is immune to post-processing, which means that arbitrary post-hoc computations can be performed on privatized data without weakening differential privacy. It is therefore common to filter private data streams. To characterize this setup, in this paper we present error and entropy bounds for Kalman filtering differentially private state trajectories. We consider systems in which an output trajectory is privatized in order to protect the state trajectory that produced it. We provide bounds on a priori and a posteriori error and differential entropy of a Kalman filter which is processing the privatized output trajectories. Using the error bounds we develop, we then provide guidelines to calibrate privacy levels in order to keep filter error within pre-specified bounds. Simulation results are presented to demonstrate these developments., Comment: 17 pages, 2 figures