Monografias.com > Computación > Redes
Descargar Imprimir Comentar Ver trabajos relacionados

Redes De Petri




Enviado por mabelgonzalesu



    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.

    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:

    Condiciones

    A

    Una orden ha llegado y está
    esperando

    B

    Una orden ha sido trabajada y está
    esperando ser procesada por M2 o M3

    C

    La orden es completada

    D

    La máquina M1 está
    desocupada

    E

    La máquina M2 está
    desocupada

    F

    La máquina M3 está
    desocupada

    G

    El operador O1 está sin trabajo

    H

    El operador O2 está sin trabajo

    I

    El operador O1 está ocupando la
    máquina M1

    J

    El operador O2 está ocupando la
    máquina M1

    K

    El operador O1 está ocupando la
    máquina M2

    L

    El operador O2 está ocupando la
    máquina M3

    Eventos

    Llega una orden

    El operador O1 empieza la orden en M1

    El operador O1 termina la orden en M1

    El operador O2 empieza la orden en M1

    El operador O2 termina la orden en M1

    El operador O1 empieza la orden en M2

    El operador O1 termina la orden en M2

    El operador O2 empieza la orden en M3

    El operador O2 termina la orden en M3

    La orden es terminada y liberada

    Precondiciones y postcondiciones de cada
    evento

    Condiciones Iniciales: d, e, f, g, h

    Eventos

    Precondiciones

    Postcondiciones

    1

    Ninguna

    A

    2

    A, G, D

    I

    3

    I

    G, D, B

    4

    A, H, D

    J

    5

    J

    B, H, D

    6

    B, G, E

    K

    7

    K

    C, G, E

    8

    B, f , H

    I

    9

    L

    C, F, H

    10

    c

    Ninguna

    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.

    Condiciones

    1

    El palillo 1 está ocupado

    2

    El palillo 2 está desocupado

    3

    El palillo1 está ocupado

    4

    El palillo 2 está ocupado

    5

    El filósofo está
    meditando

    6

    El filósofo está comiendo

    Eventos

    1

    El filósofo empieza a meditar

    2

    El filósofo empieza a comer

    Condiciones iniciales: 1,2, 5

    Eventos

    Precondiciones

    Postcondiciones

    1

    6

    1,2,5

    2

    1,2,5

    3,4,6

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

    Condiciones

    1

    El palillo 1 está ocupado

    2

    El palillo 2 está desocupado

    3

    El palillo1 está ocupado

    4

    El palillo 2 está ocupado

    5

    El filósofo 1 está
    meditando

    6

    El filósofo 1 está
    comiendo

    7

    El filósofo 2 está
    meditando

    8

    El filósofo 2 está
    comiendo

    Eventos

    1

    El filósofo 1 empieza a meditar

    2

    El filósofo 1 empieza a comer

    3

    El filósofo 2 empieza a meditar

    4

    El filósofo 2 empieza a comer

    Condiciones iniciales: 1,2, 5

    Eventos

    Precondiciones

    Postcondiciones

    1

    6

    3, 4, 5

    2

    3, 4, 5

    1, 2, 6

    3

    8

    3, 4, 7

    4

    3, 4, 7

    1, 2, 8

    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

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter