Design of nonblocking modular supervisors using event priorityfunctions

A new scheme for the modular control of discrete event systems is presented and studied. This scheme, called modular control with priorities (MCP), is an extension of earlier works on modular control in the realm of the supervisory control theory of discrete event systems. The key feature of this scheme is the use of a priority mechanism based on the priority functions of individual supervisors in the process of combining the control actions of individual supervisors. This approach is motivated by both theoretical and practical considerations. The main objective is to use priority functions to mitigate or eliminate the problem of blocking that originates in conventional modular control. In this paper, we first show how to design individual supervisors so that they can operate under MCP. We then show how MCP operates and discuss the resulting properties of this approach. Finally, we present several algorithms for priority assignment to obtain nonblocking behavior under MCP. A motivating example from the area of telecommunications is given     

Modular Supervisory Control with Equivalence-Based Abstraction and Covering-Based Conflict Resolution

A modular approach to control is one way to reduce the complexity of supervisory controller design for discrete-event systems (DES). A problem, however, is that modular supervisors can conflict with one another. This paper proposes requirements on coordinating filters that will resolve this conflict. Abstractions are employed to reduce the complexity of the filter construction. Our specific approach is unique in that it employs a conflict-equivalent abstraction that offers the potential for greater reduction in model size than those abstractions employed in previous works on conflict resolution. The resulting control implemented by the modular supervisors in conjunction with coordinating filters meeting the proposed requirements is shown to be safe and nonblocking. Approaches for constructing these filters are discussed and a methodology that implements deterministic coordinating filter control laws by nondeterministic automata is presented. The covering-based filter law construction methodology presented here is further demonstrated to provide less restrictive control than existing results on state-feedback supervisory control.     

The synthesis and PLC implementation of hybrid modular supervisors for real time control of an experimental manufacturing system

In this paper, synthesis and PLC based implementation of hybrid modular supervisors for real time supervisory control of an experimental manufacturing system are proposed. The hybrid approach couples Ramadge–Wonham (RW) supervisors in the form of automata to uncontrolled PN models through inhibitor arcs. The RW supervisors can be obtained in monolithic or modular forms. In the monolithic case, there is only a single supervisor that has complex structure and huge number of states and events. The modularity of supervisors provides simple and small control structures compared to monolithic ones. Modular hybrid approach offers fewer states for the PLC implementation of the hybrid controller with less memory requirements. The applicability and effectiveness of the modular hybrid approach are demonstrated by the PLC based real-time control of an experimental manufacturing system for different cases. The obtained results show that modular supervisors require less memory space compared to monolithic counterparts.     

On deadlock-free modular supervisory control of discrete-eventsystems

In this paper the problem of synthesizing deadlock-free modular supervisors for discrete-event systems is discussed. By introducing the d-invariant relation between a pair of supervisors, it is shown that when the control objective is described in terms of intersection of two languages, a necessary and sufficient condition for the modular supervisor to be deadlock-free is that this pair of subsupervisors satisfies a d-invariant relation. A procedure for synthesizing the deadlock-free modular supervisor is presented. Some issues concerning deadlock-free modular supervisory control are also discussed     

Supervisory Control of Distributed Systems: Conflict Resolution

In distributed synthesis and control, one well-known potential hazard is conflict between modular designs. In a modular approach to the supervisory control of discrete-event systems, modular supervisors that are individually nonblocking (with respect to the plant) may nevertheless conflict and thus produce blocking, or even deadlock, when operating concurrently. A scheme of resolving this potential conflict between the modular supervisors would be to accord priorities to the conflicting supervisors. When conflict arises, the modular supervisor that is assigned a higher priority will have sole control, or in other words the control action of the lower priority supervisor will be suspended. Thus by assigning priority appropriately, control actions of the modular supervisors will be suspended and reactivated in such a way that the potential conflict can be averted. In this article we formalize this scheme with reporter maps from a hierarchical approach to the supervisory control of discrete-event systems. These maps, each acting as an interface between a modular supervisor and the plant, mediate the flow of information and control, and thus in this way achieve suspension and reactivation of the modular supervisors. Sufficient conditions on these reporter maps for conflict resolution are obtained. Roughly speaking, the conditions are that (1) the reporter maps select suitable subsystems of the plant; (2) within these subsystems, conflicts are resolved; (3) the reporter maps are refined enough to lift these local conflict resolutions back to the original plant. With these conditions, a constructive solution is developed, which in essence suspends a supervisor just in time to prevent conflict and reactivates it when the plant and the other supervisor return to the state they were in when the suspension began. Examples inspired by the feature interaction problem in telecommunication systems are provided for illustration.     

A Model Based Approach to Modular Multi-Objective Robot Control

