This study investigates the set reachability of Markovian jump Boolean networks (MJBNs). Firstly, through comprehensive analysis, two kinds of set reachability, strong set reachability and weak set ...reachability, are defined. By using semi-tensor product of matrices, the considered MJBN is converted into a Markov chain which can not only describe the state transition of the MJBN synchronously, but also maintain its transition probability. Based on this, the set reachability problem of the MJBN is transformed into the reachability and convergence problems of the corresponding Markov chain. Then some necessary and sufficient conditions for set reachability of MJBNs are obtained. Finally, the observability and output stability problems of MJBNs are discussed as two applications of set reachability.
In this paper, a compact representation of the reachability graph of a Petri net is proposed. The transition set of a Petri net is partitioned into the subsets of explicit and implicit transitions in ...such a way that the subnet induced by implicit transitions does not contain directed cycles. The firing of implicit transitions can be abstracted so that the reachability set of the net can be completely characterized by a subset of reachable markings called basis makings. We show that to determine a max-cardinality-TI basis partition is an NP-hard problem, but a max-set-TI basis partition can be determined in polynomial time. The generalized version of the marking reachability problem in a Petri net can be solved by a practically efficient algorithm based on the basis reachability graph. Finally, this approach is further extended to unbounded nets.
Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that are a frequent ...source of confusion and incomparability of results in the literature.
In this paper, we take a step back and examine three such aspects in more details, exploring their impact in a systematic way; namely, whether the temporal paths are required to be strict (i.e., the times along a path must increasing, not just be non-decreasing), whether the time labeling is proper (two adjacent edges cannot be present at the same time) and whether the time labeling is simple (an edge can have only one presence time). In particular, we investigate how different combinations of these features impact the expressivity of the graph in terms of reachability.
Our results imply a hierarchy of expressivity for the resulting settings, shedding light on the loss of generality that one is making when considering either combination. Some settings are more general than expected; in particular, proper temporal graphs turn out to be as expressive as general temporal graphs where non-strict paths are allowed. Also, we show that the simplest setting, that of happy temporal graphs (i.e., both proper and simple) remains expressive enough to emulate the reachability of general temporal graphs in a certain (restricted but useful) sense. Furthermore, this setting is advocated as a target of choice for proving negative results. We illustrate this by strengthening two known results to happy graphs (namely, the inexistence of sparse spanners, and the hardness of computing temporal components). Overall, we hope that this article can be seen as a guide for choosing between different settings of temporal graphs, while being aware of the way these choices affect generality.
Networked finite state machine takes into account communication losses in industrial communication interfaces due to the limited bandwidth. The reachability analysis of networked finite state machine ...is a fundamental and important research topic in blocking detection, safety analysis, communication system design and so on. This paper is concerned with the impact of arbitrary communication losses on the reachability of networked finite state machine from a switched perspective. First, to model the dynamics under arbitrary communication losses in communication interfaces (from the controller to the actuator), by resorting to the semi-tensor product (STP) of matrices, a switched algebraic model of networked finite state machine with arbitrary communication losses is proposed, and the reachability analysis can be investigated by using the constructed model under arbitrary switching signal. Subsequently, based on the algebraic expression and its transition matrix, necessary and sufficient conditions for the reachability are derived for networked finite state machine. Finally, some typical numerical examples are exploited to demonstrate the effectiveness of the proposed approach. Note that current results provide valuable clues to design reliable and convergent Internet-of-Things networks.
Unmanned aircraft systems (UAS) generally use Global Navigation Satellite System (GNSS) measurements to estimate their state (position and orientation) for outdoor navigation. However, in urban ...environments, GNSS pseudorange measurements contain biases due to multipath effects and signal blockages by nearby buildings. For safe navigation in such environments, it is beneficial to predict the state uncertainty while accounting for the effect of measurement biases. Reachability analysis is a commonly used tool to predict the state uncertainty of a system. However, existing works do not account for the effect of measurement biases on state estimation, which consequently affects the predicted state uncertainty. Additionally, majority of the existing literature focuses on linear systems, whereas the dynamics of widely used practical systems are better captured by non-linear models. Thus, in this paper we present a non-linear stochastic reachability analysis to predict bounds on the state uncertainty while accounting for measurement biases. We derive the analysis for a fixed-wing UAS navigating using ranging measurements. In order to evaluate our predicted bounds for GNSS-based navigation, we simulate a 3D urban environment and the pseudorange biases due to multipath effects. We validate the predicted bounds for multiple trajectories in the simulated environment. Finally, we demonstrate the applicability of our predicted bounds towards ensuring safe UAS navigation in a shared airspace.
An example of a time-invariant time-delay system that is uniformly globally attractive and exponentially stable, hence forward complete, but whose reachability sets from bounded initial conditions ...are not bounded over compact time intervals is provided. This gives a negative answer to two current conjectures by showing that (i) forward completeness is not equivalent to robust forward completeness (i.e. boundedness of reachability sets) and (ii) global asymptotic stability is not equivalent to uniform global asymptotic stability. In addition, a novel characterization of robust forward completeness for systems having a finite number of discrete delays is provided. This characterization relates robust forward completeness of the time-delay system with the forward completeness of an associated nondelayed finite-dimensional system.
We study distributional reachability for finite Markov decision processes (MDPs) from a control theoretical perspective. Unlike standard probabilistic reachability notions, which are defined over MDP ...states or trajectories, in this article reachability is formulated over the space of probability distributions. We propose two set-valued maps for the forward and backward distributional reachability problems: the forward map collects all state distributions that can be reached from a set of initial distributions, while the backward map collects all state distributions that can reach a set of final distributions. We show that there exists a maximal invariant set under the forward map and this set is the region where the state distributions eventually always belong to, regardless of the initial state distribution and policy. The backward map provides an alternative way to solve a class of important problems for MDPs: the study of controlled invariance, the characterization of the domain of attraction, and reach-avoid problems. Three case studies illustrate the effectiveness of our approach.
Configurable software verification is a recent concept for expressing different program analysis and model checking approaches in one single formalism. This paper presents CPAchecker, a tool and ...framework that aims at easy integration of new verification components. Every abstract domain, together with the corresponding operations, implements the interface of configurable program analysis (CPA). The main algorithm is configurable to perform a reachability analysis on arbitrary combinations of existing CPAs. In software verification, it takes a considerable amount of effort to convert a verification idea into actual experimental results — we aim at accelerating this process. We hope that researchers find it convenient and productive to implement new verification ideas and algorithms using this flexible and easy-to-extend platform, and that it advances the field by making it easier to perform practical experiments. The tool is implemented in Java and runs as command-line tool or as eclipse plug-in. CPAchecker implements CPAs for several abstract domains. We evaluate the efficiency of the current version of our tool on software-verification benchmarks from the literature, and compare it with other state-of-the-art model checkers. CPAchecker is an open-source toolkit and publicly available.
It is challenging in the e-healthcare system to monitor patients using wearables or embedded sensors that can gather real-time physiological data, analyze lab test results, conduct medical ...examinations, and recommend treatments because all the associated sensitive information transmission is through a hostile environment; it is always possible for an unauthorized person to access them. To improve the security of the telemedicine system in such a situation, it is imperative to develop a real-time data transmission system that can effectively handle the tasks carried out by devices in the telemedicine system. This allows administrators to assess the correctness of the various users' work and remotely monitor the real-time data gathered by the smart sensing devices. However, as stated, the real-time data is shared across a public channel-and is private and sensitive; an attacker accesses the sensitive information about the telemedicine system and makes it public to disturb user privacy and violate its security. A robust and lightweight key agreement scheme must be designed for the telemedicine system to create a secret session key between a chosen wearable or smart sensing device and the telemedicine server-a trustworthy entity installed in the telehealthcare environment. Otherwise, security for such sensitive information cannot be guaranteed. Therefore, this article presents the design of a robust and lightweight authentication protocol named RLKAS-TMS that can effectively alleviate the security and privacy concerns of sensitive medical information over a public network channel.
•This study introduces an innovative approach that employs reachability analysis to solve the dynamic envelope of the FW-VTOL UAV during the transition stage.•It proposes a safety index for the ...transition path, optimized to determine the safest transition path.•The designed optimal path enhances safety by 9.71% compared to the basic path, signifying its practical significance in mitigating risk during the transition stage of FW-VTOL UAVs.•The attributes of the transition path are analyzed based on two aspects: (a) A comparison between the optimal transition path and the two-dimensional transition path with a constant angle of attack. (b) An examination of how key UAV design parameters influence the transition path’s safety.
Flight velocity and tilt angle are commonly employed to define the safe region for fixed-wing vertical take-off and landing (FW-VTOL) UAVs as they undergo tilting, referred to as the transition corridor. Nevertheless, the transition corridor only considers the aircraft's limitations in a quasi-stationary condition and ignores the additional constraints introduced by the aircraft's kinematic behavior. To obtain a more accurate safe state space, the concept of the dynamic envelope was proposed by previous researchers. The dynamic envelope of UAV represents the safe state space taking into account aerodynamic constraints and kinematic constraints. Solving the dynamic envelope has consistently remained a focal point of research in the field. This study introduces an innovative approach that employs reachability analysis to solve the dynamic envelope of the FW-VTOL UAV during the transition stage. Building upon this, it proposes a safety index for the transition path, optimized to determine the safest transition path. Subsequently, specific case studies verified the effectiveness of the solution process and optimization method. The designed optimal path enhances safety by 9.71% compared to the basic path, signifying its practical significance in mitigating risk during the transition stage of FW-VTOL UAVs. Furthermore, the attributes of the transition path are analyzed based on two aspects: (A) a comparison between the optimal transition path and the two-dimensional transition path with a constant angle of attack; (B) an examination of how key UAV design parameters influence the transition path's safety. Overall, the methodology and general rules proposed in this study provide a theoretical basis and technical support for improving the security of FW-VTOL UAVs in the transition stage.
PDF
