Active Model Discrimination Algorithms for Switched Piecewise Affine Inclusion Systems with Temporal Logic Constraints
摘要
Cyber-physical systems (CPS) play a pivotal role in modern life, particularly in industries like transportation and power/smart grids, where safety is a top priority. These systems generally exhibit uncertain nonlinear or hybrid system dynamics that can make the characterization of their nominal behavior and, by extension, detection and understanding of faulty and/or intended model behaviors very difficult. Thus, this chapter is dedicated to exploring the concept of Active Model Discrimination (AMD), which involves designing auxiliary (perturbation) input signals to improve the model discrimination and detection process amid uncertainties. Specifically, we consider the AMD problem for a set of noisy switched piecewise affine inclusion systems constrained by signal and metric temporal logic (STL and MTL) specifications. The challenge of these problems is the presence of binary/integer variables in the lower/inner level of the associated bilevel optimization problem that stem from the switching, the piecewise affine dynamics as well as the necessary STL/MTL encoding. To deal with the challenge, we propose three algorithms/solutions: (a) the parametric approach: solve the inner problem of the bilevel AMD optimization problem using mixed-integer parametric optimization, whose parametric solution is included when solving the outer/higher level problem; (b) the binary variable relocation approach: move the integer variables/constraints from the inner to the outer problem in a manner that retains feasibility, and recast the problem as a tractable mixed-integer linear programming (MILP) by leveraging Karush-Kuhn-Tucker (KKT) conditions; (c) the brute force approach: enumerate all combinations of the binary variables in the inner problem, and for each combination, solve the mixed-integer bilevel problem (without binary variables in the inner problem) by similarly recasting it as a single-level MILP, and then, selecting the optimal solution among these combinations. Further, we provide a complementary model invalidation algorithm to rule out models that are not consistent with noisy observations at run time, and by virtue of the AMD design, only one model will not be ruled out within a desired guaranteed detection time, and hence the true model can be identified. Simulation examples for parameter identification in a planetary assisted drive system and intent estimation in a highway lane changing scenario demonstrate the effectiveness of our proposed algorithms.