| A discrete event system (DES) is a dynamic system that evolves in accordance with the abrupt occurrence, at possibly unknown and irregular intervals, of physical events. Such systems arise in a variety of contexts, such as energy distribution networks, computer and communication networks, automated manufacturing systems, air traffic control systems, highly integrated command, control, communication, and information (C3I) systems, advanced monitoring and control systems in automobiles or large buildings, intelligent transportation systems, and distributed software systems. Petri net models are widely used for modeling such systems, and consist of two key components: places (which typically model buffers that store system resources) and transitions (which typically model activities that move and process resources across places in the system). Sensors in Petri nets come in two major types: place sensors (i.e., sensors that indicate the number of resources in a particular place, e.g., vision sensors) and transition sensors (i.e., sensors that can detect whether a transition in a given subset of transitions has occurred, e.g., motion sensors).;In this dissertation, we focus on two sensor related problems in discrete event systems modeled by Petri nets: (i) State estimation. When only transition sensors are available, sensor information can be very limited because there can be uncertainty due to unobservable events or events that generate the same sensor information. As a result, multiple states could be possible given sensing information, and we show in this dissertation that the number of possible states can grow at most polynomially (but not exponentially) as a function of the length of the observation sequence. These polynomial bounds can guide the design of systems, especially when trying to configure the sensors in order to reduce the uncertainty introduced in the state estimation stage. The polynomial bounds can also be used in analyzing algorithms in the context of state estimation, fault diagnosis, supervisory control, and even reachability checking. (ii) Sensor selection. If there are only transition sensors with uncertainty, the system state is usually not unique. If we have the freedom to configure sensors (e.g., when we design the system), we might want to add a minimal number of sensors to ensure that the current system state can be uniquely reconstructed based on the system model and the initial state. The design consideration is motivated by supervisory control applications, interface design for safety critical systems, and certain fault detection and correction settings. In its most general form, this type of sensor selection problem can involve both place sensors and transition sensors. We study how to choose a minimum number of place sensors and transition sensors (or a set of place sensors and transition sensors of minimal cost) while ensuring that the system state can be determined uniquely given sensing information and knowledge of the system model; this property is called structural observability. We show that the general sensor selection problem is computationally hard. If we are given a fixed set of transition sensors and are interested in selecting place sensors from a given set to achieve structural observability, the problem can be solved optimally by linear integer programming solvers, or suboptimally by heuristic methods we propose. On the other hand, if we have a fixed set of place sensors and then select transition sensors, the problem is solvable with complexity that is polynomial in the number of places and transitions. Among other potential applications, the heuristic methods we propose have implications for sensor selection to achieve immediate diagnosis of faults, reduct calculation in rough set theory, and approximating solutions for other NP -complete problems. |
