Behavior-Preserving Simulation-to-Animation Model and Rule Transformations

In the framework of graph transformation, simulation rules define the operational behavior of visual models. Moreover, it has been shown already how to construct animation rules from simulation rules by so-called S2A-transformation. In contrast to simulation rules, animation rules use symbols representing entities from the application domain in a user-oriented visualization. Using animation views for model execution provides better insights of model behavior to users, leading to an earlier detection of model inconsistencies. Hence, an important requirement of the animation view construction is the preservation of the behavior of the original visual model. This means, we have to show on the one hand semantical correctness of the S2A-transformation, and, on the other hand, semantical correctness of a suitable backwards-transformation A2S. Semantical correctness of a model and rule transformation means that for each sequence of the source system we find a corresponding sequence in the target system. S2A-transformation has been considered in our contribution to GraMoT 2006. In this paper, we give a precise definition for animation-to-simulation (A2S) backward transformation, and show under which conditions semantical correctness of an A2S backward transformation can be obtained. The main result states the conditions for S2A-transformations to be behavior-preserving. The result is applied to analyze the behavior of a Radio Clock model's S2A-transformation.     

Scenario Views for Visual Behavior Models in GenGED

Visualizing and simulating the behavior of formal models in an adequate and flexible way becomes increasingly important in the design of complex systems. With GenGED, a tool is available which automatically generates a visual environment to process (create, edit, check, simulate) visual models in a specified formalism (a visual language). Both the specification of the formalism and the model manipulation are based on graph grammars. In this paper we present the means to transform a formal model into different application domain oriented views (scenario views). We show how the behavior of the model is transferred to the views and animated there (i.e. simulated in the layout of the application domain). Possible extensions towards animation modules (animated scenario views defined by GenGED that are accessible from other tools) are discussed.     

Scenario animation for visual behavior models: A generic approach

Visualizing and simulating formal models in a flexible way becomes increasingly important for the design of complex systems. With GenGED, a tool is available which automatically generates a visual environment to process (create, edit, check, simulate) visual models over a specified visual language. Both the specification of the language and the model manipulation are based on graph grammars. In this paper, we present the means to transform visual models into application oriented views, called scenario views. We show how a model is consistently transferred to a scenario views and animated there. The extension of GenGED concerning scenario animation is discussed.     

Automated formal verification of visual modeling languages by model checking

Graph transformation has recently become more and more popular as a general, rule-based visual specification paradigm to formally capture (a) requirements or behavior of user models (on the model-level), and (b) the operational semantics of modeling languages (on the meta-level) as demonstrated by benchmark applications around the Unified Modeling Language (UML). The current paper focuses on the model checking-based automated formal verification of graph transformation systems used either on the model-level or meta-level. We present a general translation that inputs (i) a metamodel of an arbitrary visual modeling language, (ii) a set of graph transformation rules that defines a formal operational semantics for the language, and (iii) an arbitrary well-formed model instance of the language and generates a transitions system (TS) that serve as the underlying mathematical specification formalism of various model checker tools. The main theoretical benefit of our approach is an optimization technique that projects only the dynamic parts of the graph transformation system into the target transition system, which results in a drastical reduction in the state space. The main practical benefit is the use of existing back-end model checker tools, which directly provides formal verification facilities (without additional efforts required to implement an analysis tool) for many practical applications captured in a very high-level visual notation. The practical feasibility of the approach is demonstrated by modeling and analyzing the well-known verification benchmark of dining philosophers both on the model and meta-level.     

Object—Z规格说明的SQL动画模拟

软件规格说明的确认在软件开发阶段占有举足轻重的地位。形式规格说明的动画模拟技术是一种规格说明的确认方法。本文研究了Obiect-Z规格说明的SQL动画模拟方法，设计了从Object-Z到SQL的转换规则，并提出了模块封装的思想，即用存储过程表示类、对象和模式等模块，用户通过调用执行存储过程确认规格说明是否满足其需求。     

Specification by-example of virtual agents behavior

The development of virtual agents running within graphic environments which emulate real-life contexts may largely benefit from the use of visual specification by-example. To support this specification, the development system must be able to interpret the examples and cast their underlying rules into an internal representation language. This language must find a suitable trade-off among a number of contrasting requirements regarding expressiveness, automatic executability, and suitability to the automatic representation of rules deriving from the analysis of examples. A language is presented which attains this trade-off by combining together an operational and a declarative fragment to separately represent the autonomous execution of each individual agent and its interaction with the environment, respectively. While the declarative part permits to capture interaction rules emerging from specification examples, the operational part supports the automatic execution in the operation of the virtual environment. A system is presented which embeds this language within a visual shell to support a behavioral training in which the animation rules of virtual agents are defined through visual examples     

Specification and synthesis of hybrid automata for physics-based animation

