Unconstrained optimal control of regular languages

This paper formulates an unconstrained optimal policy for control of regular languages realized as deterministic finite state automata (DFSA). A signed real measure quantifies the behavior of controlled sublanguages based on a state transition cost matrix and a characteristic vector as reported in an earlier publication. The state-based optimal control policy is obtained by selectively disabling controllable events to maximize the measure of the controlled plant language without any further constraints. Synthesis of the optimal control policy requires at most n iterations, where n is the number of states of the DFSA model. Each iteration solves a set of n simultaneous linear algebraic equations. As such, computational complexity of the control synthesis is polynomial in n.     

随机计时离散事件系统的软控制任务研究

本文通过引入马氏决策过程中的迭代算法,研究了计时离散事件系统的随机优化监控综合问题。为了对不确定的人造系统实施监控,在考虑事件的操作时间的基础上,利用带有发生事件概率分布函数的随机计时离散事件系统模型对系统建模。为了对这类随机系统实施监控,在传统方法中,采用控制任务的最大可控子语言设计控制器,不能体现系统模型的随机特性。本文提出利用软控制任务代替原控制任务的方法,使其超出原控制任务的概率在给定的容许度约束范围内。首先,通过在计时离散事件系统中定义计时事件的发生概率映射和发生费用函数,利用离散事件系统的逻辑特性,构造事件发生序列的期望费用函数,进而确立马氏决策过程的最优方程,建立软控制任务与期望费用函数之间的关系。然后,通过计算事件发生序列的费用值,提出利用有限费用值可以用来确定软控制任务,进而基于逻辑监控方法,确定最优监控器。最后,利用计算有限费用值的迭代过程,提出迭代算法,并给出了计算实例。     

Grid automata and supervisory control of dense real-time discrete event systems

We present a generalization of the classical supervisory control theory for discrete event systems to a setting of dense real-time systems modeled by Alur and Dill timed automata. The main problem involved is that in general the state space of a timed automaton is (uncountably) infinite. The solution is to reduce the dense time transition system to an appropriate finite discrete subautomaton, the grid automaton, which contains enough information to deal with the timed supervisory control problem (TSCP). The plant and the specifications region graphs are sampled for a granularity defined in a way that each state has an outgoing transition labeled with the same time amount. We redefine the controllability concept in the context of grid automata, and we provide necessary and sufficient solvability conditions under which the optimal solution to centralized supervisory control problems in timed discrete event systems under full observation can be obtained. The enhanced setting admits subsystem composition and the concept of forcible event. A simple example illustrates how the new method can be used to solve the TSCP.     

离散事件系统的一种N步在线监控策略

文中给出了离散事件系统的一种N步在线监控策略.其特点是控制策略取决于系统当前运行的N步后继运行投影或预测,无需计算非能控语言的上限能控子语言,通过适当选取N,仍可保证系统的最优运行.同时还给出了与之相关的一些理论结果.     

部分同步离散事件系统的分散监控

本文研究一类部分同步离散事件系统分散监控与集中监控等价的条件,得到按控制指标自然分解的分散监控实现方式,由此提出了整体、局部目标最优实现一致性问题,并讨论了分散监控闭合回路的两种控制作用机理.最后给出了一种辅助分散监控的协调方案.     

Multi-level hierarchical interface-based supervisory control

Hierarchical Interface-Based Supervisory Control employs interfaces that allow properties of a monolithic system to be verified through local analysis. By avoiding the need to verify properties globally, significant computational savings can be achieved. In this paper we provide local requirements for a multi-level architecture employing command-pair type interfaces. This multi-level architecture allows for a greater reduction in complexity and improved reconfigurability over the two-level case that has been previously studied since it allows the global system to be partitioned into smaller modules. This paper also provides results for synthesizing supervisors in the multi-level architecture that are locally maximally permissive with respect to a given specification and set of interfaces.     

Dynamic Control with Indistinguishable Events

We consider the problem of synthesizing controllers for dicrete event systems with indistinguishable events. The specification for the supervised system as well as the constraints for the controllers are defined by an extension of the logic of the μ-calculus that generalize the framework introduced by Ramadge and Wonham. More precisely, in order to express that some events are indistinguishable, one can specify with this extension that, from a node of a graph, two edges reach the same node. As for the μ-calculus, the model cheking problem and also the emptiness problem for this extension amount to computing winning strategies in parity games. We show that the centralized control problem with indistinguishable events is decidable by reducing it to the satisfiability problem of a formula of this extension of the μ-calculus. We prove also that, unfortunately, the decentralized control problem is undecidable by a reduction of the halting problem of a Turing machine. Moreover, we exhibit a decidable case of decentralized control by restricting the specifications to those which we called here “conic”.     

Bisimilarity enforcing supervisory control for deterministic specifications

This paper studies the supervisory control of nondeterministic discrete event systems to achieve a bisimulation equivalence between the controlled system and the deterministic specification. In particular, a necessary and sufficient condition is given for the existence of a bisimilarity enforcing supervisor, and a polynomial algorithm is developed to verify such a condition. When the existence condition holds, a bisimilarity enforcing supervisor is constructed. Otherwise, two methods are provided for synthesizing supremal feasible sub-specifications.     

Timed Discrete Event Control of Parallel Production Lines with Continuous Outputs

In this contribution we present an approach to formulate and solve certain scheduling tasks for hybrid systems using timed discrete event control methods. To demonstrate our approach, we consider a cyclically operated plant with parallel reactors using common resources and a continuous output. For this class of systems, we show how to pose the control problem within a discrete event framework by modelling system components as multirate timed automata. We propose a supervisory control strategy incorporating off-line optimisation to assure safety and nonconflicting use of resources. These properties have to be achieved in the presence of a class of bounded errors/disturbances and can be verified by applying formal methods.     

