Search

Manufacturing systems may be subject to external attacks and failures, so it is important to deal with the recovery of the system after these situations. This article deals with the problem of recovering a manufacturing system, modeled as a discrete event system (DES) using the supervisory control theory (SCT), when the control structure, called supervisor, desynchronizes from the physical plant. The desynchronization may be seen as plant and supervisor being in uncorresponding states. The recovery of the system may be attained if there is a word, the synchronizing word, that regardless the state of each one of them, brings the system and supervisor back to a known state. The concepts of synchronizing automata are used to do so. In this article, we show under what conditions a set of synchronizing plants and specifications leads to a synchronizing supervisor obtained by the SCT. The problem is extended to cope with multiple supervisors, proposing a local recovery when possible. We also present a simple way to model problems, composed of machines and buffers, as synchronizing automata such that it is always possible do restore synchronization between the control (supervisor) and the plant. Note to Practitioners—Given the unpredictability of faults and malicious attacks occurring in industrial systems, recovery strategies are crucial for a harmonic operation of the plant. The possibility of leading the system to a known state, recovering control, is of extreme importance to the safety of industrial processes. The method proposed in this article uses well-known concepts of supervisory control theory (SCT) of discrete event systems (DESs), introducing the recovery process (using recovery events) in the modeling phase such that it is possible to isolate and fix only the part of the control system subject to the fault. The result of the proposed approach allows the implementation of such control system with the recovery procedure directly in the programmable logic controllers (PLCs). [ABSTRACT FROM AUTHOR]

In practical systems, due to reasons such as sensor limitations, sensor faults, and packet losses in networks, the observation of events becomes nondeterministic. In this article, we extend strong detectability and weak detectability to the case of nondeterministic observations and denote them as A-($k_{1}$ , $k_{2}$)-detectability and O-($k_{1}$ , $k_{2}$)-detectability, respectively. A-($k_{1}$ , $k_{2}$)-detectability says that, for any string, we can distinguish state pairs in the specification for all possible observations of the string. O-($k_{1}$ , $k_{2}$)-detectability says that, for at least one string, we can distinguish state pairs in the specification for all possible observations of the string. For A-($k_{1}$ , $k_{2}$)-detectability, we construct a transformed automaton and then translate the A-($k_{1}$ , $k_{2}$)-detectability problem into the traditional detectability problem that has been solved. We show that A-($k_{1}$ , $k_{2}$)-detectability can be used to solve the deterministic supervisory control problem. For O-($k_{1}$ , $k_{2}$)-detectability, we construct an augmented automaton that includes all the information of the given automaton and its state estimates. Based on the augmented automaton, we propose a depth-first search (DFS)-based algorithm to check O-($k_{1}$ , $k_{2}$)-detectability. Note to Practitioners—Nowadays, practical engineering systems become more and more complex. In these systems, the observation of events often becomes nondeterministic due to reasons such as sensor limitations, sensor faults, and packet losses in networks. Consider a mobile robot as an example. The availability of a sensor output may depend on the current location of the mobile robot. If the mobile robot is in an area where the wireless network is unreliable, the sensor output may not be received by the supervisor. In this article, we investigate the state estimation problem for practical engineering systems under nondeterministic observations within a discrete-event system framework. The results in this article provide not only insights for engineers in the automatic control field to understand nondeterministic observations in practical systems but also the methodology to estimate the current discrete state that is always an important issue. Therefore, we believe that the engineers in the automatic control field should be interested in this article and can benefit from it. [ABSTRACT FROM AUTHOR]

Deadlock resolution has been an important research topic in the field of automated manufacturing systems (AMSs). Researchers generally assume that AMS resources never break down whereas only a few resolve the issues of resource failures in the discrete-event supervision of AMSs. In fact, an AMS consists of a number of numerically controlled machines interacting with each other. The failure of resources happens unexpectedly. In this article, we allow parallel routes to use unreliable resources. Because of their powerful modeling capabilities, Petri nets are used to model the considered AMSs. By using a look-ahead control strategy, a robust supervisory control policy is developed for AMSs with assembly operations allowing resource failures. Our objective is to advance parts requiring failed resources in their remaining routes into a special position so as to release shared resources in case some unreliable resources fail. Consequently, those parts not necessarily requiring any failed resource can keep progressing all the time. The conventional methods are on the basis of monolithic and structure-oriented control specifications with centralized supervisors. Our policy can be implemented in a distributed, online, and local way. Several examples are given to elucidate our control policy clearly. Note to Practitioners—In automated manufacturing systems (AMSs), resources such as machines and tools with higher reliablity are always expensive. Sometimes, when it is not cost-effective to use resources with higher reliability, manufacturers may choose some resources with possible failures. These resources are thus considered as unreliable ones in our article. Normally, unreliable resources may fail unexpectedly. Their occurrences can lead a system to stagnation, causing unnecessary downtime, and bringing economic loss to enterprises. To resolve such stagnation issues, we develop a robust supervisory control policy to synthesize a robust liveness-enforcing supervisor for AMSs with assembly operations and unreliable resources. The supervisor can guarantee that a controlled system continues to progress without deadlock and blocking states even if some unreliable resources fail to work. [ABSTRACT FROM AUTHOR]

