Redes De Petri

Indice
1.
Introducción.
2. Estructura de una red de
Petri.
3. Representación gráfica
de una red de Petri.
4. Reglas de disparo para una
PN.
5. Redes de Petri
Coloreadas
6. Modelado con Redes de
Petri
7. Conclusiones

1. Introducción.

Las redes de Petri representan
una alternativa para modelar sistemas, sus
características hacen que, para algunos
problemas las
redes de Petri
funcionen de una manera natural.
Las PN como ahora conoceremos a las redes de Petri (Petri Net)
fueron inventadas por el alemán Karl Adam Petri en 1962.
En su tesis doctoral
"kommunikation mit automaten" (Comunicación con autómatas),
establece los fundamentos para el desarrollo
teórico de los conceptos básicos de las PN.
Las PN son consideradas una herramienta para el estudio de los
sistemas. Con su
ayuda podemos modelar el comportamiento
y la estructura de
un sistema, y llevar
el modelo a
condiciones límite, que en un sistema real son
difíciles de lograr o muy costosas.
La teoría
de PN ha llegado a ser reconocida como una metodología establecida en la literatura de la robótica
para modelar los sistemas de manufactura
flexibles.
Comparada con otros modelos de
comportamiento
dinámico gráficos, como los diagramas de las
máquinas de estados finitos, las PN ofrecen
una forma de expresar procesos que
requieren sincronía. Y quizás lo más
importante es que las PN pueden ser analizadas de manera formal y
obtener información del comportamiento
dinámico del sistema modelado.
Para modelar un sistema se usan representaciones matemáticas logrando una abstracción
del sistema, esto es logrado con las PN, que además pueden
ser estudiadas como autómatas e investigar sus propiedades
matemáticas.
¿Qué tipo de sistemas podemos modelar con las PN? Y
¿Cómo logramos la analogía entre el sistema
real y el modelo usando
una PN? son dos de las preguntas a las que debemos atender. Para
esto pongamos atención a los sistemas: una idea
fundamental en un sistema es que se compone de módulos que
interactúan entre sí, los cuales pueden ser
considerados por si mismos un sistema, y podríamos
estudiar su comportamiento por separado y de esta manera
aislarlos, pero siempre teniendo en cuenta la interacción
que guardan con los otros módulos.
Ahora deseamos conocer en que condiciones se encuentran los
módulos, es como si detuviéramos al sistema en el
tiempo, las
condiciones internas de los módulos determinarían
el estado en
el que se encuentran, para esto entendemos que un sistema es un
arreglo dinámico que en el transcurso del tiempo tiene
variaciones y no permanece estático. El estado de un
módulo con frecuencia depende de su historia, es decir de las
acciones dadas
en un tiempo anterior.
Hablemos de dos conceptos importantes: acciones y
estados, las acciones nos conducen a un estado
determinado del módulo en el tiempo, las acciones de un
módulo en un sistema pueden ocurrir simultáneamente
con las acciones de otros módulos, dado que ellos
interacúan entre sí, es necesario sincronizar los
eventos. Esto
puede resultar en que las condiciones de un módulo en el
tiempo necesitan como entradas las salidas de otro, él
cual necesita más tiempo para generar las salidas, es
entonces cuando pensamos en paralelismo y concurrencia. Las PN
fueron diseñadas específicamente para modelar este
tipo de sistemas.
Tomemos dos conceptos más: eventos y
condiciones, los eventos son las acciones que se dan en el
sistema y nos llevan a un estado, podemos describir un estado
como un conjunto de condiciones. Es útil, para nuestro
caso, representar dichas condiciones por medio de predicados.
Para que cierto evento ocurra es necesario que ciertas
condiciones se cumplan, estas son llamadas pre-condiciones del
evento, la ocurrencia del evento nos puede llevar a otras
condiciones y es entonces cuando se dan las post-condiciones.
Para modelar un sistema en una PN debemos reconocer las
condiciones y los eventos que se dan en él, de esta manera
podemos hacer la analogía entre el sistema y el modelo, al
conocer las condiciones que se necesitan para dar cierto evento
podemos diseñar los módulos y relacionarlos con
otras condiciones, y para esto necesitamos saber la estructura de
una PN para saber que corresponde a una condición y un
evento en la red.

2. Estructura de
una red de
Petri.

Las PN se componen de cuatro partes:

• Un conjunto de nodos.
• Un conjunto de transiciones.
• Una función
  de entrada y
• Una función
  de salida.

