PRESENTACIN

CAPITULO IIRESULTADOS DE LA INVESTIGACIN:REDES DE PETRILas redes de Petri representan una alternativa para modelar sistemas, sus caractersticas 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 alemn Karl Adam Petri en 1962. En su tesis doctoral "kommunikation mit automaten" (Comunicacin con autmatas), establece los fundamentos para el desarrollo terico de los conceptos bsicos de las PN. La teora de PN ha llegado a ser reconocida como una metodologa establecida en la literatura de la robtica para modelar los sistemas de manufactura flexibles. Comparada con otros modelos de comportamiento dinmico grficos, como los diagramas de las mquinas de estados finitos, las PN ofrecen una forma de expresar procesos que requieren sincrona. Y quizs lo ms importante es que las PN pueden ser analizadas de manera formal y obtener informacin del comportamiento dinmico del sistema modelado. Para modelar un sistema se usan representaciones matemticas logrando una abstraccin del sistema, esto es logrado con las PN, que adems pueden ser estudiadas como autmatas e investigar sus propiedades matemticas. Ahora deseamos conocer en que condiciones se encuentran los mdulos, es como si detuviramos al sistema en el tiempo, las condiciones internas de los mdulos determinaran el estado en el que se encuentran, para esto entendemos que un sistema es un arreglo dinmico que en el transcurso del tiempo tiene variaciones y no permanece esttico. Las PN fueron diseadas especficamente para modelar este tipo de sistemas. Una red de Petri es un grafo dirigido bipartito, con un estado inicial, llamado marcacin inicial. Los dos componentes principales de la red de Petri son los sitios (tambin conocidos como estados) y las transiciones. Tambin constan de cuatro partes: Nodos, transiciones, Funciones de Entrada y de Salida. Grficamente, los sitios son dibujados como crculos y las transiciones como barras o rectngulos. Las aristas del grafo son conocidas como arcos. Estos tienen un peso especfico, el cual es indicado por un nmero entero positivo, y van de sitio a transicin y viceversa. Por simplicidad, el peso de los arcos no se indica cuando ste es igual a 1. Un arco que est etiquetado con k puede ser interpretado como k arcos paralelos. El estado del sistema que la red est modelando es representado con la asignacin de enteros no-negativos a los sitios. Esta asignacin es conocida como una marcacin, la cual es representada grficamente mediante unos pequeos crculos negros dentro de un sitio p, llamados tokens. Si el nmero de tokens es demasiado grande, los k tokens son representados con un nmero no-negativo dentro del correspondiente sitio. Tpicamente, los estados representan algn tipo de condicin en el sistema, y una transicin representa un evento. Un sitio de entrada (salida) a una transicin representan las pre- (post-) condiciones. Los tokens pueden tener muchas interpretaciones. Por ejemplo, cuando un sitio est marcado con un token, este puede representar que la correspondiente condicin es verdadera. En otros casos, k tokens pueden representar k recursos, por ejemplo, el nmero de clicks del Mouse realizados. Debido a que las redes de Petri pueden modelar muchos tipos de sistemas, lo que los sitios, transiciones y tokens representen vara enormemente.

Definicin:

Una red de Petri es una tupa de cinco elementos, PN = (P, T, F, W, M0) donde:

1. P=p1, p2,..., pm es un conjunto finito de sitios

2. T = t1, t2,..., tn es un conjunto finito de transiciones

3.

Es un conjunto de arcos.

4.

Es una funcin de peso

5.

Es la marcacin inicial

6.

Y Es conveniente utilizar la siguiente notacin: Para una transicin t, los sitios de entrada y los sitios de salida sern denotados como Y t , Respectivamente. De manera formal, una marcacin M es definida comoM: P . Tambin es conveniente, en algunos casos, el denotar una marcacin M de m sitios como un vector-m donde el i-simo componente es denotado como M (pi), por ejemplo M = . Una transicin t est habilitada con una marcacin M si cada sitio de entrada p est marcado con al menos W (p, t) tokens. Una transicin puede o no ser disparada al habilitrsele. Cuando ms de una transicin es habilitada, alguna de ellas es seleccionada de manera no-determnistica dependiendo del modelo empleado. Conforme las transiciones son disparadas, el nmero total de tokens distribuidos a lo largo de la red puede variar, esto es, la conservacin de los tokens no siempre sucede.

Ejemplo de Red de Petri:

