Search

We investigate the problem of synthesizing distributionally robust control policies for stochastic systems under safety and reach-avoid specifications. Using a game-theoretical framework, we consider the setting where the probability distribution of the disturbance at each time step is selected from an ambiguity set defined by the Wasserstein distance. The goal is to synthesize a distributionally robust control policy that ensures the satisfaction probability exceeds a specified threshold under any distribution within the ambiguity set. First, for both safety and reach-avoid specifications, we establish the existence of optimal policies by leveraging the dynamic programming principles. Then we demonstrate how the associated optimization problem can be efficiently solved using the dual representation of Wasserstein distributionally robust optimization. Furthermore, for safety specifications in particular, we introduce a novel concept of distributionally robust control barrier certificates and show how these enable the efficient synthesis of controllers through sum-of-squares programming techniques. Finally, our experimental results reveal that incorporating distributional robustness during the synthesis phase significantly improves the satisfaction probability during online execution, even with limited statistical knowledge of the disturbance distribution.

We investigate the problem of safe control synthesis for systems operating in environments with uncontrollable agents whose dynamics are unknown but coupled with those of the controlled system. This scenario naturally arises in various applications, such as autonomous driving and human-robot collaboration, where the behavior of uncontrollable agents, like pedestrians, cannot be directly controlled but is influenced by the actions of the autonomous vehicle or robot. In this paper, we present SPARC (Safe Prediction-Based Robust Controller for Coupled Agents), a novel framework designed to ensure safe control in the presence of coupled uncontrollable agents. SPARC leverages conformal prediction to quantify uncertainty in data-driven prediction of agent behavior. Particularly, we introduce a joint distribution-based approach to account for the coupled dynamics of the controlled system and uncontrollable agents. By integrating the control barrier function (CBF) technique, SPARC provides provable safety guarantees at a high confidence level. We illustrate our framework with a case study involving an autonomous driving scenario with walking pedestrians., Comment: It's not complete yet

In this paper, we investigate the property verification problem for partially-observed DES from a new perspective. Specifically, we consider the problem setting where the system is observed by two agents independently, each with its own observation. The purpose of the first agent, referred to as the low-level observer, is to infer the actual behavior of the system, while the second, referred to as the high-level observer, aims to infer the knowledge of Agent 1 regarding the system. We present a general notion called the epistemic property capturing the inference from the high-level observer to the low-level observer. A typical instance of this definition is the notion of high-order opacity, which specifies that the intruder does not know that the system knows some critical information. This formalization is very general and supports any user-defined information-state-based knowledge between the two observers. We demonstrate how the general definition of epistemic properties can be applied in different problem settings such as information leakage diagnosis or tactical cooperation without explicit communications. Finally, we provide a systematic approach for the verification of epistemic properties. Particularly, we identify some fragments of epistemic properties that can be verified more efficiently.

This paper investigates an aperiodic distributed model predictive control approach for multi-agent systems (MASs) in which parameterized synchronization constraints is considered and an innovative self-triggered criterion is constructed. Different from existing coordination methodology, the proposed strategy achieves the cooperation of agents through the synchronization of one-dimensional parameters related to the control inputs. At each asynchronous sampling instant, each agent exchanges the one-dimensional synchronization parameters, solves the optimal control problem (OCP) and then determines the open-loop phase. The incorporation of the selftriggered scheme and the synchronization parameter constraints relieves the computational and communication usage. Sufficient conditions guaranteeing the recursive feasibility of the OCP and the stability of the closed-loop system are proven. Simulation results illustrate the validity of the proposed control algorithm.

This paper investigates the distributed model predictive control for an asynchronous nonlinear multi-agent system with external interference via a self-triggered generator and a prediction horizon regulator. First, a shrinking constraint related to the error between the actual state and the predicted state is introduced into the optimal control problem to enable the robustness of the system. Then, the trigger interval and the corresponding prediction horizon are determined by altering the expression of the Lyapunov function, thus achieving a trade-off between control performance and energy loss. By implementing the proposed algorithm, the coordination objective of the multi-agent system is achieved under asynchronous communication. Finally, the recursive feasibility and stability are proven successively. An illustrative example is conducted to demonstrate the merits of the presented approach.

