This paper presents a clustering technique that reduces the susceptibility to data noise by learning and clustering the data-distribution and then assigning the data to the cluster of its distribution. In the process, it reduces the impact of noise on clustering results. This method involves introducing a new distance among distributions, namely the expectation distance (denoted, ED), that goes beyond the state-of-art distribution distance of optimal mass transport, also called 2-Wasserstein (denoted,$W_{2}$): The latter essentially depends only on the marginal distributions while the former also employs the information about the joint distributions, making it more powerful. Using the ED, the paper extends the classical$K$-means and$K$-medoids clustering to those over data-distributions (rather than raw-data) and further introduces$K$-medoids using$W_{2}$. The paper also presents the closed-form expressions of the$W_{2}$and ED distance measures. The implementation results of the proposed ED and the$W_{2}$distance measures to cluster real-world weather data as well as stock data are also presented, which involves efficiently extracting and using the underlying data distributions—Gaussians for weather data versus lognormals for stock data. The results show striking performance improvement over classical clustering of raw-data, with higher accuracy realized for ED. Also, not only does the distribution-based clustering offer higher accuracy, but it also lowers the computation time due to reduced time-complexity.

Supervisory control and data acquisition (SCADA) and industrial control systems (ICSs) are designed to operate for extended periods of time and can withstand extreme conditions. However, operators, engineers, and offices change over time, which can lead to outdated documentation and references. This can make it difficult to identify system components and their vulnerabilities, which can pose a security risk. In this article, we present an automated passive method for identifying system components based on network traffic structure and network message characteristics. The proposed approach considers both TCP/IP and Modbus, the two primary communication protocols in SCADA, to identify devices. The algorithm was implemented in Python and evaluated using water treatment SCADA data collected from the iTrust facility. Once the system devices have been identified, the algorithm queries the National Vulnerability Database (NVD) and the Common Vulnerabilities and Exposures (CVE) databases to identify each device’s known vulnerabilities. Using our research on automated attack graph generation and visualization (A2G2V) and strongly connected component induced min label cut (SCCiMLC), we can map device vulnerabilities to system-level attack graphs and identify the bare minimum of device vulnerabilities to mitigate in order to secure the entire system. The proposed technique has been demonstrated to be beneficial in identifying system components in SCADA and ICS systems to increase their security.

Supervisory control and data acquisition/industrial control systems (SCADA/ICSs) networks are becoming more vulnerable to attacks that exploit the interdependence of security weaknesses at the atomic level to compromise system-level security. Attack graphs are an effective approach to depict these complex attack scenarios, assisting security administrators in determining how to best safeguard their systems. However, due to time and financial constraints, it is frequently not possible to address all atomic-level flaws at the same time. In this article, we propose a method for automatically detecting a minimal set of critical attacks that, when defended against, render the system secure. Finding a minimal label cut is typically an NP-complete problem. However, we propose a linear complexity approximation that uses the attack graph’s strongly connected components (SCCs) to create a simplified version of the graph in the form of a tree over the SCCs. Then, we perform an iterative backward search over this tree to find a set of backward-reachable SCCs, as well as their outward edges and labels, in order to find a cut of the tree with the fewest labels, which is a critical attack set. We put our proposed method to the test on real-world case studies, such as IT and SCADA networks for a cyber–physical system for water treatment, and outperformed previous state-of-the-art algorithms in terms of approximation accuracy and/or computational speed. Our solution provides security administrators with a practical and efficient method for prioritizing efforts to address vulnerabilities in SCADA/ICS networks.

Stability certification and identification of a safe and stabilizing initial set are two important concerns in ensuring operational safety, stability, and robustness of dynamical systems. With the advent of machine-learning tools, these issues need to be addressed for the systems with machine-learned components in the feedback loop. To develop a general theory for stability and stabilizability of neural network (NN)-controlled nonlinear systems subject to bounded parametric variations, a Lyapunov-based stability certificate is proposed and is further used to devise a maximal Lipschitz bound for a class of stabilizing NN controllers, and also a corresponding maximal Region of Attraction (RoA) within a user-specified safety set. To compute a robustly stabilizing NN controller that also maximizes the system’s long-run utility, a stability-guaranteed training (SGT) algorithm is proposed. The effectiveness of the proposed framework is validated through an illustrative example.

Prompt online detection of anomalies induced by malicious attacks enhances the efficacy of real-time operation and mitigation of attack, an indispensable part of any cyber-physical system (CPS) management. This article proposes a novel online rapid detection scheme that continuously monitors the data packet stream and infers the sequence of probability distributions, estimated as histograms, and alerts when a change in the histogram is detected, reporting both the attack as well as an estimate of its instant of commencement. A statistical data-driven attack model is proposed and employed that is general enough to represent two ubiquitous types of attacks on CPS: 1) replay and 2) bias-injection. The proposed detection framework relies on the fact that CPSs possess well-defined dynamics that are affected by quasistationary noise, which allows the histogram sequences of the system data packets to converge (to different distributions under the presence of the attack versus the absence of attack). The proposed online scheme detects an attack, and estimates the attack commencement time by relying on the computed distance between real-time estimated histogram versus apriori learned nominal histogram. Our formulation further sheds light on two different attack initiation-time-based subcases, “early” (attack starts before sufficient data of nominal behavior was collected to allow its histogram sequence to be closer to its nominal value) versus “late.” The designed algorithm of our scheme has linear time complexities in the dimension of data packets and algorithm parameters, which makes it suited for rapid detection. The proposed algorithm is implemented and validated on two real supervisory control and data acquisition system datasets, where a low detection delay demonstrates the effectiveness of the scheme.

Power and energy systems are lifeline infrastructures to civilization. Their stable operation and security of supply are essential for the daily life of the people. Typically, they are characterized by a central generation infrastructure using large-scale power plants. The electricity is transported via long-distance transmission lines on high-voltage levels and distributed via distribution grids to customers on medium and low-voltage levels.

