PetrA - redes de Petri

Next: Modelación con redes de Up: Introducción a las redes Previous: Introducción

Algunas definiciones

Escribimos las definiciones de una red de Petri, tomando como base el artículo de Murata [2] y utilizando la notación de Peterson; [1].

Definición 1.
Una red de Petri es un tipo particular de grafo dirigido que consiste de dos tipos de nodos (lugares y transiciones). Una red de Petri es una estructura algebráica1 $PN = (P, T, I, O)$ donde:

Los conjuntos $P$ y $T$ cumplen con $P\cap T=\emptyset$.

En la representación gráfica, la red de Petri se dibuja como un grafo con dos tipos de nodos: lugares y transiciones. Los lugares se representan como círculos y las transiciones, como barras o cajas. Un arco dirigido de un lugar $p$ a una transición $t$ define una entrada de dicha transición. Un arco dirigido de una transición $t$ a un lugar $p$ define la salida de la transición. En ocasiones es necesario colocar valores de peso a los arcos y se denota por $w(p,t)$, donde $w$ es la función

\begin{displaymath} w:(P\times T)\cup(T\times P) \rightarrow N. \end{displaymath}

Cuando un arco no tiene señalado su valor de peso, por omisión se toma con valor 1.


Definición 2.
Una marca $m$ de una red de Petri es una función $m:P\rightarrow N$, lo cual asigna a cada lugar $p\in P$ un número de tokens. La presencia o ausencia de tokens indica el estado de un lugar, y la marca de lugares representa la disponibilidad de un recurso, o la ocurrencia de operaciones.

La marca asigna a cada lugar un número entero no negativo. Gráficamente colocamos $k$ puntos en un lugar $p$, si éste tiene asociado $k$ tokens. Una marca se denota por $M$, el cual es un $m$ vector donde $m$ es el número total de lugares. La componente $p$-iésma de $M$, denotado por $M(p)$, es el número de tokens en el lugar $p$.

Cuando se modelan sistemas se toman en cuenta dos conceptos fundamentales: las condiciones y los eventos (que se generan a partir de las condiciones). Las redes de Petri representan las condiciones como lugares y los eventos como transiciones. Una transición (evento) tiene un cierto número de lugares de entrada y salida, las cuales representan las precondiciones y las postcondiciones del evento respectivamente.

El comportamiento de muchos sistemas se puede describir en términos de los estados del sistema y sus cambios. En las redes de Petri, para simular el comportamiento dinámico de un sistema, un estado o marca de la red cambia de acuerdo con las siguientes reglas de transición:

  1. Se dice que una transición $t$ está habilitada si cada lugar $p$ de entrada de $t$ tiene al menos $w(p,t)$ tokens, donde $w(p,t)$. es el peso del arco de $p$ a $t$.

  2. Una transición habilitada puede o no dispararse (dependiendo en que evento tome o no el lugar).

  3. Un disparo de una transición habilitada $t$ remueve $w(p,t)$ tokens de cada lugar de entrada $p$ de $t$, y agrega un $w(t,p)$ tokens por cada lugar de salida $p$ de $t$, donde $w(t,p)$ es el peso del arco de $t$ a $p$.

Las transiciones que no tienen lugares de entrada se les llama transiciones fuente. Una transición fuente siempre está habilitada. Por otro lado una transición sin lugares de salida consume tokens, pero no los produce.

Se dice que hay un autociclo, cuando un par de nodos, un lugar $p$ y una transición $t$, cumplen con: $p$ es entrada y salida de $t$. Una red de carece de autociclos se denomina red simple.

Un ejemplo de una transición se muestra en la figura [1]. En esta figura se muestra el resultado parcial del comportamiento poblacional de zorros y conejos, donde cada zorro hambriento debe comer 3 conejos para satisfacer su apetito. Podemos observar que la transición $t$ tiene 2 lugares de entrada --1 para los zorros hambrientos y otra para los conejos--, y uno de salida (¡para el zorro feliz!).

Figura 1: Ilustración de una regla de transición.
zorro

En la figura [1]a, se muestra que hay dos zorros y cuatro conejos disponibles, por lo que la transición $t$ se habilita. Después de que $t$ se dispara, la marca se cambia al que se muestra en la figura [1]b, y la transición $t$ ya no está habilitada. Lo que significa que después de que se ha producido el evento, queda 1 conejo, un zorro hambriento y un zorro feliz.

Observemos que las transiciones asumen que cada lugar puede almacenar un número ilimitado de tokens, es decir, se asume que cada red de Petri es una red de capacidad infinita. Sin embargo, en muchos casos de modelación es preferible tener un límite superior para el número de tokens que se pueda almacenar cada lugar. A estas redes se les considera como redes de capacidad finita y se denotan como $(PN, M_0)$, donde $M_0$ representa la marca inicial, y cada lugar de $p$ de la red tiene asociado una capacidad máxima de $k(p)$ tokens. Para que una transición $t$ de una red de capacidad finita se habilite se agrega la regla estricta de transición2, en la cual de debe cumplir que cada lugar $p$ de salida, no exceda su capacidad $k(p)$ después de disparar $t$.

PetrA | Next: Modelación con redes de Up: Introducción a las redes Previous: Introducción
ameneses@computacion.cs.cinvestav.mx / amilcar@synge.stp.dias.ie