Deadlock is a rather undesirable case in automated manufacturing systems (AMSs). The appearance of deadlock can cause the partial or total stagnation of a system. So far, a large number of deadlock control policies have been developed; nevertheless, the majority are dependent on the assumption that allocated resources cannot break down. In the real world, an AMS consists of a set of concurrent production routes that share and compete for a limited number of resources, such as automated material/component handling devices, buffers, robots, and machines. Resource failures occur unexpectedly. If reasonable control does not exist, a simple resource failure can lead an entire system to stagnation, which can cause enormous economic loss. Therefore, researchers have gradually paid attention to AMSs allowing resource failures in recent years. In this paper, we focus on reviewing and comparing various robust supervisory control policies from the perspective of their structural complexity, behavioral permissiveness, and computational complexity. Some potential future directions are explored. This paper provides a reference source of robust supervisory control of AMSs for researchers and practitioners in this area. Note to Practitioners—In automated manufacturing systems (AMSs), resource failures are common. Their occurrences can lead a system to stagnation, which can cause unnecessary downtime and bring vast economic loss for enterprises. To resolve such stagnation issues, a great number of robust supervisory control policies have been proposed for AMSs with unreliable resources. These policies guarantee that a controlled system can continue to progress without deadlock and blocking states even if some unreliable resources fail to work. By a thorough review of existing robust supervisory control policies for AMSs with unreliable resources, this paper compares and analyzes these policies in terms of their structural complexity, behavioral permissiveness, and computational complexity. The goal of this paper is to provide a reference source in the area to help researchers and practitioners choose a suitable method for solving industrial application problems that are subject to resource failures. [ABSTRACT FROM AUTHOR]

The paper presents an approach to the control of black-box embedded systems by integrating automaton learning and supervisory control theory (SCT) of discrete-event systems (DES), where automaton models of both the system and requirements are unavailable or hard to obtain. First, the system is tested against the requirements. If all the requirements are satisfied, no supervisor is needed and the process terminates. Otherwise, a supervisor is synthesized to enforce the system to satisfy the requirements. To apply SCT and automaton learning technologies efficiently, the system is abstracted to be a finite-discrete model. Then, a $C^{*}$ learning algorithm is proposed based on the classical $L^{*}$ algorithm to infer a Moore automaton describing both the behavior of the system and the conjunctive behavior of the system and the requirements. Subsequently, a supervisor for the system is derived from the learned Moore automaton and patched on the system. Finally, the controlled system is tested again to check the correctness of the supervisor. If the requirements are still not satisfied, a larger Moore automaton is learned and a refined supervisor is synthesized. The whole process iterates until the requirements hold in the controlled system. The effectiveness of the proposed approach is manifested through two realistic case studies. Note to Practitioners—Supervisory control theory of DES can synthesize maximally permissive supervisory controllers to ensure the correctness of software-controlled processes. The application of supervisory control theory relies on automaton models of the plant and specifications; however, the required models are often unavailable and difficult to obtain for black-box embedded systems. Automaton learning is an effective method for inferring models of black-box systems. This paper integrates the two technologies so that the supervisory control theory is applicable to the development of black-box embedded software systems. The proposed approach is implemented in a toolchain that connects automaton learning algorithms, SCT, and testing algorithms via scripts. The obtained supervisor is implemented as a software patch to monitor and control the original system online. [ABSTRACT FROM AUTHOR]

