Multitasking Supervisory Control of Discrete-Event Systems

This paper presents an approach for functionally dealing with multiple tasks in the supervisory control of discrete-event systems (DES). The colored marking generator (CMG), a special type of Moore automaton, is introduced as a model that distinguishes classes of tasks in DES. The main results of supervisory control theory are extended to this model, allowing the synthesis of minimally restrictive supervisors, which respect the safety specifications and ensure coreachability of multiple control objectives. Reversibility is also investigated as an alternative way of ensuring liveness of multiple tasks. Two examples illustrate the convenience of this approach.     

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.     

不确定观测下离散事件系统的可诊断性

从系统诊断的角度来看,可诊断性是离散事件系统的一个重要性质.其要求系统发生故障后经过有限步的观测可以检测并隔离故障.为简单起见,对离散事件系统可诊断性的研究大都假定观测是确定的,即观测到的事件序列与系统实际发生的可观测事件序列一致.而在实际应用中,由于感知器的精度、信息传输通道的噪声等原因,获取的观测往往是不确定的.本文重点研究观测不确定条件下离散事件系统的可诊断性问题.首先,扩展了传统可诊断性的定义,定义了观测不确定条件下的可诊断性.接着,分别给出各类观测不确定条件下的可诊断性判定方法.而在更一般的情况下,各类观测不确定可能共同存在.因此,最后给出一般情况下的可诊断性判定方法.     

Near-Optimal Online Control of Dynamic Discrete-Event Systems

A class of time-varying discrete-event systems, named dynamic discrete-event systems, is defined. The goal of this paper is to provide a method which is modular and can be applied in real solutions for the optimization of the online control of such systems. First, a simple control algorithm is presented, followed by illustrative examples of different issues that can arise if it is used. Afterward, a more complicated near-optimal online control algorithm with normalization of string values is proposed. The time variability of the systems is accounted for and the average computational time is drastically reduced. This is demonstrated with a set of simulations of the performance of the new algorithm.     

On the Computation of Observers in Discrete-Event Systems

The concept of observer was introduced in previous work by the authors on a hierarchical control theory of discrete-event systems (DES). It was shown that the observer property of the “causal reporter” map, which in this theory models information flow in a hierarchical DES, plays a role in ensuring that a nonblocking supervisor at a given level of a hierarchy does not cause blocking in the level below. In this paper, we investigate the following problem: Given a causal reporter map that is not an observer, how can we design an observer by modifying this map? In case the latter is represented by a finite Mealy automaton, an effective computational algorithm is developed for computing an observer with the coarsest possible equivalence kernel that is finer than that of the given map. Three examples are provided for illustration.     

离散事件系统的无死锁模块化状态反馈控制

本文讨论离散事件系统的无死锁模块化状态反馈问题。首先我们定义自动机的交与并运算，然后通过引入自动机对的Ｄ－不变关系，我们证明当控制目标是两个谓词的交时，模块化状态反馈控制器是无死锁的充要条件是各子控制器是无死锁的且相应的控制器满足Ｄ－不变关系。我们证明了一个给定的自动机对于另一自动机的Ｄ－不变子自动机类有最大元存大，并由此给出一个综合算法。     

Modular Control of Discrete-Event Systems With Coalgebra

Modular supervisory control of discrete-event systems, where the overall system is a synchronous (parallel) product of subsystems, is considered. The main results of this paper are formulations of sufficient conditions for the compatibility between the synchronous product and various operations stemming from supervisory control as supervised product and supremal controllable sublanguages. These results are generalized to the case of modules with partial observations: e.g., modular computation of supremal normal sublanguages is studied. Coalgebraic techniques based on the coinduction proof principle are used in our main results. Sufficient conditions are derived for modular to equal global control synthesis. An algorithmic procedure for checking the new conditions is proposed and the computational benefit of the modular approach is discussed and illustrated by comparing the time complexity of modular and monolithic computation.     

Aggregation in Hierarchical Discrete-Event Systems

We propose an algorithm for the hierarchical decomposition of a large automaton-based discrete-event system. We also provide an estimation of the numerical cost in terms of the size of the system. Our hierarchical decomposition is illustrated with simple examples from dynamical ST-control and supervisory control with uncontrollable events and unsafe states.     

EDEN: An Intelligent Software Environment for Diagnosis of Discrete-Event Systems

A software environment, called EDEN, that prototypes a recent approach to model-based diagnosis of discrete-event systems, is presented. The environment integrates a specification language, called SMILE, a model base, and a diagnostic engine. SMILE enables the user to create libraries of models and systems, which are permanently stored in the model base, wherein both final and intermediate results of the diagnostic sessions are hosted as well. Given the observation of a physical system gathered during its reaction to an external event, the diagnostic engine performs the a posteriori reconstruction of all the possible evolutions of the system over time and, then, draws candidate diagnoses out of them. The diagnostic method is described using a simplified example within the domain of power transmission networks. Strong points of the method include compositional modeling, support for model update, ability to focus on any sub-system, amenability to parallel execution, management of multiple faults, and broad notions of system and observation.     

切换网络拓扑下Euler-Lagrange系统的分布式协调控制

