Optimal sensor activation for diagnosing discrete event systems

The problem of dynamic sensor activation for event diagnosis in partially observed discrete event systems is considered. Diagnostic agents are able to activate sensors dynamically during the evolution of the system. Sensor activation policies for diagnostic agents are functions that determine which sensors are to be activated after the occurrence of a trace of events. The sensor activation policy must satisfy the property of diagnosability of centralized systems or codiagnosability of decentralized systems. A policy is said to be minimal if there is no other policy, with strictly less sensor activation, that achieves diagnosability or codiagnosability. To compute minimal policies, we propose language partition methods that lead to efficient computational algorithms. Specifically, we define “window-based” language partitions for scalable algorithms to compute minimal policies. By refining partitions, one is able to refine the solution space over which minimal solutions are computed at the expense of more computation. Thus a compromise can be achieved between fineness of solution and complexity of computation.     

Decentralized Control of Discrete-Event Systems When Supervisors Observe Particular Event Occurrences

Work on decentralized discrete-event control systems is extended to handle the case when, instead of always observing or never observing an event, a supervisor may observe only some occurrences of a particular event. Results include a necessary and sufficient condition for solving this version of the decentralized problem (which is analogous to the co-observability property used in the standard version of the problem) and a method for checking when this condition holds. In this paper, whether an event is observed by a given agent is dependent on that agent's state (or the string of events that agent has seen so far). This model of event observation is applicable to problems where a supervisor communicates observations of event occurrences to another supervisor to help the other one make control decisions.      

Computing observers from observation policies in discrete-event systems

This paper considers partially-observed discrete-event systems modeled by finite-state automata. The observation of event occurrences is associated with the transitions of the automaton model. That is, whether or not an event occurrence is observed is state-dependent, i.e., it depends on the transition in which the event label appears. This is in contrast to the case when observations are static and an event is either observed or not observed at every state in which it can occur. We refer to the set of transitions whose associated events are observed as an observation policy. Given an automaton model and an observation policy, we consider the problem of computing a deterministic generator of the language of event sequences that are observed using the automaton model and observation policy (i.e., an observer). Such a generator is useful, e.g., in problems of sensor activation for providing a deterministic mapping from event observations to sensor activation decisions when the decision to activate an event’s sensor is initially modeled as an observation policy. We propose an abstraction of the automaton model that may be used to represent an observer in certain cases. We illustrate cases where this abstraction accurately represents an observer when there is no ambiguity as to which event occurrences are observed following two observationally-identical strings. For the most general case considered, we demonstrate that verifying if the case holds is PSPACE-complete.     

Minimal communication in a distributed discrete-event system

This paper deals with distributed discrete-event systems, in which agents (or local sites) are required to communicate in order to perform some specified tasks. Associated with each agent is a finite-state automaton that captures the required tasks to be performed at that site. The problem considered is that each agent must be able to distinguish between the states of its automaton. To help it disambiguate states, an agent uses a combination of direct observation (obtained from sensor readings available to that agent) and communicated information (obtained from sensor readings available to another agent). Since communication may be costly, a strategy to minimize communication between sites is developed. The complexity of the solution reflects the interdependence of the agents' communication protocols. That is, the decision to communicate the occurrence of an event relies on which event sequences are indistinguishable to an agent, which, in turn, is a result of what has already been communicated to that agent.     

Robust diagnosis of discrete event systems against intermittent loss of observations

In the usual approaches to fault diagnosis of discrete event systems it is assumed that not only all sensors work properly but also all information reported by sensors always reaches the diagnoser. Any bad sensor operation or communication failure between sensors and the diagnoser can be regarded as loss of observations of events initially assumed as observable. In such situations, it may be possible that either the diagnoser stands still or report some wrong information regarding the fault occurrence. In this paper we assume that intermittent loss of observations may occur and we propose an automaton model based on a new language operation (language dilation) that takes it into account. We refer to this problem as robust diagnosability against intermittent loss of observations (or simply robust diagnosability, where the context allows). We present a necessary and sufficient condition for robust diagnosability in terms of the language generated by the original automaton and propose two tests for robust language diagnosability, one that deploys diagnosers and another one that uses verifiers. We also extend the results to robust codiagnosability against intermittent loss of observations.     