Supervisory control theory (SCT) of a discrete-event system (DES) is well developed to find its maximally permissive supervisor. As an extension of SCT, a new framework, state-tree structures (STS), has been deployed to manage the state explosion problem of SCT. The supervisory control with partial observation is investigated in SCT, of which the state explosion issue remains to be explored. This paper dwells upon an approach to the synthesis of supervisory control with partial observation in the normal STS framework, requiring that the conjunction of any two projected subpredicates should be false. First, following the definition of the observability based on STS, it is proven that there does not exist the supremal observable subpredicate. Second, we construct a subclass of observable subpredicates of a given predicate (obtained as a specification) on the basis of normal STS. Third, a largest element is proven to exist in the subclass, and thus a weakly controllable, coreachable, and observable subpredicate is computed to solve the supervisory control problem of the normal STS by an iterative algorithm. An illustrative example with state size over 109 is given to show that the proposed algorithm based on STS is superior to the approach based on SCT, which leads to the program crashes in SCT. Note to Practitioners—DES is a collection of many contemporary computer-integrated industrial and social service systems. For the sake of technology or cost considerations, the occurrences of some events are not fully observed, rendering the supervisory control algorithmically complicated and exacerbating the originally notorious state explosion problem. This paper aims to ameliorate the state explosion problem using a novel formalism, namely, state-tree structures, that can be applied to real-world systems thanks to the computational efficiency that is demonstrated by an industrial system. Compared with the traditional SCT of DES, the significance of the proposed methodology will intrigue academic researchers and industrial practitioners. [ABSTRACT FROM AUTHOR]

A fundamental requirement of the supervisory control theory (SCT) of discrete-event systems is a finite automaton model of the plant. The requirement does not hold for black-box systems whose source code and logical model are not accessible. To apply SCT to black-box systems, we integrate automaton learning technology with SCT and apply the new method to improve the requirements conformance of software reuse. If the reused software component does not satisfy a requirement, the method adds a supervisor component to prevent the black-box system from reaching “faulty sections.” The method employs learning-based testing (LBT) to verify whether the reused software meets all requirements in the new context. LBT generates a large number of test cases and iteratively constructs an automaton model of the system under test. If the system fails the test, the learned model is applied as the plant model for control synthesis using SCT. Then, the supervisor is implemented as an executable program to monitor and control the system to follow the requirement. Finally, the integrated system, including the supervisory program and the reused component, is tested by LBT to assure the satisfiability of the requirement. This paper makes two contributions. First, we innovatively integrate LBT and SCT for the control synthesis of black-box reactive systems. Second, software component reuse is still possible even if it does not satisfy user requirements at the outset.

Note to Practitioners—In black-box software reuse, if a component does not satisfy user requirements in a new context, the developer has to abandon it and develop a new one, which is costly. The proposed method enables software reuse for black-box reactive systems by combining learning-based testing (LBT) and supervisory control theory (SCT). LBT can test whether the requirements hold in new settings and infer hypothesis models of the component at the same time. If the component does not pass the test, the learned hypothesis is used as a plant model to compute a supervisor using SCT. Then, a supervisory program is developed according to the control actions of the supervisor to govern the system to follow the behavior of the requirements. We illustrate the proposed method through an example of a simple cruise control module. The effectiveness of the new method is demonstrated with a larger software component brake-by-wire with floating point data types. The case studies show not only the methodology of the new approach but also a working tool chain to perform it. [ABSTRACT FROM PUBLISHER]

It becomes more and more critical for manufacturing enterprises to improve energy efficiency because of the escalating energy prices, increasing global competitions, and more rigorous government regulations. In this paper, a systematic method is developed to improve the energy efficiency of a multistage manufacturing system through production control. The method aims at reducing energy consumption with minimal negative impact on production. We start from the analysis of system dynamics and develop quantitative methods to estimate energy saving opportunities. A supervisory control algorithm is developed to improve system energy efficiency by periodically taking the saving opportunities. Simulation case studies are performed to validate the effectiveness of the control algorithm.

Note to Practitioners—Manufacturing systems are facing increasing pressure to reduce energy consumption, as global competition, sustainability, and green processes are becoming more prevalent. Although most of the research efforts on manufacturing energy saving have focused on developing individual energy efficient machines, it can be more cost-effective to improve energy efficiency through better control of the energy usage of the whole production system. Therefore, this paper presents a systematic method to improve system energy efficiency with a minimal negative impact on production. This paper continues the work by Chang et al. by extending the scope of energy saving opportunity theory from serial production systems to general serial–parallel production systems. It also develops analytical methods based on Markov chain models to estimate the energy saving opportunity accurately. [ABSTRACT FROM AUTHOR]

