Search

This paper proposes a novel robust fault detection (FD) approach and designs a set-theoretic unknown input observer (SUIO) for linear parameter-varying (LPV) systems with both state and output equations scheduled by inexact scheduling variables. First, for such LPV systems, we propose a novel robust FD method by combing the set theory with the unknown input observer, which considers the bounds of measurement errors of scheduling variables to generate FD-oriented sets. In general, as long as sensors with sufficiently high precision are equipped to measure the scheduling variables, the bounds of measurement errors of scheduling variables can be less conservative than those direct bounds of scheduling variables, which can reduce robust FD conservatism in this way. Second, we give the unknown input decoupling condition of SUIO for such LPV systems and propose an SUIO design method under this condition for robust state estimation (SE). Besides, stability conditions for the proposed methods are established via matrix inequalities. At the end of this paper, a case study is used to illustrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

With the advent of networked embedded control systems (NECSs) new opportunities and challenges have arisen. Among others, the challenges result mostly from variable communication delays, access constraints, and resource constraints. An event-based control and scheduling (EBCS) codesign strategy for NECSs involving a set of continuous-time LTI plants is proposed in this paper addressing all aforementioned challenges. A novel representation of the network-induced delay as an uncertain variable belonging to a finite set of different bounded intervals is further proposed. The transition from one bounded interval to another can be arbitrary or according to a stochastic process. Regarding the type of the transition and the resulting discrete-time switched polytopic system of the NECS, two versions of the EBCS problem are introduced: A robust EBCS problem under arbitrary transition and a stochastic EBCS problem under stochastic transition. Global uniform practical stability with guaranteed performance (measured by a quadratic cost function) is guaranteed for both versions after formulating them as LMI optimization problems. The effectiveness of the proposed EBCS strategy is illustrated along with a comparison between its versions for a set of mobile robots. Notably, the EBCS strategy is generally applicable to discrete-time switched polytopic systems. [ABSTRACT FROM AUTHOR]

This paper presents a supervisory algorithm that prevents side collisions among vehicles at an intersection by taking control of vehicles when necessary. Based on the vehicles’ current state and drivers’ desired inputs, the supervisor verifies whether there exists an input signal with which vehicles can cross the intersection without collision. Instead of directly searching for the existence of such an input signal, we solve an equivalent jobshop scheduling problem, which leads to a more tractable solution. The jobshop scheduling problem determines the existence of a schedule, i.e., times at which vehicles can enter conflict areas within an intersection, such that vehicles do not meet in any conflict area. This problem is approximately solved via two mixed integer linear programming problems formulated for simplified vehicle dynamics. The solutions to these problems provide over- and underapproximations of the solution to the jobshop scheduling problem with quantified approximation bounds. We theoretically demonstrate that this supervisor keeps the intersection safe and is nonblocking. Computer simulations further validate that the algorithm can run in real time for problems of realistic size. [ABSTRACT FROM PUBLISHER]

Timely examination becomes more and more important for the diagnosis of patients. When the patient arrives for reserving the examination, the scheduler needs to instantly assign a date to the patient by weighing the following factors: the acceptance of current lower-priority patient request may result in the rejection of future higher-priority and more urgent patients, whereas the rejection of the current patient may lead to the unused diagnostic capacity. To deal with this problem, this paper proposes a finite-horizon Markov decision process (MDP) model for optimal outpatients scheduling by considering their waiting time target, i.e., the maximal waiting time the patient can endure. Two types of outpatients with different waiting time targets and different rewards are considered. The objective is to maximize the expected revenue. Two time dimensions, i.e., days and time periods within a day, are used to model patient arrivals and their waiting time targets. A complete characterization of the optimal scheduling policy is given by proving the monotonicity and concavity properties of the reward functions, switching curves between different scheduling options of an incoming patient, and dynamic evolution of the optimal control policy. Extensive numerical experiments are performed to show the impact of different parameters and compare the optimal policy with other simple policies including two designed with the properties of the optimal policy. [ABSTRACT FROM AUTHOR]

In this paper, we consider dynamic channel allocation for remote state estimation of multiagent systems. For each subsystem, a sensor measures its state and transmits the data via a packet-dropping channel, which is dynamically allocated by the remote estimator. We first formulate the problem as a Markov decision process. Given the difficulty of obtaining an optimal policy of large-scale problems, we develop a suboptimal heuristic policy based on the Whittle index for the restless multiarmed bandit (RMAB) problem. The performance of the Whittle index policy is evaluated from both theoretical and practical aspects. The strong performance of Whittle index policy is illustrated by the numerical examples. [ABSTRACT FROM AUTHOR]