Physics-based animation programs can often be modeled in terms of hybrid automata. A hybrid automaton includes both discrete and continuous dynamical variables. The discrete variables define the automaton’s modes of behavior. The continuous variables are governed by mode-dependent differential equations. This paper describes a system for specifying and automatically synthesizing physics-based animation programs based on hybrid automata. The system presents a program developer with a family of parameterized specification schemata. Each schema describes a pattern of behavior as a hybrid automaton passes through a sequence of modes. The developer specifies a program by selecting one or more schemata and supplying application-specific instantiation parameters for each of them. Each schema is associated with a set of axioms in a logic of hybrid automata. The axioms serve to document the semantics of the specification schema. Each schema is also associated with a set of implementation rules. The rules synthesize program components implementing the specification in a general physics-based animation architecture. The system allows animation programs to be developed and tested in an incremental manner. The system itself can be extended to incorporate additional schemata for specifying new patterns of behavior, along with new sets of axioms and implementation rules. It has been implemented and tested on over a dozen examples. We believe this research is a significant step toward a specification and synthesis system that is flexible enough to handle a wide variety of animation programs, yet restricted enough to permit programs to be synthesized automatically.     

Automated Synthesis of Numerical Programs for Simulation of Rigid Mechanical Systems in Physics-Based Animation

Physics-based animation programs are important in a variety of contexts, including science, engineering, education and entertainment among others. Manual construction of such programs is expensive, time-consuming and prone to error. We have developed a system for automatically synthesizing physics-based animation programs for a significant class of problems: constrained systems of rigid bodies, subject to driving and dissipative forces, under the control of an interactive user. Our system includes a graphical interface for specifying a physical scenario, including objects, geometry and coordinate systems, along with a symbolic interface for specifying dynamical variables, forces and constraints operating in the scenario. The entities defined in the graphical interface serve as the underlying vocabulary for specifications entered in the symbolic interface. Our system partitions the constraints and dynamical variables into classes and assigns each class to be implemented in a different component of a general simulation program scheme. It generates a numerical C⁺⁺ simulation program that drives a real-time animation of the specified scenario. Our system is implemented as a collection of rewrite rules in the Mathematica programming language. Our approach provides some of the benefits of formal deductive program synthesis, while keeping the computational costs of program synthesis more in line with conventional program generator technology. We have successfully tested our system on numerous examples.     

The behavioral test-bed: Obtaining complex behavior from simple rules

Behavioral simulation is presented as a means to obtain complex global motion by simulating simple rules of behavior between locally related actors. A test-bed which has been developed to support experimentation with behavioral simulation is described. This test-bed has been used to create a library of physically behaving actors which can realistically reproduce the motion of flexible objects. The application of behavioral simulation to problems of motion specification in animation are described. The extension of this technique to simulate social behaviors is discussed.     

混成系统形式化验证

混成系统是实时嵌入式系统的一种重要子类,其行为中广泛存在离散控制逻辑跳转与连续实时行为交织混杂的情况,因此行为复杂,难以掌握与控制.由于此类系统广泛出现在工控、国防、交通等与国计民生密切相关的安全攸关的领域,因此,如何对相关系统进行有效的分析与理解,从而保障系统安全运营,是一项具有重要意义的工作.常规的系统安全性分析手段,如测试、仿真等仅能在一定输入的情况下运行系统来观测系统行为,无法穷尽地检测复杂混成系统在所有可能输入下的行为,因此并不足以保证系统的安全性.区别于测试等方法,形式化方法通过求解系统模型状态取值范围等方法来确认系统模型中一定不会出现相关错误.因此,其对于保障安全攸关混成系统的安全性具有十分重要的意义.形式化方法由形式化规约与形式化验证两个方面构成.因此从以上两个角度分别对形式化规约方向上现有混成系统建模语言、关注性质以及形式化验证方向的混成系统模型检验、定理证明的现有主要技术与方法进行了综述性的回顾与总结.在此基础上,针对现阶段实时嵌入式系统复杂化、网络化的特性,对混成系统形式化验证的重要关注问题与研究方向进行了探索与讨论.     

Constructing formal rules to verify message communication in distributed systems

This study presents a method to construct formal rules used to run-time verify message passing between clients in distributed systems. Rules construction is achieved in four steps: (1) Visual specification of expected behavior of the sender, receiver, and network in sending and receiving a message, (2) Extraction of properties of sender, receiver, and network from the visual specification, (3) specification of constraints that should govern message passing in distributed systems, and (4) construction of verifier rules from the properties and the constraints. The rules are used to verify actual sender, receiver, and network behavior. Expected behavior of the client (process) is one that to be and the actual one is the behavior should be verified. The rules were applied to verify the behavior of client and servers that communicated with each other in order to compute Fibonacci numbers in parallel and some violations were discovered.     

基于高级Petri网的仿真剧情正规校核方法

针对仿真剧情主观校核不理想这一问题，提出了基于高级Petri网的仿真剧情正规校核方法．首先给出仿真剧情的形式化定义，并分析仿真剧情可能存在的错误类型；其次给出仿真剧情到高级Petri网的映射途径，并给出基于高级Petri网的仿真剧情校核准则和算法，此外，还给出实现仿真剧情动态校核的推理规则和机制；最后给出了一个正规校核工具框架．实际应用已经证明了该方法的有效性．     

Analyzing, modelling, and specifying visual interaction

 This paper discusses the processes underlying human-computer visual interaction, thereby analysing the characteristics of visual interaction; a model and a theory of visual interaction, from which a formal specification of visual interactive systems that are trustable by their users can be derived, are also illustrated. Such a theory is called theory of visual sentences, since each message on the computer screen is described as a visual sentence, i.e., an element of a visual language that specifies the interaction. The concept of relational structure is introduced to take into account different kinds of relations which can exist among the characteristic patterns present in a visual sentence. A formal model of the dynamics of visual interaction is presented, which is specified as transformations of visual sentences, modelled through visual rewriting systems, and transformations of relational structures. Particular attention is given to usability issues so as to satisfy relevant features needed to allow non-ambiguity of interpretation, adequate communication, determinism and system viability. An example of visual interaction is given where an immunologist interacts with a simulation of the human immune system. This work was supported by the Italian Ministry of University and Research under the Research Project of National Interest “Specification, Design and Development of Visual Interactive Systems”.     

Validation of formal specifications through transformation and animation

A significant impediment to the uptake of formal refinement-based methods among practitioners is the challenge of validating that the formal specifications of these methods capture the desired intents. Animation of specifications is widely recognized as an effective way of addressing such validation. However, animation tools are unable to directly execute (and thus animate) the typical uses of several of the specification constructs often found in ideal formal specifications. To address this problem, we have developed transformation heuristics that, starting with an ideal formal specification, guide its conversion into an animatable form. We show several of these heuristics and address the need to prove that the application of these transformations preserves the relevant behavior of the original specification. Portions of several case studies illustrate this approach.     

Distributed Event Graphs: Formalizing Component-based Modelling and Simulation

In this work an extension to the classical Event Graphs formalism for discrete-event simulation is presented. The extensions are oriented towards the specification of component-based models. The abstract syntax has been defined through meta-modelling. Several methodological issues are discussed, concerning the use of two different meta-modelling levels or collapsing the language into a single one, where “instance-of” relationships are used between processes and their classes. The operational semantics have been defined through graph transformation. This formal definition enables analysis before code is generated from the model. The syntax and semantics of the visual language have been implemented in the multi-paradigm tool AToM³, together with a code generator that produces stand-alone applications able to run the analysed models in real-time.     

形式化研究基于Agent的行为建模及应用

为了实现虚拟环境中Agent的行为真实感以及行为动画,必须开展基于Agent的行为建模相关问题的研究。提出了一个包含Agent自主行为和全局互操作行为的基于Agent的行为模型,并利用形式化语言对相关概念例如状态、时间、动作和行为进行了规范描述与定义。在此基础上形式化研究了复杂智能行为的抽象机制,包括行为分解与聚合、行为特化与泛化,并因此提出在基于Agent的元行为模型的基础上,通过行为逻辑运算和行为抽象机制实现基于Agent的行为综合方法。同时以空间作战中的导弹预警为背景,分析了预警卫星的预警行为模型,并对预警卫星的数据获取行为进行了建模。这有利于实现预警卫星的行为动画以及对预警卫星的传感器进行调度,进而对预警行为进行规划、调度与仿真。     

基于STeC-Stateflow转换系统的实时系统仿真与验证方法

物联网以及信息物理融合系统对形式化建模提出了新的挑战, 引入了实时系统规范语言STeC, 为刻画实时系统的时空一致性提供了规范语言。针对STeC语言建立STeC至Stateflow自动转换系统, 提出一种基于STeC至Stateflow转换的仿真及验证方法, 该方法使用STeC语言对实时系统进行形式化建模, 再建立实时监控的Simulink仿真模型, 并使用Checkmate对系统进行安全性验证。通过对京沪高铁运行的实例研究, 表明该方法对高铁运行系统实时仿真的有效性, 并能够验证高铁运行系统的安全性。     

Explaining counterexamples using causality

When a model does not satisfy a given specification, a counterexample is produced by the model checker to demonstrate the failure. A user must then examine the counterexample trace, in order to visually identify the failure that it demonstrates. If the trace is long, or the specification is complex, finding the failure in the trace becomes a non-trivial task. In this paper, we address the problem of analyzing a counterexample trace and highlighting the failure that it demonstrates. Using the notion of causality introduced by Halpern and Pearl, we formally define a set of causes for the failure of the specification on the given counterexample trace. These causes are marked as red dots and presented to the user as a visual explanation of the failure. We study the complexity of computing the exact set of causes, and provide a polynomial-time algorithm that approximates it. We then analyze the output of the algorithm and compare it to the one expected by the definition. The algorithm is implemented as a feature in the IBM formal verification platform RuleBase PE, where the visual explanations are an integral part of every counterexample trace. Our approach is independent of the tool that produced the counterexample, and can be applied as a light-weight external layer to any model checking tool, or used to explain simulation traces.