1,721,015 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
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
Modular discrete-event systems: Modeling, control with priorities, and incremental model evolution.
No full textModularization is a commonly-used technique for modeling and control of large-scale systems. It can reduce the complexity of controllers, enhance the flexibility in the design of system models and controllers, and facilitate the redesign of controllers when changes are required to the system models. However, the modular design of systems and controllers can also create unexpected conflicts among controllers. This work is set in the context of the theory of supervisory control of discrete event systems. The three main contributions of this thesis address modeling, control with priorities, and incremental model evolution of modular discrete event systems. An important motivation for this thesis is the problem of feature interactions in telecommunication networks. When a new feature, such as call waiting or call forwarding, is added to the system, it may interact unexpectedly with the existing features and result in undesirable system behavior. Meanwhile, the introduction of new system components or features sometimes requires the complete redesign of the existing features. In this thesis, we model the logical behavior of telecommunication networks as discrete event systems, where features are implemented as modular supervisors that jointly control the telecommunication system. Techniques are proposed to detect the potential interactions between these supervisors. We then propose a new scheme for modular control of discrete event systems. This scheme provides a new approach to resolve conflicts among modular supervisors, such as blocking and loss of functionality, through the use of a priority mechanism. We develop algorithms that use this priority mechanism to synthesize nonblocking modular supervisors. In the case of incremental system evolution, we investigate the feasibility of reusing the existing modular supervisors. We propose systematic methods for the reuse of existing supervisors based on the automatic synthesis of input and output interfaces. Although this work was originally motivated by the problem of feature interactions, the results presented in this thesis can be readily applied to other discrete event system applications such as manufacturing systems.PhDApplied SciencesElectrical engineeringIndustrial engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/130680/2/9811051.pd
Optimal control of discrete event systems.
No full textWe are interested in the problem of designing control software for large-scale systems having discrete event-driven dynamics, in situations where the performance is specified by numerical measures. The paradigm of Supervisory Control Theory, developed for Discrete Event Systems (DES) constrained by legality specifications (0, -cost structure), is useful and we show how it can be extended to this more general class of specifications. We assume the DES is represented by a formal language consisting of strings contained in the Kleene closure of an alphabet. This language has two kinds of costs on its usage of resources. The design objective is to find sublanguages that minimize these costs. Both deterministic and stochastic languages are looked at. We present modelling methods and examples to motivate interesting ways of using our problem formulation. An existence theory is developed. Amongst other things, the theory establishes the existence of minimally restrictive solutions. Various related paradigms in stochastic control, dynamic programming and finite vertex directed graphs are discussed. For DES modelled by finite state machine we establish computability and present algorithms of polynomial complexity to compute optimal sublanguages. Our findings can collectively be considered as a theory of optimal control for DES, though it differs from the classical theory in interesting ways.PhDApplied SciencesComputer scienceIndustrial engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/129568/2/9527739.pd
Computations on distributed discrete -event systems.
No full textThis thesis explores computational issues related to the control and verification of systems with distributed structure. The framework of supervisory control theory and discrete-event systems is used where system modules are modelled as sets of finite state automata whose behavior coordinates on the occurrence of common events. It is shown that in general many problems related to the supervision of these systems are PSPACE-complete. There are methods for solving these problems that are more efficient in memory than the current state-of-the-art methods, but there are most likely no time-efficient general solution methods that would aid in the study of such large-scale systems. This thesis explores methods for avoiding the computational difficulty of solving these problems. For decentralized control situations a new state estimator is presented that accounts for past local control actions when calculating the set of estimated system states. The new state estimator is used to develop new decentralized control protocols with a common sufficient safety condition. It is also shown that it is difficult to approximate minimal solutions to a sensor selection problem for partial observation control situations. Heuristic methods for solving this approximation problem based on a type of edge-colored graph cutting problem are then discussed. It is also shown how to convert a type of communicating controller problem into this edge-colored graph cutting problem. A notion of state permutation symmetry that defines an equivalence class for the distributed system states is introduced. A method is shown to reduce the complexity of verifying mu-calculus propositions for systems with state permutation symmetry. A special class of symmetric distributed systems is also shown that allows for an even greater reduction in the difficulty of testing several fundamental system properties. Control and verification problems related to both local and global specifications for these special systems are then explored.PhDApplied SciencesComputer scienceElectrical engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/124308/2/3137937.pd
Dynamic traffic control: Decentralized and coordinated methods.
No full textAn overall dynamic traffic management system that seeks to maximize network-wide performance is the primary focus of this research. Specifically, this dissertation deals with the development of efficient techniques for the dynamic control of signalization in traffic networks in the context of Intelligent Transportation Systems. It comprises three complementary components: decentralized control, coordinated control, and coordinated control in an Advanced Traveler Information System (ATIS) environment. For the first component, an algorithm to optimize, in real-time, traffic signals for individual intersections in traffic networks is presented; it uses an efficient decision-tree searching technique to minimize delay. This decentralized algorithm for traffic controllers is called Adaptive Limited Lookahead Optimization of Network Signals (ALLONS-D). Two perspectives are addressed as part of the second component: (i) a hierarchical control architecture for enabling local controllers to maximize system performance and (ii) an iterative process (ALLONS-I) to determine an equilibrium set of control policies for traffic-responsive signal controllers like ALLONS-D. The first perspective divides local signal choice and coordination of these local controllers into two layers of control. An optimization problem is formulated to determine the coordination requirements that are imparted to the local controllers from the higher layer. The ability of this scheme to improve performance on arterial and grid networks is tested via software simulation. In the same manner, this hierarchical scheme is shown to be useful in improving the flow of transit vehicles in a traffic signal network relying on ALLONS-D controllers. The second perspective for the second component of this dissertation deals with a form of coordination achieved by iteratively recalculating the signal control policies at the intersections; this iterative method is a dynamic adjustment process. This process is successful in converging to a set of coordinated traffic signals in some cases; its convergence properties are analyzed using a game-theoretic model. The result of this analysis is a proof of convergence for a specific class of traffic networks and traffic demand. Finally, the third component of this dissertation develops a traffic optimization process that incorporates drivers' route selections as well as the resulting adaptive traffic signal control policies. This iterative signal optimization - traffic assignment technique is developed and shown to converge to a dynamic user-equilibrium solution through simulation experiments and formal analysis. This iterative method allows an examination of the long term effect of the adaptive signal control scheme on drivers' route choices.PhDApplied SciencesArtificial intelligenceElectrical engineeringOperations researchSocial SciencesSystems scienceTransportationUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/131305/2/9840627.pd
- …