Se tiene una sola lnea para atender a 100 clientes. Los tiempos de llegada de los clientes sern valores sucesivos de la variable aleatoria ta, los tiempos de servicio estn dados por la variable aleatoria ts, y N es el nmero de servidores. Este modelo en su estado inicial tiene la cola vaca y todos los servidores en estado de espera. La red de Petri para este escenario se muestra en la siguiente figura:

Los estados estn etiquetados con letras maysculas y las transiciones con minsculas. Las etiquetas de los sitios tambin sern usados como las variables de cuyos valores son los tokens.

Las aristas tienen etiquetas que podran representar las funciones de transicin, las cuales especifican el nmero de tokens eliminados o agregados cuando una transicin es activada.

El estado A inicialmente contiene la llegada de 100 clientes; el sitio B evita que los clientes entren ms de una vez; el sitio Q es la fila que realizan los clientes cuando tienen que esperar a que se les atienda. El estado S es donde los servidores ociosos esperan la oportunidad para trabajar, y el sitio E cuenta el nmero de clientes que abandonan el sistema. El estado inicial implica que los sitios tengan los siguientes valores:

A = 100

B = 1

Q = 0

S = N

E = 0

La transicin a sirve para modelar a los clientes que entran al sistema y la transicin b modela a los clientes cuando estn siendo atendidos.

Estructura de una red de Petri.

Las PN se componen de cuatro partes:

Un conjunto de nodos.

Un conjunto de transiciones.

Una funcin de entrada y

Una funcin de salida.

Las funciones de entrada y salida relacionan a los nodos y a las transiciones. La funcin de entrada es un mapeo de una transicin tj a una coleccin de nodos conocidos como los nodos de entrada de una transicin. La estructura de una PN es definida por los nodos, las transiciones, la funcin de entrada y la funcin de salida. Definicin: 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 transicin tj s pi I (tj); pi es un nodo de salida s pi O (tj). Las entradas y salidas de una transicin son conjuntos que tienen elementos repetidos o mltiples ocurrencias de nodos (bags). La multiplicidad de un nodo de entrada pi para una transicin tj es el nmero de ocurrencias del nodo en el bag de entrada de la transicin. Escribimos esto como: # (pi, I (tj)). De igual forma para la salida lo cual escribimos: # (pico (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 caracterstica de la PN, marca U es una asignacin de tokens a la PN. Un token es un concepto primitivo de una PN, un nmero de ellos reside en los nodos y se mueve entre ellos; los tokens son la parte dinmica de la PN, su nmero puede variar entre nodos y son los que determinan la situacin de la red en un momento determinado.Definicin: Una marca U de una PN P= (P, T, I, O) es una funcin U: P N.Es decir el nodo pi tiene U (pi) tokens. La PN puede ser considerada tambin como un modelo de flujo de informacin, en donde el comportamiento dinmico de los tokens representa el flujo. Dicho de otra manera la informacin depende de lo que la PN esta modelando.

Disparo y habilitacin de las transiciones.

Los cambios en los estados de un sistema son modelados mediante las reglas de activacin y habilitacin. Las reglas se describen de la siguiente manera:

1.

Una transicin t est habilitada con una marcacin M si cada sitio de entrada p est marcado con al menos W (p, t) tokens. De una manera ms formal,

Si y slo si t est habilitado.

2.

Una transicin puede o no ser disparada al habilitrsele. Cuando ms de una transicin es habilitada, alguna de esas transiciones es seleccionada de manera no-determnistica dependiendo del modelo empleado.

3.

Un disparo de una transicin t resulta en W (p, t) tokens eliminados de cada sitio de entrada p de t y la adicin de W (t, p) tokens a cada sitio de salida p'. Formalmente, el disparar una transicin habilitada t resulta en un cambio de la marcacin M a M', donde:

M '(p) = M (p) + W (t, p) si p Y p M '(p) = M (p) W (p, t) si p Y p M'(p) = M (p) para cualquier otro caso.

Si t no tiene estados de entrada(Por ejemplo, si ), Se trata de una transicin fuente y est habilitada por vacuidad. Si t no tiene sitios de salida (Por ejemplo, si ),Se dice que esta es una transicin sumergida. Una transicin sumergida ``consume'' tokens, pero no produce ningn token.

Si una transicin t es habilitada bajo la marcacin M, y M' es la marcacin resultante del disparo de t, se representa como.