Minimizing the cardinality of an events set for supervisors ofdiscrete-event dynamical systems

In this paper we study sufficient observation and work spaces for supervisors of a class of discrete-event dynamical systems (DEDS). We use finite state automata to model a DEDS. The finite automata generates a formal language defined over the set of events in the DEDS. A supervisor is a feedback system that observes a generated trace of events and dynamically disables (or enables) a subset of controllable events such that the closed-loop system behaves as desired. We model the desired behavior of the DEDS by a sublanguage defined over the set of events. A sufficient observation space is a collection of events whose observation by a supervisor is enough to realize a given desired behavior. A sufficient work space is a sufficient observation space such that the control action of the supervisor is limited to only the controllable elements of the work space. We construct algorithms to evaluate a sufficient work (or observation) space. The reduction of work (or observation) spaces results in reducing the number of event detectors, communication, and command channels between the supervisor and the plant     

基于不确定观测下离散事件系统可诊断性的研究

在实际应用系统中,由于传感器故障、传感器限制和网络中的数据包丢失等原因,事件的可观测值变得不确定,使得观测系统行为变得尤为复杂。针对离散事件系统中,同个事件串可能有多个观测值以及不同状态下同个事件观测值也可能不同的问题,提出一种不确定观测下故障诊断验证的方法。首先对不确定观测的离散事件系统的可诊断性进行形式化,然后构建出用于上述故障诊断验证的验证器;基于验证器提出了系统基于不确定观测下可诊断的充要条件及验证算法;最后,实例说明不确定观测下故障诊断验证算法的应用。与现有研究相比,提出的方法对故障事件的观测值没有约束,可以为0个或多个观测值,使此方法应用的场景更为广泛。     

基于扩展窗口的时序不完备诊断方法研究

离散事件系统诊断中,由于系统复杂度较高,对系统建模时要获得系统的完备行为非常困难。传统的诊断方法往往基于模型完备的假设,在模型不完备时会出现得不到诊断解释的问题。针对模型定义不完备中的一种情况——事件顺序定义不完备,提出了一种基于扩展窗口的时序不完备诊断方法,该方法利用相关事件无序信息,在增量诊断时通过动态改变观测窗口大小,结合两个观测窗口的观测序列,在一定程度上解决了不完备的诊断问题。该方法不仅扩展了模型完备条件的约束,得到了合理的诊断结果,而且改进了观测延迟导致的观测乱序情况,扩大了模型诊断的适用范围。最后,通过算法分析和实验结果证明该诊断方法在复杂度较低的情况下能够得到合理的诊断结果。     

Common issues in discrete optimization and discrete-eventsimulation

This note studies and exploits common issues between discrete-event simulation models and algorithms for discrete optimization problems to prove that two discrete-event simulation search problems are NP-hard. More specifically, NEIGHBORHOOD seeks a sequence of events such that two distinct states can be accessed, one state after executing all but the last k events and another state after executing all the events, while INITIALIZE seeks a sequence of events such that executing the sequence with one particular initial event results in a particular state being reached, while for a second initial event, that particular state cannot be reached. Implications of these results for discrete-event simulation modeling and analysis (e.g., assessing when steady state, termination conditions have been reached, or optimal input parameters values for simulation optimization have been established) as well as for discrete optimization problems (e.g., assessing a priori the effectiveness of a neighborhood for simulated annealing or tabu search) are discussed     

Detecting and repairing anomalous evolutions in noisy environments

