Estimation, diagnosis, and control in discrete event systems in the presence of observability constraints and faults

In recent decades, discrete event systems (DESs) have become increasingly important due to the proliferation of "human-made" and computer-controlled systems, such as automated manufacturing systems, computer networks, transportation systems and air traffic control systems. A significant portion of the "activity" in these systems is governed by rules and instructions designed by humans, and their dynamics are characterized by asynchronous occurrences of discrete events. This thesis studies various problems in the context of discrete event systems that can be modeled as Petri nets (PNs). In particular, we propose methods and algorithms for problems pertaining to event detection/estimation, state estimation, and fault tolerance in such systems.;The thesis starts by looking at the problems of event/state estimation in Petri nets. First, we focus on estimating the least-cost transition firing sequence(s) that matches (match) the observation of a sequence of labels produced by transition activity in a given labeled Petri net. The cost (associated with each transition) is in terms of the amount of workload or the amount of power needed to execute a certain transition. More specifically, we develop a recursive algorithm which is able to find the least-cost transition firing sequence(s). We also extend this algorithm to the case where unobservable transitions may be present in the net. The proposed algorithms are recursive and have complexity that is polynomial in the length of the observed sequence of labels. Our algorithms can also be used to solve the problem of bounded length least-cost planning sequence calculation in Petri nets. Given the structure of the Petri net and its initial/final markings, we develop an algorithm that is able to find the transition firing sequence(s) (with length less than or equal to a given bound) that could lead us from the initial marking to the final marking while having the least total cost. The algorithm is recursive and has complexity that is polynomial in the given bound.;We next study the problem of reconstructing the possible transition firing sequences in a given Petri net based on asynchronous observations of token changes at different places of the Petri net. We develop an algorithm that is able to reconstruct all firing sequences that are consistent with the partial ordering implied by the asynchronous observations and the structure of the given Petri net.;Besides event estimation problems in Petri nets, we also study the problem of minimum initial state (marking) estimation based on the observation of a sequence of labels produced by underlying transition activity in a given labeled Petri net. In particular, a minimum initial marking is the initial marking that has the least total number of tokens summed over all places. This work is motivated by minimum resource allocation problems in manufacturing systems that are modeled by Petri nets. The resulting algorithm is recursive and is able to find the minimum initial marking(s) with complexity that is polynomial in the length of the observed label sequence.;The final problem studied in the thesis is the problem of fault-tolerant control in Petri nets. In particular, we aim at providing tolerance against faults that may compromise the functionality of a given controller (modeled by a Petri net). We propose two approaches for the design of fault-tolerant redundant Petri net controllers. Under the reasonable assumption that the given controller is presumably designed to exactly meet the control specification of the plant to be controlled, we further require that the redundant Petri net controllers be bisimulation equivalent to the given, original controller (to retain identical control objectives). We obtain complete characterizations of redundant controllers along with necessary and sufficient conditions for bisimulation equivalence.