While the supervisory control (SC) problem of (maximally permissive) deadlock avoidance for sequential resource allocation systems (RASs) has been extensively studied in the literature, the corresponding results that are able to address potential resource outages are quite limited, both, in terms of their volume and their control capability. This paper leverages the recently developed SC theory for switched discrete event systems (s-DES) in order to provide a novel systematic treatment of this more complicated version of the RAS deadlock avoidance problem. Following the modeling paradigm of s-DES, both the operation of the considered RAS and the corresponding maximally permissive SC policy are decomposed over a number of operational modes that are defined by the running sets of the failing resources. In particular, the target supervisor must be decomposed to a set of “localized predicates,” where each predicate is associated with one of the operational modes. A significant part, and a primary contribution, of this paper concerns the development of these localized predicates that will enable the formal characterization and the effective computation of the sought supervisor. With these predicates available, a distributed representation for the sought supervisor that is appropriate for real-time implementation is eventually obtained through an adaptation of the relevant distributed algorithm that is provided by the current s-DES SC theory. Note to Practitioners—This paper extends the existing theory of deadlock avoidance for buffer-space allocation in flexibly automated production systems so that it accounts for disruptive effects due to potential temporary outages of some of the system servers. The set of the failing servers at any time instant defines the corresponding operational mode for the underlying resource allocation system. The primary problem that is addressed by this paper is the synthesis of a resource allocation policy that will ensure the ability of all process instances that do not require the failing resources in a particular mode, to execute repetitively and complete successfully while the system remains in that mode. In line with some past literature on this problem, we call the corresponding supervisory control problem as “robust deadlock avoidance,” and we leverage results from the recently emerged theory for modeling and control of switched discrete event systems in order to characterize and compute a maximally permissive solution for it. [ABSTRACT FROM AUTHOR]

For distributed discrete-event systems (DESs), which are specified by a set of coupled automata, the centralized synthesis for a composed plant model is often undesired due to a high computational effort and the need to subsequently split the result into local controllers. This paper proposes modeling and synthesis procedures to obtain optimal decentralized controllers in state-feedback form for distributed DES. In particular, this paper addresses the DES with priority structures, in which subsystems with high priorities are supplied with the output of subsystems with lower priority. If the subsystem dependencies have linear or treelike structures, the synthesis of the subsystem controllers can be accomplished separately. Any local controller is computed by algebraic computations, it communicates with controllers of adjacent subsystems, and it aims at transferring the corresponding subsystem into goal states with a minimal sum of transfer costs. As is shown for an example, the computational effort can be significantly reduced compared with the synthesis of centralized controllers following the composition of all subsystem models. [ABSTRACT FROM AUTHOR]

The Ramadge–Wonham supervisory control paradigm has been shown effective in dealing with logic control. Nevertheless, time-related performance is always one of the major concerns in industry. Current methods for synthesizing time optimal supervisors are incapable of dealing with large discrete-event systems (DESs) with massive state spaces. This paper proposes an approach for finding a time optimal accepting trace for large DESs based upon sequential language projection, and pruning. The algorithms are tested on a linear cluster tool to show their effectiveness. [ABSTRACT FROM AUTHOR]

This work considers the optimal scheduling problem for a campus central plant equipped with a bank of multiple electrical chillers and a thermal energy storage (TES). Typically, the chillers are operated in ON/OFF modes to charge TES and supply chilled water to satisfy the campus cooling demands. A bilinear model is established to describe the system dynamics of the central plant. A model predictive control (MPC) problem is formulated to obtain optimal set-points to satisfy the campus cooling demands and minimize daily electricity cost. At each time step, the MPC problem is represented as a large-scale mixed-integer nonlinear programming problem. We propose a heuristic algorithm to obtain suboptimal solutions for it via dynamic programming (DP) and mixed integer linear programming (MILP). The system dynamics is linearized along the simulated trajectories of the system. The optimal TES operation profile is obtained by solving a DP problem at every horizon, and the optimal chiller operations are obtained by solving an MILP problem at every time step with a fixed TES operation profile. Simulation results show desired performance and computational tractability of the proposed algorithm. [ABSTRACT FROM PUBLISHER]

Supervisory control is usually considered as an external control mechanism to a system by controlling the occurrences of its controllable events. There exist Petri net models whose legal reachability spaces are nonconvex. In this case, they cannot be optimally controlled by the conjunctions of linear constraints. For Petri net models of flexible manufacturing systems, this work proposes a method to classify the legal markings into several subsets. Each subset is associated with a linear constraint that can forbid all first-met bad markings. Then, the disjunctions of the obtained constraints can make all legal markings reachable and forbid all first-met bad markings, i.e., the controlled net is live and maximally permissive. An integer linear programming model is formulated to minimize the number of the constraints. A supervisory structure is also proposed to implement the disjunctions of the constraints. Finally, examples are provided to illustrate the proposed method. [ABSTRACT FROM AUTHOR]

A generic state-vector transition (SVT) model is suggested, including a flexible synchronous composition involving both shared variables and events. This model is analyzed, focusing on properties that are important for supervisor synthesis. A synthesis procedure is then developed for the SVT model, where supervisor guards are generated that guarantee a controllable, nonblocking and maximally permissive supervisor. Novel conditions are introduced, such that more flexible specifications can be applied than earlier suggested for related models. Since the SVT model includes automata and (colored) Petri nets, optionally extended with variables, guards and actions, as special cases, the suggested synthesis approach unifies supervisor synthesis for the main discrete event model classes. Finally, the SVT model is naturally represented and efficiently computed based on binary decision diagrams, and the resulting supervisor guards are easily implemented in industrial control systems. [ABSTRACT FROM PUBLISHER]

In this paper, we present a case-study on application of Ramadge-Wonham supervisory control theory (abbreviated by SCT in the sequel) to a patient support system of a magnetic resonance imaging (MRI) scanner. We discuss the whole developmental cycle, starting from the mathematical models of the uncontrolled system and of the control requirements, and ending with the implementation of the obtained controller on the actual hardware. The obtained controller was tested on the physical system. In this case study, we attempted to build the models in a modular way, in order to decrease the computational complexity of the controller synthesis and to improve the adaptability of the models. An important advantage of SCT is that it allows automatic generation of the controller, and that it can thus improve adaptability of the control software. We also briefly discuss our experience on the adaptability of the control software, obtained in the course of this case study. [ABSTRACT FROM PUBLISHER]

This paper considers fault-tolerant control that ensures the safety of a discrete-event system. We consider multiple faulty modes. Each faulty mode is modeled by an automaton. These automata, together with the automaton modeling normal mode, describe a discrete-event system with faults. Each faulty mode has some illegal states that must be avoided by control so that the fault can be tolerated. We assume that fault-tolerant control takes actions (disablements) only when the occurrence of a fault is certain. We consider cases of both full event observation and partial event observation. We derive necessary and sufficient conditions for the existence of fault-tolerant control. We also provide formulas and algorithms to calculate control actions if the necessary and sufficient conditions are satisfied. Both offline control synthesis (for full event observation) and online control synthesis (for partial event observation) are investigated. We allow multiple faults as well as single faults. [ABSTRACT FROM PUBLISHER]

In the framework of automated manufacturing systems (AMS), Petri nets are widely used to model, analyze, and control them. Resolving deadlocks is of paramount significance because their emergence may likely zero a systems throughput, if not necessarily. Supervisory control technique is the most widely adopted method to resolve them. A control policy can be converted into satisfying a set of inequalities, each of which corresponds to a siphon in a Petri net structure. The number of siphons can be exponential in the worst case, so does the number of inequalities. Taking into account the independent and dependent inequalities, this paper proposes a method to remove all the dependent inequalities, while preserving only the independent ones. This method can significantly reduce the size of a supervisory controller. Examples are presented to illustrate the effectiveness and efficiency of this method. [ABSTRACT FROM PUBLISHER]

In this paper, we symbolically represent timed discrete-event systems (TDES), which can be used to efficiently compute the supervisor in the supervisory control theory context. We model a TDES based on timed extended finite automata (TEFAs): an augmentation of extended finite automata (EFAs) by incorporating discrete time into the model. EFAs are ordinary automata extended with discrete variables, where conditional expressions and update functions can be attached to the transitions. The symbolic computations are based on binary decision diagrams (BDDs). We show how TEFAs can be represented by BDDs. The main feature of this approach is that the BDD-based fixed point computations are not based on tick models that have been commonly used in this area, leading to better performance in many cases. The approach has been implemented and applied to a simple case study and several large-scale benchmarks. [ABSTRACT FROM PUBLISHER]

If there are transitions in a Petri net (PN) that cannot be prevented from firing by a supervisory policy, then we have a partially controlled PN. The existence of a liveness enforcing supervisory policy (LESP) in a partially controlled ordinary PN is undecidable. Consequently, there can be no algorithms that synthesize an LESP for an arbitrary ordinary (general) PN. In contrast, we identify a class of general free-choice PN (FCPN) structures, which strictly includes the class of ordinary FCPN structures, where the existence of an LESP in any marked member of the class is decidable. [ABSTRACT FROM AUTHOR]

Sensors and actuators are two indispensable parts in the paradigm of feedback control. Their implementation cost should be properly evaluated and constrained. In the previous work, a Petri net monitor with the least cost is synthesized through integer programming formulation. Despite its technical correctness, the existing method may lead to undesirable results when the net structure contains some shared or unshared resource places of a manufacturing-oriented net model. A necessary and sufficient condition is established to show that certain structures can lead to deadlock-prone supervisors. An efficient algorithm is developed to identify such structures. Furthermore, it is shown that if one can identify such structures at the initial stage, it is possible to achieve desirable controllers for the original systems. The theoretical correctness of the proposed algorithm is discussed. A manufacturing example is provided to illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

