A) Definición de una red de Petri (PN):
Una Red de Petri (PN), es un dígrafo bipartido, el cual contiene dos tipo de nodos: los lugares “P” (representados por círculos) y las transiciones “T” (representadas por barras o triángulos), además los nodos están relacionados por arcos orientados (representados por fechas), que se unen nodos de diferentes tipos (dígrafo bipartido). La Figura 4 muestra como se representan gráficamente los componentes de una red de Petri, en la Figura 5 podemos observar una red de Petri, que integra estos elementos.
El número de arcos que unen dos nodos puede ser cualquiera; por convención, los arcos múltiples se denotan gráficamente anotando el número de multiplicidad o pesos (cuando es diferente de 1).
Si todos los pesos de los arcos tienen pesos unitarios, entonces se dice que la PN es una “Red Ordinaria”. En Figura 5 se muestra un ejemplo de una red de Petri “Ordinaria”.
Figura 5. Red de Petri Ordinaria
Una red de Petri en la cual no todos los arcos tienen un peso unitario se le conoce como “Red Generalizada”. En la Figura 6 podemos ver la misma red de Petri generalizada, representa de dos maneras diferentes, en donde hay tres arcos que van del lugar P2 a la transición T1. Y es precisamente la segunda forma, en donde el arco que va de P2 a T1, tiene un 3 (indicando que son tres arcos en realidad), la que se emplea habitualmente.
Figura 6. Redes de Petri generalizada.
La Figura 7 muestra subestructuras que pueden encontrarse en una red de Petri. En (a) se ilustra como especificar un conjunto de condiciones que deben de cumplirse para iniciar una actividad o proceso; en (b) muestra que es posible llegar a una misma situación por diferentes caminos; en (c) ilustra una situación de toma de decisiones, en (d) describe como se puede iniciar varias actividades simultáneamente.
Figura 7. Sub-estructuras que se pueden encontrar en una red de Petri.
Red de Petri Marcada
Una PN presenta un comportamiento dinámico, para eso se ayuda del marcado. Las marcas están contenidas en los lugares y son representadas gráficamente por puntos (ver Figura 5 y Figura 6). Cuando un número de marcas dentro de un lugar es relativamente grande, se inscribe un entero.
La distribución de marcas en un instante dado se denomina marcado y es análoga a la noción de estado estable. Una red de Petri con marcas recibe el nombre de red de Petri marcada.
Se define el marcado inicial como el conjunto de lugares marcados al inicio de una ejecución de la red de Petri.
Evolución de una red de Petri:
El comportamiento dinámico de un sistema puede describirse mediante la evolución de las marcas en la red. Aquí las transiciones juegan un papel importante pues cada una de ellas está encargada de “mover” desde sus lugares de entrada, hacia sus lugares de salida, esto es posible cuando ocurre el disparo de una transición. Una transición puede dispararse “ssi” (sí y solo sí9 está habilitada, es decir todos sus lugares de entrada tienen o almacenan marcas: tantas o más, como el peso del arco que une cada lugar de transición en cuestión. Al dispararse una transición cada lugar de la transición en cuestión. Al dispararse una transición, cada lugar de entrada pierde el número de marcas que indica el pero del arco, y cada lugar de salida gana marcas según indique el peso del arco. En la Figura 8 se muestra como evoluciona el marcado. En (a) se muestra el marcado inicial, note que el peso del arco de P3 es de 2 y el peso del arco de P4 es de 2; esto será importante cuando se dispare la transición T1, en (b) se muestra como queda el marcado después de dispararse T1. Observemos como P1 y P2 pierden 1 marca mientras P3 pierde dos, y por otro lado P4 gana 2 marcas, mientras que P5 solo gana 1.
Figura 8. Evolución del marcado inicial al dispararse la transición T1.
Red de Petri Interpretada [13]
En el modelado de sistema de eventos discretos con redes de Petri los lugares, las transiciones y las marcas toman un cierto significado acorde al contexto del sistema que se desea modelar.
· Los lugares pueden representar recursos, operaciones, estados, etapas de un proceso.
· Las Marcas representan la disponibilidad de los recursos, la orden de ejecución de operaciones, información transmitida, etc.
· Las Transiciones tienen asociados eventos tales como el inicio o fin (o ambos) de actividades, comandos, información relevante del entorno.
Aquí las condiciones de disparo se ven modificadas ligeramente, ya que para que se dispare una transición además de estar habilitada, el evento o condición asociados deben de cumplirse.
Una Red de Petri a la cual se le ha asociado un significado a sus componentes se le llama red e Petri interpretada.
B) Estructura de una red de Petri:
Las redes de Petri (PN) también tienen una representación matemática, la cual puede ser manipulada por una computadora.
Una Red de Petri (G) es un dígrafo bipartido representado por una cuatupla:
G=(P,T,I,O)
Donde:
P = {P1, P2,…….., Pn}. Es un conjunto finito de vértices llamados lugares.
T={t1, t2, ….tn}. Es un conjunto finito de vértices llamados transiciones.
I, (también conocida como Pre): PxT " N es una Función de incidencia previa la cual representa los pesos de los arcos de entrada a las transiciones.
O (también conocida como Post): PxT " N es una Función de incidencia posterior la cual representa el peso de los arcos de salida de las transiciones.
Para una PN Ordinaria, la función de incidencia mapea elemento P x T " {0,1}; a diferencia de la red generalizada que lo hace de P x T " N
Además tenemos que P I T = 0 (la intersección de lugares y transiciones es igual a cero), y
P U T ≠ 0 (la unión de lugares y transiciones es diferente de cero).
C) Una re de Petri marcada se define como:
Gm=(G, µ) es decir Gm=(P, T, I, O, µ)
Donde:
Gm = Red de Petri Marcada.
G = Estructura de la Red de Petri (definida en la sección anterior).
µ: P " N = Función de Marcado, donde N= {0,1,2,3,4,……}.
D) Representación Matricial
Las funciones de incidencia se pueden representar como una matriz de n x m, donde cada elemento I(Pi , Tj) ó O(Pi , Tj) denota el peso de los arcos de entrada y salida de las transiciones, respectivamente.
Ejemplo 1: Función de incidencia previa. I(Tj) denota los pesos de los arcos de entrada, de los lugares a TJ. En la Figura 9 se muestra la función de incidencia previa, notemos como para esta función solamente se toman en cuenta el peso de los arcos de entrada a la transición Tj (P1=2, P2=1, P3=8).
Figura 9. En la función de la incidencia previa solo se toman en cuenta los pesos de los arcos que entran a las transiciones.
Ejemplo 2: Función de incidencia posterior O (Tj) denota los pesos de los arcos de salida, de los lugares a Tj. En la Figura 10 muestra la función posterior; notemos como para esta función, solamente se toman en cuenta el peso de los arcos de salida a la transición Tj (P5=9, P6=1, P7=8).
Figura 10. En la función de Posterior solo se toman en cuenta los pesos de los arcos que entran a las transiciones
El marcado se representa por un vector
µ = [µ(P1), µ(P2), µ(P3), …… µ(Pn)]
donde:
µ(Pi) = Número de marcas en cada lugar Pi.
En la figura 11 se observan que solo P1, P2 y P3 tiene marcas y las cuales son 3, 1, 3 respectivamente, por lo que el vector de marcado queda de la siguiente manera.
µ(3,1,3,0,0,0).
Figura 11. El vector de marcado nos dice el número de marcas que tiene cada lugar.
Ejemplo 3: Para aclarar más la representación matricial observaremos la Figura 12 en donde tenemos una red de Petri ordinaria, la cual tiene la siguiente representación matricial:
P = {P1, P2. P3, P4} T = {t1, t2, t3} µo = Marcado Inicial.
Figura 12. Una red de Petri Ordinaria.
E) Evolución del Marcado.
Las Reglas de disparo se pueden expresar como sigue:
Una transición tj ε T, esta habilitada respecto a un marcado µ sí y solo sí
Es decir si para cada lugar de entrada a una transición Tj, el número de marcas es mayor o igual a que el peso de los arcos, entonces se puede disparar dicha transición. En la Figura 13 se puede apreciar como en la a) el número de marcas coincide con el pero se los arcos que entran a la transición y lo tanto se puede disipar tj; en b) podemos observar como a P3 le falta una marca para que ese lugar tenga 3 marcas, ya que el peso del arco, que va de P3 a Tj tiene un 3, y por lo tanto se puede activar la transición.
Figura 13. Se puede ver como en caso a) si se cumple la condición para el disparo: mientras que en el caso de b) no se cumple.
Al dispararse una transición, cada lugar de entrada pierde I (Pi, Tj) marcas, y cada lugar de salida gana O(Pi, Tj) marcas, ver Figura 8.
Esto se puede expresar como:
Esta expresión también se puede escribir como:
A esta ecuación se le conoce como ecuación del estado de una ecuación de estado de una PN donde:
μ K= Vector de Marcado Siguiente.
μ K-1= Vector de Marcado Actual.
A= Matriz de incidencia, donde A= -I(Pj) + O (Pj)
VK-1 = Vector de disparo. Transiciones que se disparan en el momento k-1.
Por medio de esta ecuación, podemos calcula el conjunto de marcados alcanzables desde μo, llamado conjunto de alcanzabilidad R(μo).
En la Figura 12 podemos observar la única transición habilitada es la t1 ya que μ(P1) ≥ I(P1), es decir el marcado μ(P1) es igual a 2, al igual que el pero de los arcos de estrada I(P1), po lo que nuevo marcado después de disiparse t1, se calcula con el vector de disparo Vo, la matriz de incidencia A= -I(Pj) + O(Pj), y con el marcado inicial μo
y utilizando la ecuación de estado μK = μK-1 + A VK obtendremos
μ1 = μ0 + A V1
El cálculo sucesivo de marcados mediante esta ecuación de estados nos dará:
Por lo que podemos escribir esto como:
μ S = μ0 + A V
Donde V es el vector de cuenta de disparos definidos como:
Esta ecuación nos ayuda a obtener el marcado que de puede alcanzar desde el marcado inicial, y nos muestra como evoluciona la red de Petri cuando se disparan transiciones validas.
G) Alcanzabilidad.
Se trata de simular de manera exhaustiva, las posibles evoluciones del marcado de una PN, a partir del marcado inicial. Para esto se constituye el grafo de alcanzabilidad asociado, el cual nos muestra, las posibles evoluciones de una red de Petri.
Para obtener el grafo de alcanzabilidad primero se define como nodo de partida o raiz, el marcado inicial, en segundo término se calculan los marcados asociados por el disparo de las transiciones habilitadas por el marcado inicial. En seguida se repetirá el procedimiento de expansión para esto marcado, siguiente alguna estrategia de anchura o la de profundidad.
En la Figura 14 Tenemos una red de Petri y su grafo de alcanzabilidad. Para obtener el grafo de alcanzabilidad observaremos que en a) el marcado inicial esta definido por los lugares p1 y p2, por lo que para construir el grado de alcanzabilidad, que se muestra en b), el nodo de partida contiene a estos 2 lugares; con este marcado inicial se ve que solo de puede activar t1. Cuando se dispara la transición t1, las marcas pasan a p3 y p4, por lo que nuestro siguiente nodo tendrá a estos dos lugares. Con las marcas en p3 y p4 ahora las transiciones que se pueden dispara son t2 y t3. Para seguir construyendo el grafo de alcanzabilidad se escoge una de las transiciones y se hace el análisis con un esquema de profundidad (o en anchura). Siguiente este método exhaustivamente se obtiene el grafo de alcanzabilidad.
Figura 14. a) Red de Petri. b) Grafo de alcanzabilidad de la res de Petri.
Aquí podemos observar como al construir un grafo de alcanzabilidad de una red de Petri, lo que se esta haciendo es una traducción de la red de Petri a un autómata de estado finito.
H) Sub-clases de redes de Petri:
A continuación se presentan brevemente las subclases de redes de Petri ordinarias más comunes:
Maquinas de Estados (State Machine); En las maquinas de estado cada transición tiene solo un lugar de entrada y un lugar de salida, es decir que 
, esto es la cardinalidad de las “funciones” de estrada y de salida, de una transición ha de ser igual a 1. En la figura 15 podemos observar una “Maquina de estados (subclase de red de Petri).
Figura 15. Subclase de una Red de Petri de estados (State Machine).
Con esta subclase de red de Petri no es posible modelar situaciones de elección, de sincronización.
Grafos Marcados (marked graphas): En los grafos marcados la restricción esta en los lugares, cada lugar tiene una transición de entrada y una transición de salida: 
. Aquí si se permite la sincronización, pero no se posible expresar decisiones ni situaciones de confluencia. La Figura 16 muestra una sub-red de Petri del tipo “Grafo Marcado”.
Figura 16. Grafo Marcado (Sub-clase de red de Petri).
Redes de libre elección (free choice net): Una RP es de libre elección se de cumple para cualesquiera dos transiciones ti, tj, con un lugar de estrada p en común, el que éste haya de ser el único lugar de estrada de dichas transiciones. La Figura 17 muestra un sub-red de Petri del tipo “libre elección”.
Figura 17 Red de libre elección (sub-clase de red de Petri).
I) Propiedades de las redes de Petri:
Vivacidad (Liveness): La vivacidad es una propiedad que está relacionada con la ausencia de bloqueo (dedlocks) y/o con el funcionamiento de la totalidad del sistema representado por una red de Petri.
En una red de Petri un bloqueo significa que para un marcado dado, ninguna transición puede ser activada. Por otro lado una red de Petri que no se bloquea puede evolucionar sólo en una parte de ella. En cualquiera de los dos casos de dice que la red es no viva.
Se dice que una transición tJ es una red de Petri es potencialmente disparable en un marcado µ, si existe un marcado 
que la habilita. Una transición esta viva si es potencialmente disparable para cada marcado 
Una red e Petri G=(P, T, I, O) está viva respecto a un marcado inicial μ0 sí y solo si todas sus transiciones están vivas.
En la Figura 18 podemos observar en a) que si se dispara la transición t2. La red de Petri puede evolucionar y regresa al marcado inicial, pero si la transición que se activa es la t3 entonces la red se bloquee; esto se ve más claro al observar el grafo de alcanzabilidad mostrado en b).
Figura 18. a) Red de Petri no viva. b)Grafo de alcanzabilidad de la red de Petri (a).
Grafos de Vivacidad: Algunas redes de Petri pueden ser parcialmente vivas, es decir, algunas de sus transiciones se pueden disparar un número de veces limitado. EL grafo o nivel de vivacidad se puede caracterizar determinando la disponibilidad de las transiciones usando varios niveles [13].
Una transición tj puede encontrarse en algunos de los siguientes niveles de vivacidad, respecto a un μ0:
· Nivel 0, si nunca se dispara.
· Nivel 1, si es potencialmente disparable.
· Nivel 2, si existe una secuencia de disparos en las que tj ocurre un número finito de veces.
· Nivel 3, si existe una secuencia de disparos infinita en la que tj ocurre un número infinito de veces.
· Nivel 4, si es potencialmente disparable para cada 
Se dice que una red de Petri está viva a nivel 1 si cada transición está viva para ese nivel. Una red e Petri está viva si todas las transiciones están vivas. Nótese que una transición que esté viva en el nivel 4, lo está en los niveles 3, 2 y 1.
Acotamiento (boundness): El acotamiento esta relacionado con el número de marcas que un lugar puede acumular.
Un parámetro que es importante conocer en un red de Petri es el número máximo de marcas en que un lugar puede acumular, o bien si existen lugares en los cuales el marcado crece indefinidamente. Esto puede interpretarse en el sistema de modelado, en el primer caso como limite de tareas que se pueden llevar a cado, o en el segundo caso, por ejemplo, si fuere un almacén en el que el número de productos depositados excediera la capacidad.
Un lugar 
de una red de Petri con un marcado inicia μ0 está acotado si y solo si 
. Si k es el número de marcas más grande en la red se dice que la red está k-acotada.
Una red de Petri está a salvo si y solo si está k-acotada con k=1. Esta es una propiedad importante en modelos utilizados para el diseño de sistemas digitales. Una red de Petri a salvo es llamada también red de Petri binaria.
En la Figura 19 muestra una red de Petri no acotada, el disparo de la transición t1 conduce a marcas a p2 y p3; con lo cual se habilitan las transiciones t2, t3, las cuales al dispararse regresan 2 marcas a p1 con lo cual por cada evolución completa de la red , p1 se ira incrementando en 1, con lo cual el número de marcas pudiera crecer indefinidamente.
Figura 19. Red de Petri no acotada
j) Análisis de reducción:
Se trata de reducir el tamaño de la RP al analizar, obteniendo otra red de Petri que conserve las mismas propiedades que la original.
Las siguientes seis operaciones preservan la vivacidad, seguridad y acotamiento [20], esto es, tenemos (N, μ0) y (N’, μ0’) son las redes de Petri antes y después de una de las transformaciones. Entonces (N’, μ0’) es viva, segura y acotada, si y solo si (N, μ0) es viva, segura y acotada.
1) Fusión de una serie de lugares como se muestra en la Figura 20 A).
2) Fusión de una seria de transiciones como se muestra en la Figura 20 B).
3) Fusión de transiciones en paralelo, como se muestra en l Figura 20 C).
4) Fusión de lugares en paralelo, como se muestra en la Figura 20 D).
5) Eliminación de semi-lazos de lugares, como se muestra en la Figura 20 E).
6) Eliminación de semi-lazos de transiciones, como se muestra en la Figura 20 F).
Figura 20. Seis transformaciones que preservan la vivacidad, la seguridad y el acotamiento.
Con este conjunto de reglas es posible reducir la complejidad del cálculo de la vivacidad y limitaciones de un sistema.
No comments:
Post a Comment