A Graphical Environment
Previous: Introduction
We have built a software environment to aid in the design, analysis and simulation of Discrete Event and Hybrid Systems. The environment allows the user to build a system using either Finite State Machines or Petri-Nets. The environment runs under X/Motif and supports a graphical DES (Discrete Event System) hybrid controller, simulator, and analysis framework. The framework allows for the control, simulation and monitoring of dynamic systems that exhibits a combination of symbolic, continuous, discrete, and chaotic behaviors, and includes stochastic timing descriptions (for events, states, and computation time), probabilistic transitions, controllability and observability definitions, temporal, timed, state space, petri-nets, and recursive representations, analysis, and synthesis algorithms. The environment allows not only the graphical construction and mathematical analysis of various timing paths and control structures, but also produces C code to be used as a controller for the system under consideration.
Using the environment is fairly simple. For finite state machines the designer uses the mouse to place states (represented by ovals) and connect them with events (represented by arrows). Transitions and states can be added, moved and deleted easily. Figure 1 is an example of a simple stochastically timed FSM, containing 4 states and 5 events.
The probabilities on the events (that is, which path to navigate in the automaton) is designated using the mark field in the status dialog box. The different timings (on event and state times) and distribution function type, mean and variance can be assigned through the status dialog box too. The allowable distributions are currently restricted to Gaussian and exponential functions, but can be easily extended to arbitrary discrete or continuous distributions. A window shows the distribution function at a state or event, and also allows the user to do queries. For example: queries on whether a path time probability is greater or less than a give time, or combined timing distributions to reach a goal state through various paths, etc. The dialog box allows the user to perform queries of various kinds. The currently selected state/event is drawn with a dashed line, and the information in the status window pertains to it. Optimizing paths based on stochastic timing can also be performed, in that case, windows will pop out with the event path, and the status window will have the combined distribution function. Figure 2 presents an automaton model in the environment. The environment also produces C code for controlling the system under consideration.
In our PN model we have extended the definition of stochastic timed Petri Nets, to have additional timings. Our model has three times associated with it, a place time, a delay time, and an event time (see Figure 3). The place time is a time where the token is held back, and delays the enabling of the transition, this represents the computation time of that place. The delay time is a time associated with the input arcs to a transition, it represents the time to leave the corresponding place. The event time is analogous to the single time in stochastic timed Petri Nets which is called firing time. We believe that this lends to a more intuitive representation of the times, and simplifies the modeling task since it captures more details than the original timed Petri net model.
We can define the new model as:
where,
The environment for Petri-Nets is similar. Places are represented graphically by circles, transitions by ellipses, and arcs by arrows. As mentioned above, there are three locations where one can place timing information, on the events - the event time, which is the time the actual event takes, place time - when a token is moved, through a transition firing, there is a place time, which hides the token until it has expired, the final time is a delay time, this comes into effect when a transition fires, it is the time for the event to reach the transition, the event time will not start until all of its input tokens delay time has expired. Figure 4 depicts a snap shot of the Petri-Net environment in action.
The system generates C code for the user hybrid system, so one can simulate and control an actual system using the code. The C code is currently generated for FSMs (soon code will be generated for PN's too). A Petri Net will be converted to a FSM before code is generated, all of the timing is then placed on the events. The user has to select the initial state, and provide the function for simulating/generating the events, the code will keep track of the elapsed simulated time, and will return when it reaches a state with no transitions.
The environment allows conversion back and forth between the FSM and PN models.
Conversion to a Petri net is straight forward, but one looses the event
probabilities. The only thing that's needed is to create a transition for
every event. Conversion from a Petri-net to a FSM is only possible if the PN
is -bounded, which means no place can ever have more than
tokens.
The system generates a state for every possible marking of that net.
The states are represented as the marking, the events are just the
transitions. Three 3 times are pushed into the events, The system convolves
the maximum of the input delays, with the event, and the maximum
of the place times. The maximum function is a standard convolution, except
that the maximum is used instead of multiplication.
The algorithm for generating all of the markings starts with some initial marking, then goes through all of the possible transitions, if it can fire, the firing is simulated, and the new marking is inserted in the set of states, if it is already represented, the transition is kept; otherwise the transition is kept and recursion is done with the new marking. This process is repeated till no transitions can be fired.
Our system serves as much-needed graphical simulator, analyzer, synthesizer, monitor, and controller for complex hybrid systems models using either Petri nets or FSMs high-level frameworks.
A Graphical Environment
Previous: Introduction