The design of power-aware lifetime maximization algorithms for sensor networks is an active area of research. However, the standard assumption is that the performance of the sensors remains the same throughout the network's lifetime, which is not always true. In this paper, we study the effects of power decay on the performance of individual sensors as well as of the entire network. In particular, we examine networks with decaying footprints, akin to those of RF or radar-based sensors and relate the performance of a sensor to its available power. Moreover, we propose probabilistic scheduling controllers that compensate for the effects of the decrease in power while maintaining an adequate probability of event detection under two sensing models; Boolean and non-Boolean. We simulate the performance of the proposed controllers to establish that the desired performance levels are indeed maintained throughout the lifetime of the network. [ABSTRACT FROM AUTHOR]

For systems that are affected by a priori unknown but on-line measurable dynamic components (such as parameters, nonlinearities or delays), we propose a novel design algorithm for controllers that are on-line scheduled by these so-called structured uncertainties in order to achieve closed-loop stability and a certain desired level of performance. Both the plant and the controller are assumed to admit a description in terms of a linear time-invariant system in feedback with the uncertainties as is standard in robust control. In contrast to the existing results in the literature, dynamic (i.e., frequency-dependent) D-scales are used to guarantee robust stability (and performance) of the closed-loop system in the form of frequency-dependent inequalities. Based on these well-known analysis results, it is shown in this paper how to completely reduce the synthesis of gain-scheduled controllers with dynamic D-scalings to a system of linear matrix inequalities. We sketch various potential applications of our main result and illustrate the advantages of frequency dependence in the D-scales by a simple numerical example. [ABSTRACT FROM AUTHOR]

We formulate the optimal dynamic sampling allocation decision problem for feasibility determination as a stochastic control problem in a Bayesian setting. This new formulation addresses the limitations of previous static optimization formulations. In an approximate dynamic programming paradigm, we propose an approximately optimal allocation policy that maximizes a single feature of the value function one step ahead. Numerical results demonstrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

A multi-hop control network (MCN) consists of a plant where the communication between sensors, actuators, and computational units is supported by a (wireless) multi-hop communication network, and data flow is performed using scheduling and routing of sensing and actuation data. We address the control design problem on a MCN where the plant is a SISO LTI system and links are subject to permanent failures. We first characterize controllability and observability of a MCN: we provide necessary and sufficient conditions on the plant dynamics and on the communication scheduling, and we provide a design methodology to satisfy such conditions for any failure configuration. Then we address the problem of detecting the failure of links of the radio connectivity graph: we provide necessary and sufficient conditions on the plant dynamics and on the communication protocol, and we provide a design methodology to satisfy the above conditions. [ABSTRACT FROM AUTHOR]

A fundamental component of the game-theoretic approach to distributed control is the design of local utility functions. Relative to resource allocation problems that are additive over the resources, Part I showed how to design local utilities so as to maximize the associated performance guarantees (Paccagnan, et al., 2020), which we measure by the price of anarchy. The purpose of this article is to specialize these results to the case of submodular, covering, and supermodular problems. In all these cases, we obtain tight expressions for the price of anarchy that often match or improve the guarantees associated with state-of-the-art approximation algorithms. Two applications and corresponding numerics are presented: the vehicle-target assignment problem and a coverage problem arising in wireless data caching. [ABSTRACT FROM AUTHOR]

We study the deadline scheduling problem for multiple deferrable jobs that arrive in a random manner and are to be processed before individual deadlines. The processing of the jobs is subject to a time-varying limit on the total processing rate at each stage. We formulate the scheduling problem as a restless multiarmed bandit problem. Relaxing the scheduling problem into multiple independent single-arm scheduling problems, we define the Lagrangian priority value as the greatest tax under which it is optimal to activate the arm. We propose a Lagrangian priority policy that processes jobs in the order of their Lagrangian priority values, and establish its asymptotic optimality as the system scales. Numerical results show that the proposed Lagrangian priority policy achieves 22%–49% higher average reward than the classical Whittle index policy (that does not take into account the processing rate limits). [ABSTRACT FROM AUTHOR]