In systems where agents are required to interact with a partially known and dynamic world, sensors can be used to obtain knowledge about the environment. However, sensors may be unreliable, that is, they may deliver wrong information (due, e.g., to hardware or software malfunctioning) and, consequently, they may cause agents to take wrong decisions, which is a scenario that should be avoided. The paper considers the problem of reasoning in noisy environments in a setting where no (either certain or probabilistic) data is available in advance about the reliability of sensors. Therefore, assuming that each agent is equipped with a background theory encoding its general knowledge about the world, a concept of detecting an anomaly perceived in sensor data and the related concept of agent recovering to a coherent status of information are defined. In this context, the complexities of various anomaly detection and anomaly recovery problems are studied. Finally, rewriting algorithms are proposed that transform recovery problems into equivalent inference problems under answer set semantics, thereby making them effectively realizable on top of available answer set solvers.     

REALIZATION THEORY OF DISCRETE-EVENT SYSTEMS AND ITS APPLICATION TO THE UNIQUENESS AND UNIVERSALITY OF DEVS FORMALISM

Many man-made systems have discrete event nature. Many modeling formalisms for discrete-event mechanisms have invented and been used for many problems. Among those models, the DEVS formalism is to provide natural and universal models in some sense.

This paper first provides a realization theory of general discrete-event systems. That is, a behavioral definition of discrete-event system is defined, and then a state transition function of the system is constructed. Based on the realization, the uniqueness problem of representations for discrete-event systems is positively solved. Furthermore, as an application of that solution, this paper shows both the fact that a legitimate DEVS with surjective internal transition function is unique up to isomorphism in the class of state representations of the state system defined from the DEVS, and the fact that any discrete-event system has a DEVS realization. In this sense the DEVS modeling facility has the uniqueness and universality in modeling discrete event mechanisms.     

Optimal sensor selection for discrete-event systems with partial observation

For discrete-event systems under partial observation, we study the problem of selection of an optimal set of sensors that can provide sufficient yet minimal events observation information. The sufficiency of the observed information is captured as the fulfillment of a desired formal property. Selection of sensors can be viewed as a selection of an observation mask and also of an equivalence class of events. A sensor set is called optimal if any coarser selection of the corresponding equivalence class of events results in some significant loss of the events observation information. We study an optimal selection of sensors over the set of general "nonprojection" observation masks. We show that this problem is NP hard in general. For mask-monotonic properties, we present a "top-down" and a "bottom-up" algorithm each of polynomial complexity. We show that observerness is not mask-monotonic. We show that the computational complexity can be further improved if the property is preserved under the projection via an intermediary observation mask that is an observer. Our results are obtained in a general setting so that they can be adapted for an optimal selection of sensors for a variety of applications.     

Stochastic Event Capture Using Mobile Sensors Subject to a Quality Metric

Mobile sensors cover more area over a fixed period of time than do the same number of stationary sensors. However, the quality of coverage (QoC) achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed, and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper, we consider the following event capture problem: the events of interest arrive at certain points in the sensor field and disappear according to known arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. We analyze how the QoC scales with velocity, path, and number of mobile sensors. We characterize cases where the deployment of mobile sensors has no advantage over static sensors, and find the optimal velocity pattern that a mobile sensor should adopt. We also present algorithms for two motion planning problems: 1) for a single sensor, what is the sensor trajectory and the minimum speed required to satisfy a bound on the event loss probability and 2) for sensors with fixed speed, what is the minimum number of sensors required to satisfy a bound on the event loss probability. When the robots are restricted to move along a line or a closed curve, our algorithms return the optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor of 2 of the optimal solution. For the case where the events occur at arbitrary points on a plane, we present heuristic algorithms for the aforementioned motion planning problems and bound their performance with respect to the optimal.     

Visionary prototyping

