Search

Numerous state-feedback and observer designs for nonlinear dynamic systems (NDS) have been developed in the past three decades. These designs assume that NDS nonlinearities satisfy one of the following function set classifications: bounded Jacobian, Lipschitz continuity, one-sided Lipschitz, quadratic inner-boundedness, and quadratic boundedness. These function sets are characterized by constant scalars or matrices bounding the NDS’ nonlinearities. These constants depend on the NDS’ operating region, topology, and parameters and are utilized to synthesize observer/controller gains. Unfortunately, there is a near-complete absence of algorithms to compute such bounding constants. In this article, we develop analytical and computational methods to compute such constants. First, for every function set classification, we derive analytical expressions for these bounding constants through global maximization formulations. Second, we utilize a derivative-free interval-based global maximization algorithm based on the branch-and-bound framework to numerically obtain the bounding constants. Third, we showcase the effectiveness of our approaches to compute the corresponding parameters on some NDS such as highway traffic networks and synchronous generator models. [ABSTRACT FROM AUTHOR]

In this article, the problem of online distributed optimization with a set constraint is solved by employing a network of agents. Each agent only has access to a local objective function and set constraint, and can only communicate with its neighbors via a digraph, which is not necessarily balanced. Moreover, agents do not have prior knowledge of their future objective functions. Different from existing works on online distributed optimization, we consider the scenario, where objective functions at each time step are nonconvex. To handle this challenge, we propose an online distributed algorithm based on the consensus algorithm and the mirror descent algorithm. Of particular interest is that regrets involving first-order optimality condition are used to measure the performance of the proposed algorithm. Under mild assumptions on the communication graph and objective functions, we prove that regrets grow sublinearly. Finally, a simulation example is worked out to demonstrate the effectiveness of our theoretical results. [ABSTRACT FROM AUTHOR]

In this article, we propose a notion of high-order (zeroing) barrier functions (HOBFs) that generalizes the concept of zeroing barrier functions and guarantees set forward invariance by checking their higher order derivatives. The proposed formulation guarantees asymptotic stability of the forward invariant set, which is highly favorable for robustness with respect to model perturbations. No forward completeness assumption is needed in our setting in contrast to existing HOBF methods. For the case of controlled dynamical systems, we relax the requirement of uniform relative degree and propose a singularity-free control scheme that yields a locally Lipschitz control signal and guarantees safety. Furthermore, the proposed formulation accounts for “performance-critical” control: it guarantees that a subset of the forward invariant set will admit any existing, bounded control law while still ensuring forward invariance of the set. Finally, a nontrivial case study with rigid-body attitude dynamics and interconnected cell regions as the safe region is investigated. [ABSTRACT FROM AUTHOR]

Control scheduling refers to the problem of assigning agents or actuators to act upon a dynamical system at specific times so as to minimize a quadratic control cost, such as the objectives of the linear-quadratic-Gaussian (LQG) or linear quadratic regulator problems. When budget or operational constraints are imposed on the schedule, this problem is in general NP-hard and its solution can therefore only be approximated even for moderately sized systems. The quality of this approximation depends on the structure of both the constraints and the objective. This article shows that greedy control scheduling is near-optimal when the constraints can be written as an intersection of matroids, algebraic structures that encode requirements such as limits on the number of agents deployed per time slot, total number of actuator uses, and duty cycle restrictions. To do so, it proves that the LQG cost function is $\alpha$ -supermodular and provides new $\alpha /(\alpha + P)$ -optimality certificates for the greedy minimization of such functions over an intersection of $P$ matroids. These certificates are shown to approach the $1/(1+P)$ guarantee of supermodular functions in relevant settings. These results support the use of greedy algorithms in nonsupermodular quadratic control problems as opposed to typical heuristics such as convex relaxations and surrogate figures of merit, e.g., the $\log \det$ of the controllability Gramian. [ABSTRACT FROM AUTHOR]

This article considers the optimal control problem for path-constrained switched systems with guaranteed feasibility. First, a method is proposed to reduce continuous path constraints of the switched systems into discrete abstract constraints in terms of the switch time vector and the input. Second, differentiability of the optimal value function, i.e., the cost function optimized over the input, is analyzed by using perturbation analysis theory. For a given switch time vector, the derivative of the optimal value function is proved equal to the derivative of the cost function evaluated at the optimal input provided that there is a unique optimal input in the optimal set of the cost function for continuous inputs. Third, a bilevel algorithm is proposed to find optimal switch times and the optimal input with guaranteed satisfaction of path constraints over the entire time horizon. At the inner level, the input is optimized by iteratively solving dynamic optimization problems of path-constrained switched systems with fixed switch time vector, and at the outer level, the fixed switch time vector is optimized by sequentially solving quadratic programs related to the optimal value function of switch time vectors. Fourth, it is rigorously proven that the bilevel algorithm terminates within a finite number of iterations. Finally, a numerical example is provided to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We prove a robust converse barrier function theorem via the converse Lyapunov theory. While the use of a Lyapunov function as a barrier function is straightforward, the existence of a converse Lyapunov function as a barrier function for a given safety set is not. We establish this link by a robustness argument. We show that the closure of the forward reachable set of a robustly safe set must be robustly asymptotically stable under mild technical assumptions. As a result, all robustly safe dynamical systems must admit a robust barrier function in the form of a Lyapunov function for set stability. We present the results in both continuous-time and discrete-time settings and remark on connections with various barrier function conditions. [ABSTRACT FROM AUTHOR]