Las funciones de
entrada y salida relacionan a los nodos y a las transiciones. La
función de entrada es un mapeo de una transición
tj a una colección de nodos conocidos como los
nodos de entrada de una transición. La estructura de una
PN es definida por los nodos, las transiciones, la función
de entrada y la función de salida.
Definición: La estructura de la PN P=(P,T,I,O) donde:}
P={p1,p2,…,pn} es un
conjunto finito de nodos, con n³ 0.
T={t1,t2,…,tm} es un
conjunto finito de transiciones con m³ 0.
PÇ
T= Æ

I,O: T ®
P

Un nodo pi es un nodo de entrada de la
transición tj sí pi
Î
I(tj); pi es un nodo de salida
sí pi Î O(tj). Las entradas y salidas
de una transición son conjuntos que
tienen elementos repetidos o múltiples ocurrencias de
nodos (bags). La multiplicidad de un nodo de entrada
pi para una transición tj es el
número de ocurrencias del nodo en el bag de entrada de la
transición. Escribimos esto como:
#(pi,I(tj)). De igual forma para la salida
lo cual escribimos: #(pi,O(tj)).

Ejemplo:
P=(P,T,I,O)
P={p1,p2,p3, p4,
p5} T={t1,t2,t3,
t4, t5}
I(t1)
={p1} O(t1)={p2,
p3, p5}
I(t2) ={p2, p3,
p5} O(t2)={p5}
I(t3)
={p3} O(t3)={p4}
I(t4) ={} O(t4)={p2,
p3}
I(t5)
={p4} O(t5)={p2,
p3}
Donde:
#(p3,I(t2))=1
#(p5,O(t1))=1

Una marca U es una
característica de la PN, marca U es una
asignación de tokens a la PN. Un token es un concepto
primitivo de una PN, un número de ellos reside en los
nodos y se mueve entre ellos; los tokens son la parte dinámica de la PN, su número puede
variar entre nodos y son los que determinan la situación
de la red en un momento
determinado.
Definición: Una marca U de una PN P=(P,T,I,O) es una
función U: P ® N.
Es decir el nodo pi tiene U(pi) tokens.
La PN puede ser considerada también como un modelo de
flujo de información, en donde el comportamiento
dinámico de los tokens representan el flujo. Dicho de otra
manera la información depende de lo que la PN esta
modelando.

3.
Representación gráfica de una red de
Petri.

La representación gráfica de una PN es
importante porque al observar el modelo del sistema en forma
gráfica y observar como cambia de un estado a otro puede
mantener la atención y dar una perspectiva más
clara a quién esté analizando el problema.
Definición: Una gráfica G de una PN P=(P,T,I,O) es
una gráfica múltiple bipartita dirigida G=(V,A)
donde V={ v1, v2, …, vn}
es un conjunto de vértices y A={ a1,
a2, …, an} es un conjunto de arcos
dirigidos ai=(vj,vk) con
vj, vk Î V, V=PÈ T para cada ai
Î A se cumple
aj=(vj,vk) Þ vj
Î P,
vk Î
T, ó vj Î T, vk Î P.

Un circulo O
representa un nodo; una barra | representa una transición. Los
arcos o curvas conectan los nodos y las transiciones, si un arco
va de un nodo a una transición, el nodo será una
entrada y si el arco va de una transición a un nodo, el
nodo será una salida de esa transición. Los tokens
son representados por pequeños puntos · .

Ahora consideremos la PN vista anteriormente:
P=(P,T,I,O)
P={p1,p2,p3, p4,
p5} T={t1,t2,t3,
t4, t5}
I(t1)
={p1} O(t1)={p2,
p3, p5}
I(t2) ={p2, p3,
p5} O(t2)={p5}
I(t3)
={p3} O(t3)={p4}
I(t4) ={} O(t4)={p2,
p3}
I(t5)
={p4} O(t5)={p2,
p3}
Donde:
#(p3,I(t2))=1
#(p5,O(t1))=1

4. Reglas de disparo
para una PN.