We study the joint scheduling of deferrable demands (e.g., the charging of electric vehicles) and storage systems in the presence of random supply, demand arrivals, processing costs, and subject to processing rate limit constraint. We formulate the scheduling problem as a dynamic program so as to minimize the expected total cost, the sum of processing costs, and the noncompletion penalty (incurred when a task is not fully processed by its deadline). Under mild assumptions, we characterize an optimal index-based priority rule: Tasks with less laxity should be processed first, and for two tasks with the same laxity, the task with a later deadline has the priority. Based on the established optimal control policy characterizations (on resource allocation among multitasks and storage operation), we propose to apply data-driven reinforcement learning (RL) methods to make energy procurement decisions. Numerical results show that the proposed approach significantly outperforms existing RL methods combined with the earliest deadline first priority rule (by reducing 26%–32% of system cost). [ABSTRACT FROM AUTHOR]

In this article, we investigate the problem of actuator selection for linear dynamical systems. We develop a framework to design a sparse actuator schedule for a given large-scale linear system with guaranteed performance bounds using deterministic polynomial-time and randomized approximately linear-time algorithms. First, we introduce systemic controllability metrics for linear dynamical systems that are monotone and homogeneous with respect to the controllability Gramian. We show that several popular and widely used optimization criteria in the literature belong to this class of controllability metrics. Our main result is to provide a polynomial-time actuator schedule that on average selects only a constant number of actuators at each time step, independent of the dimension, to furnish a guaranteed approximation of the controllability metrics in comparison to when all actuators are in use. Our results naturally apply to the dual problem of sensor selection, in which we provide a guaranteed approximation to the observability Gramian. We illustrate the effectiveness of our theoretical findings via several numerical simulations using benchmark examples. [ABSTRACT FROM AUTHOR]

This article proposes a resource-aware triggering-based dynamic controller codesign scheme for Markov jump systems (MJSs) to fulfill both disturbance rejection and computational resources saving goals. Specifically, a self-trigger strategy is presented for precomputing the next execution time for state measurement, executing the controller, and updating the actuators using the current sampled information. To achieve a desired system performance and reduce the resource occupation, the self-triggering parameters and the gains of state feedback controller are codesigned. Moreover, a dynamic triggering technique is employed to improve the system performance by adapting the trigger coefficients to the different subsystems of MJSs. The effectiveness of the proposed method is demonstrated via two examples. [ABSTRACT FROM AUTHOR]

Advanced persistent threats (APTs) infiltrate cyber systems and compromise specifically targeted data and/or resources through a sequence of stealthy attacks consisting of multiple stages. Dynamic information flow tracking has been proposed to detect APTs. In this article, we develop a dynamic information flow tracking game for resource-efficient detection of APTs via multistage dynamic games. The game evolves on an information flow graph, whose nodes are processes and objects (e.g., file, network endpoints) in the system and the edges capture the interaction between different processes and objects. Each stage of the game has prespecified targets that are characterized by a set of nodes of the graph. The goal of the APT is to evade detection and reach a target node of each stage. The goal of the defender is to maximize the detection probability while minimizing performance overhead on the system. The resource costs of the players are different and the information structure is asymmetric, resulting in a nonzero-sum imperfect information game. We first calculate the best responses of the players and then compute Nash equilibrium for single-stage attacks. We then provide a polynomial-time algorithm to compute a correlated equilibrium for the multistage attack case. Finally, we simulate our model and algorithm on real-world nation state attack data obtained from the Refinable Attack INvestigation (RAIN) system. [ABSTRACT FROM AUTHOR]

Mechanism design for fully strategic agents typically assumes that agents broadcast their messages to a central authority that performs allocation and taxes/subsidizes agents. In addition, most of the designed mechanisms do not provide any guarantees that the Nash equilibrium (NE) will be reached asymptotically. Whenever such results are provided, they refer to convergence of specific predesigned learning dynamics and it is assumed that agents will follow such prescription. Both assumptions are an impediment in practical application of mechanism design in real-life allocation problems. In this article, we consider two common resource allocation problems: sharing K infinitely divisible resources among strategic agents for their private consumption (private goods), and determining the level for an infinitely divisible public good with P features, that is shared between strategic agents. For both cases, we present a distributed mechanism for a set of agents who communicate through a given network. In a distributed mechanism, agents’ messages are not broadcasted to all other agents as in the standard mechanism design framework, but are exchanged only in the local neighborhood of each agent. The presented mechanisms produce a unique NE, they fully implement the social welfare maximizing allocation, and are budget-balanced at NE. Subsequently, it is shown that the mechanisms induce a game with contractive best-response, leading to guaranteed convergence for all learning dynamics within the adaptive best-response dynamics class, including dynamics such as Cournot best-response, k-period best-response, and Fictitious Play. While the abovementioned mechanisms have message dimensionality that grows quadratically with the number of agents, we show that if one is willing to forgo the strong convergence guarantees, it is possible to design a distributed mechanism with total message space dimensionality growing only linearly with the number of agents. Finally, we demonstrate the abovementioned results through a numerical study of convergence under repeated play, for various communication graphs and learning dynamics. [ABSTRACT FROM AUTHOR]

