Virgilio Vásquez López

Principal
Arriba

 

 

 

 

vlopez@itesm.mx

  1. Definición
  2. Estructuras particulares
  3. Notación
  4. Propiedades
  5. Árbol de alcanzabilidad
  6. Redes de Petri no binarias

 

 

 

Definición

Formalmente, una red de Petri se define como:

PN=(P,T,I,O,Mo);

donde:

  1. P={p1,p2,...,pm}  es un conjunto de lugares
  2. T={t1,t2,...,tn}    es un conjunto finito de transiciones, P U T ≠ 0, P Ω T = 0
  3. I:(P x T)®  N es una función de entrada que define arcos que van de los lugares a las transiciones, donde N es un conjunto de enteros no negativos
  4. O:(P x T)® N es una función de salida el cual define los arcos que van de las transiciones a los lugares
  5. Mo: P® N es el marcado inicial.

Si I(p,t) = k, entonces existen k arcos que conectan el lugar p con la transición t

Si O(p,t) = k, entonces existen k arcos que conectan la transición t con el lugar p

SUBIR

 

 

 

Estructuras particulares

  1. Grafo de estado. Una PN es un grafo de estado si y solo sí, cada transición tiene exactamente un lugar de entrada y un lugar de salida

  2. Grafo de evento. Una PN es un grafo de eventos si y solo sí cada lugar tiene exactamente una transición de entrada y una transición de salida

  3. Red de Petri de conflicto libre. Esta es una PN en el cual cada lugar tiene al menos una transición de salida. Un conflicto corresponde a la existencia de un lugar, Pj, el cual tiene al menos dos transiciones de salida, T1, T2,... Este conflicto es denotado por un par formado por un lugar y un conjunto de transiciones: <P1,{T1, T2,...}>

  4. Red de Petri de elección libre. Existen dos definiciones conocidas como elección libre y elección libre extendida.

    1. Una PN de elección libre es aquella que para cada conflicto <P1,{T1, T2,...}> ninguna de las transiciones T1, T2,... no posee otro lugar de entrada más que P1

    2. Una PN de elección libre extendida es tal que para cada conflicto <P1,{T1, T2,...}> todas las transiciones T1, T2,..tienen el mismo conjunto de lugares de entrada. Esto significa que si T1 tiene a P1 y a P2 como lugares de entradas, entonces T2 tiene a P1 y P2 como lugares de entrada también.

     

  5. Red de Petri simple. Esta es una PN en la cual cada transición puede ser afectada solamente por al menos un conflicto. En otras palabras, si existe una transición T1 y dos conflictos <P1,{T1, T2,...}> y <P2,{T1, T2,...}>, entonces la PN no es simple.

  6. Red de Petri Pura. Un lugar Pi y una transición Tj se llaman auto-lazos si Pi es un lugar de entrada y un lugar de salida de Tj. Una PN es una red pura si no tiene auto-lazos.

SUBIR

 

 

Notación.

 

El marcado de una PN en cualquier momento, es un vector columna cuyo i-th componente es la marca del lugar Pi en ese momento. Por ejemplo

M0 = [1 0 0 0 0]´

A partir del marcado inicial M0, existe una transición activada, T1. El disparo de T1 desde M0 resulta en el marcado M1 = [0 1 1 0 0]´. Esto se escribe como