Two broad classes of robot controllers are the modular, and the model based approaches. The modular approaches include the Reactive or Behavior Based designs. They do not rely on mathematical system models, but are easy to design, modify and extend. In the model based approaches, a model is used to design a single controller with verifiable system properties. The resulting designs are however often hard to extend, without jeopardizing the previously proven properties. This paper describes an attempt to narrow the gap between the flexibility of the modular approaches, and the predictability of the model based approaches, by proposing a modular design that does the combination, or arbitration, of the different modules in a model based way. By taking the (model based) time derivatives of scalar, Lyapunov-like, objective functions into account, the arbitration module can keep track of the time evolution of the objectives. This enables it to handle objective tradeoffs in a predictable way by finding controls that preserve an important objective that is currently met, while striving to satisfy another, less important one that is not yet achieved. To illustrate the approach a UAV control problem from the literature is solved, resulting in comparable, or better, performance.     

Supervisory Control Architecture for Discrete-Event Systems

A flexible decentralized and hierarchical architecture is presented to reduce computational effort in designing optimal nonblocking supervisors for discrete-event systems (DES). We organize a DES into modular subsystems that embody internal interacting dependencies. Verification of, and coordination among modular subsystems are achieved through their model abstractions. Sufficient conditions are presented to guarantee that coordinators and modular supervisors result in maximally permissive and nonblocking control. A medium-sized example demonstrates the computational effectiveness of our approach.      

Reliable decentralized supervisory control of discrete eventsystems