An engineered system is designed to deliver certain performance related to its quality-of-service, and while doing so, it must also maintain stable operation. Resilience of a system is its ability to continue to offer system performance stably, while withstanding any adverse events. Motivated by this concept, we propose to measure the resilience level of a power system by quantifying its stability level as measured by: transient stability margin (TSM), critical clearance time (CCT), relay margin (RM), and load security margin (LSM), as well as its performance level as measured by: load loss (LL) and recovery/repair time (RT) while being exposed to adverse events. For comparability, we also propose a normalization for each of the 6 measures to a number in the unit interval [0, 1], which is scale-invariant, and further probabilistically average each of those across all possible sequences of faults (of a specified length) against their occurrence probabilities to arrive at a set of 6 unit-interval valued indices. New polynomial complexity algorithms (in the number of generators) are proposed for estimating TSM (in form of volume of region of stability) and CCT; new quadratic program formulation for precise computation of RM is developed and implemented; also, new security and stability informed notions of LSM and LL are introduced and implemented by extending continuation power flow. Such quantification of resilience levels provides a numerical measure to compare the relative abilities of different power grids to withstand the impact of sequences of adverse events. The proposed approach is illustrated by computing and comparing the resilience of three similar power system topologies differing only in the location of generators. The framework is further validated by implementing it on the IEEE 30-bus test system.

Securing cyber-physical systems (CPS) and Internet of Things (IoT) systems requires the identification of how interdependence among existing atomic vulnerabilities may be exploited by an adversary to stitch together an attack that can compromise the system. Therefore, accurate attack graphs play a significant role in systems security. A manual construction of the attack graphs is tedious and error-prone, this paper proposes a model-checking-based automated attack graph generator and visualizer (A2G2V). The proposed A2G2V algorithm uses existing model-checking tools, an architecture description tool, and our own code to generate an attack graph that enumerates the set of all possible sequences in which atomic-level vulnerabilities can be exploited to compromise system security. The architecture description tool captures a formal representation of the networked system, its atomic vulnerabilities, their pre-and post-conditions, and security property of interest. A model-checker is employed to automatically identify an attack sequence in the form of a counterexample. Our own code integrated with the model-checker parses the counterexamples, encodes those for specification relaxation, and iterates until all attack sequences are revealed. Finally, a visualization tool has also been incorporated with A2G2V to generate a graphical representation of the generated attack graph. The results are illustrated through application to computer as well as control (SCADA) networks.

Recent years have witnessed the rapid development and deployment of cyber and computer technologies, thus highly influencing the design methodologies of discrete-event and hybrid systems, i.e., systems with discrete and mixed discrete-continuous states/inputs. Their prevalence can be found in almost all areas of human life, such as embedded software, automated manufacturing systems, work-flow management, logic controllers, communication protocols, robotics, transportation and mobility, military, smart buildings, etc. Given the criticality of such applications, such systems ought to be carefully modeled, thoroughly verified, and adequately analyzed.

We show that the notion of copredictability studied in the considered paper is equivalent to the already existing notion of uniformly bounded coprognosability introduced in a 2010 article of Kumar and Takai. In fact, a weaker, more general notion of coprognosability, which does not need a uniform bound for prognosing an impending failure, was also introduced by Kumar and Takai in 2010. It was shown that for the case of regular languages, the two notions (the one with a uniform bound and the other without it) coincide. As a result, the algorithm for testing coprognosability for regular languages presented by Kumar and Takai in their 2010 paper also tests the copredictability concept in the considered paper, which presented a test of its own. Finally, the fact that copredictability is stronger than codiagnosability in the absence of unobservable cycles was also shown in the 2010 article of Kumar and Takai, and it is another result that is reproduced in the considered paper.

This paper provides revisions to the algorithms presented by Chen et al., 2013 for testing diagnosability of stochastic discrete-event systems. Additional new contributions include PSPACE-hardness of verifying strong stochastic diagnosability (referred as A-Diagnosability in Thorsley et al., 2005) and a necessary and sufficient condition for testing stochastic diagnosability (referred as AA-Diagnosability in Thorsley et al., 2005) that involves a new notion of probabilistic equivalence.

Most of existing digital content recommendation systems use explicit feedback data like user's ratings. While such systems rely on user input, those do not sense the context. In this paper, we propose a framework for digital content recommendation using only implicit feedback data (i.e., information collected from session usage without any direct feedback from user), which not only considers interactions among users and contents but also various other implicit information available during a video session. To capture interactions among such attributes, we choose Higher-Order Factorization Machines (HoFM) as our predictor and test our approach on real-world video usage data. In the experiments we explore different possible factors that may affect the performance of HoFM predictor. We observe that increasing the number of sessions of users considered to build the predictor significantly improves prediction accuracy, whereas increasing the order or depth of interactions may not. We also present an application of our work to a video recommendation system.

In the analysis of digital content consumption, session progress provides a good alternative to using manual ratings for measuring user engagement. A good prediction of session progress is useful for optimizing and personalizing the end-user experience. Most prevalent methods of predicting session progress are based on matrix completion and only consider the interaction among users and videos, while the associated contextual information is usually not used. In this paper, we present our approach for video recommendation, based on session progress prediction and incorporating the context. We test our approach on real-world session progress data, and observe considerable improvement in prediction accuracy achieved by incorporating selected context. Our experiments also show that proper context selection and the number of observed sessions for users are two key factors affecting the prediction accuracy.

While cryptography is used to protect the content of information (e.g., a message) by making it undecipherable, behaviors (as opposed to information) may not be encrypted and may only be protected by partially or fully hiding through creation of ambiguity (by providing covers that generate indistinguishable observations from secrets). Having a cover together with partial observability does cause ambiguity about the system behaviors desired to be kept secret, yet some information about secrets may still be leaked due to statistical difference between the occurrence probabilities of the secrets and their covers. In this paper, we propose a Jensen-Shannon divergence (JSD)-based measure to quantify secrecy loss in systems modeled as partially observed stochastic discrete event systems, which quantifies the statistical difference between two distributions, one over the observations generated by secret and the other over those generated by cover. We further show that the proposed JSD measure for secrecy loss is equivalent to the mutual information between the distributions over possible observations and that over possible system status (secret versus cover). Since an adversary is likely to discriminate more if he/she observes for a longer period, our goal is to evaluate the worst case loss of secrecy as obtained in the limit over longer and longer observations. Computation for the proposed measure is also presented. Illustrative examples, including the one with side-channel attack, are provided to demonstrate the proposed computation approach.

Previously we have introduced an inference-based framework for decentralized decision-making, where inferencing over the ambiguities of the self and the others is used to issue decisions. In this setting, we previously introduced the notion of N-inference V-diagnosability to characterize the existence of a disjunctive decentralized diagnosis scheme so that any fault can be detected within bounded delay, using at most N-levels of inferencing, by one of the diagnosers. While the disjunctive scheme relies on one of the diagnosers making the failure decision, the dual conjunctive scheme relies on none of the diagnosers making the nonfailure decision. It is known that the two schemes are incomparable, and in another paper we extend our earlier work to provide a more general framework, introducing the notion of N-inference diagnosability, capturing both disjunctive and conjunctive schemes. The contribution of this paper is developing a method for verifying N-inference diagnosability.

