Wednesday, September 27, 2006

A random variable: some usefull links on wikipedia

Wednesday, July 19, 2006

A Multimodel Methodology for Qualitative Model Engineering

Modeling and Computer Simulation, Vol. 2, No. 1. (1992), pp. 52-81.
Paul Verstraete

This article introduces a methodology and formalism for developing multiple, cooperative models of physical systems of the type studied in qualitative physics. The formalism combines discrete event and continuous models and offers an approach to building intelligent machines capable of physical modeling and reasoning.

1 Introduction

... simulation methodology developed concepts to model complex systems over multiple levels of abstraction ... a concept of multimodel to formalize models containing several submodels, only one of which is put into effect at any given time.The idea of a multimodel has its roots within the work in combined simulation modeling.Combined modeling has traditionally referred to a integration of discrete event and continuous modeling within the same system description.

formalism for developing multiple, cooperative models of physical systems of the type studied in qualitative physics. The formalism should help to build intelligent machines capable of physical modeling and reasoning.

... to aid in question-answering at di erent levels.

... Using the canonical model definition ...

The emphasis on behavior preservation through homomorphic mapping insures maximal consistency when dynamically mapping between abstraction levels.

We see the need for multiple models and effective methods for linking models using behavior preserving morphisms.

If you boil the water, what will happen next?"

  • Initial a priori physical knowledge of

  • knowledge induced from the robot having visually sensed previous occurrences of what happens to water when boiled.

... a top-down approach

models can be derived in a top-down approach. We start with an abstract model expressed as an FSA ( nite state automaton) and perform homogeneous (i.e., staying within the same formalism) refinement to derive two more levels of refinement...

2 Defining a System

2.1 Formal specification

A deterministic system < T, U, Y, Q,omega,delta,lambda > within classical systems theory 29, 40] is defined as follows:

  • T - is the time set. For continuous systems T = R (reals), and for discrete time systems, T = Z (integers).

  • U - is the input set containing the possible values of the input to the system.

  • Y - is the output set.

  • S - is the state set.

  • omega - is the set of admissible (or acceptable) input functions. This contains a set of input functions that could arise during system operation. Often, due to physical limitations, omega is a subset of the set of all possible input functions (T -> U).

  • delta - is the transition function. It is defined as: delta:SxTxTxomega -> S

  • lambda is the output function, lambda: TxS -> Y .

delta(s,t,w): the input w for a duration of t time units

2.2 Model Types

Discrete State Space:

  • discrete time: difference equations, FSA, Cellular Automata

  • continous time: queing models, digital logic models

Continuous State Space:

  • discrete time: difference equations

  • continuous time: differential equations

Discrete event models cannot be localized within table 2 since the concept of "discrete event" refers to a discrete updating process rather than to the discrete or continuous character of time or state.

What about continuous events -> no references in literature. They are discrete since they map to cognitive and linguistic concets connected with the processes that we model.

A combined model combines two or more of the above model typesl.

2.3 Event identification

An event is a state < s, ..., sn > (where si are components of the state vector) at a specific time t. Therefore, an event is of the form < t, s, ..., sn >. This definition of event was first used in physics, and is defined in systems theory

