Search

This work extends recent results on lifted controlled invariant sets for discrete-time controllable linear systems to non-convex safe sets, consisting of a union of polytopes. First, we show how to construct a closed-form expression of an invariant set in an extended state and input space using additional binary variables. A more efficient encoding is also provided albeit with additional conservativeness. By avoiding the projection of this set onto the original state space, we use this implicit representation in the lifted space as a supervisor in an online planning context where the safe set grows as new information about the environment is sensed. An example with a double-integrator model with a LiDAR sensor is used to demonstrate the overall approach.

We study the problem of synthesizing controllers that enforce hard state-constraints under occasionally missing state measurements. Although the problem can be solved as a partial information game via power set construction, it is undesired to do so because power set construction is computationally expensive. In this paper, we consider the instances where the missing data pattern can be specified by an automaton, and show that, for such cases, the synthesis problem admits a simpler solution. We introduce string automata and exploit the causality requirement to define the structure of the controller, and further use this structure to derive a product system. The synthesis problem then reduces to a full-information game on this product system. Two examples illustrate the efficacy of the proposed approach.

Non-asymptotic bounded-error state estimators that provide hard bounds on the estimation error are crucial for safety-critical applications. This paper proposes a class of optimal bounded-error affine estimators to achieve a novel property we are calling Equalized Recovery that can be computed by leveraging ideas from the dual problem of affine finite horizon optimal control design. In particular, by using Q-parametrization, the estimator design problem is reduced to a convex optimization problem. An extension of this estimator to handle missing data (e.g., due to package drops or sensor glitches) is also proposed. These ideas are illustrated with a numerical example motivated by vehicle safety systems.

We consider the problem of incrementally segmenting auto-regressive models with exogenous inputs (ARX models) when the data is received sequentially at run-time. In particular, we extend a recently proposed dynamic programming based polynomial-time algorithm for offline (batch) ARX model segmentation to the incremental setting. The new algorithm enables sequential updating of the models, eliminating repeated computation, while remaining optimal. We also show how certain noise bounds can be used to detect switches automatically at run-time. The efficiency of the approach compared to the batch method is illustrated on synthetic and real data.

This paper considers the design of separating input signals in order to discriminate among a finite number of uncertain nonlinear models. Each nonlinear model corresponds to a system operating mode, unobserved intents of other drivers or robots, or to fault types or attack strategies, etc., and the separating inputs are designed such that the output trajectories of all the nonlinear models are guaranteed to be distinguishable from each other under any realization of uncertainties in the initial condition, model discrepancies or noise. We propose a two-step approach. First, using an optimization-based approach, we over-approximate nonlinear dynamics by uncertain affine models, as abstractions that preserve all its system behaviors such that any discrimination guarantees for the affine abstraction also hold for the original nonlinear system. Then, we propose a novel solution in the form of a mixed-integer linear program (MILP) to the active model discrimination problem for uncertain affine models, which includes the affine abstraction and thus, the nonlinear models. Finally, we demonstrate the effectiveness of our approach for identifying the intention of other vehicles in a highway lane changing scenario.

In this paper, we consider the robustification and parametrization of an invariance switching controller with respect to a scalar variable (parameter) that affects the system dynamics. By robustification, we mean searching for a switching controller that guarantees invariance of a set, under a large enough range of the parameter values. In case such a robust controller does not exist, we do parametrization, i.e., searching for a collection of controllers, each one robust to a smaller range of parameter values. A parametrized controller can be applied in real-time by picking the appropriate switching surfaces based on the measurement of the parameter. To be more specific, assuming (i) the system dynamics is affine, and is monotone in the considered parameter, (ii) the invariance switching controller is defined on a rectangle in the state space, we show that the robustification and parametrization problems can be reduced to solving a sequence of linear programming problems. The proposed approach is illustrated by several numerical examples.

In this paper, we consider the problem of active model discrimination amongst a finite number of affine models with uncontrolled and noise inputs, each representing a different system operating mode that corresponds to a fault type or an attack strategy, or to an unobserved intent of another robot, etc. The active model discrimination problem aims to find optimal separating inputs that guarantee that the outputs of all the affine models cannot be identical over a finite horizon. This will enable a system operator to detect and uniquely identify potential faults or attacks, despite the presence of process and measurement noise. Since the resulting model discrimination problem is a nonlinear non-convex mixed-integer program, we propose to solve this in a computationally tractable manner, albeit only approximately, by proposing a sequence of restrictions that guarantee that the obtained input is separating. Finally, we apply our approach to attack detection in the area of cyber-physical systems security.

In this paper, the model (in)validation problem is addressed for the class of switched state space models. We pose the model invalidation problem as a mixed-integer linear program and solve it using the state-of-the-art MILP solvers. Model invalidation is mainly utilized to build trust in the models obtained from system identification. However, we turn our attention to solve another important class of problems using model invalidation approach proposed in this paper. It is shown that the model invalidation approach can be utilized to detect any general fault in cyber-physical systems. Moreover, it is illustrated that knowing the fault model can reduce the complexity of fault detection approach proposed here, if the fault and system model satisfy certain conditions.

This paper proposes a method to compute finite abstractions that can be used for synthesizing robust hybrid control strategies for nonlinear systems. Most existing methods for computing finite abstractions utilize some global, analytical function to provide bounds on the reachable sets of nonlinear systems, which can be conservative and lead to spurious transitions in the abstract systems. This problem is even more pronounced in the presence of imperfect measurements and modelling uncertainties, where control synthesis can easily become infeasible due to added spurious transitions. To mitigate this problem, we propose to compute finite abstractions with robustness margins by over-approximating the local reachable sets of nonlinear systems. We do so by linearizing the nonlinear dynamics into linear affine systems and keeping track of the linearization error. It is shown that this approach provides tighter approximations and several numerical examples are used to illustrate of effectiveness of the proposed methods.