This paper studies the fault detection of discrete-time stochastic systems with linear-time temporal logic (LTL) as correctness requirement-A fault is a violation of LTL specification. The temporal logic allows system correctness properties to be specified compactly and in a user-friendly manner (being close to natural-languages), and supports automatic translation into other formal models such as automata. We introduce the notion of input-output stochastic hybrid automaton (I/O-SHA) and show that the refinement of a continuous physical system (modeled as stochastic difference equations) against a certain class of LTL correctness requirement can be modeled as an I/O-SHA. The refinement preserves the behaviors of the physical system and also captures requirement-violation as a reachability property. Probability distribution over the discrete locations of hybrid system is estimated recursively by computing the distributions for continuous variables for each discrete location. This is then used to compute the likelihood of fault, a statistic that we employ for the purpose of fault detection. The performance of the detection scheme is measured in terms of false alarm (FA) and missed detection (MD) rates, and the condition for the existence of a detector to achieve any desired rates of FA and MD is captured in form of Stochastic-Diagnosability, a notion that we introduce in this paper for stochastic hybrid systems. The proposed method of fault detection is illustrated by a practical example.

This paper presents a highly sensitive dedicated sensor that selectively measures nitrate ions. Nitrate-selective electrode of the three-electrode electrochemical sensor is formed by modifying the working electrode of the sensor with a novel nanofibrous mat made of conductive polypyrrole nanofibers. The nanofibers are formed by electrospinning technique. By doping the polypyrrole nanofibers with nitrate ions during an electrochemical polymerization process, numerous nanopores complimentary to the size of the target ions are created in the surface of the nanofibers, thus forming nitrate selective trapping sites. In addition, the porous structure of the nanofibers provides a large surface area of interacting with the analyte. This leads to high sensitivity of the sensor at the level of 1-2 nA per μM. The design, fabrication, and characterization of this new sensor are presented. The results are also discussed.

A methodology to extract sensor data from underground, in-situ, multi-frequency soil content sensors is presented. The underground sensor, that contains a small metamaterial inspired antenna that doubles up as a sensing element, measures the impedance of the surrounding soil by sending multiple signals of known frequencies in the range 1-40 MHz and comparing the magnitude and phase of reflected signal to those of incident signal. The amplitude and phase values that represent the reflection coefficient are stored in an internal register. In each transmission cycle, this packet is transmitted to an over ground receiver. The receiver decodes the data and processes it to extract the impedance value at the sensing element. The impedance values are then used to extract soil contents by solving certain dielectric mixing and relaxation models. A user-friendly graphical interface is developed that can support the automation of the whole process, and display the estimates of soil content as the output to help an end-user make effective decision about irrigation and fertilization.

Stateflow, a graphical interface tool for Matlab, is a common choice for design of event-driven software and systems. In order for their offline analysis (testing/verification) or online analysis (monitoring), the Stateflow model must be converted to a form that is amenable to formal analysis. In this paper, we present a systematic method, which translates Stateflow into a formal model, called Input/Output Extended Finite Automata (I/O-EFA). The translation method treats each state of the Stateflow model as an atomic module, and applies composition/refinement rules for each feature (such as state-hierarchy, local events) recursively to obtain the entire model. The size of the translated model is linear in the size of the Stateflow chart. Our translation method is sound and complete in the sense that it preserves the discrete behaviors as observed at the sample times. Further, the translation method has been implemented in a Matlab tool, which outputs the translated I/O-EFA model that can itself be simulated in Matlab.

FlexRay is a communication bus (and associated protocol) that supports transmission of time-triggered and event-triggered frames. A method for determining the worst-case response-time of FlexRay frames is proposed by Pop in 2008, and is formulated as iterative sequence of Integer Linear Programming (ILP) problems. As we show, the method of Pop is conservative (overestimates the response time). We propose a new ILP formulation that computes a precise value of the worst-case response time of FlexRay frames transmitted in the dynamic segment. Furthermore, our approach is non-iterative as it requires the solving of a single ILP for computing, respectively, the delay of full bus cycles and the delay of a partial (last) bus cycle. The proposed solution is also validated by applying it to a SAE benchmark and can be used for formally guaranteeing that no message will miss its deadline during system operation.

In an earlier work, we introduced a framework for fault-tolerant supervisory control of discrete event systems and presented a necessary and sufficient condition for its existence. In this paper, we introduce the synthesis of an optimal fault-tolerant supervisory controller. Given a discrete event plant with both post-fault and prefault behaviors, an optimal fault-tolerant supervisor we synthesize enforces a set of behaviors in which: 1) a recovery is guaranteed within a bounded delay following any fault; 2) all safety and nonblocking properties are satisfied; 3) the enforced set of prefault behaviors is maximized, and 4) a minimal set of post-fault behaviors is tolerated to achieve recovery in a minimal number of steps. An optimal solution requires a simultaneous maximization (of prefault behaviors) and minimization (of post-fault and prerecovery behaviors), which is quite novel. The optimal solution further minimizes the delay of recovery. The computation has complexity quadratic in the size of plant.

This paper presents a dielectric mixture model based approach for in-situ detection of soil-nitrates in real time. The dielectric constant of a material determines the impedance across a pair of electrodes immersed in that medium. We make accurate measurements on soil impedance over multiple frequencies using an in-situ soil-sensor we have designed. The impedance values are then used to determine the effective permittivity of the soil-bulk, which is then used to determine the concentration of individual components like soil, air, water and nutrients, e.g., nitrates using the data from measurements at multiple frequencies, and solving mixing models that involves component concentration as solution variables. The method shows good accuracy in the frequency range 1-70 MHz and can determine nitrate solution with less than 12% error. By considering 3% bound water percentage and assuming snow-like dielectric nature of bound water, this error reduces to 10%. If a parametrized apparent permittivity is considered in the vicinity of constituent particles, this error further reduces to less than 9%. Accurate nitrate detection based on our on-board, real-time, in-situ soil moisture sensors can provide an accurate real-time soil nitrate sensor and has the potential to greatly enhance agricultural production and reduce the impacts to the environment.

