Search

We propose a Markov Chain Monte Carlo (MCMC) algorithm based on Gibbs sampling with parallel tempering to solve nonlinear optimal control problems. The algorithm is applicable to nonlinear systems with dynamics that can be approximately represented by a finite dimensional Koopman model, potentially with high dimension. This algorithm exploits linearity of the Koopman representation to achieve significant computational saving for large lifted states. We use a video-game to illustrate the use of the method.

Data-driven control benefits from rich datasets, but constructing such datasets becomes challenging when gathering data is limited. We consider an offline experiment design approach to gathering data where we design a control input to collect data that will most improve the performance of a feedback controller. We show how such a control-oriented approach can be used in a setting with linear dynamics and quadratic objective and, through design of a gradient estimator, solve the problem via stochastic gradient descent. We show our formulation numerically outperforms an A- and L-optimal experiment design approach as well as a robust dual control approach.

This paper presents an in-reachability based classification of invariant synchrony patterns in Coupled Cell Networks (CCNs). These patterns are encoded through partitions on the set of cells, whose subsets of synchronized cells are called colors. We study the influence of the structure of the network in the qualitative behavior of invariant synchrony sets, in particular, with respect to the different types of (cumulative) in-neighborhoods and the in-reachability sets. This motivates the proposed approach to classify the partitions into the categories of strong, rooted and weak, according to how their colors are related with respect to the connectivity structure of the network. Furthermore, we show how this classification system acts under the partition join ($ \vee $) operation, which gives us the synchrony pattern that corresponds to the intersection of synchrony sets., Comment: 52 pages, 20 figures, 3 tables

A general upper bound for topological entropy of switched nonlinear systems is constructed, using an asymptotic average of upper limits of the matrix measures of Jacobian matrices of strongly persistent individual modes, weighted by their active rates. A general lower bound is constructed as well, using a similar weighted average of lower limits of the traces of these Jacobian matrices. In a case of interconnected structure, the general upper bound is readily applied to derive upper bounds for entropy that depend only on "network-level" information. In a case of block-diagonal structure, less conservative upper and lower bounds for entropy are constructed. In each case, upper bounds for entropy that require less information about the switching signal are also derived. The upper bounds for entropy and their relations are illustrated by numerical examples of a switched Lotka-Volterra ecosystem model., Comment: 31 pages, 3 figures

We study a scenario where an aircraft has multiple heterogeneous sensors collecting measurements to track a target vehicle of unknown location. The measurements are sampled along the flight path and our goals to optimize sensor placement to minimize estimation error. We select as a metric the Fisher Information Matrix (FIM), as "minimizing" the inverse of the FIM is required to achieve small estimation error. We propose to generate the optimal path from the Hamilton-Jacobi (HJ) partial differential equation (PDE) as it is the necessary and sufficient condition for optimality. A traditional method of lines (MOL) approach, based on a spatial grid, lends itself well to the highly non-linear and non-convex structure of the problem induced by the FIM matrix. However, the sensor placement problem results in a state space dimension that renders a naive MOL approach intractable. We present a new hybrid approach, whereby we decompose the state space into two parts: a smaller subspace that still uses a grid and takes advantage of the robustness to non-linearities and non-convexities, and the remaining state space that can by found efficiently from a system of ODEs, avoiding formation of a spatial grid., Comment: Updated to comply with conference formatting. To appear in the proceedings of the 2023 IEEE Aerospace Conference

We address the problem of finding a local solution to a nonconvex-nonconcave minmax optimization using Newton type methods, including interior-point ones. We modify the Hessian matrix of these methods such that, at each step, the modified Newton update direction can be seen as the solution to a quadratic program that locally approximates the minmax problem. Moreover, we show that by selecting the modification in an appropriate way, the only stable equilibrium points of the algorithm's iterations are local minmax points. As a consequence, the algorithm can only converge towards an equilibrium point if such point is a local minmax, and it will escape if the point is not a local minmax. Using numerical examples, we show that the computation time of our algorithm scales roughly linearly with the number of nonzero elements in the Hessian., Comment: Published at the Journal of the Mathematics of Control, Signals, and Systems

This work makes explicit the degrees of freedom involved in modeling the dynamics of a network, or some other first-order property of a network, such as a measurement function. In previous work, an admissible function in a network was constructed through the evaluation of what we called oracle components. These oracle components are defined through some minimal properties that they are expected to obey. This is a high-level description in the sense that it is not clear how one could design such an object. The goal is to obtain a low-level representation of these objects by unwrapping them into their degrees of freedom. To achieve this, we introduce two decompositions. The first one is the more intuitive one and allows us to define the important concept of coupling order. The second decomposition is built on top of the first one and is valid for the class of coupling components that have finite coupling order. Despite this requirement, we show that this is still a very useful tool for designing coupling components with infinite coupling orders, through a limit approach., Comment: main text has 40 pages and 3 figures. Supplementary appendix has 14 pages