We investigate the problem of optimal control synthesis for Markov Decision Processes (MDPs), addressing both qualitative and quantitative objectives. Specifically, we require the system to fulfill a qualitative surveillance task in the sense that a specific region of interest can be visited infinitely often with probability one. Furthermore, to quantify the performance of the system, we consider the concept of efficiency, which is defined as the ratio between rewards and costs. This measure is more general than the standard long-run average reward metric as it aims to maximize the reward obtained per unit cost. Our objective is to synthesize a control policy that ensures the surveillance task while maximizes the efficiency. We provide an effective approach to synthesize a stationary control policy achieving $\epsilon$-optimality by integrating state classifications of MDPs and perturbation analysis in a novel manner. Our results generalize existing works on efficiency-optimal control synthesis for MDP by incorporating qualitative surveillance tasks. A robot motion planning case study is provided to illustrate the proposed algorithm.

In this paper, we investigate the problem of linear temporal logic (LTL) path planning for multi-agent systems, introducing the new concept of \emph{ordering constraints}. Specifically, we consider a generic objective function that is defined for the path of each individual agent. The primary objective is to find a global plan for the team of agents, ensuring they collectively meet the specified LTL requirements. Simultaneously, we aim to maintain a pre-determined order in the values of the objective function for each agent, which we refer to as the ordering constraints. This new requirement stems from scenarios like security-aware planning, where relative orders outweigh absolute values in importance. We present an efficient algorithm to solve this problem, supported by proofs of correctness that demonstrate the optimality of our solution. Additionally, we provide a case study in security-aware path planning to illustrate the practicality and effectiveness of our proposed approach., Comment: This article is withdrawn due to errors in the methodology section, specifically concerning the insufficient explanation of the data collection process. Upon review, it's clear that the data sampling methods were not adequately described, potentially leading to misinterpretations of the results

In this paper, we investigate the problem of optimal supervisory control for the discrete event systems under energy constraints. We consider that the execution of events consumes energy and the energy can be replenished at specific reload states. When the energy level drops below zero, the system will be crashed. To capture the above scenario, we introduce a new model, called consumption discrete event system (cDES). Our objective is to find the minimal initial energy value and synthesize an optimal supervisor ensuring that the energy will never be exhausted. To solve this problem, we propose a game-theoretical approach by converting the cDES as a consumption two-player graph game (cTPG) and reformulate the optimal supervisory control problem in game theory. In particular, we demonstrate that the converted game can be decomposed into independent reachability games related to reload vertices, which can be solved by a fixed point iterative algorithm proposed in this paper. Through iteratively removing unsafe reload vertices and solving reachability games for the remaining reload vertices, a solution can be found., Comment: We will add richer content

This paper investigates the problem of designing control policies that satisfy high-level specifications described by signal temporal logic (STL) in unknown, stochastic environments. While many existing works concentrate on optimizing the spatial robustness of a system, our work takes a step further by also considering temporal robustness as a critical metric to quantify the tolerance of time uncertainty in STL. To this end, we formulate two relevant control objectives to enhance the temporal robustness of the synthesized policies. The first objective is to maximize the probability of being temporally robust for a given threshold. The second objective is to maximize the worst-case spatial robustness value within a bounded time shift. We use reinforcement learning to solve both control synthesis problems for unknown systems. Specifically, we approximate both control objectives in a way that enables us to apply the standard Q-learning algorithm. Theoretical bounds in terms of the approximations are also derived. We present case studies to demonstrate the feasibility of our approach., Comment: Accepted to ICRA 2024

Inspired by biological motion generation, central pattern generators (CPGs) is frequently employed in legged robot locomotion control to produce natural gait pattern with low-dimensional control signals. However, the limited adaptability and stability over complex terrains hinder its application. To address this issue, this paper proposes a terrain-adaptive locomotion control method that incorporates deep reinforcement learning (DRL) framework into CPG, where the CPG model is responsible for the generation of synchronized signals, providing basic locomotion gait, while DRL is integrated to enhance the adaptability of robot towards uneven terrains by adjusting the parameters of CPG mapping functions. The experiments conducted on the hexapod robot in Isaac Gym simulation environment demonstrated the superiority of the proposed method in terrain-adaptability, convergence rate and reward design complexity.

