Réseau de Petri P-temporel

Le modèle de Khansa^[1], communément appelé réseau de Petri p-temporel a été développé afin de pouvoir modéliser et analyser les systèmes à contraintes de temps et permettent la prise en compte de manière naturelle de la situation de synchronisation sous obligation^[2].

Définition

Réseau de Petri p-temporel

Un réseau de Petri p-temporel et un doublet = (R, IS) tel que :

$R$ est un réseau de Petri marqué
$IS:P\to Q^{+}\times (Q^{+}\cup \infty )$ avec $Q^{+}$

l’ensemble des nombres rationnels positifs.

    $p_{i}\to IS(p_{i})=[a_{i},b_{i}]$  avec  $a_{i}\leq b_{i}$

$IS(p_{i})$ définit l’intervalle statique associé à la place $p_{i}$ (voir la figure). La sémantique de cet intervalle est la durée de séjour admissible d’une marque dans cette place : ainsi, un jeton contenu dans la place $p_{i}$ ne participera à la validation des transitions dont $p_{i}$ est une place d’entrée que s'il a séjourné pendant au moins $a_{i}$ unités de temps. Au-delà de $b_{i}$ unités de temps, le jeton sera considéré comme mort, et de ce fait ne participera plus à la validation des transitions. L’état de marque morte est spécifique au modèle des réseaux de Petri p-temporels, de même que la notion de séquence de tir marque-vivante.

Ce dernier aspect est utilisé pour la spécification des contraintes temporelles. En fait, la mort d’une marque représente un non-respect des spécifications et correspond à un état interdit dans la terminologie qui a été définie par^[3]. Par conséquent, on est amené à contrôler les instants de tir des transitions.

Le fait d’associer les intervalles temporels aux places du réseau permet de conserver le traitement des conflits : toutes les transitions d’un conflit ont la même priorité de franchissement, comme pour les réseaux de Petri temporisés et élémentaires. Mais contrairement aux réseaux de Petri t-temporels, les temporisations n’imposent pas de contraintes sur les franchissements des transitions d’un conflit.

D’autre part, ce modèle impose que les dates d’arrivées des marques dans les places en amont des transitions de synchronisation soient compatibles, si on veut éviter la violation d’une spécification de temps de séjour, soit en d’autres termes, l’apparition de marques mortes dans le réseau.

États d’un réseau de Petri p-temporel : Pour un instant donné, la notion d’état est utilisée pour caractériser la situation du réseau p-temporel.

État d'un réseau de Petri p-temporel

L’état d’un réseau de Petri p-temporel est défini par une paire $E=<M,Q>$ , telle que :

$M$ est le marquage du réseau ;
$Q$ est une application temps de séjour qui associe à chaque jeton $k$

présent dans la place pi un nombre réel $q_{i}^{k}$ correspondant à l’âge de ce jeton, c’est-à-dire le temps écoulé depuis son arrivée dans la place.

Notons $[a_{i},b_{i}]$ l’intervalle statique associé à la place $p_{i}$ . L’âge $q_{i}^{k}$ d’un jeton doit alors être supérieur ou égal à $a_{i}$ pour qu’il puisse participer à la validation des transitions de sortie de $p_{i}$ . De même, il doit être inférieur ou égale à bi sinon le jeton sera considéré comme mort.

Condition de tir d’une transition : Une transition $t_{v}$ est potentiellement tirable à partir de l’état $E=<M,Q>$ si et seulement si :

elle est validée au sens des réseaux de Petri autonomes,
$\forall p_{i}\in t_{v}$ , il existe au moins $Pre(p_{i},t_{v})$ jetons telles que $\cap [a_{i}^{k},b_{i}^{k}]=[a_{i},b_{i}]\neq \varnothing$

avec $k\in 1,2,...,Pre(p_{i},t_{v})$ ,

$\forall p_{i}\in t_{v}$ il n’existe pas de jetons ne participant pas au franchissement de $t_{v}$ dont les bornes supérieures de l’intervalle dynamique soient

strictement inférieures à $a_{i}^{i}$ .

Sinon le réseau sera marques-mortes.

Enfin, l’intervalle d’intersection de toutes les places d’entrée de $t_{v}$ , noté $[a_{v},b_{v}]$ , doit être non-vide. Cet intervalle représente celui pendant lequel la transition est tirable.

Liens externes

Bibliographie

↑ Khansa (W.). – Réseaux de Petri P-temporels : Contribution à l’Étude des systèmes à Evenements Discrets. – Thèse de doctorat, Université de Savoie, 1997.
↑ Collart Dutilleul (S.) et Denat (J.P.). – p-time petri nets and the hoist scheduling problem. IEEE Conference on Systems, Man, and Cybernetics (SMC’98), p. 558–563. – San Diego, CA, USA, october 1998.
↑ Ramadge (P. J. G.) etWonham (W. M.). – Supervisory control of a class of discrete event processes. SIAM Journal of Control Optimization, vol. 25, n1, janvier 1987, p. 206–230.

Portail de l'informatique théorique

[1] Khansa (W.). – Réseaux de Petri P-temporels : Contribution à l’Étude des systèmes à Evenements Discrets. – Thèse de doctorat, Université de Savoie, 1997.

[2] Collart Dutilleul (S.) et Denat (J.P.). – p-time petri nets and the hoist scheduling problem. IEEE Conference on Systems, Man, and Cybernetics (SMC’98), p. 558–563. – San Diego, CA, USA, october 1998.

[3] Ramadge (P. J. G.) etWonham (W. M.). – Supervisory control of a class of discrete event processes. SIAM Journal of Control Optimization, vol. 25, n1, janvier 1987, p. 206–230.

[1]

[2]

[3]