Today, besides introducing intelligence directly into equipment/systems through embedded microcomputers and providing virtual prototyping through enhanced computer-aided design/computer-aided engineering (CAD/CAE) facilities, information now is well regarded as an essential part of the integrated design approach whereby all members of the prototype development and manufacturing automation team can work closely together throughout the design and manufacturing cycle. The article focuses on two subtopics. The first is the development of a theory for prototyping discrete-event and hybrid systems and its applications. In discrete-event dynamic systems (DEDS), state transitions are caused by internal, discrete events in the system. An overview for the development of a simple graphical environment for simulating, analyzing, synthesizing, monitoring, and controlling discrete-event and hybrid systems is also presented. The second focus is on prototyping machine vision for real-time automation applications. We discuss the problems associated with traditional machine vision systems for cost-effective, real-time applications, novel alternative system design to overcome these problems, and the new trends of modern vision sensors. Modern smart sensors provide the features of traditional machine vision systems at less than half of the usual price by eliminating the signal-conversion electronics, fixed-frame rates, and limited gray-scale quantization. The camera, image-acquisition electronics, and computer are integrated into a single unit to allow dynamic access to the charge-coupled devices without image float or flutter. We also present a physically accurate image synthesis method as a flexible, practical tool for examining a large number of hardware/software configuration combinations for a wide range of parts     

Scan-Based Movement-Assisted Sensor Deployment Methods in Wireless Sensor Networks

The efficiency of sensor networks depends on the coverage of the monitoring area. Although, in general, a sufficient number of sensors are used to ensure a certain degree of redundancy in coverage, a good sensor deployment is still necessary to balance the workload of sensors. In a sensor network with locomotion facilities, sensors can move around to self-deploy. The movement-assisted sensor deployment deals with moving sensors from an initial unbalanced state to a balanced state. Therefore, various optimization problems can be defined to minimize different parameters, including total moving distance, total number of moves, communication/computation cost, and convergence rate. In this paper, we first propose a Hungarian-algorithm-based optimal solution, which is centralized. Then, a localized scan-based movement-assisted sensor deployment method (SMART) and several variations of it that use scan and dimension exchange to achieve a balanced state are proposed. An extended SMART is developed to address a unique problem called communication holes in sensor networks. Extensive simulations have been done to verify the effectiveness of the proposed scheme.     

Optimal decision f usion given sens or rules

When all the rules of sensor decision are known ,the optimal distributed decision fusion ,which relies only on the joint conditional probability densities , can be derived for very general decision systems. They include those systems with interdependent sensor observations and any network structure. It is also valid for m-ary Bayesian decision problems and binary problems under the Neyman- Pearson criterion. Local decision rules of a sensor with communication from other sensors that are optimal for the sensor itself are also presented ,which take the form of a generalized likelihood ratio test . Numerical examples are given to reveal some interesting phenomena that communication between sensors can improve performance of a senor decision ,but cannot guarantee to improve the global fusion performance when sensor rules were given before fusing.     

Consensus of multi‐agent systems with time‐varying topology: An event‐based dynamic feedback scheme

The event‐based control strategy is an effective methodology for reducing the controller update and communication over the network. In this paper, the event‐based consensus of multi‐agent systems with linear dynamics and time‐varying topology is studied. For each agent, a state‐dependent threshold with an exponentially decaying bound is presented to determine the event times, and a new event‐based dynamic feedback scheme is proposed. It is shown that the controller update for each agent is only dependent on its own event times, which reduces significantly the controller update or computation for each agent. Moreover, based on the event‐based dynamic feedback scheme and the event triggering function presented in this paper, the continuous communication among neighboring agents is avoided, and the Zeno‐behavior of the closed‐loop systems is excluded. A numerical example is given to illustrate the effectiveness of theoretical results. Copyright © 2016 John Wiley & Sons, Ltd.     

Optimal decision fusion given sensor rules

When all the rules of sensor decision are known,the optimal distributed decision fusion,which relies only on the joint conditional probability densities, can be derived for very general decision systems. They include those systems with interdependent sensor observations and any network structure. It is also valid for m-ary Bayesian decision problems and binary problems under the Neyman-Pearson criterion. Local decision rules of a sensor withfrom other sensors that are optimal for the sensor itself are also presented, which take the form of a generalized likelihood ratio test. Numerical examples are given to reveal some interesting phenomem that communication between sensors can improve performance of a senor decision,but cannot guarantee to improve the global fusion performance when sensor rules were given before fusing.