This paper presents a framework based on matrices of monoids for the study of coupled cell networks. We formally prove within the proposed framework, that the set of results about invariant synchrony patterns for unweighted networks also holds for the weighted case. Moreover, the approach described allows us to reason about any multiedge and multiedge-type network as if it was single edge and single-edge-type. Several examples illustrate the concepts described. Additionally, an improvement of the coarsest invariant refinement algorithm to find balanced partitions is presented that exhibits a worst-case complexity of $ \mathbf{O}(\vert\mathcal{C}\vert^3) $, where $\mathcal{C}$ denotes the set of cells., Comment: 29 pages, 7 figures

We study a two-player Stackelberg game with incomplete information such that the follower's strategy belongs to a known family of parameterized functions with an unknown parameter vector. We design an adaptive learning approach to simultaneously estimate the unknown parameter and minimize the leader's cost, based on adaptive control techniques and hysteresis switching. Our approach guarantees that the leader's cost predicted using the parameter estimate becomes indistinguishable from its actual cost in finite time, up to a preselected, arbitrarily small error threshold. Also, the first-order necessary condition for optimality holds asymptotically for the predicted cost. Additionally, if a persistent excitation condition holds, then the parameter estimation error becomes bounded by a preselected, arbitrarily small threshold in finite time as well. For the case where there is a mismatch between the follower's strategy and the parameterized function that is known to the leader, our approach is able to guarantee the same convergence results for error thresholds larger than the size of the mismatch. The algorithms and the convergence results are illustrated via a simulation example in the domain of network security.