Two types of diagnosability of stochastic discrete-event systems (DESs) were introduced by Thorsley in 2005, where a necessary and sufficient condition for Strong Stochastic (SS)-Diagnosability (referred as A-diagnosability by Thorsley and Teneketzis, 2005), and a sufficient condition for Stochastic (S)-Diagnosability (referred as AA-diagnosability by Thorsley and Teneketzis, 2005), both with exponential complexity, were reported. In this paper, we present polynomial complexity tests for checking: (i) necessity and sufficiency of SS-Diagnosability; (ii) sufficiency of S-Diagnosability; and (iii) sufficiency as well as necessity of S-Diagnosability; the latter requires an additional notion of probabilistic equivalence. Thus, the work presented improves the accuracy as well as the complexity of verifying stochastic diagnosability.

In this paper we develop a formal approach for the synthesis of a cost-effective and correct-by-construction communication network (focusing on ZigBee wireless networks) subject to a set of end-to-end communication constraints of latency, bandwidth and error-rate, together with the constraints of the network protocols and the desired geographical placement of the network. We also develop a software platform to implement the proposed approach for network synthesis, and apply it to a practical wireless network synthesis for centralized as well as distributed estimation application.

Some discrete-event systems such as software are typically infinite state systems, and a commonly used technique for performing formal analysis such as automated verification is based on their finite abstractions. In this paper, we consider a model for reactive untimed infinite state systems called input-output extended finite automaton (I/O-EFA), which is an automaton extended with discrete variables such as inputs, outputs, and data. Using I/O-EFA as a model many value-passing processes can be represented by finite graphs. We study the problem of finding a finite abstraction that is bisimilar to a given I/O-EFA. We present a sufficient condition under which the underlying transition system of an I/O-EFA admits a finite bisimilar quotient. We then identify a class of I/O-EFAs for which a partition satisfying our sufficient condition can be constructed by inspecting the structure of the given I/O-EFA. We also identify a lower bound abstraction (that is coarser than any finite bisimilar abstraction), and present an iterative refinement algorithm whose termination guarantees the existence of a finite bisimilar abstraction. The results are illustrated through examples that model reactive software.

A method for determining worst-case response-time properties of the FlexRay protocol frames is proposed by Pop et al. in 2008, where the determination of the worst-case response time of frames transmitted in the dynamic segment is formulated as iterative sequences of an Integer Linear Programming (ILP) problems. In this paper, we show that the analysis method of Pop et al. provides pessimistic results of the worst-case response time of frames transmitted in the dynamic segment. Then, we propose a new ILP formulation that computes the exact value of the worst-case response time of FlexRay frames transmitted in the dynamic segment. Further our approach is non-iterative requiring a solving of a single ILP for computing respectively the number of cycles a frame is delayed access to the bus and the delay spent in the unfilled cycle before the transmission of the frame starts.

The use of wireless sensor networks is essential for implementation of information and control technologies in precision agriculture. We present our design of network stack for such an application where sensor nodes periodically collect data from fixed locations in a field. Our design of the physical (PHY) layer consists of multiple power modes in both the receive and transmit operations for the purpose of achieving energy savings. In addition, MAC layer is designed which uses these multiple power modes to save energy during the wake-up synchronization phase. We also present analytical models and simulation studies to compare the energy consumption of our MAC protocol with that of the popular S-MAC protocol and show that our protocol has better energy efficiency as well as latency in a periodic data collection application.

Extended Finite Automata (EFA), i.e., finite automata extended with variables, are a suitable modeling framework for discrete event systems owing to their compactness, resulting from the use of variables. In this paper, we propose a symbolic algorithm that efficiently synthesizes a supervisor for a plant modeled by an EFA and a specification defined by another EFA. The principle of the algorithm is to iteratively strengthen the guards of the plant EFA so that forbidden or blocking states become unreachable in the controlled plant. As a consequence of the algorithm, the controlled behavior is modeled by an EFA having the same structure as the plant EFA, having stronger guards and is shown to be maximally permissive. We illustrate our algorithm via a simple manufacturing example.

ABSTRACT The use of wireless sensor networks is essential for implementation of information and control technologies in precision agriculture. We present our design of network stack for such an application where sensor nodes periodically collect data from fixed locations in a field. Our design of the physical layer consists of multiple power modes in both the receive and transmit operations for the purpose of achieving energy savings. In addition, we design our MAC layer to use these multiple power modes to improve the energy efficiency of wake‐up synchronization phase. Our MAC protocol also organizes all the sender nodes to be synchronized with the receiver simultaneously and transmit their data in a time scheduled manner. Next, we design our energy aware routing strategy that balances the energy consumption over the nodes in the entire field and minimizes the number of wake‐up synchronization overheads by scheduling the nodes for transmission in accordance with the structure of the routing tree. We develop analytical models and simulation studies to compare the energy consumption of our MAC protocol with that of the popular S‐MAC protocol for a typical network topology used in our application under our routing strategy. Our MAC protocol is shown to have better energy efficiency as well as latency in a periodic data collection application. We also show the improvements resulting from the use of our routing strategy, in simulations, compared with the case when the next hop is chosen randomly from the set of neighbors that are closer to the sink node. Copyright © 2011 John Wiley & Sons, Ltd.

The use of wireless sensor networks is essential to implementation of information and control technologies in application areas such as precision agriculture. We design MAC and Network layers for a wireless sensor network deployed for a precision agriculture application which requires periodic collection of sensor readings from fixed locations in a field. The Physical layer consists of a radio which operates in multiple power levels in the transmit mode and multiple sensitivity levels in the receive mode. The MAC layer is designed to save energy during the wake-up synchronization phase. The network layer is designed to custom fit the needs of the application, namely periodic data collection from fixed locations, and to minimize the energy consumption through balancing the communication load. The design of various protocol layers involves a cross-layer design strategy, taking into consideration the requirements and the characteristics of the application.

We study the decentralized control of discrete-event systems withmultiplelocal specifications. Only a subset of events occur at a local site, and a local specification as well as control/observation capabilities of a local supervisor are defined with respect to such local events. The goal of control is to ensure that the executed behavior at each local site is as desired, i.e., there are multiple specifications, one for each site. We show that the control problem for multiple local specifications is different from that of a single global specification, and present a necessary and sufficient condition for the existence of decentralized supervisors for enforcing the given multiple local specifications. The synthesis of decentralized control for enforcing multiple local specifications is also presented. We also specialize our results to the case of concurrent plants (one which is composed of several local subplants), which offers certain computational savings. The results are illustrated through a simple manufacturing system example.