Debe hacerse notar el hecho de que conforme las transiciones son disparadas, el nmero total de tokens distribuidos a lo largo de la red puede variar, esto es, la conservacin de los tokens no siempre sucede.

Ejemplo

La figura (a) es un ejemplo de una red de Petri con ambas transiciones habilitadas mediante la marcacin inicial M0 = < 1, 2, 0>. Cualquiera de las dos puede ser disparada. Es posible tener:

O .

La figura (a) muestra las marcaciones de M1 y M2, respectivamente. En M1 tanto t1 como t2 estn deshabilitadas. En M2, t2 est habilitada y, si t2 se vuelve a disparar, se tendr que . La figura (a) muestra a M3 marcada. En M3 ninguna transicin ha sido habilitada. Una transicin que nunca es habilitada se conoce como transicin muerta ([Dwyer et al., 1995])

Es importante hacer notar el que la definicin de la red de Petri y sus reglas de disparo y habilitacin le permiten a un sitio estar marcado con un nmero ilimitado de tokens. Estas redes de Petri en particular, reciben el nombre de redes de capacidad infinita. Existen tambin las redes de capacidad finita, en donde la marcacin de cada sitio p tiene una cota superior K (p). As, una restriccin extra es incluida para la habilitacin de una transicin t: M (p) no puede excederse de K (p) para todo , Si t fuera a ser disparada.

Una extensin importante a las redes de Petri es el arco inhibidor, el cual es indicado como un pequeo circulo en lugar de una flecha, al final del arco. En la figura (b) la transicin T1 est habilitada porque no existe ningn token en P1. En general, una transicin est habilitada si hay al menos un token en cada uno de sus arcos de entrada (normales) y ningn token en su arco inhibidor. En la figura (b) T1 est deshabilitada, debido a que hay un token en P1.

Figura (a): Secuencia de disparo en una red de Petri

Figure (b): Arco inhibidor

Reglas de disparo para una PN.

