On Hybrid Petri Nets

Petrinets (PNs) are widely used to model discrete event dynamic systems(computer systems, manufacturing systems, communication systems,etc). Continuous Petri nets (in which the markings are real numbersand the transition firings are continuous) were defined morerecently; such a PN may model a continuous system or approximatea discrete system. A hybrid Petri net can be obtained if onepart is discrete and another part is continuous. This paper isbasically a survey of the work of the authors' team on hybridPNs (definition, properties, modeling). In addition, it containsnew material such as the definition of extended hybrid PNs andseveral applications, explanations and comments about the timingsin Petri nets, more on the conflict resolution in hybrid PNs,and connection between hybrid PNs and hybrid automata. The paperis illustrated by many examples.     

<Emphasis Type="Italic">SetExp</Emphasis>: a method of transformation of timed automata into finite state automata

Real-time discrete event systems are discrete event systems with timing constraints, and can be modeled by timed automata. The latter are convenient for modeling real-time discrete event systems. However, due to their infinite state space, timed automata are not suitable for studying real-time discrete event systems. On the other hand, finite state automata, as the name suggests, are convenient for modeling and studying non-real time discrete event systems. To take into account the advantages of finite state automata, an approach for studying real-time discrete event systems is to transform, by abstraction, the timed automata modeling them into finite state automata which describe the same behaviors. Then, studies are performed on the finite state automata model by adapting methods designed for non real-time discrete event systems. In this paper, we present a method for transforming timed automata into special finite state automata called Set-Exp automata. The method, called SetExp, models the passing of time as real events in two types: Set events which correspond to resets with programming of clocks, and Exp events which correspond to the expiration of clocks. These events allow to express the timing constraints as events order constraints. SetExp limits the state space explosion problem in comparison to other transformation methods of timed automata, notably when the magnitude of the constants used to express the timing constraints are high. Moreover, SetExp is suitable, for example, in supervisory control and conformance testing of real-time discrete event systems.     

Discrete port-Hamiltonian systems

Either from a control theoretic viewpoint or from an analysis viewpoint it is necessary to convert smooth systems to discrete systems, which can then be implemented on computers for numerical simulations. Discrete models can be obtained either by discretizing a smooth model, or by directly modeling at the discrete level itself. One of the goals of this paper is to model port-Hamiltonian systems at the discrete level. We also show that the dynamics of the discrete models we obtain exactly correspond to the dynamics obtained via a usual discretization procedure. In this sense we offer an alternative to the usual procedure of modeling (at the smooth level) and discretization.     

Event‐driven model predictive control of timed hybrid Petri nets

Hybrid Petri nets represent a powerful modeling formalism that offers the possibility of integrating, in a natural way, continuous and discrete dynamics in a single net model. Usual control approaches for hybrid nets can be divided into discrete‐time and continuous‐time approaches. Continuous‐time approaches are usually more precise, but can be computationally prohibitive. Discrete‐time approaches are less complex, but can entail mode‐mismatch errors due to fixed time discretization. This work proposes an optimization‐based event‐driven control approach that applies on continuous time models and where the control actions change when discrete events occur. Such an approach is computationally feasible for systems of interest in practice and avoids mode‐mismatch errors. In order to handle modelling errors and exogenous disturbances, the proposed approach is implemented in a closed‐loop strategy based on event‐driven model predictive control. Copyright © 2013 John Wiley & Sons, Ltd.     

REALIZATION THEORY OF DISCRETE-EVENT SYSTEMS AND ITS APPLICATION TO THE UNIQUENESS AND UNIVERSALITY OF DEVS FORMALISM

Many man-made systems have discrete event nature. Many modeling formalisms for discrete-event mechanisms have invented and been used for many problems. Among those models, the DEVS formalism is to provide natural and universal models in some sense.

This paper first provides a realization theory of general discrete-event systems. That is, a behavioral definition of discrete-event system is defined, and then a state transition function of the system is constructed. Based on the realization, the uniqueness problem of representations for discrete-event systems is positively solved. Furthermore, as an application of that solution, this paper shows both the fact that a legitimate DEVS with surjective internal transition function is unique up to isomorphism in the class of state representations of the state system defined from the DEVS, and the fact that any discrete-event system has a DEVS realization. In this sense the DEVS modeling facility has the uniqueness and universality in modeling discrete event mechanisms.     

Fault tolerant control design via hybrid petri nets