In the local approach to linear parameter varying (LPV) system identification, it is widely acknowledged that locally estimated linear state-space models should be made coherent before being interpolated, but the accurate meaning of the term “coherent” or “coherence” is rarely defined. The purpose of this article is to analyze the relevance of two existing definitions and to point out the consequence of this analysis on the practice of LPV system identification. [ABSTRACT FROM AUTHOR]

We consider the problem of controlling the dynamic state of each of a finite collection of targets distributed in physical space using a much smaller collection of mobile agents. Each agent can attend to no more than one target at a given time, thus agents must move between targets to control the collective state, implying that the states of each of the individual targets are only controlled intermittently. We assume that the state dynamics of each of the targets are given by a linear, time-invariant, controllable system, and develop conditions on the visiting schedules of the agents to ensure that the property of controllability is maintained in the face of the intermittent control. We then introduce constraints on the magnitude of the control input and a bounded disturbance into the target dynamics and develop a method to evaluate system performance under this scenario. Finally, we use this method to determine how the amount of time the agents spend at a given target, before switching to the next in its sequence, influences the control of the states of the entire collection of targets. [ABSTRACT FROM AUTHOR]

We consider a class of continuous-time hybrid dynamical systems that correspond to subgradient flows of a piecewise linear and convex potential function with finitely many pieces, and which includes the fluid-level dynamics of the Max-Weight scheduling policy as a special case. We study the effect of an external disturbance/perturbation on the state trajectory, and establish that the magnitude of this effect can be bounded by a constant multiple of the integral of the perturbation. [ABSTRACT FROM AUTHOR]

We consider the problem of dynamically scheduling $M$ out of $N$ binary Markov chains when only noisy observations of state are available, with ergodic (equivalently, long run average) reward. By passing on to the equivalent problem of controlling the conditional distribution of state given observations and controls, it is cast as a restless bandit problem and its Whittle indexability is established. [ABSTRACT FROM PUBLISHER]

We consider sensor data scheduling with communication energy constraint for remote state estimation over a time-varying fading channel. Given that the fade channel state with temporal correlated variation influences the estimation accuracy, the goal is to obtain a schedule for a sensor to decide whether using high energy to send its local estimate to a remote estimator in order to minimize the expected average estimation error covariance. By exploiting the feedback information, we propose an effective closed-form dynamic stationary scheduling scheme. We prove that such simple schedule is optimal in terms of the estimation performance by comparing with a general stationary schedule under energy constraint. Furthermore, we derive the sufficient and necessary condition for estimation stability when the sensor can only use low energy at each time. Numerical examples are provided to illustrate the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

Sparse resource allocation to shape a network dynamical process is studied. Specifically, we consider allocating limited distributed control resources among a subset of a network's nodes, to minimize the dominant eigenvalue of a linear dynamical spread process associated with the network. Structural characterizations of the closed-loop dynamics at the optimum are obtained. These results are then used to 1) develop constructive algorithms for optimal resource allocation, 2) identify limits on the control performance, and 3) understand the relationship between the network's graph and the optimal resource profile. While the focus here is on a simplified linear model, an exploratory study of the design's applicability to realistic stochastic and nonlinear spread processes is undertaken, via simulation examples. As a whole, this study advances a research thrust on disease spread control in networks, toward the realistic paradigm that control resources can only be allocated at a subset of network locations. [ABSTRACT FROM AUTHOR]