Events are defined as points in time relative to the level of abstraction associated with the model; many events such as NextToWaterFountain can be modeled as activities (rather than ...

  • In general, an event can occur when a significant (or marked) change occurs in one of the following trajectories: input, output, state. Consider an input trajectory that isa square wave. Leading and trailing edges are good potential locations for events. In continuous systems, state variables specify orders of derivatives. The sign change for a state variable denotes a potential event location.

  • Form a list of questions to be asked of the model. If objects are part of the question then they should be represented in the simulation model, and interaction with the objects are possible events. In general, actions are applied to objects and have a beginning and end -- these are possible locations for events. (Indeed, in the activity scanning "world view" of discrete-event simulation activities or actions form the basic primitives for model expression.)

  • In general, consider all boundary conditions. With respect to collisions between geometrical objects, the points of collision indicate events. Example events are when a projectile hits a target or when an articulated gure comes into physical contact with the environment.-

  • Just as programs have context switches (i.e., subroutines) models can have model context switches. When a model is deliberately composed of separate sub-models then each submodel can be seen as a phase where events demarcate phase boundaries.

3 Example System: Boiling Water

3.1 Overview

3.2 Knowledge Base

3.3 Two Homogeneous Refinements

Note that a transition condition may sometimes refer to a more detailed state specication than is available at the current level of abstraction.

Alternatively, the modeller may decide to terminate the refinement process leaving the transition non-deterministically specified.

3.4 A Heterogeneous Refinement

Note that the continuous models share a common set of state variables. However, in general state variables may be diff

erent for each Mi model.

3.5 Forming a Multimodel

the lowest level. To form a multimodel, we need to specify how the set of models that we have defined can be coordinated so that exactly one submodel is active at any time.



  • Note that zero, one, or more transition conditions may be associated with any phase.

  • In the case that there are no internal transitions out of a phase, the multimodel will

    remain in the phase forever unless there is an external event that can send it to another

    phase. In the case of one transition condition emerging from a phase, the multimodel

    will remain in the phase until the condition becomes true - then it will immediately

    switch to the new phase indicated. In the case of several transition conditions, the

    multimodel will remain in the current phase until one of the conditions becomes true

    _ and will immediately switch to the phase corresponding to that transition.

3.6 DEVS abstractionn of FSA-controlled Multimodels

3.7 Discrete event simulation of multimodels

4 Question Answering and Choice of Model

"Q-Type" means category of question. There are 4 types of questions specified PRED (prediction), DIAG (diagnostic), EXP (explanation), and REF (reference). A predictive question is one where simulation is required to generate the answer. A diagnostic question yields a short answer specifying the immediate cause, whereas an explanation is more lengthy and may involve a summary of information to be presented. A reference question is one that does not involve analysis or simulation such as "What is the material in the pot?"

4.1 Relation to qualitative modeling

5 Conclusions

About the paper summaries I post here ...

You'll notice that many posts are tagged "summary". These post are summaries of a few papers I read as literature study. They are quickly written, intended to remember the content of the paper. They are not complete, they only contain the parts of the paper that struck me when reading them. I make them available, so that they can be reused when somebody wants to read the paper.

Modeling with a Sense of Purpose

Modeling with a Sense of Purpose.

IEEE Software, Vol. 19, No. 1. (2002), pp. 8-10.

by Daniels J

Paul Verstraete

1 It's all a question of purpose

But all too often, the understanding is muddled and confused because the designer hasn’t clearly established the picture’s (remark: that represent some aspect of the software or its requirements) purpose or explained how others should interpret it.

The important difference is the level of abstraction.

2 Implementation, specification and conceptual models

  • implementation model: a model built to explain how something is implemented

  • specification model: a more abstract model that explains what should be implemented

Two issues with models to better understand the real-world problem to be solved:

  • the scope of the models

  • apply their content directly to system-building projects

I’ll refer to all models of situations in the world—of which information models are one example—as conceptual models; other terms that are used include essential models, domain models, business models, and even, most confusingly in my view, analysis models.

Three kind of models:

  • Conceptual models describe a situation of interest in the world, such as a business operation or factory process. They say nothing about how much of the model is implemented or supported by software.

  • Specification models define what a software system must do, the information it must hold, and the behavior it must exhibit. They assume an ideal computing platform.

  • Implementation models describe how the software is implemented, considering all the computing environment’s constraints and limitations.

Opportunities for confusion between these three modeling perspectives are particularly large.

We find different representations of the same concept in many different parts of the application.

3 Notation overload

life gets much more complicated when we attempt to model behavior

... they claimed that the process of moving from conceptual model to code was one that simply involved elaboration rather than mapping or translation.

But the generality of class diagram is part of the problem. Even within the limited scope of a single development project, you’ll typically find class diagrams used for a range of purposes, including the structural aspects of all three kinds of models discussed earlier.

System, models and views

System, models and views

by Cooks S, Daniels J
Paul Verstraete

1 The ecology of software

A breakthrough in software systems will be a consequece of building software systems by assembling them from pre-fabricated parts, rather than repeatedly starting system development from scratch.

2 Modelling

simulation: software model are for the purpose of understanding the system itself. The model does not correspond in real time to any portion of the world: instead it is used to ask 'what if' questions

controlling a process: software responds to stimuli generated within the process and produces appropriate responses to control the future development of the process

3 Software and the world

The world is partially predictable. We can predict the sun will rise, and having risen will not rise again after it has set.

Does the sun send messages to all birds individually? If so, in what order? Is there a problem of deadlock? This is a problem of software execution.

To model the world we use two basic concepts: objects and events.

Somewhere in the software is a concept model, partially mimicking the behaviour of certain things in the world.

Notion of a domain: separately considered sub-systems: e.g. concept domain, interaction domain

Three kind of essential models:

  • essential model of a situation (=purposeful system situated in a context): understand and establish facts about the situation

  • specification model: describes the behaviour of the software system at a high level of abstraction, and in particular says nothing about internal sequencing or concurrency.

  • implementation model: specify patterns of flow of control.

To offer significant advantages, there must be consistency and systematic correspondance between these three models of a system.

4 Essential models

  • building blocks: objects and events

  • interpretation: set of facts


  • possible states the situation can be in

  • set of events which cause changes between one state and another

  • possible sequences of events to occur

Important activity: decide what to include: infinity of phenomena which can be perceived and might be included

all events are instantaneous, regardless of how long they take in the real world

The essential model does not describe cause and effect relationships. This is infinitely complex and non-deterministic. However, we do notice that some sequences of events do occur in the world, whereas others don't.

The essential model tracks the changes of state of the observed situation. The essential model states which sequences of events can happen, and which cannot. There are no 'run-time errors' in a correct essential model: if an event occurs which is not allowed by the model, then the model does not describe the situation properly.

An essential model, once built, could in principle be executed and would act as a kind of simulation of the modelled situation.

It is necessary to define the boundary between the software and its environment.

  • hard systems: the performance of the system depends completely upon the software

  • semi-hard: software does not change the behaviour of the system, but the role of the software within the overall system can be chosen (e.g. automating payroll processingen).

  • soft: introduction of software will influence border between environment and software (e.g. introduction mail system)

It is important not to under-estimate the changes which introducing software can make to a situation.

5 Specification models

To state what the software will do.

A specification model can:

  • generate events itself

  • leave the response to an event undefined

It ignores control flow, concurrency, user-interface details, persistence and so on. The specification should describe the implementation accurately, in the sense that it would be possible to produce a formul proof that the implementation implements the specification correctly ... in the current state of the art, such proofs a rarely a practical proposition for software systems of any significant size or complexity.

To create a specification model we must draw a boundary between the software and the rest of the situation, which we call the environment. To design a specification model requires considerable thought about how the software and its environment will interact.

  • determining the boundary and responsibilities of the software we must identify all stimuli and responses.

  • consider untimely responses: model the attempt to withdraw money when the account is overdrawn by more than a certain amount (not possible according to essential model)

  • specification model as a 'transparent box': the state of the model can be observed by its users at any time

6 Implementation models

semantically close to the execution model

the effects of languages are most likely to be seen in this model

  • which class libraries exist already

  • subtleties about the semantics of inheritance

  • choice between object type and value type

egg model: data, operations and shell

event: detected by hardware device, then detected by interaction domain objects which will send appropriate messages to concept domain objects

In essential and specification models speed of execution is not an issue

7 Views and notations

each view shows a different aspect of the model. Textual view, graphical view.

Two most important views:

  • type view: showing the types of objects in the model

  • state view: showing the state of objects change over time as a result of events

.. we define how formal, mathematical, specification can be used to enchance these views

8 Encapsulated software components

We would like to be able to reuse elements from our essential and specification models too.

Sunday, July 02, 2006

Welcome to my personal weblog.

In this online diary, I want to give a personal selection on the enormous stream of information that 'overruns' us every day. Getting information is no problem any longer. Discovering which information you really need is the problem. This makes information filters, like this one, a valuable thing.

That's the theory. If you enjoy reading this blog as much as I do writing it, I already reached my goal.