We consider a discrete event system controlled by a decentralized supervisor consisting of n local supervisors, and formulate a new decentralized supervisory control problem, called a reliable decentralized supervisory control problem. A decentralized supervisor is said to be k-reliable (1相似文献   

Navigating mobile robots with a modular neural architecture

Neural architectures have been proposed to navigate mobile robots within several environment definitions. In this paper a new neural modular constructive approach to navigate mobile robots in unknown environments is presented. The problem, in its basic form, consists of defining and executing a trajectory to a pre-defined goal while avoiding all obstacles, in an unknown environment. Some crucial issues arise when trying to solve this problem, such as an overflow of sensorial information and conflicting objectives. Most neural network (NN) approaches to this problem focus on a monolithic system, i.e., a system with only one neural network that receives and analyses all available information, resulting in conflicting training patterns, long training times and poor generalisation. The work presented in this article circumvents these problems by the use of a constructive modular NN. Navigation capabilities were proven with the NOMAD 200 mobile robot.     

Structural types for systems of equations

Characterising a problem in terms of a system of equations is common to many branches of science and engineering. Due to their size, such systems are often described in a modular fashion by composition of individual equation system fragments. Checking the balance between the number of variables (unknowns) and equations is a common approach to early detection of mistakes that might render such a system unsolvable. However, current approaches to modular balance checking have a number of limitations. This paper investigates a more flexible approach that makes it possible to treat equation system fragments as true first-class entities. Furthermore, the approach handles so-called structurally dynamic systems, systems whose behaviour changes discretely and abruptly over time. The central idea is to record balance information in the type of an equation fragment. This information can then be used to determine if individual fragments are well formed, and if composing fragments preserves this property. The type system presented in this paper is developed in the context of Functional Hybrid Modelling (FHM). However, the key ideas are in no way specific to FHM, but should be applicable to any language featuring a notion of modular systems of equations, including systems with first-class components and structural dynamism.     

Think globally, act locally: decentralized supervisory control

Decentralized supervisory control is investigated by considering problem formulations that model systems whose specifications are given as global constraints, but whose solution is described by local controllers. A necessary and sufficient condition is given for the existence of a solution to the problem of finding decentralized supervisors that ensure that the behavior of the closed-loop system lies in a given range. Where the range of behavior can be described by regular languages, it can be effectively tested whether the decentralized control problem is solvable; in this case, a procedure is given to compute the associated supervisors     

A learning-based synthesis approach todecentralized supervisory control of discrete event systems with unknown plants

In this paper, we consider the problem of automatic synthesis of decentralized supervisor for uncertain discrete event systems. In particular, we study the case when the uncontrolled plant is unknown a priori. To deal with the unknown plants, we first characterize the conormality of prefix-closed regular languages and propose formulas for computing the supremal conormal sublanguages; then sufficient conditions for the existence of decentralized supervisors are given in terms of language controllability and conormality and a learning-based algorithm to synthesize the supervisor automatically is proposed. Moreover, the paper also studies the on-line decentralized supervisory control of concurrent discrete event systems that are composed of multiple interacting unknown modules. We use the concept of modular controllability to characterize the necessary and sufficient conditions for the existence of the local supervisors, which consist of a set of local supervisor modules, one for each plant module and which determines its control actions based on the locally observed behaviors, and an on-line learning-based local synthesis algorithm is also presented. The correctness and convergence of the proposed algorithms are proved, and their implementation are illustrated through examples.     

Probability method for cryptanalysis of general multivariate modular linear equation

Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. However, one problem arises here that if the equation has a short solution in given bounded range, the results outputted by earlier algorithms are often not the ones we are interested in. In this paper, we present a probability method based on lattice basis reduction to solve the problem. For a g...     

Selective Smooth Fictitious Play: An approach based on game theory for patrolling infrastructures with a multi-robot system

The multi-robot patrolling problem is defined as the activity of traversing a given environment. In this activity, a fleet of robots visits some places at irregular intervals of time for security purpose. To date, this problem has been solved with different approaches. However, the approaches that obtain the best results are unfeasible for security applications because they are centralized and deterministic. To overcome the disadvantages of previous work, this paper presents a new distributed and non-deterministic approach based on a model from game theory called Smooth Fictitious Play. To this end, the multi-robot patrolling problem is formulated by using concepts of graph theory to represent an environment. In this formulation, several normal-form games are defined at each node of the graph. This approach is validated by comparison with best suited literature approaches by using a patrolling simulator. The results for the proposed approach turn out to be better than previous literature approaches in as many as 88% of the cases of study. Moreover, the novel approach presented in this work has many advantages over other approaches of the literature such distribution, robustness, scalability, and dynamism. The achievements obtained in this work validate the potential of game theory to protect infrastructures.     

Decentralized control of networked discrete event systems with communication delays

In many practical systems, supervisory control is not performed by one centralized supervisor, but by multiple local supervisors. When communication networks are used in such a system as the medium of information transmission, the communication channels between local supervisors and the system to be controlled will unavoidably result in communication delays. This paper investigates how to use these local supervisors to control the system in order to satisfy given specifications even under communication delays. The specifications are described by two languages: a minimal required language which specifies the minimal required performance that the supervised system must have and a maximal admissible language which specifies the maximal boundary that the supervised system must be in. The results show that if the control problem is solvable, then there exists the minimal control policy which can be calculated based on state estimates. Furthermore, we derive algorithms to check whether the control problem is solvable or not.     

Machine Learning for Information Extraction in Informal Domains

We consider the problem of learning to perform information extraction in domains where linguistic processing is problematic, such as Usenet posts, email, and finger plan files. In place of syntactic and semantic information, other sources of information can be used, such as term frequency, typography, formatting, and mark-up. We describe four learning approaches to this problem, each drawn from a different paradigm: a rote learner, a term-space learner based on Naive Bayes, an approach using grammatical induction, and a relational rule learner. Experiments on 14 information extraction problems defined over four diverse document collections demonstrate the effectiveness of these approaches. Finally, we describe a multistrategy approach which combines these learners and yields performance competitive with or better than the best of them. This technique is modular and flexible, and could find application in other machine learning problems.     

Supervisory control of discrete-event systems with output: Application to hybrid systems

In this paper, the problem of supervisory control of discrete-event systems (DES) with output is presented and discussed at length. In such systems, causal output maps are employed to assign to each sequence of input events a corresponding sequence of output events. When the specification of desired behaviour is given by a formal language over the output alphabet, necessary and sufficient conditions are derived for the existence of non-blocking input as well as non-blocking output supervisory control. After making minor adjustments the theory is applied to non-deterministic discrete-event abstractions of hybrid systems, giving rise to the development of a theory for non-blocking supervisory control of hybrid systems. Our results enable one to apply classical supervisory control theory to design supervisors for DES approximations of hybrid systems, and to import many interesting concepts from classical theory such as modular and hierarchical control.     

一种双向求解平行结构类问题的方法

平行结构类问题是一类适于分布式求解的人工智能问题．已有的大多数求解方法均采用预期或目标来指导自底向上的问题求解．但这些预期或目标是以局部问题求解状态为基础的，指导性较弱．尽管有的方法（如改进的ＤＶＭＴ结构）允许高层了解，但未给出明确的求解算法．本文提出一种双向求解平行结构类问题的方法，首先根据全局问题求解状态生成预期，指导自底向上的求解，然后根据新产生的假设来验证和修改预期，并用新的预期重新指导求解．该方法不仅提高了预期的指导性，而且使问题求解更为灵活．     

An Efficient Algorithm for Solving Fuzzy Linear Programming Problems

In this article, we consider some well-known approaches for solving fuzzy linear programming (FLP) problems. We present some of the difficulties of these approaches. Then, crisp linear programming problems are suggested for solving FLP problems. A new algorithm is also given. The proposed approach has advantages over the other methods. For example, we can achieve higher membership degrees for objective function and constraints. Moreover, we show that the fuzzy optimal solutions obtained by the proposed approach are efficient enough. Also, we see that unlike the previous methods, our method finds efficient solutions by solving only one crisp linear problem instead of solving two or three crisp problems. Finally some numerical examples are presented to show the efficiency of the given approach over the other approaches.     

一种改进的模块PCA人脸识别新方法

提出了一种改进的模块PCA方法,即基于独立特征抽取的模块PCA方法。算法先对图像进行分块,然后对每一子块独立地进行PCA处理,求出测试样本子块与训练样本对应子块间的距离;最后将这些距离相加得到测试样本与训练样本的距离,用最近距离分类器分类。在ORL人脸库和Yale人脸库上的实验结果表明,提出的方法在识别性能上明显优于普通模块PCA方法。