La ejecucin en una PN es controlada por el nmero y distribucin de los tokens que tiene. Los tokens presentes en los nodos controlan la ejecucin de las transiciones de la red. Una PN se activa disparando transiciones. Una transicin es disparada removiendo tokens de los nodos de entrada y creando tokens de salida. De aqu podemos obtener la primera condicin de disparo en una transicin: todos los nodos de entrada de la transicin, deben tener al menos el mismo nmero de tokens, que de arcos que van hacia la transicin, para que sta sea disparada, cuando la transicin cumpla esta condicin se dice que es una transicin ENABLED. Definicin: Una transicin 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 (t j)). Por ejemplo una transicin t3 con I (t3)= {p3} y O (t3)= {p4} es ENABLED slo cuando p3 tiene al menos un token. Cuando t3 es disparada slo un token es quitado a p3 y un token es depositado en p4 (s tuviera ms 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: Slo 3 transiciones estn en un estado ENABLED t1, t3, t4. La transicin 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 transicin 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 nmero de tokens en p3 de dos a tres; el vector u sera (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 disparndose indefinidamente hasta llegar a un estado deseado o hasta que ninguna pueda ser disparada. De lo anterior surgen dos preguntas: Cmo decidimos que transicin debe dispararse?Por qu no podemos disparar dos transiciones al mismo tiempo?Decidir que transicin debe dispararse depende de nuestro modelo y s podemos disparar ms de una transicin en un mismo instante entonces estamos hablando de paralelismo. Pensemos en un ejemplo concreto: queremos sumar cuatro nmeros cualesquiera por medio de una PN. Dependiendo de cada nmero 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 transicin para cada nodo es la que se encarga de quitar unidades en los sumandos y poner unidades en el resultado, cuando se efectan 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 anterioresRedes de Petri ColoreadasLas 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 transicin en CPN est en estado ENABLED si todos sus nodos de entrada contienen un nmero de colores igual o mayor que los definidos por fi donde fi es una funcin lineal asociada al nodo pi con la transicin tj. Entonces adems del concepto de color, estas redes manejan una funcin asociada para los elementos de las funciones I, O de la PN. Es fcil ver en una Red las transiciones que estn ENABLED y observar que a veces son ms 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 sincronizacin. Extensiones al Modelo de Redes de Petri un arco inhibidor es otro componente de una PN, ste va de un nodo a una transicin y es representado con un pequeo circulo al final del arco. La transicin 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 teora de PN dependen del modelo o la aplicacin donde se estn usando.

Redes de Petri Temporales.Este tipo de redes son las que consideran el tiempo en el modelo. Es una consideracin importante ya que los sistemas reales casi siempre es indispensable considerarlo en la sincronizacin de los procesos.El modelo ms simple es el que asigna duracin a:

1. Los nodos, en el sentido de que una condicin es verdadera para una cierta cantidad de tiempo.

2. La transicin, en el sentido de que un evento toma una cierta cantidad de tiempo en ocurrir.

Cuando la duracin de los eventos no son fijos, o no pueden ser expresados con valores nominales, simplemente se estiman lmites dentro de los cuales el evento puede ocurrir.Modelado con Redes de PetriEventos y condiciones. Podemos modelar sistemas complejos con PN, dividiendo el sistema en eventos y condiciones y de esta manera encontrar la analoga 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 condicin 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 mquinas, M1, M2 y M3, y dos operadores O1 y O2. El operador O1 puede trabajar las mquinas M1 y M2 y el operador O2 las mquinas M1 y M3. Las rdenes requieren de dos procesos, el primer proceso debe ser hecho por la mquina M1 y el segundo proceso puede ser hecho con la mquina M2 o la M3. Enlistemos las condiciones y los eventos:CondicionesEventos

AUna orden ha llegado y est esperandoLlega una orden

BUna orden ha sido trabajada y est esperando ser procesada por M2 o M3El operador O1 empieza la orden en M1

CLa orden es completadaEl operador O1 termina la orden en M1

DLa mquina M1 est desocupadaEl operador O2 empieza la orden en M1

ELa mquina M2 est desocupadaEl operador O2 termina la orden en M1

FLa mquina M3 est desocupadaEl operador O1 empieza la orden en M2

GEl operador O1 est sin trabajoEl operador O1 termina la orden en M2

HEl operador O2 est sin trabajoEl operador O2 empieza la orden en M3

I

El operador O1 est ocupando la Mquina M1El operador O2 termina la orden en M3

J

El operador O2 est ocupando la mquina M1La orden es terminada y liberada

K

El operador O1 est ocupando la mquina M2

L

El operador O2 est ocupando la mquina M3

Precondiciones y postcondiciones de cada evento

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

EventosPrecondicionesPostcondiciones

1NingunaA

2A, G, DI

3IG, D, B

4A, H, DJ

5JB, H, D

6B, G, EK

7KC, G, E

8B, f , HI

9LC, F, H

10CNinguna

CAPITULO IIIConclusiones

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 sincronizacin de procesos.

Tambin se dijo que constan de cuatro partes:

Nodos

Transiciones

Funciones de entrada

Funciones de salida

Las entradas y/o salidas de una transicin son conjuntos que pueden tener elementos repetidos o mltiples ocurrencias.

Cuentan con una asignacin de tokens que es la parte dinmica de las Redes de Petri.

Las Redes de Petri se pueden representar grficamente, un circulo O representa un nodo y una barra | representa una transicin, y los tokens son representados por pequeos puntos .

Las Redes de Petri tienen reglas de disparo, siendo la principal, la que dice: "todos los nodos de entrada de la transicin, deben tener al menos el mismo nmero de tokens, que nmero de arcos van hacia la transicin para que sta sea disparada". Cuando la transicin cumple dicha condicin se dice que es ENABLED.

Tambin se dijo que constan de cuatro partes:

Nodos

Transiciones

Funciones de entrada

Funciones de salida.

Podemos modelar los sistemas dividindolos en eventos y condiciones. Las condiciones son representadas por los nodos, y los eventos por las transiciones. Tambin existen redes petri coloreadas y temporales que de igual forma pertenecen a la misma familia de redes petri.Fuentes documental.http://www.fismat.umich.mx/~crivera/tesis/node30.htmlhttp://www.fismat.umich.mx/~crivera/tesis/node25.htmlhttp://www.fismat.umich.mx/~crivera/tesis/node26.htmlhttp://www.fismat.umich.mx/~crivera/tesis/node27.htmlhttp://www.fismat.umich.mx/~crivera/tesis/node28.htmlhttp://www.fismat.umich.mx/~crivera/tesis/node29.htmlhttp://www.monografias.com/trabajos14/redesdepetri/redesdepetri.shtml#estru161