We study diagnosis of timed discrete-event systems (TDESs) modeled as timed-automata. Earlier works on diagnosis of TDESs assumed that a diagnoser has partial observation of events but can measure (or observe) time with arbitrary precision. In practice, however, time can only be measured with finite precision. We model the finite precision observability of time using a digital-clock that measures time discretely by executing ticks. For the diagnosis purposes, the set of nonfaulty timed-traces is specified as another timed-automaton that is deterministic, generalizing the forms of nonfaulty specifications considered in the earlier works. We show that the set of timed-traces observed using a digital-clock with finite precision is regular, i.e., can be represented using a finite (untimed) automaton. We show that the verification of diagnosability (ability to detect the execution of a faulty timed-trace within a bounded time delay) as well as the offline synthesis of a diagnoser are decidable by reducing these problems to the untimed setting. The reduction of the diagnosis problem to the untimed setting also suggests an effective method for the offline computation of a diagnoser as well as its online implementation for diagnosis.

The task of decentralized decision-making involves interaction of a set of local decision-makers, each of which operates under limited sensing capabilities and is thus subjected to ambiguity during the process of decision-making. In our previous work, we made an observation that such ambiguities are of differing gradations and presented a framework for inferencing over various local control decisions of varying ambiguity levels to arrive at a global control decision. A similar inferencing-based framework for the management of ambiguities in the decentralized diagnosis of failures was also reported by us in another earlier work. For each event-trace executed by a system being monitored, each local diagnoser issues its own diagnosis decision (failure or nonfailure or unsure), tagged with a certain ambiguity level (zero being the minimum). A global diagnosis decision is taken to be a ?winning? local diagnosis decision, i.e., one with a minimum ambiguity level. The computation of an ambiguity level for a local decision requires an assessment of the self-ambiguities as well as the ambiguities of the others, and an inference based up on such knowledge. This correspondence paper extends this to the decentralized diagnosis of nonfailures which requires that any ambiguity about the nonoccurrence of a failure be resolved within a uniformly bounded delay. It is known that the decentralized diagnosability for failures does not imply that for nonfailures, and vice versa. Further, the following difference exists: Once the ambiguity about the occurrence of a failure is resolved, future observations do not cause the ambiguity to reoccur. The same is not true when one is concerned with the diagnosis for nonfailures, and so, a different formulation is needed. In order to characterize the class of systems for which the ambiguity about the nonoccurrence of a failure can be resolved within a uniformly bounded delay, we introduce the notion of N-inference diagnosability for NonFailures (also called N-inference NF-diagnosability), where the indexNrepresents the maximum ambiguity level of any winning local decision. We present a method for verifying N-inference NF-diagnosability and also establish various properties of it.

More and more advanced features such as adaptive cruise control, collision avoidance, and stability control are being implemented in vehicles. These features are usually implemented as distributed CAN (controller area network) systems right now. In a CAN system, normally there is no clock synchronization among the ECU (electronic control unit) nodes connected by the CAN bus. Without synchronization, the clocks of those ECU nodes could drift away from each other. A typical clock drift rate of 30 ppm (parts per million) could cause a clock to drift by 108 milliseconds in one hour. The clock drift this large could cause problems in those advanced vehicle control systems. In fact, a sequence of messages could get lost in a distributed CAN system due to the combination of clock drift, transmission jitter, and finite buffer size. To solve the above problem, instead of performing high overhead clock synchronization in the CAN system, this paper provides an economical solution for the prevention of the above message loss problem. The idea is to synchronize the task activations on different ECU nodes and such synchronizations are performed only when necessary. An analysis method is developed for the determination of the synchronization frequency; and an algorithm is provided for the task activation synchronization.

We develop a modeling approach for Simulink diagrams. Simulink is a commercial graphical representation tool for representing and simulating dynamical systems. We propose a recursive approach for modeling a class of Simulink diagrams as input/output-extended finite automata (I/O-EFA). A model of a Simulink diagram can be used for further analysis such as test generation and formal verification. The modeling approach is sound and complete: The input-output behavior of an I/O-EFA model, as defined in terms of a step-trajectory, preserves the input-output behavior of the corresponding Simulink diagram at each sample time.

We address the problem of optimizing mediator-based service composition where the services and the desired composition (goal) functionality are represented as i/o automata with loops. The objective of optimization is to minimize the costs of communications and computations necessary to realize the goal from the existing services. We develop an algorithm to compute the minimum cost of an automaton representing the choreographed behavior of services realizing the goal. This forms the central theme of our technique for developing automatically a strategy of decentralized mediation that will result in the optimized composition of services.

The task of decentralized decision-making involves interaction of a set of local decision-makers, each of which operates under limited sensing capabilities and is thus subjected to ambiguity during the process of decision-making. In our prior work, we made a key observation that such ambiguities are of differing gradations and presented a framework for inferencing over varying ambiguity levels to arrive at local and global control decisions. We develop a similar framework for performing diagnosis in a decentralized setting. For each event-trace executed by a system being monitored, each local diagnoser issues its own diagnosis decision (failure or nonfailure or unsure), tagged with a certain ambiguity level (zero being the minimum). A global diagnosis decision is taken to be a ldquowinningrdquo local diagnosis decision, i.e., one with a minimum ambiguity level. The computation of an ambiguity level for a local decision requires an assessment of the self-ambiguity as well as the ambiguities of the others, and an inference based up on such knowledge. In order to characterize the class of systems for which any fault can be detected within a uniformly bounded number of steps (or ldquodelayrdquo), we introduce the notion ofN-inference-diagnosability for Failures (also calledN-inference F-diagnosability), where the indexNrepresents the maximum ambiguity level of any winning local decision. We show that the codiagnosability introduced in is the same as 0-inference F-diagnosability; the conditional F-codiagnosability introduced in , is a type of 1-inference F-diagnosability; the class of higher-index inference F-diagnosable systems strictly subsumes the class of lower-index ones; and the class of inference F-diagnosable systems is strictly subsumed by the class of systems that are centrally F-diagnosable.