M0[T1>M1

Para el marcado M1, existen dos transiciones activadas o habilitadas, T2 y T3. Si las marcas obtenidas al disparar estas transiciones son llamadas M2 y M3, respectivamente, tenemos:

M1[T2>M2=[0 0 1 1 0]´ y M1[T3>M3=[0 1 0 1 0]´

 

  1. Para el marcado M2, solo la transición T3 es activada. Su disparo resulta en M4

  2. Para el marcado M3, solo la transición T2 es activada. Su disparo resulta en M4

  3. Para el marcado M4, solo la transición T4 es activada. Su disparo resulta en el marcado inicial M0

*M0 denota el conjunto de marcas alcanzable desde el marcado M0 ([M0>). Para nuestro ejemplo *M0={M0, M1, M2, M3, M4}

SUBIR

 

 

Propiedades

 

Red de Petri acotada.

Un lugar Pi se dice que es acotado para un marcado inicial Mo si existe un número entero k tal que, para todo el conjunto de marcados alcanzables desde Mo, el número de marcas en Pi no es más grande que k (Pi se dice que es k-acotado).

Una PN es acotada para un marcado inicial Mo si todos los lugares son acotados para Mo (la PN es k-acotada si todos los lugares son k-acotados)

 

 

Red segura o binaria.

Una PN se dice que es segura para un marcado inicial Mo si para todas las marcas alcanzables cada lugar tiene a lo más una marca. Una PN segura es un caso particular de una PN para el cual todos los lugares son 1-acotados.

 

Vivacidad.

Una transición Tj es viva para un marcado inicial Mo si para cada marcado alcanzable Mi Î *Mo una secuencia de disparo S desde Mi el cual contiene la transición Tj existe.

Una PN es viva para un marcado inicial Mo si todas sus transiciones son vivas de Mo

Una transición Tj es casi-viva si para un marcado inicial Mo, existe una secuencia de disparo desde Mo el cual contiene a Tj. En otras palabras, una transición es casi-viva si existe una oportunidad de que esa transición sea disparada.

Deadlock.

Es un marcado donde ninguna transición es habilitada

 

Estado inicial e invertibilidad

Una PN tiene un estado inicial Mh para un marcado inicial Mo, si para cada marcado alcanzable Mi Î *Mo, existe una secuencia de disparos Si tal que Mi[Si>Mh

Una PN es invertible para una marcado inicial Mo si Mo es el estado inicial.

 

SUBIR

 

 

Árbol de alcanzabilidad

Algoritmo.

  1. A partir del marcado inicial Mo, se indican todas las transiciones habilitadas y el marcado correspondiente. Si alguna de estas marcas cubre a Mo, la letra w (infinito) es ubicada para cada uno de los componentes más grandes que Mo.
  2. Para cada nueva marca Mi del árbol, se realiza lo siguiente:
    1. Si existe una nueva marca Mj = Mi del trayecto desde Mo a Mi (éste último no debe ser incluido), entonces Mi no tiene sucesor y el marcado se repite.
    2. Si no existe un marcado Mj = Mi del trayecto desde Mo a Mi, entonces el árbol se extiende al añadir todos los sucesores de Mi. Si existe una marca Mj sobre el trayecto de Mo a Mk tal que Mk > Mj, entonces w (infinito) es ubicada para cada uno de los componentes mas grandes que los componentes de Mj.

Algunas de las propiedades anteriores se pueden verificar a partir del árbol de alcanzabilidad:

  1. Una PN es acotada si y solo si w no aparece en ningún nodo
  2. Una PN es segura si y solo si aparecen únicamente 1´s y 0´s en los nodos
  3. Una transición es viva si y solo si aparece en los arcos

Ejemplos. Determine el árbol de alcanzabilidad de los siguientes ejercicios y determine si son PN´s acotadas, vivas, invertibles, etc.

SUBIR

 

 

Redes de Petri no binarias

Hasta ahora se han programado PN binarias, las cuales el máximo marcado de un lugar es uno. Las PN no binarias pueden tener lugares que contengan más de una marca. Estos lugares pueden modelar, por ejemplo, el número de objetos que hay en un almacén, el número de piezas de un palet, el número de piezas que hay sobre una banda transportadora, etc.

Para programar estos lugares se utilizan los bloques contadores:

Ejemplo: Un productor produce objetos que deposita en el almacén de una fábrica. Este almacén tiene una capacidad de 4 objetos. El consumidor (la fábrica) retira los objetos del almacén con el fin de utilizarlos en un proceso de fabricación. Al almacén no se puede acceder simultáneamente, es decir, el productor y el consumidor tienen que acceder al almacén en exclusión mutua (o se depositan o se extraen objetos)

Lugares:

  1. CE Consumidor en espera de almacén

  2. PE Productor en espera de almacén

  3. O  No. de objetos en el almacén

  4. H  No. de huecos en el almacén

  5. A  Estado del almacén

  6. EXT  El consumidor extrae un objeto del almacén

  7. DEP  El productor deposita un objeto en el almacén

  8. P  El productor produce

  9. C  El consumidor consume

Transiciones:

  1. FEXT  El consumidor termina de extraer el objeto del almacén

  2. FDEP El productor termina de depositar el objeto en el almacén

  3. FC  El consumidor ha terminado su labor que había realizado con el objeto y pasa al estado de espera de almacén para extraer un nuevo objeto

  4. FP  El productor ha terminado de fabricar un objeto y pasa al estado de espera de almacén para depositarlo

Los lugares H y O son programados en el autómata mediante contadores.

SUBIR