An extended quadratic function is a quadratic function plus the indicator function of an affine set, i.e., a quadratic function with embedded linear equality constraints. In this article, we show that, under some technical conditions, random convex extended quadratic functions are closed under addition, composition with an affine function, expectation, and partial minimization, i.e., minimizing over some of its arguments. These properties imply that dynamic programming can be tractably carried out for stochastic control problems with random affine dynamics and extended quadratic cost functions. While the equations for the dynamic programming iterations are much more complicated than for traditional linear quadratic control, they are well suited to an object-oriented implementation, which we describe. We also describe a number of known and new applications. [ABSTRACT FROM AUTHOR]

Submodular maximization has applications in networked control, data summarization, and path planning, among other areas. While several efficient algorithms with provable optimality bounds have been developed for maximizing a single submodular function, the more computationally challenging problem of maximizing the minimum of a set of submodular functions (robust submodular maximization) has received less research attention. In this article, we investigate robust submodular maximization when the objective functions are correlated, i.e., the marginal benefits of adding elements to each function are within a given ratio of each other. We propose two modified greedy algorithms that exploit our defined correlation ratio to achieve the provable optimality bounds under matroid and cardinality constraints. As a case study, we consider minimization of graph effective resistance, and derive bounds on the correlation ratio using the graph spectrum. Our results are evaluated through numerical study. [ABSTRACT FROM AUTHOR]

Actuator placement is an active field of research, which has received significant attention for its applications in complex dynamical networks. In this article, we study the problem of finding a set of actuator placements minimizing the metric that measures the average energy consumed for state transfer by the controller, while satisfying a structural controllability requirement and a cardinality constraint on the number of actuators allowed. As no computationally efficient methods are known to solve such combinatorial set function optimization problems, two greedy algorithms, forward and reverse, are proposed to obtain approximate solutions. We first show that the constraint sets these algorithms explore can be characterized by matroids. We then obtain performance guarantees for the forward and reverse greedy algorithms applied to the general class of matroid optimization problems by exploiting properties of the objective function such as the submodularity ratio and the curvature. Finally, we propose feasibility check methods for both algorithms based on maximum flow problems on certain auxiliary graphs originating from the network graph. Our results are verified with case studies over large networks. [ABSTRACT FROM AUTHOR]

We investigate the enforcement of opacity, an information-flow privacy property, using insertion sequences that modify the output of the system by event insertions. Previous work considered the problem of enforcing the opacity under the assumption that the insertion functions were based on the observed system strings. Now, we investigate the more powerful method of insertion sequences based on the exact system states and events. In this case, the insertion function would be embedded into the system itself, rather than being an output interface. In this article, we develop methods that verify if a valid insertion function exists in this setting; if one exists, synthesize one using a computationally effective algorithm; and investigate a special case where it is possible to verify and synthesize a valid embedded insertion function with polynomial complexity in the size of the system. [ABSTRACT FROM AUTHOR]

Starting from a symmetrization and extension of the basic definitions and results of dissipativity theory, we obtain new results on cyclo-dissipativity, in particular on external characterization and description of the set of storage functions. [ABSTRACT FROM AUTHOR]

We investigate a linear-quadratic-Gaussian (LQG) control and sensing codesign problem, where one jointly designs sensing and control policies. We focus on the realistic case where the sensing design is selected among a finite set of available sensors, where each sensor is associated with a different cost (e.g., power consumption). We consider two dual problem instances: sensing-constrained LQG control, where one maximizes a control performance subject to a sensor cost budget, and minimum-sensing LQG control, where one minimizes a sensor cost subject to performance constraints. We prove that no polynomial time algorithm guarantees across all problem instances a constant approximation factor from the optimal. Nonetheless, we present the first polynomial time algorithms with per-instance suboptimality guarantees. To this end, we leverage a separation principle, which partially decouples the design of sensing and control. Then, we frame LQG codesign as the optimization of approximately supermodular set functions; we develop novel algorithms to solve the problems; and we prove original results on the performance of the algorithms and establish connections between their suboptimality and control-theoretic quantities. We conclude the article by discussing two applications, namely, sensing-constrained formation control and resource-constrained robot navigation. [ABSTRACT FROM AUTHOR]

