Un réseau de Petri coloré (, CPN) est un réseau de Petri dans lequel les jetons peuvent être distingués par des valeurs, appelées « couleurs ».
Les réseaux de Petri colorés sont un formalisme mathématique permettant de représenter et d’analyser des systèmes dynamiques complexes. Par rapport aux réseaux de Petri classiques, ils permettent notamment de distinguer et de manipuler plusieurs types d’objets ou de données au sein d’un même réseau.
Le formalisme des réseaux de Petri colorés a été développé à la fin des années 1970 par le chercheur danois , notamment dans le prolongement des réseaux prédicat/transition proposés par Hartmann J. Genrich et Kurt Lautenbach.
Définition mathématique
Un réseau de Petri coloré peut être défini par un tuple
où :
est un ensemble fini de places ; est un ensemble fini de transitions, tel que est un ensemble fini d'arcs orientés ;
est un ensemble fini de types de couleurs, chaque type correspondant à un ensemble non vide de valeurs possibles ;
est un ensemble fini de variables typées. À chaque variable est associé un ensemble de couleurs appartenant à ; est la fonction de couleur, qui associe à chaque place un type de couleur ; est la fonction de garde, qui associe à chaque transition une expression booléenne. Une transition ne peut être franchie que si sa garde est évaluée à vrai ; est la fonction d'expression des arcs, qui associe à chaque arc une expression déterminant les jetons consommés ou produits lors du franchissement d'une transition ; est la fonction d'initialisation, qui associe à chaque place une expression définissant son marquage initial. Cette expression doit produire un multiensemble de jetons dont les couleurs correspondent au domaine associé à la place.
Un marquage décrit l'état du réseau à un instant donné en associant à chaque place un multiensemble de jetons dont les couleurs appartiennent au type .
Remarque. Le marquage initial résultant de la fonction d'initialisation est souvent noté .
Franchissement des transitions
Une transition est dite tirable lorsque sa garde est évaluée à vrai et que les jetons requis par ses arcs entrants sont disponibles dans le marquage courant.
Pour formaliser cette évaluation, les réseaux de Petri colorés utilisent la notion de liaison ( binding). Une liaison associe une valeur à chacune des variables utilisées par la transition. Ces valeurs permettent d'évaluer conjointement la garde et les expressions des arcs, et donc de déterminer les jetons qui doivent être consommés pour que la transition puisse être tirée.
Lors du tir, ces jetons sont consommés dans les places d'entrée et les jetons définis par les expressions des arcs sortants sont produits dans les places de sortie.
Pour une transition et une liaison , on note l'évaluation de la garde de sous cette liaison. Cette évaluation produit une valeur booléenne :
avec :
Une transition est tirable sous une liaison si sa garde est vraie :
et si, pour chaque arc entrant , le multiensemble de jetons requis par l'expression de l'arc est contenu dans le marquage de la place :
L'inégalité désigne ici l'inclusion entre multiensembles : chaque jeton requis par doit être présent en quantité suffisante dans .
On appelle élément de liaison ( binding element) un couple formé d'une transition et d'une liaison possible pour cette transition. L'ensemble des éléments de liaison est noté :
où l'ensemble des liaisons possibles de dans le marquage peut être défini par :
Un pas ( step) est un multiensemble d'éléments de liaison :
Le pas est conjointement tirable dans le marquage si, pour chaque élément qu'il contient,
et si les jetons requis par l'ensemble des éléments de liaison sont simultanément disponibles :
Le coefficient représente la multiplicité de l'élément de liaison dans le pas .
Exemple : tri de bagages dans un aéroport
Un exemple simple d'utilisation des réseaux de Petri colorés consiste à modéliser le système de traitement des bagages d'un aéroport. Chaque bagage doit être acheminé vers la zone de chargement correspondant à son vol. Les couleurs permettent de représenter l'identité et la destination des différents bagages sans devoir créer un réseau distinct pour chaque destination.
On considère, par exemple, trois destinations :
et un ensemble d'identifiants de bagages :
Le type de couleur associé aux bagages peut alors être défini par le produit cartésien :
Un jeton de couleur représente ainsi le bagage destiné à Nantes.
Le réseau comporte une place , contenant les bagages en attente de tri, ainsi qu'une place pour chacune des destinations :
Toutes ces places sont associées au type de couleur .
Une transition représente l'opération de tri. Lors de son franchissement, un bagage est retiré de puis placé dans la place correspondant à sa destination. L'expression associée à chaque arc de sortie dépend donc de la couleur du jeton. Par exemple, l'arc conduisant à produit le jeton si :
Le même principe s'applique aux destinations et .
Un marquage initial possible est :
Les autres places sont initialement vides. Après le tri de tous les bagages, le réseau peut atteindre le marquage :
et
Cet exemple illustre l'intérêt des couleurs : une même structure de réseau peut manipuler des bagages ayant des identités et des destinations différentes, ces informations étant portées directement par les jetons.
Remarque. Dans un système réel de traitement des bagages, le temps constitue également une contrainte importante, puisqu'un bagage doit atteindre sa zone de chargement avant le départ du vol correspondant. Cette contrainte peut notamment être représentée à l'aide de réseaux de Petri temporisés ou de réseaux de Petri colorés temporisés.
Notes et références
Voir aussi Articles connexes Réseau de Petri Réseau de Petri temporisé Réseau de Petri temporel Réseau de Petri hiérarchique coloré
Workflow net
R Catégorie:Méthode formelle