We introduce the notion ofsafe-codiagnosability, extending the notion of safe-diagnosability (Paoli and Lafortune, 2005) to the decentralized setting. For a system, a certain subbehavior is deemed safe (captured via a safety specification), and a further subbehavior is deemed nonfaulty (captured via a nonfault specification). Safe-codiagnosability requires that when the system executes a trace that is faulty, there exists at least one diagnoser that can detect this within bounded delay and also before the safety specification is violated. The above notion of safe-codiagnosability may also be viewed as an extension of the notion of codiagnosability (Qiu and Kumar, 2006), where the latter did not have any safety requirement. We show that safe-codiagnosability is equivalent to codiagnosability together with ldquozero-delay codiagnosabilityrdquo of ldquoboundary safe tracesrdquo. (A safe trace is a boundary safe trace if there exists a single-event extension that is unsafe.) We give an algorithm of polynomial complexity for verifying safe-codiagnosability. For a safe-codiagnosable system, the same methods as those proposed in (Qiu and Kumar, 2006) can be applied for offline synthesis of individual diagnosers, as well as for online diagnosis using them.

We propose a two-tiered hierarchical approach for detecting faults in embedded control software during their runtime operation: The observed behavior is monitored against the appropriate specifications at two different levels, namely, the software level and the controlled-system level. (The additional controlled- system level monitoring safeguards against any possible incompleteness at the software level monitoring.) A software fault is immediately detected when an observed behavior is rejected by a software level monitor. In contrast, when a system level monitor rejects an observed behavior it indicates a system level failure, and an additional isolation step is required to conclude whether a software fault occurred. This is done by tracking the executed behavior in the system model comprising of the models for the software and those for the nonfaulty hardware components: An acceptance by such a model indicates the presence of a software fault. The design of both the software-level and system-level monitors is modular and hence scalable (there exists one monitor for each property), and further the monitors are constructed directly from the property specifications and do not require any software or system model. Such models are required only for the fault isolation step when the detection occurs at the system level. We use input-output extended finite automata (I/O- EFA) for software as well as system level modeling, and also for modeling the property monitors. Note since the control changes only at the discrete times when the system/environment states are sampled, the controlled- system has a discrete-time hybrid dynamics which can be modeled as an I/O-EFA.

We introduce the notion ofdirectedcontrol, where a directed controller is one that selects at most one controllable event to be enabled at any instant. This is in contrast tosupervisorycontrol, where a supervisory controller enables a maximum allowable set of controllable events at any instant, i.e., no specific selection for executing an enabled event is made. While the design of a supervisory controller is meaningful for plants that aregeneratorof controllable events, a directed controller design makes more sense for plants that areexecutorof controllable events. The control goal is the same as that in a supervisory control setting, namely, safety and nonblockingness. A safe and nonblocking directed controller exists if and only if a safe and nonblocking supervisory controller exists, thereby proving the polynomiality of verifying existence. We also develop a set of algorithms of polynomial complexity to compute a safe and nonblocking directed controller (whenever one exists).

This paper introduces a formalism for modeling interaction and control of partially observed discrete event systems (DESs), called prioritized synchronous composition under mask (PSC/M). In PSC/M, each system is associated with an event priority set and an observation mask. The existing formalisms have their limitations and what we propose is a general canonical mode of interaction that is suitable for control under partial observation as well as for modeling a variety of interaction modes such as strict/prioritized synchronization, interleaving, hiding, and renaming. In PSC/M, an event is globally enabled if it is locally enabled by all the interacting systems. The tracking of a globally enabled event is done by executing a transition on an indistinguishable event. PSC/M possesses the useful properties of commutativity and associativity. PSC/M can be applied to compose local controller modules having limited sensing and actuation capabilities to obtain an equivalent global controller module. PSC/M can itself be employed as a control mechanism, in which case it helps remove the control and the observation compatibility requirements of a controller. We study the PSC/M-based control problem where both the plant and the supervisor have their own control and observation limitations. The plant and the specification models need not be at the same level of abstraction and so new classes of control problems can be solved in the framework. The existence condition is the achievability with respect to an augmented plant, which is weaker than controllability and observability combined. The weaker condition is required since we allow supervisors to be nondeterministic, which also facilitates the existence and synthesis to be performed polynomially in the size of the plant and the specification. Note to Practitioners-This paper presents a mechanism of composition for modeling the interaction of DESs. To form the composition one needs to identify for each system the events that it can control (actuator events) and the events that it can observe (sensor events). The composition ensures that a system never blocks its uncontrollable events and never reacts differently to events that are observationally indistinguishable. An event is executable in the composition if it is enabled by all participating systems and either trackable or executable in some participating system. An event is enabled by a participating system if it is either currently executable or a nonpriority event, whereas an event is trackable by a participating system if it is observable and indistinguishable to some currently executable event. A state update on an event, executable in the composition, occurs by executing an indistinguishable event by each participating system in which the event is trackable, whereas the other participating systems retain their current states. The composition is commutative and associative, supporting incrementality. We obtain a condition under which a given system (plant) can be controlled to exhibit the desired behaviors when the proposed mechanism is employed to compose the plant and a controller. The plant and the desired behavior models may differ in their levels of abstraction. The condition can be polynomially verified and a controller can be synthesized in linear complexity.

We study distributed failure diagnosis under a -bounded communication delay, where each local site transmits its observations to other sites immediately after each observation and the transmitted observation is received within at most more event executions of the plant. A notion of diagnosability is introduced so that any failure can be diagnosed within a bounded delay of its occurrence by one of the local sites using its own observations and the -bounded delayed observations received from other local sites. The local sites communicate among each other using an ldquoimmediate observation passing (iop)rdquo protocol, forwarding any observation immediately up on its occurrence. We construct models for the -bounded communication delay and use them to extend the system and nonfault specification models for capturing the effect of bounded-delay communication. By using the extended system and specification models, the distributed diagnosis problem under the immediate observation passing protocol is then converted to a decentralized diagnosis problem of our previous work, where the results are applied for verifying diagnosability and for synthesizing local diagnosers. Methods by which complexity of testing diagnosability and of online diagnosis can be reduced are presented. Finally, we compare the notions of diagnosability, codiagnosability, and diagnosability.

We study the problem of synthesis of a choreographer in Web service composition for a given set of services and a goal. Services and goal are represented using I/O automata which can succinctly and precisely describe the interfaces of the services. Our technique considers existence and synthesis of two types of the choreographers: a simple choreographer capable of only relaying outputs from one service to input of another and a transducing choreographer which is capable of storing and reusing inputs/outputs from the services. The central theme of our technique relies on generating I/O automata representation of all possible choreographed behavior of existing services (captured in form of universal service automaton, a concept introduced in this paper) and verifying that the goal can be simulated by the universal set of choreographed behaviors.

