Petri Nets

Recommended Citation
T. Murata, 'Petri nets: Properties, analysis and applications', Proceedings of the IEEE, vol. 77, no. 4, pp. 541-580, 1989.

By,
Tadao Murata (Fellow,  IEEE)

For,
Invited Paper


Petri nets are a graphical and mathematical modeling tool applicable to many systems. They are a favorable tool for describing and studying information processing systems that are characterized as being concurrent, asynchronous, distributed, parallel, nondeterministic and/or stochastic. As a graphical tool, Petri nets can be used as a visual-communication aid similar to flow charts, block diagrams and networks. In addition, tokens are used in these nets to simulate the dynamic and concurrent activities of the systems. As a mathematical tool, it is possible to set up state equations, algebraic equations, and other mathematical models governing the behavior of systems. Petri nets can be used by both practitioners and theoreticians. Thus, they provide a powerful medium of communication between them: practitioners can learn from theoreticians how to make their models more methodical, and theoreticians can learn from practitioners how to make their models more realistic [1].

Petri nets have been proposed for a very wide variety of applications. This is due to the generality and permissiveness inherent in Petri nets. They can be applied informally to any area or system that can be described graphically like flow charts and that needs some means of representing parallel or concurrent activities. However, careful attention must be paid to a tradeoff between modeling generality and analysis capability. That is, the more general the model, the less amenable it is to analysis. In fact, a major weakness of Petri nets is the complexity problem, i.e., Petri-net-based models tend to become too large for analysis even for a modest-size system. In applying Petri nets, it is often necessary to add special modifications or restrictions suited to the particular application [1].

Two successful application areas are performance evaluation and communication protocols. Promising areas of applications include,

• Modeling and analysis of distributed-software systems
• Distributed-database systems
• Concurrent and parallel programs
• Flexible manufacturing/industrial control systems
• Discrete-event systems
• Multiprocessor memory systems
• Dataflow computing systems
• Fault-tolerant systems
• Programmable logic and VLSl arrays
• Asynchronous circuits and structures
• Compiler and operating systems
• Office-information systems
• Formal languages
• Logic programs

Other interesting applications considered in the literature are local-area networks, legal systems, human factors, neural networks, digital filters, and decision models. 

Transition Enabling and Firing

This is the only rule one has to learn about Petri-net theory: “the rule for transition enabling and firing”. A Petri net is a particular kind of directed graph, together with an initial state called the initial marking, M₀. The underlying graph N of a Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called places and transitions, where arcs are either from a place to a transition or from a transition to a place.

In graphical representation, places are drawn as circles, transitions as bars or boxes. Arcs are labeled with their weights (positive integers), where a k-weighted arc can be interpreted as the set of k parallel arcs. Labels for unity weight are usually omitted. A marking (state) assigns to each place a nonnegative integer. If a marking assigns to place p a nonnegative integer k, we say that p is marked with k tokens. Pictorially, we place k black dots (tokens) in place p. A marking is denoted by M, an m-vector, where m is the total number of places. The pth component of M, denoted by M (p), is the number of tokens in place p.

In modeling, using the concept of conditions and events, places represent conditions, and transitions represent events. A transition (an event) has a certain number of input and output places representing the pre-conditions and post conditions of the event, respectively. The presence of a token in a place is interpreted as holding the truth of the condition associated with the place. In another interpretation, k tokens are put in a place to indicate that k data items or resources are available.

Formal Definition of a Petri Net

A Petri net is a 5-tuple, PN = (P, T, F, W, M₀) where:

A Petri net structure N = (P, T, F, W) without any specific initial marking is denoted by N.

A Petri net with the given initial marking is denoted by (N, M_O).

A state or marking in a Petri nets is changed according to the following transition (firing) rule:

1. A transition t is said to be enabled if each input place p of t is marked with at least w(p,t) tokens, where w(p,t) is the weight of the arc from p to t.
2. An enabled transition mayor may not fire (depending on whether or not the event actually takes place).
3. A firing of an enabled transition t removes w(p, t) tokens from each input place p of t, and adds w(t, p) tokens to each output place p of t, where w(t, p) is the weight of the arc from t to p