研究切换网络拓扑下含未知参数的分布式Euler-Lagrange系统(简称EL系统)的自适应协调控制问题.通过引入一种新颖的自适应控制构架,设计了分散式控制器,使其容许未知的系统参数.基于图论,Lyapunov稳定性理论以及切换控制理论证明了算法的稳定性.本文特色在于在同一理论框架下处理EL系统协调控制中的未知参数问题与切换拓扑问题,实现静态和动态两种情况下的控制目标.仿真结果验证了算法的有效性.     

离散事件动态系统的输出反馈与周期配置

对一类用极大代数描述的离散事件动态系统,本文得到了能用输出反馈任意配置其周期的充分必要条件.证明了一个系统如果能用输出反馈任意配置周期,那么它是能达能观的.     

基于状态树结构的离散事件系统模块化监督控制

在状态树结构(State tree structures, STS)的基础上提出了离散事件系统的模块化监督控制方法. 该方法中, 系统模型是状态树结构模型, 控制指标以谓词形式给出. 把控制指标分解为几个子控制指标的合取形式, 对每个子控制指标分别设计非阻塞最优监督控制器, 并保证闭环系统行为满足控制指标要求且是非阻塞最优的. 本文研究了模块化监督控制器存在性条件, 给出了模块化监督控制器的综合过程; 当闭环系统阻塞时, 引入协调器来解决闭环系统阻塞问题并且给出了协调器的设计方法.     

PSPACE-completeness of Modular Supervisory Control Problems*

In this paper we investigate computational issues associated with the supervision of concurrent processes modeled as modular discrete-event systems. Here, modular discrete-event systems are sets of deterministic finite-state automata whose interaction is modeled by the parallel composition operation. Even with such a simple model process model, we show that in general many problems related to the supervision of these systems are PSPACE-complete. This shows that although there may be space-efficient methods for avoiding the state-explosion problem inherent to concurrent processes, there are most likely no time-efficient solutions that would aid in the study of such large-scale systems. We show our results using a reduction from a special class of automata intersection problem introduced here where behavior is assumed to be prefix-closed. We find that deciding if there exists a supervisor for a modular system to achieve a global specification is PSPACE-complete. We also show many verification problems for system supervision are PSPACE-complete, even for prefix-closed cases. Supervisor admissibility and online supervision operations are also discussed.*This research was supported in part by NSF grant CCR-0082784.     

Group Hybrid Coordination Control of Multi-Agent Systems With Time-Delays and Additive Noises

A new kind of group coordination control problemgroup hybrid coordination control is investigated in this paper.The group hybrid coordination control means that in a whole multi-agent system(MAS) that consists of two subgroups with communications between them,agents in the two subgroups achieve consensus and containment,respectively.For MASs with both time-delays and additive noises,two group control protocols are proposed to solve this problem for the containment-oriented case and consensus-ori...     

分层离散事件系统的不透明性

针对离散事件系统（DES）的不透明性问题，结合具有分层（hierarchical）结构的自动机模型，提出了分层离散事件系统的不透明性.对分层离散事件系统进行标准化，给出了分层离散事件系统不透明性和K延迟不透明性两个概念.为了对分层离散事件系统的两种不透明性进行验证，分别构造了两种相应的不透明性验证器，得到了关于不透明性和K延迟不透明性的充分必要条件，并对构造不透明性验证器的复杂度进行了分析.     

Distributed computation of supremal conditionally controllable sublanguages

In this paper, we further develop the coordination control framework for discrete-event systems with both complete and partial observations. First, a weaker sufficient condition for the computation of the supremal conditionally controllable sublanguage and conditionally normal sublanguage is presented. Then we show that this condition can be imposed by synthesising a-posteriori supervisors. The paper further generalises the previous study by considering general, non-prefix-closed languages. Moreover, we prove that for prefix-closed languages the supremal conditionally controllable sublanguage and conditionally normal sublanguage can always be computed in the distributed way without any restrictive conditions we have used in the past.     

离散时滞大系统的最优跟踪递阶控制方法

考虑具有控制时滞及输入输出之间向通道的大系统，应用线性二次型加积分（ＬＱＩ）＾１的最优状态反馈控制理论和带时增广状态向量方法，转化原大系统为满足马尔可夫性质的增广状态大系统，再作了问题分解后，整个大系统的解可由于问题层的局部控制器和上层协调器迭代计算。     

Hierarchical control of timed discrete-event systems

An abstract hierarchical control theory is developed for a class of timed discrete-event systems (TDES) within the discrete-event control architectural framework proposed earlier by the authors. For this development, a control theory for TDES is introduced in the spirit of a prior theory of Brandin. A notion of time control structures is introduced, and on its basis a general property of hierarchical consistency is achieved by establishing control consistency — namely preservation of time control structures through the aggregation mapping in a two-level hierarchy.     

Learning Situation-Specific Coordination in Cooperative Multi-agent Systems

Achieving effective cooperation in a multi-agent system is a difficult problem for a number of reasons such as limited and possibly out-dated views of activities of other agents and uncertainty about the outcomes of interacting non-local tasks. In this paper, we present a learning system called COLLAGE, that endows the agents with the capability to learn how to choose the most appropriate coordination strategy from a set of available coordination strategies. COLLAGE relies on meta-level information about agents' problem solving situations to guide them towards a suitable choice for a coordination strategy. We present empirical results that strongly indicate the effectiveness of the learning algorithm.