We present a goal-directed, local and on-the-fly algorithm for verifying the existence and synthesizing a choreographer forWeb service composition. We use i/o-automata to represent services, the desired functionality of the composition, and a choreographer to achieve the desired service by composing the existing ones. Choreographer existence and synthesis are typically performed by identifying all possible compositions realizable from the existing services and verifying whether one such composition conforms to the desired required functionality. Such a technique is subject to state-space explosion. In light of this, we have developed a tabled-logic programming technique which generates and explores compositions in a goal-directed fashion to prove/disprove the existence of choreographer and to infer whether the desired functionality is realizable. We present a prototype implementation and show the practical applicability of our technique using a variety of composition problems with the corresponding computational savings in terms of number of states and transitions explored.

This paper studies supervisory control of discrete event systems subject to specifications modeled as nondeterministic automata. The control is exercised so that the controlled system is simulation equivalent to the (nondeterministic) specification. Properties expressed in the universal fragment of the branching-time logic can equivalently be expressed as simulation equivalence specifications. This makes the simulation equivalence a natural choice for behavioral equivalence in many applications and it has found wide applicability in abstraction-based approaches to verification. While simulation equivalence is more general than language equivalence, we show that existence as well as synthesis of both the target and range control problems remain polynomially solvable. Our development shows that the simulation relation is a preorder over automata, with the union and the synchronization of the automata serving as an infimal upperbound and a supremal lowerbound, respectively. For the special case when the plant is deterministic, the notion of state-controllable-similar is introduced as a necessary and sufficient condition for the existence of similarity enforcing supervisor. We also present conditions for the existence of a similarity enforcing supervisor that is deterministic.

This paper extends our prior result on decidability of bisimulation equivalence control from the setting of complete observations to that of partial observations. Besides being control compatible, the supervisor must now also be observation compatible. We show that the "small model theorem" remains valid by showing that a control and observation compatible supervisor exists if and only if it exists over a certain finite state space, namely the power set of the Cartesian product of the system and the specification state spaces. Note to Practitioners-Non-determinism in discrete-event systems arises due to abstraction and/or unmodeled dynamics. This paper addresses the issue of control of non-deterministic systems subject to non-deterministic specifications, under a partial observation of events. Non-deterministic plant and specification are useful when designing a system at a higher level of abstraction so that lower level details of the system and its specification are omitted to obtain higher level models that are non-deterministic. The control goal is to ensure that the controlled system has an equivalent behavior as the specification system, where the notion of equivalence used is that of bisimilarity. Bisimilarity requires the existence of an equivalence relation between the states of the two systems so that transitions on common events beginning from a pair of equivalent states end up in a pair of equivalent successor states. Supervisors are also allowed to be nondeterministic, where the nondeterminism in control is implemented by selecting control actions nondeterministically from among a set of precomputed choices. The main contribution of this paper is to show that a supervisor exists if and only if one exists where the size of its state-space upper bounded and so it suffices to search over this state space. We illustrate our results through a manufacturing example

In an earlier paper, we introduced the notion of directed control, where a directed controller, which is simply referred to as a director, is one that selects at most one controllable event to be enabled at any instant. In this paper, we develop an optimization-based approach for the design of a director: starting from any state, the worst cost to the nearest reachable marked state is minimized. The motivation is that a pending task can be completed in the least possible cost. A necessary and sufficient condition for the existence of an optimal director is obtained. Furthermore, for systems that are cycle-free, we provide an algorithm of polynomial complexity to compute an optimal director.

In our earlier work, we introduced a state-based approach for the diagnosis of repeatedly occurring failures in discrete event systems (DESs). Since temporal logic provides a simpler way of specifying system properties; in this paper, a temporal-logic-based approach for diagnosing the occurrence of a repeated number of failures is developed. Linear-time temporal-logic (LTL) formulae are used to represent the specifications of DESs. Notions of prediagnosability for failures and diagnosability for repeated failures are introduced in the setting of temporal logic. A polynomial algorithm for the test of prediagnosability for failures is provided. The diagnosis problem for repeated failures in the temporal-logic setting is reduced to one in a state-based setting, and so the prior results of a state-based repeated failure diagnosis can be applied. Finally, a simple example is given for illustration. Note to Practitioners-Certain failures in a system are repeatable, such as routing errors in a manufacturing system. A theory for the diagnosis of such failures was presented in an earlier work of Jiang et al. The present paper uses temporal logic to specify such failures. It turns out that repeatable failures can be specified as violations of invariant properties (i.e., properties that must always hold). Given an invariant property that the system must always satisfy, an algorithm is presented to refine the system model and label those states of the refined system where the property is violated. The problem of repeated diagnosis then requires determining, within a bounded delay, each time a "failure-state" is visited. For this analysis, the existing theory developed by Jiang et al. is used.

By decentralized diagnosis we mean diagnosis using multiple diagnosers, each possessing its own set of sensors, without involving any communication among diagnosers or to any coordinators. The notion of decentralized diagnosis is formalized by introducing the notion of codiagnosability that requires that a failure be detected by one of the diagnosers within a bounded delay. Algorithms of complexity polynomial in the size of the system and the nonfault specification are provided for: 1) testing codiagnosability, 2) computing the bound in delay of diagnosis, 3) offline synthesis of individual diagnosers, and 4) online diagnosis using them. The notion of codiagnosability and the above algorithms are initially presented in a setting of a specification language (violation of which represents a fault) and are later specialized to the case where faults are modeled as the occurrences of certain events. The notion of strong codiagnosability is also introduced to capture the ability of being certain about both the failure as well as the nonfailure conditions in a system within a bounded delay.

In an earlier paper, the authors introduced the notion of safety control of stochastic discrete event systems (DESs), modeled as controlled Markov chains. Safety was specified as an upper bound on the components of the state probability distribution, and the class of irreducible and aperiodic Markov chains were analyzed relative to this safety criterion. Under the assumption of complete state observations: 1) the authors identified the set of all state-feedback controllers that enforce the safety specification, for all safe initial probability distributions and 2) for any given state-feedback controller, the authors constructed the maximal invariant safe set (MISS). In this paper, the authors extend the work in several ways: 1) safety is specified in terms of both upper and lower bounds; 2) we consider a larger class of Markov chains that includes reducible and periodic chains; 3) we present a more general iterative algorithm for computing the MISS, which is quite flexible in its initialization; 4) we obtain an explicit upper bound for the number of iterations needed for the algorithm to terminate. Note to Practitioners-The paper studies "safety" control of stochastic systems modeled as Markov chains. Safety is defined as a requirement that the probability distribution in each state remain bounded between an upper and a lower bound. For example, a financial investment policy should be such that the probability of ever being bankrupt is bounded below by a positive number. Prior works on control of Markov chains have addressed optimality but not safety. A condition is obtained under which a controlled Markov chain is guaranteed to be safe at all times. For those chains that do not satisfy such a condition, a maximal subset of the safe set of distributions is computed so that if the chain is initialized with a distribution in that maximal subset, it remains safe all the times. A condition is obtained under which such a maximal set is nonempty. The computation of such a maximal set is iterative and we provide a condition under which the computation terminates in a finite number of iterations. Manufacturing system examples are included to illustrate the results.