The state estimation of continuous-time nonlinear systems in which a subset of sensor outputs can be maliciously controlled through injecting a potentially unbounded additive signal is considered in this paper. Analogous to our earlier work for continuous-time linear systems in \cite{chong2015observability}, we term the convergence of the estimates to the true states in the presence of sensor attacks as `observability under $M$ attacks', where $M$ refers to the number of sensors which the attacker has access to. Unlike the linear case, we only provide a sufficient condition such that a nonlinear system is observable under $M$ attacks. The condition requires the existence of asymptotic observers which are robust with respect to the attack signals in an input-to-state stable sense. We show that an algorithm to choose a compatible state estimate from the state estimates generated by the bank of observers achieves asymptotic state reconstruction. We also provide a constructive method for a class of nonlinear systems to design state observers which have the desirable robustness property. The relevance of this study is illustrated on monitoring the safe operation of a power distribution network., Comment: This paper has been accepted for publication at the 59th IEEE Conference on Decision and Control, 2020

This paper considers a set of sensors, which as a group are tasked with taking measurements of the environment and sending a small subset of the measurements to a centralized data fusion center, where the measurements will be used to estimate the overall state of the environment. The sensors' goal is to send the most informative set of measurements so that the estimate is as accurate as possible. This problem is formulated as a submodular maximization problem, for which there exists a well-studied greedy algorithm, where each sensor sequentially chooses a set of measurements from its own local set, and communicates its decision to the future sensors in the sequence. In this work, sensors can additionally share measurements with one another, in order to augment the decision set of each sensor. We explore how this increase in communication can be exploited to improve the results of the nominal greedy algorithm. Specifically, we show that this measurement passing can improve the quality of the resulting measurement set by up to a factor of $n+1$, where $n$ is the number of sensors.

We consider a two-player zero-sum network routing game in which a router wants to maximize the amount of legitimate traffic that flows from a given source node to a destination node and an attacker wants to block as much legitimate traffic as possible by flooding the network with malicious traffic. We address scenarios with asymmetric information, in which the router must reveal its policy before the attacker decides how to distribute the malicious traffic among the network links, which is naturally modeled by the notion of Stackelberg equilibria. The paper focuses on parallel networks, and includes three main contributions: we show that computing the optimal attack policy against a given routing policy is an NP-hard problem; we establish conditions under which the Stackelberg equilibria lead to no regret; and we provide a metric that can be used to quantify how uncertainty about the attacker's capabilities limits the router's performance.

We present a method for optimal coordination of multiple vehicle teams when multiple endpoint configurations are equally desirable, such as seen in the autonomous assembly of formation flight. The individual vehicles' positions in the formation are not assigned a priori and a key challenge is to find the optimal configuration assignment along with the optimal control and trajectory. Commonly, assignment and trajectory planning problems are solved separately. We introduce a new multi-vehicle coordination paradigm, where the optimal goal assignment and optimal vehicle trajectories are found simultaneously from a viscosity solution of a single Hamilton-Jacobi (HJ) partial differential equation (PDE), which provides a necessary and sufficient condition for global optimality. Intrinsic in this approach is that individual vehicle dynamic models need not be the same, and therefore can be applied to heterogeneous systems. Numerical methods to solve the HJ equation have historically relied on a discrete grid of the solution space and exhibits exponential scaling with system dimension, preventing their applicability to multiple vehicle systems. By utilizing a generalization of the Hopf formula, we avoid the use of grids and present a method that exhibits polynomial scaling in the number of vehicles., Comment: Minor updates to final published version

We study a scenario where a group of agents, each with multiple heterogeneous sensors are collecting measurements of a vehicle and the measurements are transmitted over a communication channel to a centralized node for processing. The communication channel presents an information-transfer bottleneck as the sensors collect measurements at a much higher rate than what is feasible to transmit over the communication channel. In order to minimize the estimation error at the centralized node, only a carefully selected subset of measurements should be transmitted. We propose to select measurements based on the Fisher information matrix (FIM), as "minimizing" the inverse of the FIM is required to achieve small estimation error. Selecting measurements based on the FIM leads to a combinatorial optimization problem. However, when the criteria used to select measurements is both monotone and submodular it allows the use of a greedy algorithm that is guaranteed to be within $1-1/e\approx63\%$ of the optimum and has the critical benefit of quadratic computational complexity. To illustrate this concept, we derive the FIM criterion for different sensor types to which we apply FIM-based measurement selection. The criteria considered include the time-of-arrival and Doppler shift of passively received radio transmissions as well as detected key-points in camera images., Comment: Corrected a minor typo in the references. To appear in the proceedings of the 2020 IEEE Aerospace Conference

The maximization of submodular functions is an NP-Hard problem for certain subclasses of functions, for which a simple greedy algorithm has been shown to guarantee a solution whose quality is within 1/2 of the optimal. When this algorithm is implemented in a distributed way, agents sequentially make decisions based on the decisions of all previous agents. This work explores how limited access to the decisions of previous agents affects the quality of the solution of the greedy algorithm. Specifically, we provide tight upper and lower bounds on how well the algorithm performs, as a function of the information available to each agent. Intuitively, the results show that performance roughly degrades proportionally to the size of the largest group of agents which make decisions independently. Additionally, we consider the case where a system designer is given a set of agents and a global limit on the amount of information that can be accessed. Our results show that the best designs partition the agents into equally-sized sets and allow agents to access the decisions of all previous agents within the same set.

We solve a linear quadratic optimal control problem for sampled-data systems with stochastic delays. The delays are stochastically determined by the last few delays. The proposed optimal controller can be efficiently computed by iteratively solving a Riccati difference equation, provided that a discrete-time Markov jump system equivalent to the sampled-data system is stochastic stabilizable and detectable. Sufficient conditions for these notions are provided in the form of linear matrix inequalities, from which stabilizing controllers and state observers can be constructed., Comment: 28 pages, 3 figures

There is growing evidence regarding the importance of spike timing in neural information processing, with even a small number of spikes carrying information, but computational models lag significantly behind those for rate coding. Experimental evidence on neuronal behavior is consistent with the dynamical and state dependent behavior provided by recurrent connections. This motivates the minimalistic abstraction investigated in this paper, aimed at providing insight into information encoding in spike timing via recurrent connections. We employ information-theoretic techniques for a simple reservoir model which encodes input spatiotemporal patterns into a sparse neural code, translating the polychronous groups introduced by Izhikevich into codewords on which we can perform standard vector operations. We show that the distance properties of the code are similar to those for (optimal) random codes. In particular, the code meets benchmarks associated with both linear classification and capacity, with the latter scaling exponentially with reservoir size.

In this paper, we consider a problem motivated by search-and-rescue applications, where an unmanned aerial vehicle (UAV) seeks to approach the vicinity of a distant quasi-stationary radio frequency (RF) emitter surrounded by local scatterers. The UAV employs only measurements of the Doppler frequency of the received RF signal, along with its own bearing, to continuously adapt its trajectory. We propose and evaluate a trajectory planning approach that addresses technical difficulties such as the unknown carrier frequency offset between the emitter and the UAV's receiver, the frequency drifts of the local oscillators over time, the direction ambiguity in Doppler, and the noise in the observations. For the initial trajectory, the UAV estimates the direction of the emitter using a circular motion, which resolves direction ambiguity. The trajectory is then continuously adapted using feedback from frequency measurements obtained by perturbing the bearing around the current trajectory. We show that the proposed algorithm converges to the vicinity of the emitter, and illustrate its efficacy using simulations., Comment: Submitted to IEEE SPAWC 2018, Greece

Time awareness is critical to a broad range of emerging applications -- in Cyber-Physical Systems and Internet of Things -- running on commodity platforms and operating systems. Traditionally, time is synchronized across devices through a best-effort background service whose performance is neither observable nor controllable, thus consuming system resources independently of application needs while not allowing the applications and OS services to adapt to changes in uncertainty in system time. We advocate for rethinking how time is managed in a system stack. In this paper, we propose a new clock model that characterizes various sources of timing uncertainties in true time. We then present a Kalman filter based time synchronization protocol that adapts to the uncertainties exposed by the clock model. Our realization of a uncertainty-aware clock model and synchronization protocol is based on a standard embedded Linux platform., Comment: In Proc. of the Embedded Operating Systems Workshop, 2016

Research evidence in Cyber-Physical Systems (CPS) shows that the introduced tight coupling of information technology with physical sensing and actuation leads to more vulnerability and security weaknesses. But, the traditional security protection mechanisms of CPS focus on data encryption while neglecting the sensors which are vulnerable to attacks in the physical domain. Accordingly, researchers attach utmost importance to the problem of state estimation in the presence of sensor attacks. In this work, we present SecSens, a novel approach for secure nonlinear state estimation in the presence of modeling and measurement noise. SecSens consists of two independent algorithms, namely, SecEKF and SecOPT, which are based on Extended Kalman Filter and Maximum Likelihood Estimation, respectively. We adopt a holistic approach to introduce security awareness among state estimation algorithms without requiring specialized hardware, or cryptographic techniques. We apply SecSens to securely localize and time synchronize networked mobile devices. SecSens provides good performance at run-time several order of magnitude faster than the state of art solutions under the presence of powerful attacks. Our algorithms are evaluated on a testbed with static nodes and a mobile quadrotor all equipped with commercial ultra-wide band wireless devices.

Through the last decade, we have witnessed a surge of Internet of Things (IoT) devices, and with that a greater need to choreograph their actions across both time and space. Although these two problems, namely time synchronization and localization, share many aspects in common, they are traditionally treated separately or combined on centralized approaches that results in an ineffcient use of resources, or in solutions that are not scalable in terms of the number of IoT devices. Therefore, we propose D-SLATS, a framework comprised of three different and independent algorithms to jointly solve time synchronization and localization problems in a distributed fashion. The First two algorithms are based mainly on the distributed Extended Kalman Filter (EKF) whereas the third one uses optimization techniques. No fusion center is required, and the devices only communicate with their neighbors. The proposed methods are evaluated on custom Ultra-Wideband communication Testbed and a quadrotor, representing a network of both static and mobile nodes. Our algorithms achieve up to three microseconds time synchronization accuracy and 30 cm localization error.

We consider a multi-adversary version of the supervisory control problem for discrete-event systems, in which an adversary corrupts the observations available to the supervisor. The supervisor's goal is to enforce a specific language in spite of the opponent's actions and without knowing which adversary it is playing against. This problem is motivated by applications to computer security in which a cyber defense system must make decisions based on reports from sensors that may have been tampered with by an attacker. We start by showing that the problem has a solution if and only if the desired language is controllable (in the Discrete event system classical sense) and observable in a (novel) sense that takes the adversaries into account. For the particular case of attacks that insert symbols into or remove symbols from the sequence of sensor outputs, we show that testing the existence of a supervisor and building the supervisor can be done using tools developed for the classical DES supervisory control problem, by considering a family of automata with modified output maps, but without expanding the size of the state space and without incurring on exponential complexity on the number of attacks considered., we construct observers that are robust against attacks and lead to an automaton representation of the supervisor. We also develop a test for observability under such replacement-removal attacks by using the so-called product automata., Comment: 17 pages, 2 figures. We have added examples on multi-layer cyber attacks to computer systems

This work introduces the one-class slab SVM (OCSSVM), a one-class classifier that aims at improving the performance of the one-class SVM. The proposed strategy reduces the false positive rate and increases the accuracy of detecting instances from novel classes. To this end, it uses two parallel hyperplanes to learn the normal region of the decision scores of the target class. OCSSVM extends one-class SVM since it can scale and learn non-linear decision functions via kernel methods. The experiments on two publicly available datasets show that OCSSVM can consistently outperform the one-class SVM and perform comparable to or better than other state-of-the-art one-class classifiers.

We study the stabilization of networked control systems with asynchronous sensors and controllers. Offsets between the sensor and controller clocks are unknown and modeled as parametric uncertainty. First we consider multi-input linear systems and provide a sufficient condition for the existence of linear time-invariant controllers that are capable of stabilizing the closed-loop system for every clock offset in a given range of admissible values. For first-order systems, we next obtain the maximum length of the offset range for which the system can be stabilized by a single controller. Finally, this bound is compared with the offset bounds that would be allowed if we restricted our attention to static output feedback controllers., Comment: 32 pages, 6 figures. This paper was partially presented at the 2015 American Control Conference, July 1-3, 2015, the USA

This paper addresses the decomposition of biochemical networks into functional modules that preserve their dynamic properties upon interconnection with other modules, which permits the inference of network behavior from the properties of its constituent modules. The modular decomposition method developed here also has the property that any changes in the parameters of a chemical reaction only affect the dynamics of a single module. To illustrate our results, we define and analyze a few key biological modules that arise in gene regulation, enzymatic networks, and signaling pathways. We also provide a collection of examples that demonstrate how the behavior of a biological network can be deduced from the properties of its constituent modules, based on results from control systems theory., Comment: Journal / technical report, 43 pages, 17 figures

We consider a game played between a hider, who hides a static object in one of several possible positions in a bounded planar region, and a searcher, who wishes to reach the object by querying sensors placed in the plane. The searcher is a mobile agent, and whenever it physically visits a sensor, the sensor returns a random direction, corresponding to a half-plane in which the hidden object is located. We first present a novel search heuristic and characterize bounds on the expected distance covered before reaching the object. Next, we model this game as a large-dimensional zero-sum dynamic game and we apply a recently introduced randomized sampling technique that provides a probabilistic level of security to the hider. We observe that, when the randomized sampling approach is only allowed to select a very small number of samples, the cost of the heuristic is comparable to the security level provided by the randomized procedure. However, as we allow the number of samples to increase, the randomized procedure provides a higher probabilistic security level., Comment: A short version of this paper (without proofs) will be presented at the 18th IFAC World Congress (IFAC 2011), Milan (Italy), August 28-September 2, 2011

We study the problem of estimating vector-valued variables from noisy "relative" measurements. This problem arises in several sensor network applications. The measurement model can be expressed in terms of a graph, whose nodes correspond to the variables and edges to noisy measurements of the difference between two variables. We take an arbitrary variable as the reference and consider the optimal (minimum variance) linear unbiased estimate of the remaining variables. We investigate how the error in the optimal linear unbiased estimate of a node variable grows with the distance of the node to the reference node. We establish a classification of graphs, namely, dense or sparse in Rd,1<= d <=3, that determines how the linear unbiased optimal estimation error of a node grows with its distance from the reference node. In particular, if a graph is dense in 1,2, or 3D, then a node variable's estimation error is upper bounded by a linear, logarithmic, or bounded function of distance from the reference, respectively. Corresponding lower bounds are obtained if the graph is sparse in 1, 2 and 3D. Our results also show that naive measures of graph density, such as node degree, are inadequate predictors of the estimation error. Being true for the optimal linear unbiased estimate, these scaling laws determine algorithm-independent limits on the estimation accuracy achievable in large graphs., Comment: 15 pages, submitted to IEEE Transactions on Information Theory

We consider a decentralized bidirectional control of a platoon of N identical vehicles moving in a straight line. The control objective is for each vehicle to maintain a constant velocity and inter-vehicular separation using only the local information from itself and its two nearest neighbors. Each vehicle is modeled as a double integrator. To aid the analysis, we use continuous approximation to derive a partial differential equation (PDE) approximation of the discrete platoon dynamics. The PDE model is used to explain the progressive loss of closed-loop stability with increasing number of vehicles, and to devise ways to combat this loss of stability. If every vehicle uses the same controller, we show that the least stable closed-loop eigenvalue approaches zero as O(1/N^2) in the limit of a large number (N) of vehicles. We then show how to ameliorate this loss of stability by small amounts of "mistuning", i.e., changing the controller gains from their nominal values. We prove that with arbitrary small amounts of mistuning, the asymptotic behavior of the least stable closed loop eigenvalue can be improved to O(1/N) All the conclusions drawn from analysis of the PDE model are corroborated via numerical calculations of the state-space platoon model., Comment: 14 pages, 11 figures, to appear in IEEE transactions in automatic control in 2009/2010