In this note, we consider a nonlinear process with delayed dynamics to be controlled over a communication network in the presence of disturbances and study robustness of the resulting closed-loop system with respect to network-induced phenomena such as sampled, distorted, delayed and lossy data as well as scheduling protocols. For given plant-controller dynamics and communication network properties (e.g., propagation delays and scheduling protocols), we quantify the control performance level (in terms of \mathcalLp- gains) as the transmission interval varies. Maximally Allowable Transfer Interval (MATI) labels the greatest transmission interval for which a prespecified \mathcalLp- gain is attained. The proposed methodology combines impulsive delayed system modeling with Lyapunov-Razumikhin techniques to allow for MATIs that are smaller than the communication delays. Other salient features of our methodology are the consideration of variable delays, corrupted data and employment of model-based estimators to prolong MATIs. The present stability results are provided for the class of Uniformly Globally Exponentially Stable (UGES) scheduling protocols. The well-known Round Robin (RR) and Try-Once-Discard (TOD) protocols are examples of UGES protocols. Finally, a nonlinear example is provided to demonstrate the benefits of the proposed approach. [ABSTRACT FROM PUBLISHER]

We consider the scheduling of multiple tasks with pre-determined deadlines under arbitrarily random processing cost and task arrival. This problem is motivated by the potential of large scale adoption of plug-in (hybrid) electric vehicles (PHEVs) in the near future. We seek to properly schedule the battery charging of multiple PHEVs so as to minimize the overall cost, which is derived from the total charging cost and the penalty for not completing charging before requested deadlines. Through a dynamic programming formulation, we establish the Less Laxity and Longer remaining Processing time (LLLP) principle that improves any charging policy on a sample-path basis, when the non-completion penalty is a convex function of the additional time needed to fulfill the uncompleted request. Specifically, the LLLP principle states that priority should be given to vehicles that have less laxity and longer remaining processing times. Numerical results demonstrate that heuristic policies that violate the LLLP principle, for example, the earliest deadline first policy, can result in significant performance loss. [ABSTRACT FROM AUTHOR]

In this technical note, we consider the dynamic coverage control problem from a clustering perspective, to which we apply control-theoretic methods to identify and track the cluster center dynamics. To the authors' knowledge, this is the first work to consider tracking cluster centers when the dynamics of the system elements involve acceleration fields. We show that a dynamic control design is necessary to achieve dynamic coverage under these acceleration fields. We pose the goal of maximizing the instantaneous coverage as a combinatorial optimization problem, and propose a framework that extends the concepts of the deterministic annealing algorithm to the dynamic setting. The resulting Lagrangian is used as a control Lyapunov function for designing coverage control. The algorithms we propose guarantee asymptotic tracking of cluster group dynamics, and we further establish continuity and boundedness of the corresponding control laws. Simulations are provided to corroborate these results. [ABSTRACT FROM AUTHOR]

We consider a discrete time queueing system where a controller makes a 2-stage decision every slot. The decision at the first stage reveals a hidden source of randomness with a control-dependent (but unknown) probability distribution. The decision at the second stage generates an attribute vector that depends on this revealed randomness. The goal is to stabilize all queues and optimize a utility function of time average attributes, subject to an additional set of time average constraints. This setting fits a wide class of stochastic optimization problems, including multi-user wireless scheduling with dynamic channel measurement decisions, and wireless multi-hop routing with multi-receiver diversity and opportunistic routing decisions. We develop a simple max-weight algorithm that learns efficient behavior by averaging functionals of previous outcomes. [ABSTRACT FROM PUBLISHER]

Linear parameter-varying (LPV) systems are usually described in either state-space or input–output form. When analyzing system equivalence between different representations it appears that the time-shifted versions of the scheduling signal (dynamic dependence) need to be taken into account. Therefore, representations used previously to define and specify LPV systems are not equal in terms of dynamics. In order to construct a parametrization-free description of LPV systems that overcomes these difficulties, a behavioral approach is introduced that serves as a basis for specifying system theoretic properties. LPV systems are defined as the collection of trajectories of system variables (like inputs and outputs) and scheduling variables. LPV kernel, input–output, and state-space system representations are introduced with appropriate equivalence transformations. [ABSTRACT FROM AUTHOR]

We discuss adding a measure of scheduling to the popular Anti-Windup design. The main idea is to develop a scheme in which the Anti-Windup gains depend on how much the actuator command exceeds the saturation bound. The aim is to design and implement more aggressive Anti-windup gains in lower levels of saturation. Global stability and performance are addressed by adding an outer-loop Anti-windup compensation which become active when the system is in higher levels of saturation. We present results for both static and dynamic Anti-Windup gains, along with the convex synthesis LMIs. Benefits of the proposed design method are shown using well-known examples. [ABSTRACT FROM AUTHOR]