Types of Petri Nets

A transition without any input place is called a source transition, and one without any output place is called a sink transition. Note that a source transition is unconditionally enabled, and that the firing of a sink transition consumes tokens, but does not produce any.

A pair of a place p and a transition t is called a self-loop if p is both an input and output place of t. A Petri net is said to be pure if it has no self-loops. A Petri net is said to be ordinary if all of its arc weights are 1’s.

Explanation Using Example

The chemical reaction, 2H₂ + O₂ à 2H₂O

Figure a

Two units of H2 and 0, are available and the transition t is enabled.

Figure b

After firing t, the marking will change to the one shown in this figure (figure b), where the transition t is no longer enabled

One unit of O2 is still available in the O2 state, But, two units of H2O is generated consuming one unit from O2 and two units from H2

For the above rule of transition enabling, it is assumed that each place can accommodate an unlimited number of tokens. Such a Petri net is referred to as an infinite capacity net. For modeling many physical systems, it is natural to consider an upper limit to the number of tokens that each place can hold. Such a Petri net is referred to as a finite capacity net.

Motion-Based Video Games for Stroke Rehabilitation with Reduced Compensatory Motions

Recommended Citation
Alankus, Gazihan, "Motion-Based Video Games for Stroke Rehabilitation with Reduced Compensatory Motions" (2011). All Theses and Dissertations (ETDs). Paper 547.

By,
Gazihan Alankus
Washington University in St. Louis

For,
Doctor of Philosophy

Introduction

This research is done as a set of steps starting from implementing a computer aided upper arm rehabilitation project using Wii remotes and a web cameras. The researcher improves his implementation with a set of VR based single player and multiplayer games with the aim of reducing compensatory motions of the user. The researcher has dived this process into a set of sections and describe the research progressively. They first demonstrated that games and affordable game systems can be designed for effective stroke rehabilitation. Then that stroke survivors would play therapeutic games at home, daily and benefit from them. Finally, they showed that games can be designed for therapeutically correct exercise by reducing compensatory motions.

Contribution and Novelty.

They have extended the knowledge about using games for home based stroke rehabilitation that targets upper extremities. They have listed their contribution as follows,

• Finding ways of using affordable end-user devices for sensing therapeutic exercises and using them as game inputs 
• Exploring a portion of the design space of games for stroke rehabilitation 
• Developing a video game system and conducting a home-based case study to test the feasibility of including games in current outpatient therapy practice 
• Exploring ways of using video games as tools for assessing motion ability levels 
• Identifying compensatory motions as one of the major issues that reduce the quality of exercise performed using game-based stroke rehabilitation 
• Finding ways of detecting torso motions during shoulder exercises using affordable end-user devices 
• Developing a game that can detect and apply corrections for compensatory motions 
• Comparing different approaches to reduce compensation in controlled experiments as a summative study

According to the era this research was done, the researchers has used latest hardware equipment the Wii motes for th research and used a web camera for arm recognition as well.

How Does it relate into my work?

Create a table for literature review

Free-Hand Interaction with Leap Motion Controller for Stroke Rehabilitation

IEEE Citation: 

M. Khademi, H. Mousavi Hondori, A. McKenzie, L. Dodakian, C. Lopes and S. Cramer, 'Free-hand interaction with leap motion controller for stroke rehabilitation', Proceedings of the extended abstracts of the 32nd annual ACM conference on Human factors in computing systems - CHI EA '14, 2014.

Introduction

Free hand interaction, a part of human computer interaction (HCI) is a cutting-edge technology has been used for several applications including games, immersive 3D modeling, mobile augmented reality applications, air painting, writing and sketching etc. This paper use it with assistive technology to serve stroke patients. Using the suggested gaming application, the researcher has tried to explore on how leap motion sensor can be used with assistive technology in order to implement a gaming application for the rehabilitation of upper limb (also known as upper extremity) of stroke patients.