This paper proposes a novel fault tolerant control (FTC) scheme for hybrid systems modeled by hybrid Petri nets (HPNs). The HPNs model consists of discrete and continuous PNs. The faults are represented by unobservable discrete transitions or the normal observable discrete transitions with abnormal firing time in discrete PNs. First, an observer‐based fault diagnosis method is proposed to estimate the marking in discrete places with unknown initial marking and diagnose the faulty behavior simultaneously. Then, an adaptive fault tolerant controller is designed to maintain the general mutual exclusion constraints (GMEC) of discrete PNs, and a scheme that adjusts firing speeds of continuous transitions is provided to maintain the optimality of continuous PNs. Finally, an example of an intelligent transportation system consisting of automated vehicles on a bridge is included to demonstrate the effectiveness of our developed techniques. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Formal verification of SysML diagram using case studies of real-time system

System and software engineers use SysML models for the graphical modeling of the embedded systems. The SysML models are inadequate to express the discrete controllers with continuously evolving variables. The real-time constraints such as discrete and continuous dynamics are considered to be an important aspect in embedded systems. The lack of support of real-time aspect in SysML model can lead to inexplicit modeling of the embedded systems. The imprecise modeling could cause catastrophic results when an embedded system gets operational. In this paper, we propose hybrid automata-based semantics that supports the discrete and continuous behavior in upgraded SysML block diagram. The upgraded SysML block diagram is used for the modeling of the embedded system. Furthermore, we use model checker PRISM for the early design verification of upgraded SysML block diagram. Finally, we demonstrate the effectiveness of our proposed approach with the help of two case studies “temperature control system” and “water level control system”.

     

Tutorial and Survey Articles: An introduction to Petri Nets

This paper describes the fundamental concepts and characteristics of Petri nets (PNs) that make them a significant tool for modeling and analyzing asynchronous systems with concurrent and parallel activities and follows the extensions that improved the implementation capabilities of the original PNs.

Their first and most relevant extension was time modeling, a vital aspect of system performances not considered in the original version. There are several possibilities for introducing time in PNs. Among them, a technique that associates time with places is presented in some detail. As PNs tend to become cumbersome and time consuming when large and complex systems are involved, a method for decomposing timed PNs of open queuing networks is reviewed here.

Though initially developed as an information/computer-based technique, PNs were immediately adopted in a variety of application areas, such as manufacturing, design, planning and control. Viewed through a more recently developed programming perspective, the ordinary PNs became “high level” PNs suitable for defining different data types and for applying hierarchical approaches.

It is expected that the robust theoretical basis of this tool coupled with its visual and flexibility features will continue to appeal to researchers and practitioners alike in a variety of domains and as a result will continue to evolve and expand.     

A formal mathematical framework for modeling probabilistic hybrid systems

The development of autonomous agents, such as mobile robots and software agents, has generated considerable research in recent years. Robotic systems, which are usually built from a mixture of continuous (analog) and discrete (digital) components, are often referred to as hybrid dynamical systems. Traditional approaches to real-time hybrid systems usually define behaviors purely in terms of determinism or sometimes non-determinism. However, this is insufficient as real-time dynamical systems very often exhibit uncertain behavior. To address this issue, we develop a semantic model, Probabilistic Constraint Nets (PCN), for probabilistic hybrid systems. PCN captures the most general structure of dynamic systems, allowing systems with discrete and continuous time/variables, synchronous as well as asynchronous event structures and uncertain dynamics to be modeled in a unitary framework. Based on a formal mathematical paradigm exploiting abstract algebra, topology and measure theory, PCN provides a rigorous formal programming semantics for the design of hybrid real-time embedded systems exhibiting uncertainty.      