We study supervisory control of discrete event systems with potentially infinite state-space using state variables for representation and specification. An assignment program model consisting of state variables and a finite set of conditional assignment statements is used for representing a discrete event system, and a predicate over state variables is used for representing a state avoidance control specification. The contribution of this paper is to show how to perform supervisory control computations symbolically. In the case of a Petri net (vector addition system) with the set of forbidden states being a right-closed set, we present a finitely terminating algorithm for maximally permissive supervision. Discrete-event systems are systems with discrete states that evolve in response to discrete events. The state space of such systems can be finite or infinite. The latter case occurs when the state-variables can take infinitely many values such as integers. Certain states in a given system may be "bad", such as a deadlocking state. Then, controllers must be designed to restrict the system behavior by dynamically disabling events occurring in the system so that system never reaches the bad states. Also, certain events can be uncontrollable and cannot be disabled. State-avoidance control of potentially infinite-state discrete-event systems is studied in this paper. A compact program-like modeling formalism has been adopted. Although the control problem for infinite-state systems is in general not solvable in an automated fashion owing to its undecidability established We develop a symbolic technique, that is iterative in nature and can be automated, for computing a control strategy. If the iteration terminates (there is no guarantee though), a controller is computed. We illustrate through several examples where the iterative computation does terminate. Finally, we show that for a certain class of infinite-state systems that can be modeled as Petri nets, the iterative computation is guaranteed to terminate whenever the state-avoidance set is lower-bounded (every state that "dominates" a bad state is itself bad).

We introduce the notion of repeated failure diagnosability for diagnosing the occurrence of a repeated number of failures in discrete event systems. This generalizes the earlier notion of diagnosability that was used to diagnose the occurrence of a failure, but from which the information regarding the multiplicity of the occurrence of the failure could not be obtained. It is possible that in some systems the same type of failure repeats a multiple number of times. It is desirable to have a diagnoser which not only diagnoses that such a failure has occurred, but also determines the number of times the failure has occurred. To aid such analysis we introduce the notions of K-diagnosability (K failures diagnosability), [1, K]-diagnosability (1 through K failures diagnosability), and [1, /spl infin/]-diagnosability (1 through /spl infin/ failures diagnosability). Here the first (resp., last) notion is the weakest (resp., strongest) of all three and the earlier notion of diagnosability is the same as that of K-diagnosability or that of [1, K]-diagnosability with K=1. We give polynomial algorithms for checking these various notions of repeated failure diagnosability and also present a procedure of polynomial complexity for the online diagnosis of repeated failures.

The design of logic controllers for event-driven systems continue to rely largely on intuitive methods rather than on formal techniques. This approach results in a control code that requires extensive verification, is hard to maintain and modify, and may even fail at times. Supervisory control theory (SCT) provides a formal approach to logic control synthesis. In order to demonstrate the usefulness of the supervisory control theory in manufacturing systems, an educational test-bed that simulates an automated car assembly line has been built using LEGO/spl reg/ blocks. Finite state machines (FSMs) are used for modeling operations of the assembly line, and for the specifications that accomplish the task of successfully completing the assembly repeatedly. Using the technique of SCT, we derive a supervisor that enforces the specifications while offering the maximum flexibility of assembly. Subsequently a controller is extracted from the maximally permissive supervisor for the purpose of implementing the control by selecting, when possible, at most one controllable event from among the ones allowed by the supervisor. Testing to check the correctness of the control code is reduced, since the controller is guaranteed to enforce the specifications.

The decentralized supervisory control problem of discrete event systems under partial observation is studied in this paper. The main result of the paper is a necessary and sufficient condition for the existence of decentralized supervisors for ensuring. That the controlled behavior of the system lies in a given range. The contribution of the paper is (1) our setting of decentralized control generalizes the prior ones; (2) we present an alternative approach for solving the decentralized control problem, which leads to computational saving for concurrent systems and certain other systems; and (3) our generalized formulation and its solution lets us extend several of the existing results reported previously. The results of our paper are illustrated by an example of a simple manufacturing system.

Presents a behavior-based intelligent control architecture for designing controllers which, based on their observation of sensor signals, compute the discrete control actions. These control actions then serve as the "set-points" for the lower level controllers. The behavior-based approach yields an intelligent controller which is a cascade of a perceptor and a response controller. The perceptor extracts the relevant symbolic information from the incoming continuous sensor signals, which enables the execution of one of the behaviors. The response controller is a discrete event system that computes the discrete control actions by executing one of the enabled behaviors. The behavioral approach additionally yields a hierarchical two layered response controller, which provides better complexity management. The inputs from the perceptor are used to first compute the higher level activities, called behaviors, and next to compute the corresponding lower level activities, called actions. The paper focuses on the discrete event subsystem, namely, the response controller. We illustrate the intelligent control architecture by discussing its application to the design of intelligent controllers for autonomous underwater vehicles used for ocean sampling missions. A complete set of discrete event models of the response controller of the underwater vehicles for the above application has been given, and their formal verification discussed.

The traditional framework for discrete-event control is extended to include the case of control with active events, in which both the user and the environment have events that they can trigger. A variety of liveness and safety specifications can be considered within this extended framework. A synthesis algorithm of minimally restrictive controllers is outlined.

An optimal control theory for designing a controller, that selects unique control actions is developed for controlling discrete event systems (DESs). Prior work on supervisor synthesis problems studied the design of supervisors for satisfying qualitative specifications within the framework of the DESs. In this paper we define and investigate the synthesis of an optimal controller in the sense that, regardless the state of the plant, the worst cost of all surviving paths from that state to the set of frontier marked states is minimized. Our work differs from prior works on optimal control of DESs in that the controller selects a unique controllable event to be executed per state, rather than a set of admissible controllable events. An efficient algorithm is provided to solve this problem under complete observation.