Contribution and Novelty

This research has using Free hand interaction which is one of the emerging research interests in HCI paradigm. It uses leap motion a new depth sensing device introduced lately for their application. Their contribution was to adopt a computer game called “fruit ninja” as a stroke rehabilitation application focusing the rehabilitation motor skills of finger movements of stroke patients. Their aim was to evaluate the applicability of such application for stroke rehabilitation. They proposed a kinematic model of the hand. This model allowed them to incorporate 3D parameters of the hand in tracking and made tracking more robust

How does it relates into my work?

One of the patient communities who may benefit largely from hand interaction are individuals with stroke. Previously, most researcher targeted on stroke hand rehabilitation used some wearable or robotic tools. The current trend moves to use free hand interaction for stroke rehabilitation as it has many advantages in patient’s point of view as well as technology.

The researcher has reviewed some literatures which made several attempts to enhance stroke rehabilitation with HCI technologies. They are

•  Interactive glove to foster acceptance of partners after one of them is affected by stroke and help them reunite.
•  A table top game built using windows surface hand input. The study involved exercises such as curling and uncurling fingers as well as a wrist flexion and extension of the hand back and forth about the wrist
• Point Assist: a mouse interface that adapts to a user's level of impairment in reaching and clicking.
• Hand Tutor: a glove-based treatment system which provides intensive flexion and extension movement of finger(s) and the wrist.
• Music Glove: finger movements by pressing fingers against each other to play GuitarHero.

These literature focus on mainly finger and writs rehabilitation. An advancement of hand rehabilitation. Since it’s necessary to have a wide knowledge on the topic, these literature needs to be reviewed well. Author says that these literature are example of touch, mouse, glove-based technologies that have been applied to stroke rehabilitation and using free-hand interaction as the most intuitive option to stroke rehabilitation has to be investigated.

The researcher has combined fruit ninja game with leap sensor for Finger Individuation. They have open source java version of fruit ninja game on top of the leap motion sdk where hand monitoring API resides in between. They have not mentioned further implementation details but they mentioned that they have used a model called “inverse kinematics” when recognizing hand using leap motion.

They have also pointed out the reason of using gamified tasks for rehabilitation and the advantages of them. For a stroke patient, it is quite difficult to play a typical computer game as well as a normal player. So some modifications need to be done. In here, the difficulty has been reduced removing the bombs of the fruit ninja game and a time limit was introduced in order to give a fair gaming condition which helps for a fair evaluation.

Since evaluation procedure of a research is very important while conducting a research, it necessary to have an idea on how the evaluation needs to be done at the end of a research. The evaluation of this research gives some information and advice points to do a good evaluation.

This study used only 14 stroke patients including both male and female aged 35-71. They have different stroke levels and they are calculated using Fugl-Meyer score and Box and Blocks Test score which are famous methods of estimating disability levels of stroke patients. Sot it it’s better to adopt these setting in to my research as well.

Before conducting the research, they have provided an informed consent and the patients were briefed on how to play the game. Then the subjects had a warm-up play which is not considered as a experiment trial. One subject played three times and the patient had an interval between the experiments. Then the researcher’s had given a Likert questions on a scale of 1-4 to learn about the patients' overall satisfaction.  The evaluation is being done using both test results and the answers of the questionnaire.

Advantages and Disadvantages

Advantages

• Uses latest technology: Free hand interaction and leap motion
• Robustness
• A simple hardware used: easy to set up even in a home environment.

Disadvantages

• Tracking issue: Some of the patients found out that they had difficulty individuating their index finger to make a pointing gesture. The reason is that Leap sensor assigns temporary ID’s (1-5) to different fingers.

Suggested Future work

To solve the tracking issue: To solve this problem, we propose a 3D model of the hand that includes specific ID’s for each finger and contains all skeletal parameters of the hand.

Refer the paper from ACM Digital Library: http://dl.acm.org/citation.cfm?id=2581203

Download Paper: http://mkhademi.wix.com/maryamkhademi#!publications/c1cpo