Kumar and Takai have proposed an architecture for the decentralized prognosis of discrete-event systems (DES), where several local prognosers cooperate to predict failures in a DES. In this paper, we first present the proposition (Kumar and Takai, “Decentralized prognosis of failures in discrete event systems,” IEEE Trans. Autom. Control, vol. 55, no. 1, pp. 48–59, Jan. 2010) as a disjunctive architecture, and then we develop a conjunctive architecture which is dual and complementary to the disjunctive one. We also propose a mixed architecture that combines and generalizes the disjunctive and conjunctive architectures. We finally show that our work can be easily extended to predict a failure at least k steps before its occurrence, for a given k\geq 1. [ABSTRACT FROM PUBLISHER]

This paper establishes modular and hierarchical supervisory control theories of Fuzzy Discrete-Event Systems (FDES). It aims to resolve the horizontal and vertical complexities present in large-scale event-driven systems, which are affected by uncertainties in their event and state representations. The modular supervisory control architecture composed of a set of noncommunicating local supervisors, in which one supervisor is assigned for each module having its own sensing and acting capabilities. The notion of separability for languages in FDES is introduced and the property of a language specification of FDES, termed as separably-controllable-observability, is proposed to determine the existence of modular supervisors to the control problem. The hierarchical supervisory control architecture consists of multilevel supervisors assigned to detailed low-level and abstract high-level models of the plant. The notion of output-control-consistency is introduced for languages in FDES. Then, the property called strictly-output-control-consistency is defined for FDES in order to maintain the hierarchical consistency between low-level and high-level FDES modules. The property of H-fuzzy observability is introduced to ensure the hierarchical consistency under the partial observation of low-level FDES. Finally, using the established hierarchical supervisory control theory of FDES, a behavior-based mobile robot navigation example is discussed. [ABSTRACT FROM PUBLISHER]

This paper presents new results on the formal design of distributed coordinating agents in a discrete-event framework. In this framework, agents are modeled to be individually equipped with a coordination module, through which they interact and communicate. In terms of existing control-theoretic concepts, we first define the concept of a coordinable language and show that it is the necessary and sufficient existence condition of coordination modules for distributed agents to achieve conformance to a prespecified interagent constraint language. Following, we present a synthesis algorithm to compute near-optimal coordination modules. An example is provided to illustrate the design synthesis using the proposed algorithm. Finally, a discussion with related work distinguishes our coordination design problem from related problems in the literature. [ABSTRACT FROM PUBLISHER]

Past works towards the effective deployment of the maximally permissive liveness-enforcing supervisor (LES) for sequential resource allocation systems (RAS) have been stalled by: (i) the NP-Hardness of the computation of this policy for the majority of the considered RAS classes and (ii) the inability of the adopted more compact representations of the underlying RAS dynamics to provide an effective representation of the target policy for all RAS instantiations. This paper proposes a novel approach to the aforementioned problem, that can be perceived as a two-stage process: The first stage computes the maximally permissive LES by employing an automaton-based representation of the RAS behavior and techniques borrowed from the Ramadge & Wonham (R&W) Supervisory Control framework. The second stage seeks the development of a more compact representation for the dichotomy into admissible and inadmissible—or “safe” and “unsafe”—subspaces of the RAS state space, that is effected by the LES developed in the first stage. This compact representation is obtained by: (i) taking advantage of certain properties of the underlying subspaces and (ii) the employment of pertinent data structures. The resulting approach is also “complete,” i.e., it will return an effectively implementable LES for any given RAS instantiation. Numerical experimentation demonstrates the efficacy of the approach and establishes its ability to support the deployment of maximally permissive LES for RAS with very large structure and state spaces. [ABSTRACT FROM AUTHOR]

For automated manufacturing systems (AMSs), deadlock resolution in terms of Petri nets remains an attractive topic to which many approaches are dedicated. However, few of them can quantitatively optimize certain indices during their supervisor synthesis process. This causes unnecessary control limitations and often leads to high implementation cost. In the framework of Petri nets, this paper proposes a method to synthesize a cost-effective supervisor with the aid of a set of mathematical programming formulations. Along the same vein, we also show some results by investigating timed Petri nets, which can be utilized to make a good tradeoff between implementation cost and system cycle time. Examples are used to validate the effectiveness of our result. [ABSTRACT FROM AUTHOR]

In the supervisory control theory, a supervisor is generated based on given plant and specification models. The supervisor restricts the plant in order to fulfill the specifications. A problem that is typically encountered in industrial applications is that the resulting supervisor is not easily comprehensible for the users. To tackle this problem, we introduce an efficient method to characterize a supervisor by tractable logic conditions, referred to as guards, generated from the models. The guards express under which conditions an event is allowed to occur to fulfill the specifications. To obtain tractable guard expressions, we reduce them by exploiting the structure of the given models. In order to be able to handle complex systems efficiently, the models are symbolically represented by binary decision diagrams and all computations are performed on these data structures. The algorithms have been implemented in a supervisory control tool and applied to an industrially relevant example. [ABSTRACT FROM AUTHOR]

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 FROM PUBLISHER]

