This thesis proposes a new methodology for modeling, analysis and design of discrete event control systems based on the DEVS formalism. For modeling and analysis of timed discrete event systems, we propose an extended version of the DEVS (discrete event systems specification) formalism, called communicating real-time DEVS (CRTDEVS) formalism that not only inherits essential features of the DEVS formalism but gives us more freedom to describe nondeterministic behavior commonly encountered in logical analysis as well as timing analysis of timed discrete event systems. Also we propose timed process model, a representation model for the behavior of CRTDEVS models that effectively deals with time uncertainty caused by indeterminate time specified in real-intervals.
Interaction scheme between concurrently running real-time discrete event processes greatly affects the composite behaviors in general. As the interaction scheme of CRTDEVS models, weak event synchronization(WS) is explicitly defined in the way that it conforms to the simulation algorithms of DEVS models. It offers intuitive and definite semantics because it is defined over a timed system model with explicit input/output events in point-wise time semantics. With this synchronization scheme, first we define untimed behavior analysis (UBA) method over untimed CRTDEVS models to get a set of maximal trajectories. Next, timed behavior analysis (TBA) is proposed to get a timed process that shows maximal behaviors with minimal uncertainty, which is geared by the notion of interval vector time proposed here to reduce the divergent uncertainty effect. Some important properties of TBA and UBA for analysis of discrete event systems control is identified.
With this DEVS-based modeling and analysis framework, we propose a DEVS-based controller design framework of discrete event systems both in the untimed domain and in the time domain. We first use UBA to get untimed behaviors and to obtain a desired state trajectory that meets the control objectives. Then we check if the desired state trajectory is controllable or not. If controllable in the untimed domain, we found that a time-independent robust controller can be obtained by the inverse DEVS transform in a straightforward way. Although it is not controllable in the untimed domain, we found that there is still a chance to control in timely fashion; that is, by carefully adjusting time, we can control the order of event occurrences in the systemm such that the resultant behavior meets the control objectives. This case is called weakly (timely) controllable. TBA is such a very a useful tool to verify if a designed controller given with timing specification satisfies the control objectives by analyzing both logical sequences and timing of events. Due to the maximality property, TBA can always guarantee a safeness property that a system does not fall in any bad state.
To reduce burden of verification of implementation correctness of discrete event system models, we develop, as a digressive contribution, the concepts of RTSE&RTEE (real-time simulation environment and real-time execution environment, respectively) that converts an abstract model to an implementation model with little effort. under the enviroment, one can realize a real system from a simulation model used for performance evaluation which in turn is designed under the DEVS framework. To do so, we provide an underpinning theoretic backgroung by defining RTDEVS formalism which preserves RTDEVS-DEVS homomorphism between an execution model in RDEVS formalism and corresponding simulation model in DEVS. A real- tiem execution engine, named RTDEVSim++, that implements our concepts is reported in [HSKP97].
Consequently, the goal of this study is to establish a DEVS-based frame work for modeling, analysis and design of descrete event control systems. As the results, we propose the CRT-DEVS formalism adequate for analysis, a timed behavior analysis methodology defined over CRTDEVS models, and a control framework for discrete event systems specified by DEVS. For future works, it is required to develop a method to get an optimal timing specification in the timely control problem that may require the linear programming technique.
본 논문에서는 DEVS 형식론에 기반한 이산사건 시스템 제어를 위한 모델링, 논리 및 시간 해석 및 설계 방법론을 제안한다. 모델링 방법으로는 DEVS (Discrete Event Systems Specification) 형식론을 논리해석에 적합하도록 확장한 CRTDEVS (Communicating Real-Time DEVS)를 정의하였다. CRTDEVS는 기존의 RTDEVS (Real-Time DEVS) 와 DEVS를 논리적 시간적 해석 측면에서 포괄 할 수 있는 구조를 가지고 있다. 특히 시스템 모델들간의 상호작용에 있어서 사건들이 약동기(Weak Synchronization) 방법을 가지는 것으로 명백히 정의되었으며 이것이 다른 DEVS 모델들과의 큰 차이점이다. 해석 방법에 있어서는 정의된 상호작용을 적용하여 사건의 순서 및 사건이 일어나는 시간이 구간으로 얻어지는 TBA(Timed Behavior Analysis)방법을 제안하였다. 이 방법에 따르면 주어진 CRTDEVS 모델의 동적 행위가 TPM (Timed Process Model)의 형태로 얻어지며 모델이 수행할 가능성이 있는 모든 행위가 얻어진다는 특성을 가지고 있다. 제어기의 설계방법에 있어서는 먼저 시간이 없는 모델에 대해서 제어 목적 (상태 순서)을 만족하는지 제어가능성 (controllability)을 먼저 점검하고 만약 제어 가능하다면 역변환 (inverse DEVS transform)을 통해 시간과 상관없이 올바른 제어를 할 수 있는 제어기를 얻는 것이 가능함을 보였다. 하지만 시간이 없는 모델에서 제어가능하지 않다 하더라도 적절히 시간을 조절하여 사건이 일어나는 순서를 제어하면 원하는 제어목적을 달성할 가능성이 있다는 것을 TBA 해석을 통해 얻을 수 있었다. 이러한 제어를 시간제어 (timely control)이라고 하며 향후 과제로서 최적의 시간 제어를 위한 시간 변수값을 얻어내는 기법을 연구할 필요성이 도출되었다.