In this paper, we propose an event-based sampling policy to implement a constraint-tightening, robust MPC method. The proposed policy enjoys a computationally tractable design and is applicable to perturbed, linear time-invariant systems with polytopic constraints. In particular, the triggering mechanism is suitable for plants with no centralized sensory node as the triggering mechanism can be evaluated locally at each individual sensor. From a geometrical viewpoint, the mechanism is a sequence of hyperrectangles surrounding the optimal state trajectory such that robust recursive feasibility and robust stability are guaranteed. The design of the triggering mechanism is cast as a constrained parametric-in-set optimization problem with the volume of the set as the objective function. Reparameterized in terms of the set vertices, we show that the problem admits a finite tractable convex program reformulation and a linear program relaxation. Several numerical examples are presented to demonstrate the effectiveness and limitations of the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we study connections between structured storage or Lyapunov functions of a class of interconnected systems (dynamical networks) and dissipativity properties of the individual systems. We prove that if a dynamical network, composed as a set of linear time invariant systems interconnected over an acyclic graph, admits an additive quadratic Lyapunov function, then the individual systems in the network are dissipative with respect to a (nonempty) set of interconnection neutral supply functions. Each supply function from this set is defined on a single interconnection link in the network. Specific characterizations of neutral supply functions are presented, which imply robustness of network stability/dissipativity to removal of interconnection links. [ABSTRACT FROM AUTHOR]

In this paper, a novel distributed stochastic approximation algorithm (DSAA) is proposed to seek roots of the sum of local functions, each of which is associated with an agent from multiple agents connected over a network. At each iteration, each agent updates its estimate for the root utilizing the noisy observations of its local function and the information derived from the neighboring agents. The key difference of the proposed algorithm from the existing ones consists in the expanding truncations (so it is called the DSAAWET), by which the boundedness of the estimates can be guaranteed without imposing the growth-rate constraints on the local functions. The estimates generated by the DSAAWET are shown to converge almost surely to a consensus set, which belongs to a connected subset of the root set of the sum function. In comparison with the existing results, we impose weaker conditions on the local functions and on the observation noise. We then apply the proposed algorithm to two applications, one from signal processing and the other one from distributed optimization, and establish the almost sure convergence. Numerical simulation results are also included. [ABSTRACT FROM AUTHOR]

We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in nonstationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to Markov decision processes, in which the target sets and control policies are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study. [ABSTRACT FROM AUTHOR]

This paper studies the consensus tracking problem of uncertain Lagrangian systems. In contrast to the existing results where the command signals are sufficiently smooth, we consider a class of nonsmooth command signals generated by a switched command generator, which might be more realistic from the perspective of practical applications. The main technical innovations of this paper are threefold. First, to enable a rigorous problem formulation, some piecewise decaying function sets are defined to precisely describe the steady-state behaviors of the tracking errors. Second, to ensure the stability of the switched nonlinear closed-loop system, a system-based scaling method with the establishment of several lemmas is developed to determine the minimal dwell time of the switching signal. Third, a quantitative analysis is performed to acquire the ultimate bound for the steady-state tracking errors. The proposed control approach is evaluated by a simulation example. [ABSTRACT FROM AUTHOR]

We consider the leader selection problem in a network with consensus dynamics where both leader and follower agents are subject to stochastic external disturbances. The performance of the system is quantified by the total steady-state variance of the node states, and the goal is to identify the set of leaders that minimizes this variance. We first show that this performance measure can be expressed as a submodular set function over the nodes in the network. We then use this result to analyze the performance of two greedy, polynomial-time algorithms for leader selection, showing that the leader sets produced by the greedy algorithms are within provable bounds of optimal. [ABSTRACT FROM AUTHOR]

For the control of discrete event systems, the notion of directed control refines that of supervisory control. A directed controller is one that selects at most one controllable event to be enabled at any state (without disabling any uncontrollable event), which is in fact how a discrete event control is implemented. In contrast, a supervisory controller computes a maximal allowable set of controllable events at each state, leaving undecided exactly which controllable event should be enabled. In previous works, we developed a framework for the computation of optimal directed controllers and a polynomial synthesis algorithm for acydlic plants. In this paper, we present a novel synthesis approach for general plants, i.e., plants with or without cycles, thus providing a complete solution to the optimal directed control problem. The complexity of the approach remains polynomial in the size of plant. [ABSTRACT FROM AUTHOR]

In the above paper, it was claimed that the necessary and sufficient conditions for the quadratic stability and stabilization of dynamic interval systems are given in terms of linear matrix inequalities (LMIs). In this note, numerical examples are presented to show that the necessity of the conditions given in [1] does not hold. [ABSTRACT FROM AUTHOR]

The article reports that the existing generalization of the direct Routh table truncation method for interval systems fails to produce a stable system. Additionally, it was shown how to extend the method to ensure the stability of the resulting interval system. An omission in the proposed algorithm of building interval Routh table-the newly calculated line in the table may be inconsistent with the last existing line. Two additional conditions should be formulated to avoid this situation. To obtain the self-contained interval Routh table one should replace the first column of the table. The aforementioned additional conditions ensure the stability of the interval polynomial constructed from the truncated interval Routh table and at the same time argue the claim of stating that it is impossible to ensure stability of the interval Routh approximants. The point-by-point property holds only for pairs of rows and not for the span of three rows-and again it is not problematic.