Jean-Sébastien Bolduc
Welcome
Research
TAing
Meeting Logs
Here are a few links to some of my work:
  • Early in my work I have developped a Modelling and Simulation package for Classic Hierarchical DEVS in Python. You can download the prototype (.tar) and the documentation (pdf) .
  • I also started to work on a Modelling and Simulation package for the Parallel-DEVS formalism, which isn't yet completed. However you can have a look at my Structured Set module (.py). Structured (or Multivariable) Sets are used to implement bags, which are central to the Parallel-DEVS formalism. I also wrote a draft tutorial (.pdf) on how to use the module, and I worked on a formal definition (.pdf) of Structured Sets.
  • I am now working mainly on the theoretical aspects of mapping ODEs onto DEVS. More on this to come.

Objectives and Motivations

The objective is twofold:

  • Design a hierarchical specification that allows simulation experiments to be modelled, in addition to modelling the system under study.

  • Provide a concrete implementation in the DEVS formalism (classic or parallel).

    Here we view DEVS as a universal simulation (or execution) platform or Virtual Machine (VM), rather than a universal modeling formalism.

    The systems under study are either discrete (discrete time or discrete event), continuous, or hybrid (contain both discrete and continuous parts).

Description

  1. Mod/Sim Entities and their Relationships

    The usual focus in Mod/Sim is on models, the formalisms in which they are described, and how to execute (simulate) them (e.g., numerical methods for continuous models). In a complex simulation experiment (or just experiment), the control logic is usually hard-coded.

    Here we bring our focus to a higher, more abstract level: our aim is to define an abstract syntax in which experiments can be described.

    The abstract syntax defines how an experiment can be decomposed into interconnected components. The experiment ``meta-model'' will thus be specified in UML (or more precisely, Class Diagram [CD] and Object Constraint Language [OCL]), which can easily express hierarchy and modularity.

    Zeigler [10,7] identifies four different entities in the Mod/Sim framework (and also discusses their relationships, although not in the way we are interested in):

    • Source System (or System) - see also [1]
    • Experimental Frame
    • Model
    • Simulator

    We will start from those entities, whose role will be specified in detail. Other entities might also be considered (e.g., experiment control). In this context, all entities will be viewed as (or inherit from) a common basic entity.

    Some types of experiments include (see also chapter 3 of [10] for a review of Klir's Fundamental Systems Problems, and chapter 2 of [7]):

    • Simple simulation run
    • Iterated (e.g., optimization)
    • Sequential
    • Parallel, or cosimulation (e.g., agents)
    • ...

  2. DEVS Implementation

    To describe an actual experiment, we need on the one hand to provide a concrete syntax, which defines how an experiment and transformations on an experiment can be represented and manipulated in a persistent, computer-usable format.

    On the other hand, we also need to specify the semantics of an experiment (see [8] for further details): how is it interpreted (in the sense of meaning) and, by extension, how can it be implemented. This will be accomplished by providing a mapping from the experiment syntax to the DEVS formalism. The operational semantics of DEVS is well defined, and can be described in a VM (a DEVS simulator, see next item).

    In the discrete world, Balci [1] has identified four conceptual frameworks (CF, or world view, simulation strategie, formalism) ``under which the simulationist is guided for the development of a simulation model'', in a High-Level Programming Language (HLPL):

    • Event Scheduling,
    • Activity Scanning (Two-Phase Approach),
    • Three-Phase Approach,
    • Process Interaction.

    We can partially motivate the choice of DEVS as a target formalism by the fact that it provides a rigorous common basis for discrete-event modeling and simulation, by which we mean that it is possible to express in the formalism those CF's.

    More precisely, we want our target formalism to be ``low enough'' to be able to express all types of systems to be modelled, and ``as high as possible'' to be practical. It is our belief that the DEVS formalism offers just such a compromise.

    Although continuous systems cannot be expressed in the DEVS formalism, we rely, to solve such a system numerically, on some approximate mapping onto the discrete domain. It thus follows that it is possible to solve (approximately) a continuous system in DEVS. However, we would like the possibility to model continuous systems using DEVS' inherent modularity (for distribution/optimization, or to deal with ``black-boxes''). Because it is then difficult to assert numerical properties of the coupledsystem (e.g., global error), this turns out to be a difficult problem.

    An important part of the work will be concerned with that problem: how coupled continuous models can be simulated in the DEVS formalism. We might consider approaching approaching the problem with a time-slicing strategy.

    Similar problems arise in the case of hybrid systems, which involve both continuous and discrete systems. Another important issue in that case is that of monitoring functions (zero-crossing detection). A good starting point for such systems is Cellier's work [6], whose ``flowchart'' extends the event scheduling CF.

    We have previously studied the so-called quantization approach [2,4] to solve continuous systems with DEVS. Our conclusion was that the usual discretization approach is more appropriate.

  3. PyDEVS

    A modeling and simulation package for classic hierarchical DEVS with ports has been developed in Python [3]. This first prototype, imaginatively called PythonDEVS, has been used extensively by students of COMP 522A (Modelling and Simulation). It also became a target specification for DEVS-related work in MSDL (see for instance [9,5]). We consider building a newer version of the package, which would bring several improvements:

    • better encapsulation,
    • support for output translation functions,
    • better API, that would allow for instance to reset an experiment,
    • support for custom termination condition,
    • parameterizable output format,
    • possibility to save/load snapshots of a DEVS model,
    • real-time capability.

    It is not decided whether the new version will implement the classical (C-DEVS) or parallel version of the formalism (P-DEVS). Considering the amount of work that has been done using the first prototype, backward-compatibility might be an important issue.

References

[1]
Osman Balci. The implementation of four conceptual frameworks for simulation modeling in high-level languages. In Michael A. Abrams, Peter L. Haigh, and John C. Comfort, editors, Proceedings of the 1988 Winter Simulation Conference, pages 287-295, 1988.

[2]
Jean-Sébastien Bolduc and Hans Vangheluwe. Expressing ODE models as DEVS: Quantization approaches. In Fernando Barros and Norbert Giambiasi, editors, Proceedings of the AIS'2002 Conference (AI, Simulation and Planning in High Autonomy Systems), pages 163-169. Society for Modeling and Simulation International (SCS), april 2002.

[3]
Jean-Sébastien Bolduc and Hans Vangheluwe. A modeling and simulation package for classic hierarchical DEVS. Internal document for the Modelling, Simulation and Design Lab (MSDL), School of Computer Science, McGill University, 2002.

[4]
Jean-Sébastien Bolduc and Hans Vangheluwe. Mapping ODEs to DEVS: Adaptive quantization. In Proceedings of the 2003 Summer Simulation MultiConference (SCSC'03), pages 401-407, Montréal, Canada, july 2003.

[5]
Spencer Borland. Real-time pythonDEVS (pythonDEVS-RT). Internal document for the Modelling, Simulation and Design Lab (MSDL), School of Computer Science, McGill University, 2003.

[6]
François E. Cellier. Combined Continuous/Discrete System Simulation by Use of Digital Computers: Techniques and Tools. PhD thesis, Swiss Federal Institute of Technology, ETH Zürich, Switzerland, 1979.

[7]
David J. Cloud and Larry B. Rainey, editors. Applied Modeling and Simulation: an Integrated Approach to Development and Operation. Space Technology Series. McGraw-Hill, New York, NY, 1998.

[8]
David Harel and Bernhard Rumpe. Modeling languages: Syntax, semantics and all that stuff - part I: The basic stuff. Technical Report MCS00-16, The Weizmann Institute of Science, Rehovot, Israel, septembre 2000.

[9]
Ernesto Posse and Jean-Sébastien Bolduc. Generation of DEVS modelling & simulation environments. In Proceedings of the 2003 Summer Simulation MultiConference (SCSC'03), Montréal, Canada, july 2003.

[10]
Bernard P. Zeigler, Herbert Praehofer, and Tag Gon Kim. Theory of modeling and simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems. Academic Press, San Diego, CA, second edition, 2000.