A survey of recursive analysis and Moore’s notion of real computation

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore’s class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230–265, 1936), Grzegorczyk (Fundam Math 42:168–202, 1955), and Lacombe (Compt Rend l’Acad Sci Paris 241:151–153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore’s class and the relationships between them.     

Self-assembly of discrete self-similar fractals

In this paper, we search for theoretical limitations of the Tile Assembly Model (TAM), along with techniques to work around such limitations. Specifically, we investigate the self-assembly of fractal shapes in the TAM. We prove that no self-similar fractal weakly self-assembles at temperature 1 in a locally deterministic tile assembly system, and that certain kinds of discrete self-similar fractals do not strictly self-assemble at any temperature. Additionally, we extend the fiber construction of Lathrop et al. (2009) to show that any discrete self-similar fractal belonging to a particular class of “nice” discrete self-similar fractals has a fibered version that strictly self-assembles in the TAM.     

Analytical derivatives technology for structural shape design

The ability to perform and evaluate the effect of shape changes on the stress and modal responses of components is an important ingredient in the “design” of aircraft engine components. The classical design of experiments (DOE)-based approach that is motivated from statistics (for physical experiments) is one of the possible approaches for the evaluation of the component response with respect to design parameters [Myers, Montgomery. Response surface methodology, process and product optimization using design of experiments. John Wiley and Sons, NY (1995)]. As the underlying physical model used for the component response is deterministic and understood through a computer simulation model, one needs to re-think the use of the classical DOE techniques for this class of problems. In this paper, we explore an alternate sensitivity-analysis-based technique where a deterministic parametric response is constructed using exact derivatives of the complex finite-element (FE)-based computer models to design parameters. The method is based on a discrete sensitivity analysis formulation using semi-automatic differentiation (Griewank, SIAM (2000), ADIFOR, Automatic Differentiation of FORTRAN codes ) to compute the Taylor series or its Pade equivalent for finite-element-based responses. Shape design or optimization in the context of finite element modeling is challenging because the evaluation of the response for different shape requires the need for a meshing consistent with the new geometry. This paper examines the differences in the nature and performance (accuracy and efficiency) of the analytical derivatives approach against other existing approaches with validation on several benchmark structural applications. The use of analytical derivatives for parametric analysis is demonstrated to have accuracy benefits on certain classes of shape applications.     

Syntax and consistent equation semantics of hybrid Chi

The hybrid χ (Chi) formalism integrates concepts from dynamics and control theory with concepts from computer science, in particular from process algebra and hybrid automata. It integrates ease of modeling with a straightforward, structured operational semantics. Its ‘consistent equation semantics’ enforces state changes to be consistent with delay predicates, that combine the invariant and flow clauses of hybrid automata. Ease of modeling is ensured by means of the following concepts: (1) different classes of variables: discrete and continuous, of subclass jumping or non-jumping, and algebraic; (2) strong time determinism of alternative composition in combination with delayable guards; (3) integration of urgent and non-urgent actions; (4) differential algebraic equations as a process term as in mathematics; (5) steady-state initialization; and 6) several user-friendly syntactic extensions. Furthermore, the χ formalism incorporates several concepts for complex system specification: (1) process terms for scoping that integrate abstraction, local variables, local channels and local recursion definitions; (2) process definition and instantiation that enable process re-use, encapsulation, hierarchical and/or modular composition of processes; and (3) different interaction mechanisms: handshake synchronization and synchronous communication that allow interaction between processes without sharing variables, and shared variables that enable modular composition of continuous-time or hybrid processes. The syntax and semantics are illustrated using several examples.     

Graph theoretic foundations of multibody dynamics

This second part of a two part paper uses concepts from graph theory to obtain a deeper understanding of the mathematical foundations of multibody dynamics. The first part (Jain in Graph theoretic foundations of multibody dynamics. Part I. Structural properties, 2010) established the block-weighted adjacency (BWA) matrix structure of spatial operators associated with serial- and tree-topology multibody system dynamics, and introduced the notions of spatial kernel operators (SKO) and spatial propagation operators (SPO). This paper builds upon these connections to show that key analytical results and computational algorithms are a direct consequence of these structural properties and require minimal assumptions about the specific nature of the underlying multibody system. We formalize this notion by introducing the notion of SKO models for general tree-topology multibody systems. We show that key analytical results, including mass-matrix factorization, inversion, and decomposition hold for all SKO models. It is also shown that key low-order scatter/gather recursive computational algorithms follow directly from these abstract-level analytical results. Application examples to illustrate the concrete application of these general results are provided. The paper also describes a general recipe for developing SKO models. The abstract nature of SKO models allows for the application of these techniques to a very broad class of multibody systems.     

Modeling problems of hybrid event dynamic systems

This paper is aiming at discussing modeling problems of hybrid event dynamic systems, which consist of continuous, discrete and inference-decision event dynamic systems. The event is the fundamental element of all kinds of event dynamic systems mentioned above. The very important meaning of the hybrid event dynamic system is that the large scale, complex and especially comprehensive systems could be abstracted as a hybrid event dynamic system, whose concept and theory are convenient for studying and analyzing them. Therefore, this paper discusses the problems about event, continuous, discrete, inference-decision and hybrid event dynamic systems and its modeling.     

Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees

Extensive facility location models in networks deal with the location of special types of subgraphs such as paths or trees and can be considered as extensions of classical facility location models. In this paper we consider the problem of locating a path-shaped or tree-shaped (extensive) facility in trees, under the condition that existing facilities are already located. We introduce a parametric-pruning method to solve the conditional discrete/continuous extensive weighted 1-center location problems in trees in linear time. This improves the recent results of O(nlog n) by Tamir et al. (J. Algebra 56:50–75, [2005]).     

A Dynamic Travel Time Model for Spillback

In this paper we introduce travel time models that incorporate spillback and bottleneck phenomena. In particular, we study a model for determining the link travel times for drivers entering a link as well as drivers already in the link but whose travel times are affected by a significant change in traffic conditions (e.g. spillback or bottleneck phenomena). To achieve this goal, we extend the fluid dynamics travel time models proposed by Perakis (1997)and subsequently by Kachani (2002), and Kachani and Perakis (2001), to also incorporate such phenomena. These models utilize fluid dynamics laws for compressible flow to capture a variety of flow patterns such as the formation and dissipation of queues, drivers’ response to upstream congestion or decongestion and drivers’ reaction time. We propose variants of these models that explicitly account for spillback and bottleneck phenomena. Our investigation considers both separable and non-separable velocity functions.     

On the Planar Piecewise Quadratic 1-Center Problem

In this paper we introduce a minimax model unifying several classes of single facility planar center location problems. We assume that the transportation costs of the demand points to the serving facility are convex functions {Q _i }, i=1,…,n, of the planar distance used. Moreover, these functions, when properly transformed, give rise to piecewise quadratic functions of the coordinates of the facility location. In the continuous case, using results on LP-type models by Clarkson (J. ACM 42:488–499, 1995), Matoušek et al. (Algorithmica 16:498–516, 1996), and the derandomization technique in Chazelle and Matoušek (J. Algorithms 21:579–597, 1996), we claim that the model is solvable deterministically in linear time. We also show that in the separable case, one can get a direct O(nlog n) deterministic algorithm, based on Dyer (Proceedings of the 8th ACM Symposium on Computational Geometry, 1992), to find an optimal solution. In the discrete case, where the location of the center (server) is restricted to some prespecified finite set, we introduce deterministic subquadratic algorithms based on the general parametric approach of Megiddo (J. ACM 30:852–865, 1983), and on properties of upper envelopes of collections of quadratic arcs. We apply our methods to solve and improve the complexity of a number of other location problems in the literature, and solve some new models in linear or subquadratic time complexity.     

Hybrid Generative-Discriminative Visual Categorization

Learning models for detecting and classifying object categories is a challenging problem in machine vision. While discriminative approaches to learning and classification have, in principle, superior performance, generative approaches provide many useful features, one of which is the ability to naturally establish explicit correspondence between model components and scene features—this, in turn, allows for the handling of missing data and unsupervised learning in clutter. We explore a hybrid generative/discriminative approach, using ‘Fisher Kernels’ (Jaakola, T., et al. in Advances in neural information processing systems, Vol. 11, pp. 487–493, 1999), which retains most of the desirable properties of generative methods, while increasing the classification performance through a discriminative setting. Our experiments, conducted on a number of popular benchmarks, show strong performance improvements over the corresponding generative approach. In addition, we demonstrate how this hybrid learning paradigm can be extended to address several outstanding challenges within computer vision including how to combine multiple object models and learning with unlabeled data.     

Numerical simulation of the motion of red blood cells and vesicles in microfluidic flows

We study the mathematical modeling and numerical simulation of the motion of red blood cells (RBC) and vesicles subject to an external incompressible flow in a microchannel. RBC and vesicles are viscoelastic bodies consisting of a deformable elastic membrane enclosing an incompressible fluid. We provide an extension of the finite element immersed boundary method by Boffi and Gastaldi (Comput Struct 81:491–501, 2003), Boffi et al. (Math Mod Meth Appl Sci 17:1479–1505, 2007), Boffi et al. (Comput Struct 85:775–783, 2007) based on a model for the membrane that additionally accounts for bending energy and also consider inflow/outflow conditions for the external fluid flow. The stability analysis requires both the approximation of the membrane by cubic splines (instead of linear splines without bending energy) and an upper bound on the inflow velocity. In the fully discrete case, the resulting CFL-type condition on the time step size is also more restrictive. We perform numerical simulations for various scenarios including the tank treading motion of vesicles in microchannels, the behavior of ‘healthy’ and ‘sick’ RBC which differ by their stiffness, and the motion of RBC through thin capillaries. The simulation results are in very good agreement with experimentally available data.