Ensuring safety for vehicle overtaking systems is one of the most fundamental and challenging tasks in autonomous driving. This task is particularly intricate when the vehicle must not only overtake its front vehicle safely but also consider the presence of potential opposing vehicles in the opposite lane that it will temporarily occupy. In order to tackle the overtaking task in such challenging scenarios, we introduce a novel integrated framework tailored for vehicle overtaking maneuvers. Our approach integrates the theories of varying-level control barrier functions (CBF) and time-optimal model predictive control (MPC). The main feature of our proposed overtaking strategy is that it is safe-by-construction, which enables rigorous mathematical proof and validation of the safety guarantees. We show that the proposed framework is applicable when the opposing vehicle is either fully autonomous or driven by human drivers. To demonstrate our framework, we perform a set of simulations for overtaking scenarios under different settings. The simulation results show the superiority of our framework in the sense that it ensures collision-free and achieves better safety performance compared with the standard MPC-based approach without safety guarantees.

Learning binary classifiers from positive and unlabeled data (PUL) is vital in many real-world applications, especially when verifying negative examples is difficult. Despite the impressive empirical performance of recent PUL methods, challenges like accumulated errors and increased estimation bias persist due to the absence of negative labels. In this paper, we unveil an intriguing yet long-overlooked observation in PUL: \textit{resampling the positive data in each training iteration to ensure a balanced distribution between positive and unlabeled examples results in strong early-stage performance. Furthermore, predictive trends for positive and negative classes display distinctly different patterns.} Specifically, the scores (output probability) of unlabeled negative examples consistently decrease, while those of unlabeled positive examples show largely chaotic trends. Instead of focusing on classification within individual time frames, we innovatively adopt a holistic approach, interpreting the scores of each example as a temporal point process (TPP). This reformulates the core problem of PUL as recognizing trends in these scores. We then propose a novel TPP-inspired measure for trend detection and prove its asymptotic unbiasedness in predicting changes. Notably, our method accomplishes PUL without requiring additional parameter tuning or prior assumptions, offering an alternative perspective for tackling this problem. Extensive experiments verify the superiority of our method, particularly in a highly imbalanced real-world setting, where it achieves improvements of up to $11.3\%$ in key metrics. The code is available at \href{https://github.com/wxr99/HolisticPU}{https://github.com/wxr99/HolisticPU}., Comment: 25 pages

In this work, we investigate task planning for mobile robots under linear temporal logic (LTL) specifications. This problem is particularly challenging when robots navigate in continuous workspaces due to the high computational complexity involved. Sampling-based methods have emerged as a promising avenue for addressing this challenge by incrementally constructing random trees, thereby sidestepping the need to explicitly explore the entire state-space. However, the performance of this sampling-based approach hinges crucially on the chosen sampling strategy, and a well-informed heuristic can notably enhance sample efficiency. In this work, we propose a novel neural-network guided (NN-guided) sampling strategy tailored for LTL planning. Specifically, we employ a multi-modal neural network capable of extracting features concurrently from both the workspace and the B\"{u}chi automaton. This neural network generates predictions that serve as guidance for random tree construction, directing the sampling process toward more optimal directions. Through numerical experiments, we compare our approach with existing methods and demonstrate its superior efficiency, requiring less than 15% of the time of the existing methods to find a feasible solution., Comment: submitted

This paper addresses the multi-agent control problem under global temporal logic tasks, considering agents with heterogeneous capabilities. These global tasks involve not only absolute and relative temporal and spatial constraints, but also group behaviors, including task completion times, agent capabilities, and task interdependencies such as the need for synchronous execution. The global tasks are formally formulated into global signal temporal logic (STL) formulae, and a synchronous robustness metric is designed to evaluate the synchronization quality with real values. A mixed-integer linear programming (MILP) encoding method is further proposed to realize task-satisfied motion planning with high synchronicity and minimum control efforts. The encoding method uses a logarithmic number of binary variables to fully capture synchronous robustness, leading to only linear computational complexity. Simulations are conducted to demonstrate the efficiency of the proposed control strategy., Comment: 10 pages, 4 figures

We investigate the problem of synthesizing optimal control policies for Markov decision processes (MDPs) with both qualitative and quantitative objectives. Specifically, our goal is to achieve a given linear temporal logic (LTL) task with probability one, while maximizing the \emph{entropy rate} of the system. The notion of entropy rate characterizes the long-run average (un)predictability of a stochastic process. Such an optimal policy is of our interest, in particular, from the security point of view, as it not only ensures the completion of tasks, but also maximizes the unpredictability of the system. However, existing works only focus on maximizing the total entropy which may diverge to infinity for infinite horizon. In this paper, we provide a complete solution to the entropy rate maximization problem under LTL constraints. Specifically, we first present an algorithm for synthesizing entropy rate maximizing policies for communicating MDPs. Then based on a new state classification method, we show the entropy rate maximization problem under LTL task can be effectively solved in polynomial-time. We illustrate the proposed algorithm based on two case studies of robot task planning scenario.

In this paper, we investigate the problem of Model Predictive Control (MPC) of dynamic systems for high-level specifications described by Signal Temporal Logic (STL) formulae. Recent works show that MPC has the great potential in handling logical tasks in reactive environments. However, existing approaches suffer from the heavy computational burden, especially for tasks with large horizons. In this work, we propose a computationally more efficient MPC framework for STL tasks based on time interval decomposition. Specifically, we still use the standard shrink horizon MPC framework with Mixed Integer Linear Programming (MILP) techniques for open-loop optimization problems. However, instead of applying MPC directly for the entire task horizon, we decompose the STL formula into several sub-formulae with disjoint time horizons, and shrinking horizon MPC is applied for each short-horizon sub-formula iteratively. To guarantee the satisfaction of the entire STL formula and to ensure the recursive feasibility of the iterative process, we introduce new terminal constraints to connect each sub-formula. We show how these terminal constraints can be computed by an effective inner-approximation approach. The computational efficiency of our approach is illustrated by a case study.

Online monitoring aims to evaluate or to predict, at runtime, whether or not the behaviors of a system satisfy some desired specification. It plays a key role in safety-critical cyber-physical systems. In this work, we propose a new monitoring approach, called model predictive monitoring, for specifications described by Signal Temporal Logic (STL) formulae. Specifically, we assume that the observed state traces are generated by an underlying dynamical system whose model is known but the control law is unknown. The main idea is to use the dynamic of the system to predict future states when evaluating the satisfaction of the STL formulae. To this end, effective approaches for the computation of feasible sets of STL formulae are provided. We show that, by explicitly utilizing the model information of the dynamical system, the proposed online monitoring algorithm can falsify or certify of the specification in advance compared with existing algorithms, where no model information is used. We also demonstrate the proposed monitoring algorithm by several real world case studies., Comment: This paper is accepted to Automatica. arXiv admin note: substantial text overlap with arXiv:2203.16267

In this paper, we investigate property verification problems in partially-observed discrete-event systems (DES). Particularly, we are interested in verifying observational properties that are related to the information-flow of the system. Observational properties considered here include diagnosability, predictability, detectability and opacity, which have drawn considerable attentions in the literature. However, in contrast to existing results, where different verification procedures are developed for different properties case-by-case, in this work, we provide a unified framework for verifying all these properties by reducing each of them as an instance of HyperLTL model checking. Our approach is based on the construction of a Kripke structure that effectively captures the issue of unobservability as well as the finite string semantics in partially-observed DES so that HyperLTL model checking techniques can be suitably applied. Then for each observational property considered, we explicitly provide the HyperLTL formula to be checked over the Kripke structure for the purpose of verification. Our approach is uniform in the sense that all different properties can be verified with the same model checking engine. Furthermore, our unified framework also brings new insights for classifying observational properties for partially-observed DES in terms of their verification complexity.

In this paper, we investigate the diagnosability verification problem of partially-observed discrete-event systems (DES) subject to unreliable sensors. In this setting, upon the occurrence of each event, the sensor reading may be non-deterministic due to measurement noises or possible sensor failures. Existing works on this topic mainly consider specific types of unreliable sensors such as the cases of intermittent sensors failures, permanent sensor failures or their combinations. In this work, we propose a novel \emph{uniform framework} for diagnosability of DES subject to, not only sensor failures, but also a very general class of unreliable sensors. Our approach is to use linear temporal logic (LTL) with semantics on infinite traces to describe the possible behaviors of the sensors. A new notion of $\varphi$-diagnosability is proposed as the necessary and sufficient condition for the existence of a diagnoser when the behaviors of sensors satisfy the LTL formula $\varphi$. Effective approach is provided to verify this notion. We show that, our new notion of $\varphi$-diagnosability subsumes all existing notions of robust diagnosability of DES subject to sensor failures. Furthermore, the proposed framework is user-friendly and flexible since it supports an arbitrary user-defined unreliable sensor type based on the specific scenario of the application. As examples, we provide two new notions of diagnosability, which have never been investigated in the literature, using our uniform framework.

The goal of Inverse Optimal Control (IOC) is to identify the underlying objective function based on observed optimal trajectories. It provides a powerful framework to model expert's behavior, and a data-driven way to design an objective function so that the induced optimal control is adapted to a contextual environment. In this paper, we design an IOC algorithm for linear-quadratic tracking problems with random time horizon, and prove the statistical consistency of the algorithm. More specifically, the proposed estimator is the solution to a convex optimization problem, which means that the estimator does not suffer from local minima. This enables the proven statistical consistency to actually be achieved in practice. The algorithm is also verified on simulated data as well as data from a real world experiment, both in the setting of identifying the objective function of human tracking locomotion. The statistical consistency is illustrated on the synthetic data set, and the experimental results on the real data shows that we can get a good prediction on human tracking locomotion based on estimating the objective function. It shows that the theory and the model have a good performance in real practice. Moreover, the identified model can be used as a control target in personalized rehabilitation robot controller design, since the identified objective function describes personal habit and preferences.

In this paper, we revisit the fault diagnosis problem of discrete-event systems (DES) under non-deterministic observations. Non-deterministic observation is a general observation model that includes the case of intermittent loss of observations. In this setting, upon the occurrence of an event, the sensor reading may be non-deterministic such that a set of output symbols are all possible. Existing works on fault diagnosis under non-deterministic observations require to consider all possible observation realizations. However, this approach includes the case where some possible outputs are permanently disabled. In this work, we introduce the concept of output fairness by requiring that, for any output symbols, if it has infinite chances to be generated, then it will indeed be generated infinite number of times. We use an assume-guarantee type of linear temporal logic formulas to formally describe this assumption. A new notion called output-fair diagnosability (OF-diagnosability) is proposed. An effective approach is provided for the verification of OF-diagnosability. We show that the proposed notion of OF-diagnosability is weaker than the standard definition of diagnosability under non-deterministic observations, and it better captures the physical scenario of observation non-determinism or intermittent loss of observations.

In this paper, we investigate the optimal robot path planning problem for high-level specifications described by co-safe linear temporal logic (LTL) formulae. We consider the scenario where the map geometry of the workspace is partially-known. Specifically, we assume that there are some unknown regions, for which the robot does not know their successor regions a priori unless it reaches these regions physically. In contrast to the standard game-based approach that optimizes the worst-case cost, in the paper, we propose to use regret as a new metric for planning in such a partially-known environment. The regret of a plan under a fixed but unknown environment is the difference between the actual cost incurred and the best-response cost the robot could have achieved if it realizes the actual environment with hindsight. We provide an effective algorithm for finding an optimal plan that satisfies the LTL specification while minimizing its regret. A case study on firefighting robots is provided to illustrate the proposed framework. We argue that the new metric is more suitable for the scenario of partially-known environment since it captures the trade-off between the actual cost spent and the potential benefit one may obtain for exploring an unknown region.

This paper investigates the problem of synthesizing sensor deception attackers against privacy in the context of supervisory control of discrete-event systems (DES). We consider a DES plant controlled by a supervisor, which is subject to sensor deception attacks. Specifically, we consider an active attacker that can tamper with the observations received by the supervisor by, e.g., hacking on the communication channel between the sensors and the supervisor. The privacy requirement of the supervisory control system is to maintain initial-state opacity, i.e., it does not want to reveal the fact that it was initiated from a secret state during its operation. On the other hand, the attacker aims to deceive the supervisor, by tampering with its observations, such that initial-state opacity is violated due to incorrect control actions. In this work, we investigate from the attacker's point of view by presenting an effective approach for synthesizing sensor attack strategies threatening the privacy of the system. To this end, we propose the All Attack Structure (AAS) that records state estimates for both the supervisor and the attacker. This structure serves as a basis for synthesizing a sensor attack strategy. We also discuss how to simplify the synthesis complexity by leveraging the structural property of the initial-state privacy requirement. A running academic example is provided to illustrate the synthesis procedure., Comment: 8 pages, 7 figures

In this paper, we investigate a class of information-flow security properties called opacity in partial-observed discrete-event systems. Roughly speaking, a system is said to be opaque if the intruder, which is modeled by a passive observer, can never determine the "secret" of the system for sure. Most of the existing notions of opacity consider secrets related to the actual behaviors of the system. In this paper, we consider a new type of secret related to the knowledge of the system user. Specifically, we assume that the system user also only has partial observation of the system and has to reason the actual behavior of the system. We say a system is high-order opaque if the intruder can never determine that the system user knows some information of importance based on its own incomparable information. We provide the formal definition of high-order opacity. Two algorithms are provided for the verification of this new notion: one with doubly-exponential complexity for the worst case and the other with single-exponential complexity. Illustrative examples are provided for the new notion of high-order opacity.