La ejecución en una PN es controlada por el
número y distribución de los tokens que tiene. Los
tokens presentes en los nodos controlan la ejecución de
las transiciones de la red. Una PN se activa disparando
transiciones. Una transición es disparada removiendo
tokens de los nodos de entrada y creando tokens de salida. De
aquí podemos obtener la primera condición de
disparo en una transición: todos los nodos de entrada de
la transición, deben tener al menos el mismo número
de tokens, que de arcos que van hacia la transición, para
que ésta sea disparada, cuando la transición cumpla
esta condición se dice que es una transición
ENABLED.
Definición: Una transición tj
Î T en una PN
P=(P,T,I,O) con una marca U es ENABLED si para todo
pj Î
P, U(pj)>=#(
pj,I(tj)).
Por ejemplo una transición t3 con
I(t3)={p3} y
O(t3)={p4} es ENABLED sólo cuando
p3 tiene al menos un token. Cuando t3 es
disparada sólo un token es quitado a p3 y un
token es depositado en p4 (sí tuviera
más nodos de salida, depositaria un token en cada uno de
ellos). Es decir por cada arco de salida es liberado un
token.

Consideremos la siguiente PN:
Sólo 3 transiciones están en un estado ENABLED
t1, t3, t4. La transición
t2 no puede ser disparada porque no hay tokens en el
nodo p2, el cual es entrada de ella. Dado que
t1, t3 y t4 son ENABLED
cualquiera de ellas puede ser disparada. Podemos asociar de
manera natural un vector u enlistando los valores de
U. Así para la PN mostrada tenemos u=(1,0,2,1,0).
Sí la transición t4 es disparada,
remueve tokens de cada entrada y los deposita en cada salida,
entonces remueve un token de p4 y deposita un token en
p2 e incrementa el número de tokens en
p3 de dos a tres; el vector u sería (1,1,3,0,0)
y el estado de
la red se mueve a como se muestra en la
siguiente figura.
Las transiciones pueden seguir disparándose
indefinidamente hasta llegar a un estado deseado o hasta que
ninguna pueda ser disparada.

De lo anterior surgen dos preguntas:
¿Cómo decidimos que transición debe
dispararse?
¿Porqué no podemos disparar dos transiciones al
mismo tiempo?
Decidir que transición debe dispararse depende de nuestro
modelo y sí podemos disparar más de una
transición en un mismo instante entonces estamos hablando
de paralelismo.
Pensemos en un ejemplo concreto:
queremos sumar cuatro números cualesquiera por medio de
una PN. Dependiendo de cada número se ponen tantos tokens
en los nodos correspondientes p1, p2,
p3 y p4. Los primeros resultados parciales
se almacenan en p5, y los últimos en
p6, una transición para cada nodo es la que se
encarga de quitar unidades en los sumandos y poner unidades en el
resultado, cuando se efectúan las dos sumas, se realiza
una tercera suma, la realizan t5 y t6, su
resultado se pone en p7. El orden en el que se
realizan las operaciones no es
un orden secuencial ya que la primer suma puede ocurrir
indistintamente de las sumas anteriores.

5. Redes de Petri
Coloreadas

Las redes de Petri coloreadas (CPN) pertenecen a
la familia de
las PN, la diferencia viene marcada por las consideraciones en
CPN de colores y de
funciones
lineales asociadas a sus arcos. Los tokens de color pueden
representar un atributo o distintivo, si es necesario definir dos
atributos entonces surge la idea de colores
compuestos. Una transición en CPN está en estado
ENABLED si todos sus nodos de entrada contienen un número
de colores igual o mayor que los definidos por
fi<c> donde fi es una función
lineal asociada al nodo pi con la transición
tj. Entonces además del concepto de
color, estas
redes manejan una función asociada para los elementos de
las funciones I,O de la PN.
Es fácil ver en una Red las transiciones que están
ENABLED y observar que a veces son más de dos transiciones
las que se pueden disparar, en la siguiente figura notamos que
t1 y t2 pueden dispararse, pero si
t1 es disparada, t2 dejará de ser
ENABLED y si disparamos t2, no podremos disparar
t1. Esto es conocido como un conflicto y
nos ayuda a modelar problemas de
sincronización.

Extensiones al Modelo de Redes de Petri
Un arco inhibidor es otro componente de una PN, éste va de
un nodo a una transición y es representado con un
pequeño circulo al final del arco. La transición
que tiene arcos inhibidores no puede dispararse si el nodo de
entrada contiene por lo menos tantos tokens como la multiplicidad
del arco inhibidor. Así por ejemplo la siguiente figura
disparará cuando p1 tenga un token, y
p2 no tenga tokens.
En general las extensiones a la teoría
de PN dependen del modelo o la aplicación donde se
estén usando.

Redes de Petri Temporales.
Este tipo de redes son las que consideran el tiempo en el modelo.
Es una consideración importante ya que los sistemas reales
casi siempre es indispensable considerarlo en la
sincronización de los procesos.
El modelo más simple es el que asigna duración
a:

1. Los nodos, en el sentido de que una condición
   es verdadera para una cierta cantidad de tiempo.
2. La transición, en el sentido de que un evento
   toma una cierta cantidad de tiempo en ocurrir.

Cuando la duración de los eventos no son fijos, o
no pueden ser expresados con valores
nominales, simplemente se estiman límites
dentro de los cuales el evento puede ocurrir.

6. Modelado con Redes de
Petri

Eventos y condiciones.
Podemos modelar sistemas complejos con PN, dividiendo el sistema
en eventos y condiciones y de esta manera encontrar la
analogía con la PN. Se toma como referencia que las
condiciones que se dan en un sistema, son representadas por los
nodos, ya que los tokens indican si esta condición se
cumple o no, y los eventos con las transiciones, que necesitan de
condiciones para poder ser
disparadas.

Consideremos el siguiente sistema: Un taller que tiene
tres máquinas,
M1,M2 y M3, y dos operadores O1 y O2. El operador O1 puede
trabajar las máquinas M1 y M2 y el operador O2 las
máquinas M1 y M3. Las ordenes requieren de dos procesos,
el primer proceso debe
ser hecho por la máquina M1 y el segundo proceso puede
ser hecho con la máquina M2 o la M3. Enlistemos las
condiciones y los eventos:

La PN se muestra a
continuación:

El problema de los cinco filósofos.
Este problema puede dar una idea clara del potencial de una PN,
el problema consiste de cinco filósofos que en forma alternada piensan y
comen.
Están sentados en una mesa circular donde ha sido
depositada comida china, cada
filósofo tiene frente a él un plato donde servirse
y entre cada uno de ellos un palillo chino. Como sabemos, para
comer comida china
necesitamos dos palillos, entonces cada filósofo para
comer debe tener dos palillos en su poder.
El problema está en que si cada filósofo tiene un
sólo palillo en su poder todos los filósofos
entrarán en una espera eterna para comer, otro problema
puede surgir y es el que un filósofo obtenga siempre los
dos palillos y se mantenga comiendo, lo que producirá que
los otros filósofos no puedan comer (cayendo en un estado
de inanición). Analicemos los eventos y condiciones de
este problema así como las precondiciones y
postcondiciones para un sólo filósofo y luego para
más.

Sí ahora se trata de dos filósofos se
obtendrá lo siguiente:

Como sabemos las condiciones corresponden a nodos y los
eventos a transiciones, las condiciones 1 y 3, 2 y 4 pueden
modelarse con un sólo nodo. El problema para cinco
filósofos es modelado como se muestra en la siguiente
figura. Los nodos P1,.,P5 representan los palillos, al inicio
cuando todos los filósofos piensan, cada nodo tiene un
token. Cada filósofo es representado por dos nodos M y C
representan los estados meditando y comiendo respectivamente.
Para que un filósofo coma es necesario que tenga los dos
palillos en sus manos, entonces sus dos nodos deben tener un
token y de esta manera poder comer.

7.
Conclusiones

• Podemos concluir diciendo de que las Redes de Petri
  son una alternativa de modelado de sistemas, aplicados
  principalmente hacia el control y
  proceso, por su facilidad de manejo en el problema de la
  sincronización de procesos.
• También se dijo que constan de cuatro
  partes:
• Nodos
• Transiciones
• Funciones de entrada
• Funciones de salida
• Las entradas y/o salidas de una transición son
  conjuntos
  que pueden tener elementos repetidos o múltiples
  ocurrencias.
• Cuentan con una asignación de tokens que es la
  parte dinámica de las Redes de
  Petri.
• Las Redes de Petri se pueden representar
  gráficamente, un circulo O representa un nodo y una barra
  | representa una
  transición, y los tokens son representados por
  pequeños puntos · .
• Las Redes de Petri tienen reglas de disparo, siendo
  la principal, la que dice: "todos los nodos de entrada de la
  transición, deben tener al menos el mismo número
  de tokens, que número de arcos van hacia la
  transición para que ésta sea disparada". Cuando
  la transición cumple dicha condición se dice que
  es ENABLED.
• Existen extensiones a las Redes de Petri: por ejemplo
  las Redes de Petri Coloreadas (PNC), las Redes de Petri
  Temporales, Redes de Petri Estocásticas.
• Podemos modelar los sistemas dividiéndolos en
  eventos y condiciones. Las condiciones son representadas por
  los nodos, y los eventos por las transiciones.

Autor:

Mabel Gonzales Urmachea