部分能观的DES监控器设计

离散事件监控理论是目前研究DEDS的一个主要分支.本文研究了在事件部分能控、能观情况下监控器存在的一个充要条件和设计方法,并用实例说明了该方法的有效性.     

Model-based detection of routing events in discrete flow networks

A theoretical framework and its practical implications for formulating and implementing model-based monitoring of discrete flow networks are discussed. Possible flows of items are described as discrete-event (DE) traces. Each trace defines the DE sequence(s) that are triggered when an entity follows a given flow-path, visiting tracking locations within the monitored system. To deal with alternative routing, creation of items, flow bifurcations and convergences are allowed. Given the set of possible discrete flows, a possible-behavior model—an interacting set of automata—is constructed, where each automation models the item discrete flow at each tracking location. In this model, which assumes total observability, event labels or symbols contain all the information required to unambiguously distinguish each discrete movement. Within the possible behavior, there is a special sub-behavior whose occurrence is required to be detected. The special behavior may be specified by the occurrence of routing events, such as faults or route violations, for example. These intermittent or non-persistent events may occur repeatedly. An observation mask is then defined, characterizing the observation configuration available for collecting item tracking data. The verification task is to determine whether this observation configuration is capable of detecting the specified special behavior. The assessment is accomplished by evaluating several observability notions, such as detectability and diagnosibility. If the corresponding property is satisfied, associated formal observers are constructed to perform the monitoring task at hand. The synthesis of observation masks may also be conducted to suggest optimal observation configurations (specifying number, type, and tracking locations of observation devices) guaranteeing the detection of special events and to construct associated monitoring agents. The developed framework, modeling methodology, and supporting techniques for defining and implementing discrete flow monitoring of entity movements are presented and illustrated with examples.     

On optimal and reasonable control in the presence of adversaries

This paper constitutes a sketch of a unified framework for posing and solving problems of optimal control in the presence of uncontrolled disturbances. After laying down the general framework we look closely at a concrete instance where the controller is a scheduler and the disturbances are related to uncertainties in task durations.     

Compositional Synthesis of Maximally Permissive Supervisors Using Supervision Equivalence

This paper presents a general framework for efficient synthesis of supervisors for discrete event systems. The approach is based on compositional minimisation, using concepts of process equivalence. In this context, a large number of ways are suggested how a finite-state automaton can be simplified such that the results of supervisor synthesis are preserved. The proposed approach yields a compact representation of a least restrictive supervisor that ensures controllability and nonblocking. The method is demonstrated on a simple manufacturing example to significantly reduce the number of states constructed for supervisor synthesis.

On the supervisory control of multi-agent product systems: Controllability properties

Multi-Agent (MA) product systems were defined in [I. Romanovski, P.E. Caines, On the supervisory control of multi-agent products systems, IEEE Trans. Automated Control 51(5) (2006)] where the notion of an MA controllable vector language specification was introduced and necessary and sufficient conditions for the existence of a supervisor for such a specification were derived. In this paper we present a set of results about the controllability of an MA product system and its components. In particular, we obtain an algorithm for finding the infimal MA-controllable superlanguage inf_MA(K) of a given vector (language) specification K w.r.t. an MA product system G and establish that in fact . It is proven that there is an algorithmic procedure for the recursive construction of MA supervisors when additional automata are added to a system via the MA product. Controllability properties of component structures (such as standard controllability and MA controllability of projections) are considered. Several examples are given to illustrate the results of the paper.     

事件图的混合控制器设计

指数级计算复杂性的可达性分析导致较大规模Petri 网上的监控器设计非常困难. 为了解决这一问题, 本文给出了事件图上的混合型控制器设计方法：首先得到了观测器的设计方法;其次给出了根据观测器计算最大允许控制策略的算法. 结果表明,该方法降低了需要观测的状态空间的维数,从而提高了计算效率,并且该方法不要求对象网是活的或有界的.     

Model predictive control for perturbed max-plus-linear systems

Model predictive control (MPC) is a popular controller design technique in the process industry. Conventional MPC uses linear or nonlinear discrete-time models. Recently, we have extended MPC to a class of discrete event systems that can be described by a model that is “linear” in the (max,+) algebra. In our previous work, we have only considered MPC for the deterministic noise-free case without modeling errors. In this paper, we extend our previous results on MPC for max-plus-linear systems to cases with noise and/or modeling errors. We show that under quite general conditions the resulting optimization problems can be solved very efficiently.     

Control of large scale discrete event systems: Task allocation and coordination

To control a large scale discrete event system, decentralized control and hierarchical control can be used, where several local supervisors are used to control events in local sites and a coordinator is used to coordinate the local supervisors. Two important problems that need to be solved in such a control architecture are task allocation and coordination. That is, how to allocate tasks to the supervisors, and how to coordinate those tasks. We propose and solve a task allocation problem of assigning tasks to the local supervisors and a minimal intervention problem of coordinating tasks so that the intervention by the coordinator is minimal.     

基于神经网络算法的实时DES监督控制

本文在包含状态转移时间离散事件系统（ＤＥＳ）的自动机模型基础上,引入神经网络优化算法用以确定表征闭环系统最大允许逻辑行为的语言Ｋ的一个某项指标最优的子集Ｋｅｐｔ,并探讨了这种情况下用Ｒ－Ｗ理论设计监控ＤＥＳ的有关问题．