In the context of automated manufacturing, this work proposes a new special class of timed Petri nets, namely, Timed ratio-enforced Augmented Marked Graph (TAMG) and its low-cost and high-performance supervisor synthesis methodology. A supervisor is composed of a set of control places (monitors), each of which is easy to be algebraically specified by a generalized mutual exclusion constraint (GMEC) to prevent certain siphons from being undermarked. In order to make a good tradeoff between the supervisor implementation cost and system performance, a mixed integer programming (MIP) approach is formulated to synthesize the monitors. An example is used to validate the effectiveness and efficiency of the proposed method. The results show that the proposed method remarkably outperforms any existing ones. [ABSTRACT FROM PUBLISHER]

For practical automated manufacturing systems (AMSs), the time dimension is of great significance and should be integrated in their plant models. Reasonably, many of the realistic general mutual exclusion constraints (GMECs) imposed on these discrete models should be timed rather than merely algebraic or logic. In the past, such a problem was studied on the basis of the Ramadge-Wonham supervisory control technique (SCT) and the theory of regions. It proves to be NP-hard since it necessitates the generation of reachability graphs. This paper shows that it can be solvable in polynomial time by using generalized linear constraints, which are originally proposed to increase the expressive power of the linear marking constraints. By dividing each constraint into marking, firing vector, and Parikh terms, its respective control place can be synthesized algebraically without considering the separation of dangerous states and events. Several examples are used to validate the effectiveness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

We study the decentralized control of discrete-event systems with multiple local 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. [ABSTRACT FROM AUTHOR]

Generalized algebraic deadlock avoidance policies (DAPs) for sequential resource allocation systems (RASs) have recently been proposed as an interesting extension of the class of algebraic DAPs, that maintains the analytical representation and computational simplicity of the latter, while it guarantees completeness with respect to the maximally permissive DAP. The authors' original work that introduced these policies also provided a design methodology for them, but this methodology is limited by the fact that it necessitates the deployment of the entire state space of the considered RAS. Hence, this paper seeks the development of an alternative computational tool that can support the synthesis of correct generalized algebraic DAPs, while controlling the underlying computational complexity. More specifically, the presented correctness verification test possesses the convenient form of a mixed integer programming (MIP) formulation that employs a number of variables and constraints polynomially related to the size of the underlying RAS, and it can be readily solved through canned optimization software. Furthermore, since generalized algebraic DAPs do not admit a convenient representation in the Petri net modeling framework, an additional contribution of the presented results is that they effect the migration of the relevant past insights and developments with respect to simpler DAP classes, from the representational framework of Petri nets to that of the Deterministic Finite-State Automata. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the problem of modeling railway networks with Petri nets so as to apply the theory of supervisory control for discrete event systems to automatically design the system controller. We provide a modular representation of railway networks in terms of stations and tracks including sensors and semaphores. We first ensure safeness and local liveness imposing both generalized mutual exclusion constraints and constraints also involving the firing vector. The detailed model used in this first step can be abstracted, considering a higher level description of a railway network that belongs to the class of ES² PR (extended simple sequential process with resources) nets and show that global liveness may be enforced by adding appropriate monitor places designed using siphon analysis. In our approach, this can be done without an exhaustive computation of all siphons and we can, characterize the cases in which the procedure can be recursively applied, giving a simple test for closed-loop net to remain an ES² PR net. [ABSTRACT FROM AUTHOR]

