In this report we present an overview for the development of a theory for discrete event dynamic systems(DEDS). Dynamic systems (DEDS). Dynamic systems are ususally modeled by finite state automata with partially overvable events together with a mechanism for enabling and disabling a subset of state transitions. DEDS are attracting considerable interests, current applicationsare found in manufacturing systems, communications and air traffic systems, future applications will include robotics, computer vision and AI. We will discuss notions of modeling, stability issues, observability , feedback and ivertibility. We will also discuss the perturbation analysis techinque (PA) for analyzing and describing the behaviour of DEDS

What is a Discrete event dynamic system ?

Discrete event dynamic systems (DEDS) are dynamic systems (typically asynchronous) in which state transitions are triggered by the occurence of discrete events in the system. Many existing dynamic system have a DEDS structure, manufacturing systems and communication systems are just two of them. The state space approach in representing and analyzing such systems will probably lead to more applications that might be incorporated into the framework of DEDS. It will be assumed in the development of the state space approach of analyzing DEDS that some of the events in the system are Controllable, i.e, can be enabled or disabled. The goal of controlling DEDS is to "guide" the behaviour of the system in a way that we consider "desirable". It is further assumed that we are able to observe only a subset of the event, i.e, we can only see some of the events that are occuring in the system and not all. In some cases we will be forced to make decisions regarding the stat of the system and how to control a DEDS based upon our observations only.

The notions of stability and the possibility of stabilizing a discrete event dynamic system.

In Particular, we are going to concentrate on stability notions with respect to the states of a DEDS automation. Assuming that we have identified the set of "good" states, E, that we would like our DEDS to "stay within" or donot stay outside for an infinite time, the problem would reduce to:

• Checking out whether all trajectories from the other states will visit E infinitely often.
• Trying to "guide" the system using the controllable events in a way such that the system will visit the "good" states infinitely often.

We shall start by defining and testing for different notions of stability and then discuss ways to stabilize a system. We shall start by assuming that a DEDS model under consideration is an uncontrolled system with perfect knowledge of the state and event trajectories ( ), to simplify the definitions and examples.

To capture the idea of stability, we can suppose that we have already identified a subset of states E in X that returning to E implies being in a position to continue desired behaviour from that point on. We can define that notion of a state in the DEDS being stable with respect to E in two stages. The first stage will be weaker notion and will be termed pre-stability.We say that x belonging X is pre-stable if all paths from x can go to E in a finite number of transitions, i.e, no path from x ends up in a cycle that does not go through E.

In Figure x31, states 0,2,3, and 4 are pre-stable, since all transitions from them can goto {0,3} in a finite number of transitions. State 1 is not pre-stable since it will stay forever outside E if an infinitely long string of Delta's occurs.

A definition of pre-stability can be formalized as follows:Given a live system A and some E part of X , a state x belonging to X is pre-stable with respect to E (or E-pre-stable) if for all x belonging X (A,x) such that |x|>=n, there exists y belonging x such that y belongs to E. We say that a set of states is E-per-stable if all its elements are E-pre-stable and a system A is pre-stable if X is E-pre-stable.

In this section we address the problem of determining the current state of the system.In particular, we are interested in observing a certain sequence of observable events and making a decision regarding the state that the DEDS automation A might possibly is in. In our definition of observability, we visualize an intermittent observation model, no direct measurements of the state are made, the events we observe are only those that are in lamda belonging sigma, we will not observe events in sigma union not lamda and will not even know that any of which has occured. State ambiguities are allowed to develop (which must happen if sigma not equal to lamda) but they are required to be resolved after a bounded interval of events.This notion of observability can be illustrated graphically as in Figure x41

A simple example.

In figure x42 and x43 a simple system and its observer are illustrated. It can be seen that the observer will never know when will the system be in states 3,4 or 5, since the events that takes the system to those events are unobservable, namely delta and gama. There are two states in the observer which are ambiguous, however, another two states are singleton states, i.e, when observer reaches them, we'll know the exact state that the DEDS is currently in.

A project 'DEDS' to determine stability, pre stability , observability a DEDS system. DEDS, Discrete Event Dynamic Systems are dynamic systems (typically asynchronous) in which state transformations are triggered by the occurance of discrete events in the system. It is assumed that some of the events are controllable i.e., enabled or disabled . The goal of the DEDS system is to guide the behaviour of the system in a way that we consider desirable. It is further assumed that we are able to observe only a subset of the event, i.e., we can only see some of the events that are occuring in the system and not all.The issues considered in the development and their explanation is given in the following pages.

Stability: If a set of good states are known also known as good states, E, that we would like the DEDS to stay within or donot stay outside for an infinite time.So for each of the states The automated system will be able to tell whether any of the states are stable with respect to the reported good states. the advantage of the automation is we can change the good states at will and check to see the affect they have on the stability of a particular state or event. This rule also applies to states themselves whose events we can change at will to determine the change in their stabilty with respect to the good states.Stability of a state is determined using the following methods.checking out whether all trajectories from the other states will visit E infinitely often Trying to guide the system using the controllable events in a way such that the system will visit the good states infinitely often.

Pre stability: When x belonging to X is pre-stable if all paths from x can go to E in a finite number of transitions, i.e., no path from x ends up in a cycle that does not go through E. The definition of pre-stability can be formalized as follows: Given a live system A and some E belonging to X, a state x belonging to X is pre- stable with respect to E (or E-per-stable) if for all x belonging to X such that |x| >= n, there exists y belonging to x such that y belongs to E. We say that a set of states is E-pre-stable if all its elements are E-pre-stable and a system A is pre-stable if X is E-pre-stable.

Observability: It is assumed that all events are not observable.The events that are considered as observable are those observable events in the system.Since it is not desirable to have the system generate arbitrarily long sequence of unobservable events in network. A necessary condition to gaurantee this is that the automation after removing the observable events must not be alive.

Understanding the DEDS project

More examples of input and corresponding output files are explained and shown here for additional clarification. The working of DEDS project and its interface is also explained in the README.DOC, is a must read if you are planning to use the project for further easing of the utilisization of Dynamic Event Discrete System Project.

Further reading on the topic can be obtained from Professor Tarek M. Sobh, University of Bridgeport. The IEEE Robotics and Automation Society DEDS Technical Committee is chaired by Professor Tarek M. Sobh, University of Bridgeport, and Professor Kimon Valavanis of the University of Toronto.

Kanniganti Radesh , B.Tech, (M.S.) , Computer Engg, University of Bridgeport.

Choices:

Figures: