Reseau Petri

Thèse C.A. Pétri en 1962.

- Outil de modélisation formelle

- Outil adapté à la modélisation dynamique des S.E.D.

- Outil mathématiques : Preuve des propriétés

- Outil graphique

- Simulation (PN/Design)

- Nombreuses extensions : dans notre cas Réseaux de Pétri autonomes, sinon :

 Réseaux de Pétri non autonomes, causalités (P-temporisé, T-temporisé)

 Réseaux de Pétri continus

 Réseaux de Pétri statistiques, possibilistes, probabilistes

 Réseaux de Pétri colorés

 Réseaux de Pétri flous, …

II. Formalisme de base

a. Définition

R = < P, T, Pré, Post >

P : ensemble de Places

T : ensemble de Transitions

Pré : Application P × T → ℕ: incidence avant

Post : Application P × T → ℕ : incidence arrière

Places : p est une place d’entrée de t si Pré (p, t) > 0

P est une place de sortie de t si Post (p, t) > 0

Transitions : t est une transition d’entrée de p si Post (p, t) > 0

t est une transition de sortie de p si Pré (p, t) > 0

Exemple : P = {1, 2, 3, 4, 5} et T = {a, b, c, d, e}

Pré a b c d e

1 1 0 0 0 0

2 0 1 0 0 0

3 0 0 1 0 0

4 0 0 0 1 0

5 0 0 0 1 1

Post a b c d e

1 0 0 0 1 0

2 1 0 0 0 0

3 1 0 0 0 1

4 0 1 0 0 0

5 0 0 1 0 0

b. Représentation matricielle

Pré (., t) et Post (., t) sont des vecteurs colonnes associés à une transition t.

Pré (., a) = 1

0

0

0

0

Pré (p, .) et Post (p, .) sont des vecteurs lignes associés à une place p.

c. Marquage

Permet de définir un réseau de Pétri marqué est une couple définit par un réseau de Pétri et un marquage associé N = <R, M>, couple formé par réseau de Pétri R et une application

M : P → ℕ appelé Marquage.

M(p) : marquage de la place p : nombre de marquages ou jetons contenus dans p. M est un vecteur.

M0 = 1

0

0

0

0

d. Graphe associé

Réseau de Pétri peut-être vu comme un graphe orienté biparti (P, T)

P U T est l’ensemble des sommets du graphe

Γ application multivoque de P U T → 2p U 2T

Ensemble des successeurs d’une place ou d’une transition

V : l’ensemble des valuations des arcs du graphe définie par Pré et Post

Graphe = (P, T, Γ, V)

R est défini par :

- ∀ p ∈ P, Γ (p) = {t ∈ T, Pré (p, t) > 0} = p.

- ∀ t ∈ T, Γ (t) = {p ∈ P, Post (p, t) > 0} = t.

- ∀ t ∈ T, ∀ p ∈ P, V (p, t) = Pré (p, t)

V (t, p) = Post (p, t)

En reprenant l’exemple :

Γ (1) = {a} ; Γ (2) = {b} ; Γ (3) = {c} ; Γ (4) = {d} ; Γ (5) = {d, e} ;

Γ (a) = {2, 3} ; Γ (b) = {4} ; Γ (c) = {5} ; Γ (d) = {1} ; Γ (e) = {5}

P = {x, y} et T = {a, b, c}

R = <P, T, Pré, Post>

Pré a b c

x 5 2 0

y 0 1 5

Post a b c

X 2 0 5

y 3 3 0

III. Fonctionnement d’un

...