This paper defines a reconfiguration method for the class of discrete-event systems (DES) that is subject to linear constraints as their control specifications. Some existing methods for enforcing these constraints make use of Petri-net P-invariants for controller synthesis. These methods are quite appealing because their computational complexity is much more tractable than most other methods for controller synthesis. However, a common limitation of all existing P-invariant-based control architectures for DES plants is the assumption that the linear constraints defining the control specification of the plant do not change over time. Here, we relax this assumption and allow the control specifications to change during controller runtime. Under certain assumptions on DES behavior, we automatically reconfigure the DES controller after the control specification is changed. In addition, if the current state of the controlled DES has become infeasible under the new control specification, we automatically generate a so-called plant reconfiguration procedure whose execution leads the system back to a feasible state. This reconfiguration procedure is optimal in that it seeks to minimize the cost of reconfiguration actions through an Integer Programming (IP) model. The objective function of the IP model can be used to generate reconfiguration solutions that meet some desired properties. Depending on the cost of each reconfiguration action, a minimum cost reconfiguration solution may use only actions contained in the current plant configuration (an internal response), or ask for a change in the plant configuration, for instance, by adding new resources (an external response), or a combination of both strategies. Finally, we illustrate our method by applying it to a hospital control system example. Note to Practitioners—This paper proposes a dynamic reconfiguration framework that can revise the operations of systems whose control requirements change over time. The proposed framework can be applied to systems that satisfy the following two assumptions. First, the behavior of the system under study is described in terms of a set of discrete states and events. Events will cause the system to transition between states. Second, the control requirements must be expressed by linear equalities and inequalities on the system states. Under these circumstances, the proposed framework can identify an optimal transition to a new control policy that satisfies the new control requirements. Moreover, the system under consideration will continue operating while this transition is taking place. One application of this method is in modifying hospital control strategies when a hospital experiences unexpected events. In this case, the hospital operations-such as patient handling, resource assignment, and procedure scheduling-can be represented by discrete state models (e.g., Petri nets). Constraints on these operations can be modeled by linear inequalities on hospital and patient state. Upon a change in the constraints, the proposed reconfiguration method revises the hospital control strategies. For example, a shift in the hospital service demands (e.g., an increase in the flow of patients to the hospital due to a mass casualty situation) can be translated to changes in the constraints. In this case, the hospital operations must be revised to accommodate the new constraints without disrupting the operation of the hospital. The reconfiguration method of this paper provides a framework for modeling the reconfiguration steps and for calculating the least cost reconfiguration solution. [ABSTRACT FROM AUTHOR]

This paper considers a matrix-based discrete event control approach for a warehouse. The control system is organized in two modules: a dynamic model and a controller. The model provides a complete description of the discrete event dynamics of the warehouse, and is used as a means to track the stock-keeping units, and identify and inhibit control actions that violate system's constraints. The controller has several functions. At the supervisory level, it is in charge of inhibiting operations that may lead to deadlocks, commanding the actual start of the task, and the release of the resources once a task is completed. At the operational level, it is in charge of performing decisions regarding the order in which allowable tasks waiting for service should be performed. All the modules are implemented using the same matrix-based formalism, and thus integrated with each other. The main advantages of the approach are the inherent modularity (the matrix-based control is obtained by assembling individual atomic components), and the integration between the various modules, which permits a better overall resource utilization. Simulation examples describing an actual industrial warehouse are finally provided to emphasize the main advantages of the proposed approach. Note to Practitioners—This paper illustrates the application of a discrete-event modeling and control framework based on a matrix notation to an automated warehouse. The material handling equipment must continuously transfer stock-keeping units between various buffers using a network of interconnected rail guided vehicles. Since transfer requests are issued at random times, the role of the control system is extremely challenging, as it must handle low level tasks (synchronizing hardware, avoiding conflicts) and high level ones (allocating the rail guided vehicles efficiently to avoid congestions and long service times). Giving a complete mathematical characterization of such a system is challenging, due to its inherently turbulent and discrete-event nature. The proposed original approach allows one to attack the problem from a modular, divide-and-conquer perspective. In fact, the complete model of the system is achieved by a sequence of simple modeling steps, starting from the description of the atomic components of the system, and progressively specifying constraints, objectives and control rules to obtain a complete characterization of the entire system within a unified formalism based on binary matrices. Since the final model integrates supervisory and operational functions, it permits to perform the allocation of rail guided vehicles more effectively, using information that is generally unavailable to the dispatching modules. Examples and numerical results based on the equipment actually operating in the warehouse are also provided to illustrate the potential of the approach. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes a correct and complete translation algorithm that converts a class of propositional linear-time temporal-logic (PTL) formulae to deterministic finite (-trace) automata. The translation algorithm is proposed as a specification interface for finitary control design of discrete-event systems (DESs). While there has been a lot of computer science research that connects PTL formulae to ω-automata, there is relatively little prior work that translates state-based PTL formulae in the context of a finite-state DES model, to event-based finite automata—the formalism on which well-established control synthesis methods exist. The proposed translation allows control requirements to be more easily described and understood in temporal logic, widely recognized as a useful specification language for its intuitively appealing operators that provide the natural-language expressiveness and readability needed to express and ex- plain these requirements. Adding such a translation interface could therefore effectively combine specifiability and readability in temporal logic with prescriptiveness and computability in finite automata. The former temporal-logic features support specification while the latter automata features support the prescription of DES dynamics and algorithmic computations. A practical implementation of the interface has been developed, providing an enabling technology for writing readable control specifications in PTL that it translates for discrete-event control synthesis in deterministic finite automata. Two application examples illustrate the use of the proposed temporal-logic interface. Practical implications of the complexity of the translation algorithm are discussed. [ABSTRACT FROM AUTHOR]

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 CTL* 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]