462 research outputs found
Fault diagnosis of manufacturing systems using finite state machines
No full textThis chapter presents the salient features of a general methodology for fault diagnosis in partially observed finite-state automata and its application to automated manufacturing systems. The system of interest is modeled as a set of interacting automata coupled by common events. The total event set comprises observable and unobservable events, reflecting the set of sensors attached to the manufacturing system. Fault events are inherently unobservable and the diagnostic task is to infer their occurrence from the sequences of observable events and the system model. On-line diagnosis is performed using diagnoser automata, that are constructed from the system model. The analysis of the diagnosability properties of the system is done off-line using verifier automata, also constructed from the system model. The algorithms presented are illustrated with relevant examples. The chapter concludes with a discussion of sensor selection for diagnosability and of cooperative diagnosis for systems with decentralized information
Supervisory control for collision avoidance in vehicular networks with imperfect measurements
No full textSupervisory control for collision avoidance in vehicular networks using discrete event abstractions
No full textWe consider the problem of collision avoidance at vehicular intersections for a set of controlled and uncontrolled vehicles that are linked by wireless communication. Each vehicle is modeled by a first order system. We use a disturbance to account for bounded model uncertainty. We construct a discrete event system abstraction and formulate the problem in the context of supervisory control for discrete event systems with uncontrollable events. This allows us to mitigate computational limitations related to the presence of continuous dynamics and infinite state spaces. For solving the resulting supervisory control problem at the discrete event level, we develop an algorithm that exploits the structure of the transition map to compute the supremal controllable sublanguage more efficiently than standard algorithms. We present implementation results on an intersection with several vehicles.National Science Foundation (U.S.) (Grant CNS-0930081
Stephane Mallarme: A synthesis of romanticism and parnassianism, 1970
No full textThe purpose of this paper is to analyse works of Stephane Mallarme, father of Symbolism, pointing out romantic and parnassian elements. Symbolism, like Romanticism, attempted to express the interior thoughts of man. The symbolist movement then, was not only a revolt against Parnassianism but also a return to Romanticism. On the other hand, one would not be incorrect in saying that Romanticism reached its culmination in the works of the symbolists poets. For this reason, an attempt will be made to show that the works of Mallarme, father of Symbolism, can be considered as a synthesis of Romanticism and Parnassianism. This thesis contains three chapters. The first chapter is devoted to a discussion of Romanticism and of Parnassianism. Special attention is given to the origin, development, characteristics and influences of each school. The relationship of one School with the other is also pointed out. The second chapter consists of a biographical sketch of Stephane Mallarme. Special emphasis is placed on factors and events in his life which may have influenced or determined the elements of Romanticism and Parnassianism in his poetry. The third chapter is devoted to an analysis of some of the poems of Stephane Mallarme", "Les Fenetres," V Apparition," "L'Azur," "Toast Funebre," "Le Vierge," "L'Apres-Midi d'un Faune." In these analyses special attention is given to the romantic and parnassian tendencies of the poems. Since these romantic-parnaassian elements occur frequently throughout his works, it has been concluded that Mallarme's poetry can be considered as a synthesis of the two poetic schools
Artifact for Paper: On tolerance of discrete systems with respect to transition perturbations
No full textThis is an artifact supplemented with the TACAS 2022 submission Romulo Meira-Goes, Eunsuk Kang, Stephane Lafortune, and Stavros Tripakis: **On tolerance of discrete systems with respect to transition perturbations**. This is a prototype implementation of the tolerance tool. The implementation assumes the user should provide the system modeled as an LTS, a controller, and an invariance property. The tool automatically computes the tolerance of the given controller. Moreover, the tool can also synthesize the most tolerant, the least tolerant, and the controller that achieves a given minimum threshold of tolerance.
The source code for the tool is included as well as the necessary libraries for compiling it. Additionally, this artifact contains the means to reproduce the experimental results from the paper
Modeling and on-line control of software/hardware systems.
No full textStatistics show that the cost of control software for computer-integrated manufacturing systems and other discrete-event systems is on the rise. Some of the important reasons behind these facts are: non-reusability and inflexibility. In prior work, we developed a methodology for designing control software that overcomes the above problems. It is based on assemblages of software/hardware components, formal models, and generic controllers. Rule-based models are used for specification purposes, and event-based models are used for control purposes. Generic controllers compute the control policy on-line, while allowing for changes in the models. This thesis expands the above concepts. First, a mechanism for "assembling" rule-based models is provided: Models of assembly components are given in terms of constituents' models, thus reducing the specification effort. Second, the supervisory control strategy of Ramadge and Wonham is adopted. Given an event-based model of the system, its behavior is restricted within a given specification under the presence of "uncontrollable" and "unobservable" events. We develop and formally study an on-line supervisory control scheme which avoids the pitfalls of off-line methods. This scheme involves three main algorithms. The first, VLP-S, assumes "total" behavior observation and efficiently generates the optimal behavior (the supremal controllable sublanguage of the specification). The second algorithm, VLP-PO, assumes only partial behavior observation. Under this condition, an optimal solution (a supremal) may not exist and off-line computations involve exponential complexities. Using a priority scheme, VLP-PO generates maximal observable and controllable sublanguages with a linear on-line computational effort. By varying the event priorities, different maximals and maximals containing the supremal controllable and normal sublanguage (a benchmark) can be generated. The third, DI-VLP-PO, a distributed version of VLP-PO, computes the control action on-line using several communicating agents. This reduces the computational effort by orders of magnitude, and with reasonable communication bounds. If the system has special structure, DI-VLP-PO recovers the policies of its sequential counterpart. Extensions of the algorithms to allow for "limited-lookahead", where only partial models are available, are provided (to handle infinite systems and time-constrained computation).PhDComputer Information and Control EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/104308/1/9513368.pdfDescription of 9513368.pdf : Restricted to UM users only
Control of discrete event systems using limited lookahead policies.
No full textThis thesis proposes a new supervisory control scheme for discrete event systems, termed Supervisory Control using Limited Lookahead Policies (LLP), which is capable of addressing some of the most complicated working conditions in supervisory control: the system to be controlled is time-varying, the construction of an automaton recognizer for the legal constraint is difficult, and the state space is too large for conventional approaches. Instead of attempting to calculate off-line the complete control policy for the entire set of possible behaviors of the process, we consider an on-line scheme where after the occurrence of an event, the next control action is determined on the basis of an N-step ahead projection of the behavior of the process; uncertainty beyond this lookahead window is resolved by either a conservative or an optimistic attitude. This procedure then repeats after the execution of the next event. We address two fundamental issues concerning this control scheme: the resultant system behavior and the associated on-line calculations. In characterizing the system behavior, we present a precise formulation of the LLP operational mechanism and, in addition, results pertaining to: monotonicity and convergence properties of the optimistic and conservative N-step policies in terms of N, and comparison of the on-line system behavior with the optimal off-line solution, including lower bounds for N that guarantee that these two are equal. To facilitate the on-line control calculations, we reformulate the problem of finding the supremal controllable sublanguage in the context of LLP as a finite horizon optimal control problem, which helps to reveal the generic two-nested recursive structure inherent in general LLP control schemes: step-to-step and level-to-level recursiveness. Subsequently, we are able to recognize and accordingly to take advantage of (i) the structural similarity between successive windows, and (ii) the fact that not all traces in the window contribute to the control actions, in order to substantially reduce the required on-line calculations. To demonstrate its feasibility in solving general on-line supervisory control problems, the LLP scheme is applied to a complicated time-varying system that would be considered computationally intractable by conventional approaches.PhDElectrical Engineering: SystemsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/103055/1/9303718.pdfDescription of 9303718.pdf : Restricted to UM users only
Query optimization by intelligent search.
No full textQuery optimization is a crucial part in relational database management systems because it can make a significant improvement in the overall performance of these systems. As the need for relational database management systems to handle larger amounts of data and more complex queries increases, it is of paramount importance that an optimal and efficient solution is found to answer a given query. Traditionally, dynamic programming or exhaustive search has been used to guarantee optimality, but these approaches are not effective for complex queries with large search spaces. In this dissertation, we investigate the problem of finding an optimal solution to the query optimization problem without having to search all the possibilities. The savings result from the idea of intelligently predicting future processing costs. Specifically, four query optimization problems are addressed: query optimization by semijoins, join query optimization, multiple query optimization, and query optimization for fragmented databases. For each problem, a new query optimization method is developed in light of the goal of enhancing the search efficiency while preserving optimality. Simulation experiments are carried out to show that substantial improvements can indeed be achieved. Another advantage of our approach is its modularity, in that different query processing strategies can be easily incorporated into the methods and general cost functions can be used for the optimization. Modularity is achieved because the methods developed consist of four well-defined and unrelated modules so that one module can be modified without affecting the others.PhDComputer Information and Control EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/104427/1/9034549.pdfDescription of 9034549.pdf : Restricted to UM users only
Monitoring and control of centralized and decentralized partially -observed discrete -event systems.
No full textCentralized and decentralized monitoring and control of discrete-event systems under partial observation are considered. For the centralized control problem, algorithms computing supremal sublanguages developed in the context of supervisory control theory are revisited and a new algorithm providing an uniform tool for computing supremal sublanguages is developed. The problem of verifying the property of diagnosability is considered in the context of centralized monitoring. A new polynomial time algorithm for deciding diagnosability is presented. We also consider the problem of finding an observable event set with minimum cardinality with respect to three properties: diagnosability, normality, and observability. We prove that these search problems are computationally hard by showing that the corresponding decision problems are NP-complete. We consider a generalized form of the conventional decentralized control architecture for discrete-event systems where the control actions of a set of supervisors can be fused using both union and intersection of enabled events. Namely, the supervisors agree a priori, on choosing fusion by union for certain controllable events and fusion by intersection for certain other controllable events. We show that under this architecture, a larger class of languages can be achieved than before since a relaxed version of the notion of co-observability appears in the necessary and sufficient conditions for the existence of supervisors. The computational complexity of verifying these new conditions is studied. A method of partitioning the controllable events between fusion by union and fusion by intersection is presented. The algebraic properties of co-observability in the context of this architecture are presented. We show that appropriate combinations of fusion rules with corresponding decoupled local decision rules guarantee the safety of the closed-loop behavior with respect to a given specification that is not co-observable. We characterize an optimal combination of fusion rules among those combinations guaranteeing the safety of the closed-loop behavior. In addition, a simple supervisor synthesis technique generating the infimal prefix-closed controllable and co-observable superlanguage is presented. Finally, we consider a decentralized control architecture for discrete-event systems where local supervisors are allowed to change dynamically the manner in which their local decisions are combined globally. This is done by employing dynamic default decisions regarding the enablement of controllable events. In the general architecture, this default was fixed a priori and remained constant throughout the operation of the system. We show that under dynamic decision fusion rules that result from dynamic default decisions, a larger class of languages can be achieved as compared with architectures with static fusion rules. A dynamic version of the notion of co-observability appears in the necessary and sufficient conditions for the existence of supervisors in the new architecture. Dynamic co-observability relaxes (static) co-observability. The existence of a set of local dynamic default decision rules that ensures dynamic co-observability can be decided in polynomial time. A constructive methodology for updating dynamically default decisions for the enablement of controllable events is developed.PhDApplied SciencesElectrical engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/123097/2/3058083.pd
Languages, blocking properties and algorithms in supervisory control of discrete event systems.
No full textThis thesis addresses three important aspects in the supervisory control of discrete event systems: the study of blocking, the characterization of some important languages, and the representation of relational algebraic algorithms. Blocking occurs in the supervisory control of discrete event systems when the controlled system can generate admissible traces of events that cannot be extended to any member of the set of desired marked (e.g., complete) traces. It is often the case that due to the presence of uncontrollable events, blocking is unavoidable or nonblocking solutions do not yield good performance. We study the issue of blocking in the context of a general "supervisory control problem with blocking" (SCPB). The admissible solutions of this problem are characterized and their properties analyzed. We then consider strategies to improve the performance of a given blocking supervisor. Performance is characterized in terms of two sets termed satisficing measure and blocking measure. We present techniques for improving each of these two conflicting measures. We also present techniques to improve both measures successively in order to optimize a given supervisor. The issue of blocking is of course intimately connected with the concept of controllable languages which is of central importance in supervisory control. Two important controllable languages, namely, the infimal closed controllable superlanguage of a given language and the supremal closed nonconflicting controllable sublanguage of a given language are studied in detail. Their properties are analyzed, their computational algorithms discussed and their application in supervisory control with blocking addressed. We also present a relational algebraic approach for the representation of algorithms that arise in the modular composition and control of discrete event systems modeled by finite-state machines. We show that the relational algebra from relational database theory can be employed to formally, uniformly, and concisely describe these algorithms. Relational algebraic expressions are derived for several algorithms on finite-state machines that arise in the study of discrete event systems. The computer implementation of these algebraic expressions is also discussed.PhDElectrical Engineering: SystemsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/105667/1/9208510.pdfDescription of 9208510.pdf : Restricted to UM users only
- …
