Post on 13-Dec-2015
description
Teoría de Redes de Petri
Autores:
Prog. Catalina Salvati
Prog. Leandro Cofre
Prog. Francisco Suárez
Base teórica del proyecto final de la carrera de Lic. en Sistemas
Universidad FASTA Bariloche
Apunte de Redes de Petri
Índice
INTRODUCCIÓN 1
CONTENIDO 2
DEFINICIONES 3
DEFINICIÓN FORMAL 3REPRESENTACIÓN 4REPRESENTACIÓN GRÁFICA 4REPRESENTACIÓN MATRICIAL 5EJEMPLO 1 5MARCADO 7EVOLUCIÓN DE MARCADO 7SUBCLASES DE REDES DE PETRI 8GRAFO DE ESTADOS 8GRAFO MARCADO 8RED DE LIBRE ELECCIÓN 8RED SIMPLE 8
ESTRUCTURAS BÁSICAS 9
SELECCIÓN 9ATRIBUCIÓN 9DISTRIBUCIÓN 9CONJUNCIÓN 10EJECUCIÓN SECUENCIAL 10SINCRONIZACIÓN 10CONCURRENCIA 11CONFLICTOS 11
PROPIEDADES 12
PROPIEDADES ESTRUCTURALES 12RDP PURA 12RED DE PETRI ACOTADA ESTRUCTURALMENTE 12RED DE PETRI ESTRUCTURALMENTE VIVA 12RED DE PETRI COMPLETAMENTE CONTROLABLE 12RED DE PETRI ESTRUCTURALMENTE CONSERVATIVA 12RED DE PETRI (PARCIALMENTE) REPETITIVA 12RED DE PETRI (PARCIALMENTE) CONSISTENTE 12PROPIEDADES DE COMPORTAMIENTO 13VIVACIDAD 13CICLICIDAD 14ACOTAMIENTO 15CONSERVATIVIDAD 16ALCANZABILIDAD 16
EXTENSIONES 18
I
Apunte de Redes de Petri
RECURSOS COMPARTIDOS 18ARCOS INHIBIDORES: 18
VALIDACIÓN 19
MÉTODOS DE ANÁLISIS 19
TÉCNICAS ENUMERATIVAS 19TÉCNICAS DE TRANSFORMACIÓN 20TÉCNICAS ESTRUCTURALES 21
TIPOS DE RED 23
RDP CON PESO 23RDP CON TIEMPO 23RDP COLOREADAS 23RDP JERÁRQUICAS 24ESTOCÁSTICAS (CONCEPTOS REDES PETRI.PDF) 24REDES DE PETRI ESTOCÁSTICAS GENERALIZADAS 25
EJERCICIOS 26
EJERCICIO Nº 1: 26EJERCICIO Nº 2: 26EJERCICIO Nº 3: 27¿CÓMO MODELARÍA LA SITUACIÓN DE QUE CUANDO NO HAY MÁS BEBIDAS LA MÁQUINA RETORNE LA MONEDA? 27EJERCICIO Nº 4: 27EJERCICIO Nº 5: 27EJERCICIO Nº 6: 28EJERCICIO 7 28EJERCICIO 8 28
RESPUESTAS A LOS EJERCICIOS 29
EJERCICIO 1 29EJERCICIO 2 29EJERCICIO 3 30EJERCICIO 4 30EJERCICIO 5 31EJERCICIO 6 31EJERCICIO 7 31EJERCICIO 8 32
GLOSARIO 33
CONJUNTOS 33LÓGICA 33
ÍNDICE DE IMÁGENES 34
II
Apunte de Redes de Petri
Bibliografía 35
III
Apunte de Redes de Petri
Introducción
Las Redes de Petri (RdP) son una teoría matemática postulada por el alemán Carl Adam Petri que proporciona una herramienta gráfica y matemática de modelado para la descripción formal de sistemas cuya dinámica se caracteriza por la concurrencia, sincronización, exclusión mutua y conflictos, las cuales son características típicas de sistemas distribuidos.
La principal aplicación de las redes de Petri es el modelado y el análisis de sistemas con componentes concurrentes que interactúan. Un modelo es una representación de las características más importantes de un sistema de estudio. Manipulando esta representación, se pueden obtener nuevos conocimientos del sistema modelado sin ningún coste o peligro para el sistema real. Sin embargo, el modelado por sí solo sirve de poco, es necesario analizar el sistema modelado.
El sistema se modela primero como una RdP y después, este modelo se analiza. Este análisis nos lleva a una mejor comprensión del comportamiento del sistema modelado. Para realizar el análisis de las propiedades de una red de Petri se han desarrollado diferentes técnicas, que permiten la verificación de las propiedades que el sistema construido posea.
Las RdP se han utilizado en distintas áreas de aplicación como en química, redes informáticas, Inteligencia artificial, tránsito, etc.
Definiciones 1
Apunte de Redes de Petri
Contenido
En este documento, introduciremos los fundamentos de la teoría de redes de Petri.
En la primer parte daremos las definiciones básicas de RdP y los modos de representación.
Luego daremos algunos ejemplos de estructuras básicas que describen el modo de representar algunos casos comunes.
Seguiremos con las propiedades, extensiones y métodos de análisis.
Finalizando luego con una serie de ejercicios para resolver.
Definiciones 2
Apunte de Redes de Petri
Definiciones
Una RdP está formada por lugares y transiciones, unidos alternativamente por arcos dirigidos. Un lugar puede o no contener marcas. El conjunto de marcas asociadas a cada uno de los lugares en un momento dado, constituye un marcado de la RdP. Para la descripción funcional de sistemas concurrentes los marcados representan estados y las transiciones sucesos, que dependen del cumplimiento de determinadas condiciones.
Definición formal
Podemos definir a una red de Petri como una 5-upla:
RdP = (P, T, F, W, M0), donde:
P = {p1, p2, … pm} es un conjunto finito no vacío de lugares
T = {t1, t2, …, tn} es un conjunto finito no vacío de transiciones
P T =
F (P X T) U (T X P) es un conjunto de arcos dirigidos
W: F{1,2,3,…} es una función de pesos
Mi: P{0,1,2,…} es el marcado inicial de la red // define un número inicial de marcas por lugar
Definiciones 3
Apunte de Redes de Petri
Representación
Toda herramienta de modelado tiene una o mas formas de ser representada. En el caso de las RdP, podemos encontrar una representación gráfica y otra matricial.
Representación gráfica
A una RdP podemos asociarle un grafo dirigido con dos clases disjuntas de nodos, los lugares y las transiciones.
Un círculo representa un lugar, una barra representa una transición y un arco dirigido conecta lugares y transiciones.
Algunos arcos van desde un lugar a una transición y otros desde una transición a un lugar. Un arco dirigido desde un lugar p a una transición t define p como un lugar de entrada para t. Un lugar de salida se indica con un arco desde la transición al lugar.
Los arcos se etiquetan con sus pesos (enteros positivos). Si una de esas etiquetas se omite, significa que el arco tiene peso uno.
Las marcas se representan como puntos negros en los lugares.
Figura 1
p1 t1 p2
arco
lugar transiciónmarca
Representación gráfica de una Rdp.
Los lugares que contienen marcas se consideran lugares activos.
Figura 2
p1
Lugar activo.
A las transiciones se les asocia eventos (funciones lógicas de las variables de entrada). Una transición se dice que está sensibilizada cuando todos sus lugares origen están marcados.
Definiciones 4
Apunte de Redes de Petri
Figura 3
p1
p2
t1
Transición sensibilizada.
Cuando ocurre un evento asociado a una transición, se dice que la transición está validada.
Figura 4
p2p1 t1
Transición validada.
Representación matricial
Una transición tiene un determinado número de lugares de entrada (o precondiciones) y de lugares de salida (o postcondiciones). Cada uno de estos se puede representar por una matriz binaria de dos dimensiones, donde las columnas representan las transiciones, las filas los lugares y las celdas la conexión entre ambas. Las matrices reciben los nombres de “Matriz de incidencia previa” y “Matriz de incidencia posterior” respectivamente.
Podemos decir que una RdP N se encuentra definida matricialmente por medio de dos matrices. Sea n = |P| (número de lugares de P) y m = |T| (número de transiciones de T).
Se denominan:
Matriz de incidencia previa: C− = [c−ij]n×m en la que c−ij = Pre(pi, tj).
Matriz de incidencia posterior: C+ = [c+ij]n×m en la que c+ij = Post(ti, pj).
Matriz de incidencia de N: C = C+ − C−.
Ejemplo 1
Dada la RdP R1 = (P, T, F, W, M0), donde:
P = {p1, p2, p3, p4}, T = {t1, t2, t3 }, Mo=(5, 0, 0, 0)
Definiciones 5
Apunte de Redes de Petri
Figura 5
p1 t1 p2
t2
t3 p3
p4
Red de Petri con
cuatro lugares y tres transiciones.
Definiciones 6
Apunte de Redes de Petri
Matriz de Incidencia previa y matriz de incidencia posterior:
C- = Pre(pi, tj) =
1 0 0
C+ = Post(pi, tj) =
0 0 0
0 1 1 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
Sea N una RdP, donde t ∈ T y p ∈ P. Se definen los siguientes conjuntos:
Conjunto de lugares de entrada a t : •t = {p ∈ P | Pre(p, t) > 0}
Conjunto de lugares de salida de t : t• = {p ∈ P | Post(t, p) > 0}
Conjunto de transiciones de entrada a p : •p = {t ∈ T | Post(t, p) > 0}
Conjunto de transiciones de salida de p : p• = {t ∈ T | Pre(p, t) > 0}
Definiciones 7
Apunte de Redes de Petri
Marcado
Un marcado es una función que asigna a cada lugar un entero no negativo (marca), de forma que decimos que un lugar p está marcado con k marcas, si el marcado asigna al lugar p un entero k.
Un marcado M se representa mediante un vector con tantos componentes como lugares tenga la red. La cantidad de marcas en el lugar p será M(p).
Una RdP marcada es un par (N, M) formado por una RdP N y un marcado M.
El marcado de la RdP del ejemplo 1 :
M0 =
5
0
0
0
Evolución de marcado
El marcado cambia al disparar las transiciones. Para disparar una transición ha de estar validada y sensibilizada. Cuando una transición se dispara desaparecen las marcas de los lugares origen y se añade una marca a cada uno de los lugares destino.
Una transición t ∈ T está sensibilizada (habilitada) para un marcado M dado, sii ∀p ∈ •t se verifica M(p) ≥ Pre(p, t).
El grado de habilitación de una transición indica el máximo número que la transición puede ser disparada concurrentemente.
Regla de evolución del marcado:
Si t está habilitada para un marcado M entonces t puede dispararse. En la operación se alcanza un nuevo marcado M0, y se denota por M[t] > M0, el cual resulta de quitar Pre(p, t) marcas de cada lugar p ∈ •t y añadir Post(t, p) marcas a cada lugar p ∈ t•.
El cambio en el marcado esta dado por la ecuación:
M0(p) = M(p) − Pre(p, t) + Post(t, p), ∀p ∈ P
Cada disparo de una transición modifica la distribución de las marcas, y por ello produce un nuevo marcado en la red.
Siguiendo con el ejemplo 1, al disparar la transición t1, obtenemos:
M0 - Pre(p, t) + Pos(t, p) = Mf
5 1 0 0 0 0 0 4
0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0
Definiciones 8
Apunte de Redes de Petri
0 0 0 0 0 0 0 0
Figura 6
p1 t1 p2
t2
t3 p3
p4
Evolución del
marcado de la red del ejemplo 1.
Subclases de Redes de Petri
Grafo de estados
Un grafo de estado (GE) o máquina de estados (ME) es una RdP que cumple:
∀t ∈ T, |•t| = |t•| = 1
Grafo marcado
Un grafo marcado (GM) o grafo de sincronización es una RdP que cumple:
∀p ∈ P, |•p| = |p•| = 1
Red de libre elección
Una RdP de libre elección (RLE) es una RdP que cumple:
∀p ∈ P, si |p•| > 1, entonces ∀t ∈ p•, |•t| = 1
Red simple
Una RdP simple (RS) es una RdP que cumple:
p•1 ∩ p•2 = ∅ ⇒ p•1 ⊆ p•2 o p•1 ⊇ p•2 para toda p1, p2 ∈ P.
Definiciones 9
Apunte de Redes de Petri
Estructuras básicas
Selección
Selecciona el proceso a ejecutar
Figura 7 Estructura básica. Selección.
Atribución
Ejecución independiente de un proceso por dos procesos distintos
Figura 8
t1 t2
t3
p1
Estructura básica. Atribución.
Distribución
Ejecución de procesos paralelos o concurrentes
Definiciones
t1
t2 t3
p1
p2 p2
10
Apunte de Redes de Petri
Figura 9 Estructura básica. Distribución.
Conjunción
Sincronización de procesos en paralelo
Figura 10 Estructura básica. Conjunción.
Ejecución Secuencial
La transición t2 puede ser disparada sea antes disparado t1.
Figura 11
p1 p2 p3t1 t2
Estructura básica.
Ejecución secuencial.
Sincronización
La transición t1 estará habilitada para ser disparada todos los nodos de entrada de la transición t1 poseen al menos una marca en cada uno de ellos.
Definiciones 11
Apunte de Redes de Petri
Esto ocurre principalmente en la electrónica. Ej: El en circuito AND las dos entradas producen una salida lógica.
Figura 12
p1
p2
t1 p3
p1
p2
t1 p3
=>
E
structura básica. Sincronización.
Concurrencia
Las transiciones t2 y t3 son concurrentes. Con esta propiedad, las RdP es capaz de modelar sistemas de control distribuido con múltiples procesos ejecutándose concurrentemente.
Figura 13
p1
p2 p3
t1
t2
p4 p5t3
Estructura básica.
Concurrencia.
Conflictos
Tanto la transición t1 como t2 están listas para ser disparadas, pero el disparo de alguna de ellas produce que la otra transición quede inhabilitada para ser disparada.
Definiciones 12
Apunte de Redes de Petri
Figura 14
p1
p2
p3
t1
t2
p4
p1
p2
p3
t1
t2
p4
=>
Estructura básica. Conflictos.
Definiciones 13
Apunte de Redes de Petri
Propiedades
En las RdP podemos encontrar propiedades estructurales, que dependen de la estructura topológica de las RdP, independientes del marcado inicial y, las propiedades de comportamiento que sí dependen del marcado inicial
Propiedades estructurales
RdP Pura
Una RdP N es una red pura si no existe ninguna transición que tenga un lugar que sea al mismo tiempo de entrada y salida de la transición:
∀tj ∈ T , ∀pi ∈ P, Pre(pi, tj) Post(tj , pi) = 0
Red de Petri Acotada Estructuralmente
Una red de Petri está acotada estructuralmente si está acotada para cualquier marcado inicial finito.
Un lugar p en una red de Petri se dice no acotado estructuralmente si existe un marcado M y una secuencia de disparo σ desde M tal que p no esté acotado.
Red de Petri Estructuralmente Viva
Una red de Petri está estructuralmente viva si existe algún marcado inicial para el que está viva.
Red de Petri Completamente Controlable
Una red de Petri se dice completamente controlable si cualquier marcado es alcanzable desde cualquier otro marcado.
Red de Petri Estructuralmente Conservativa
Una red de Petri es estructuralmente conservativa si, para cualquier marcado inicial M0 y un marcado alcanzable M ∈ R(M0), existe un vector x (n × 1) tal que xi≠0, para cualquier i = 1,...,n, y xtM = xtM0.
Red de Petri (parcialmente) Repetitiva
Una red de Petri es (parcialmente) repetitiva si existe un marcado finito M0 y una secuencia de disparo s tal que (alguna) toda transición ocurre un número infinito de veces en σ.
Red de Petri (parcialmente) Consistente
Una red de Petri es (parcialmente) consistente si existe un marcado finito M0 y una secuencia de disparo s cíclica (desde M0 a M0 tal que (alguna) toda transición ocurre al menos una vez en σ.
Definiciones 14
Apunte de Redes de Petri
Propiedades de comportamiento
Vivacidad
Una transición t está viva para un marcado inicial dado M0, sii existe una secuencia de disparos a partir de un marcado M sucesor de M0 que comprenda a t :
∀M ∈ M(R, M0) ∃σ : M σ→M0 tal que t ⊂ σ.
Una RdP marcada está viva para M0 sii todas sus transiciones son vivas para M0.
Se puede decir que la propiedad de vivacidad significa la ausencia en el conjunto de alcanzabilidad de un marcado en el que la red se bloquee totalmente (deadlock), ya que, para que esté viva, todas sus transiciones deben ser disparables desde cualquier marcado alcanzable.
Se dice que una RdP marcada está parcialmente viva para M0 si, tomando como punto de partida cualquier marcado alcanzable a partir de M0, existe al menos una transición disparable y otra transición no viva. Toda RdP marcada parcialmente viva tiene la posibilidad de evolución global, independientemente de que existan transiciones que no puedan ser disparadas.
Ejemplo: Una red de Petri no viva.
Figura 15
p1
t1
p2 p3
t2
t3
p4
p5
t4
Ejemplo de una
RdP no viva.
Para la secuencia de disparos t1, t2, t1, t2, no hay bloqueo. Si ahora se disparan las transiciones t1, t3, t4, ya no se puede disparar ninguna transición más, la red queda “bloqueada”.
Podemos tener redes pseudo-vivas en las que existen algunas transiciones vivas y no se bloquea totalmente.
Ejemplo: RdP Pseudoviva
Definiciones 15
Apunte de Redes de Petri
Figura 16
p2 p3
p1
t1
p4 p5
t2 t3
t4
Ejemplo de una RdP pseudoviva.
Ciclicidad
Se dice que una RdP posee un comportamiento globalmente cíclico para M0 si existe una secuencia de disparos que permite alcanzar el marcado inicial M0 a partir de cualquier marcado M alcanzable a partir de M0:
∀M ∈ M(R, M0), ∃σ tal que M σ→M0.
La ciclicidad o reversibilidad de una RdP marcada garantiza que no existen subconjuntos finales de estados (marcados). Un subconjunto final de estados (marcados) contiene estados (marcados) mutuamente alcanzables entre sí y tales que el estado inicial (marcado inicial) no es alcanzable a partir de ninguno de ellos.
Ejemplo de una red no reversible:
Definiciones 16
Apunte de Redes de Petri
Figura 17
p2 p3
p1
t1
p4
t2
t3
Ejemplo de una RdP no reversible.
Esta RdP es pseudoviva, además no tiene la propiedad de reversibilidad ya que el marcado inicial no se puede obtener jamás.
Acotamiento
El significado de esta propiedad es el de asegurar que el sistema que una red representa posee un número finito de estados (si suponemos que cada lugar de la red representa a una variable de estado del sistema y su marcado el valor de dicha variable). Luego la propiedad de acotamiento determina la finitud del número de estados del sistema representado por una RdP.
Un lugar p es k-acotado para M0 sii existe un número entero k tal que M(p) ≤ k para cualquier marcado M ∈ M(R, M0). Se denomina cota del lugar p al menor entero k que verifica la desigualdad anterior.
Una RdP marcada es k-acotada para M0 sii todos sus lugares son k-acotados para M0:
∀p ∈ P y ∀M ∈ M(R, M0), M (p) ≤ k.
Merece una consideración especial la 1-acotación. Si una RdP es 1-acotada para M0, su marcado es binario (un lugar está o no está marcado) y se dirá que la RdP es binaria para M0. Una red segura, es una RdP 1-acotada. Una RdP es estructuralmente acotada si es acotada para cualquier marcado inicial y finito.
Se dice que la red está k-acotada si para todo marcado alcanzable tenemos que ningún lugar tiene un número de marcas mayor que k. Las redes 1-acotadas son conocidas como binarias.
Definiciones 17
Apunte de Redes de Petri
Si la red diseñada generar más marcas que las que su acotación permite el modelado será erróneo.
Ejemplo: Una red no acotada:
Figura 18
p2
p1
t1
p3
t2
t3
p4
p5
t4
Ejemplo de una RdP no
acotada.
Conservatividad
Las marcas de una red se pueden entender como recursos del sistema. Normalmente los recursos de un sistema ni se crean ni se destruyen. Cuando las marcas se conservan, tras el disparo de una secuencia de transiciones, se dice que la red es conservativa.
Sea R = (P, T, Pre, Post, M0) se dice que es estrictamente conservativa sii ∀M0 ∈ M(R, M0), ΣiM0 (pi) = ΣiM(pi), pi ∈ P.
Esto es, se ha de mantener el número de marcas para cualquier marcado de la red. La definición anterior implica que el número de entradas ha de coincidir con número de salidas, es decir: (|I(t j)|) = |O(tj)|), para cada transición disparable.
Definiciones 18
Apunte de Redes de Petri
Alcanzabilidad
La alcanzabilidad es una base fundamental para estudiar las propiedades dinámicas de cualquier sistema. al dispararse una transición habilitada, esta cambiará la distribución de las señales ( marcado). De esta forma, de una secuencia de disparos resultará una secuencia de marcados, luego un marcado Mn es alcanzable a partir de M0, si existe una secuencia de disparos que a partir de M0 nos lleve a Mn. Una secuencia de disparos la denotaremos por σ = t1, t2, ....., tn . en este caso Mn es alcanzable desde M0, sii ∃σ t.q. M0 [σi Mn.
Ejemplo RdP y su grafo de alcanzabilidad
Figura 19 Ejemplo de una RdP con su grafo de alcanzabilidad.
Definiciones 19
Apunte de Redes de Petri
Extensiones
Recursos compartidos
Las RdP permiten modelar sistemas donde un recurso es compartido por dos procesos de forma que el uso del recurso durante la ejecución de un proceso impide que dicho recurso sea utilizado por el otro proceso.
Un recurso compartido se modela mediante un lugar con una marca inicial y transiciones en conflicto.
Ejemplo:
Figura 20E
xtensiones. Recursos compartidos.
Arcos inhibidores:
Figura 21 Extensiones. Arcos inhibidores.
Estos tipos de arcos se relacionan con la transición a ser inhibida y con el lugar que, de tener una marca, va a impedir el disparo de la transición.
Definiciones 20
Apunte de Redes de Petri
Validación
La validación consiste en comprobar que se cumplen las propiedades de:- VIVACIDAD; LIMITACIÓN; REVERSIBILIDAD.
Hay que considerar :
M0 : marcado inicial. De este se desprende el comportamiento del sistema.
[M0] : vector de marcados posibles a partir de un marcado inicial. (marcados alcanzables).
Ejemplo:
Figura 22 Validación de una RdP.
Métodos de Análisis
Las técnicas para el análisis de RdP (análisis cualitativo de redes) se clasifican normalmente en tres grupos.
Técnicas Enumerativas
En primer lugar se tienen las técnicas enumerativas.
Se basan en la generación del grafo de alcanzabilidad para sistemas limitados o del grafo de cobertura para sistemas no limitados. Estas técnicas se pueden aplicar en teoría, pero en la práctica están limitadas a sistemas pequeños debido a su elevada complejidad computacional. En este grafo los nodos corresponden al marcado alcanzable y los arcos corresponden al disparo de las transiciones. En la figura se muestra una red de Petri y su grafo de alcanzabilidad (Grafo de marcados).
Definiciones 21
Apunte de Redes de Petri
Figura 23
Técnica enumerativa de validación.
Este grafo puede ser utilizado para mostrar que la red es segura, viva, reversible y que esta tiene dos componentes que se repiten t1, t2,t4 y t1, t3,t5.
En una red no limitada, el número de señales en un lugar puede ser infinito. Un lugar que puede llegar a tener un número infinito de señales se representa por ω. El grafo resultante es llamado grafo de cobertura.
Técnicas de Transformación
En segundo lugar se tienen las técnicas de transformación. En este grupo de técnicas el objetivo es reducir el tamaño de los modelos mediante reglas de reducción que preserven las propiedades que se quieren estudiar. En la figura puede observarse un conjunto sencillo de seis reglas de reducción que preservan vivacidad y k-limitación.
Reglas de reducción que presentan vivacidad y k-limitación:
Definiciones 22
Apunte de Redes de Petri
Figura 24Té
cnica de transformación de validación.
Con este conjunto de reglas es posible reducir la complejidad del cálculo de la vivacidad y limitación de un sistema.
Técnicas Estructurales
En tercer lugar se tienen las técnicas estructurales. En este grupo de técnicas el objetivo es obtener la máxima información del modelo utilizando únicamente su estructura y marcado inicial.
Los métodos de álgebra lineal son utilizados para determinar las propiedades de la red.
La ecuación de estado de una red de Petri se define como sigue: el marcado Mk se define como un vector columna m × 1. La j−esima entrada de Mk denota el número de señales en el lugar j inmediatamente después del k−esimo disparo en la secuencia de disparos. El k−esimo disparo o vector de control uk es un vector columna de n × 1, con n−1 ceros y una
Definiciones 23
Apunte de Redes de Petri
entrada 1 en la i−esima posición, indicando el disparo de la transición i. Esto es, la i−esima fila de la matriz de incidencia C denota el cambio de marcado como el resultado del disparo de la transición i, luego la ecuación de estado para la red de Petri se escribe como sigue:
Mk = Mk−1 + CT uk, k = 1, 2, 3, ….
El marcado de una red de Petri puede ser cambiado cada vez que una transición se dispara. Si no ocurre un bloqueo, el número de disparos es ilimitado. Sin embargo, no todos los marcados pueden ser alcanzados y no todas las secuencias de disparos pueden ser llevadas a cabo. Las restricciones son dadas por los invariantes de la red. Un marcado invariante es obtenido si la suma de los pesos de el marcado de un subconjunto de lugares en una red es siempre constante. Los lugares contenidos en este subconjunto son llamados componentes conservativos y el vector que contiene los pesos es P-Invariante. Si el disparo de una cierta secuencia de transiciones resulta en el mismo marcado como cuando inicio, la secuencia es llamada componente repetitivo. El vector característico de la secuencia de disparos es el T-Invariante.
Definiciones 24
Apunte de Redes de Petri
Tipos de red
RdP con peso
Permite que multiples tokens puedan ser quitados/agregados cuando se dispara una transición. Las aristas están etiquetadas con el peso (número de tokens). Si no hay ningún valor se asume que es 1.
RdP con Tiempo
Las Redes de Petri no incluyen concepto alguno de tiempo, por ello, solamente es posible describir solamente la estructura lógica de los sistemas y no su evolución temporal.
La introducción del tiempo en el modelo permite la descripción de comportamientos dinámicos de los sistemas, considerando la evolución de estados y la duración de cada acción tomada por el sistema. Hay múltiples formas diferentes de introducir el concepto de tiempo.
Una primera posibilidad consiste en asociar a cada transición un número que indica, en alguna unidad temporal adecuada, el retardo entre la habilitación y el disparo de la transición. Una RdP Temporizada puede ser definida como:
TPN = {P, T, A, M0, Q}
donde P, T, A y M0 se definen como antes
Q=(q1, q2,…,qm) es el conjunto de retardos asociados a las transiciones.
Una segunda posibilidad para la introducción del concepto de tiempo consiste en asignar un retardo q al proceso de convertir una ficha en disponible luego que la misma llega a un nuevo lugar. Por ello, cada ficha puede estar en uno de dos estados: disponible y no disponible; solamente fichas disponibles habilitan transiciones. La falta de disponibilidad de una ficha modela el tiempo utilizado desarrollando una actividad. En esta abstracción, el tiempo es asociado a los lugares.
La adición de tiempos en las Redes de Petri es un proceso crítico y se deberá prestar atención especial a la comprensión total de la semántica del modelo y a los detalles de su comportamiento.
Existe una amplia variedad de extensiones adicionales, que básicamente consisten en adicionar tiempos a las diferentes componentes del grafo bipartito que constituye la red.
RdP coloreadas
En general, los tokens representan objetos (recursos, personas, etc) en el modelado de un sistema. Para representar los atributos de estos objetos, se utilizan las RdP coloreadas, donde los colores representan las características de los objetos modelados. Las transiciones usan los valores de los tokens adquiridos para determinar los valores de los tokens producidos.
Definiciones 25
Apunte de Redes de Petri
Una transición describe la relación entre los valores de los tokens. Es posible especificar precondiciones, utilizando el color de los tokens para ser consumidos.
RdP jerárquicas
Las especificaciones de sistemas reales tienen una tendencia a ser grandes y complejos. Un mecanismo de abstracción, estructuración jerárquica, se utiliza para poder modificar más fácilmente el modelo. La construcción jerárquica se llama subred. Una subred es un agregado de número de lugares, transiciones y subsistemas. Se puede utilizar para estructurar grandes procesos. En determinados niveles, se quiere dar una simple descripción de un proceso (sin considerar todos los detalles). Pero a otro nivel quizás, se quiera especificar un comportamiento mas detallado. Cada subred se representa con un rectángulo que encapsula parte del modelo general.
Estocásticas (conceptos redes petri.pdf)
Los modelos de performance tratan de representar el comportamiento de sistemas determinísticos complejos por medio de procesos estocásticos. De esta forma es posible evitar una detallada descripción determinística de las operaciones del sistema, sustituyéndola por asunciones probabilísticas, que capturen la esencia del sistema.
Las Redes de Petri Estocásticas (SPN) se obtienen asociando con cada transición en una RdP una variable aleatoria con distribución exponencial que exprese el retardo desde la habilitación hasta el disparo de la transición. Eliminando las variables aleatorias de una SPN se obtiene la RdP asociada.
Consideremos una SPN y un marcado M en el cual múltiples transiciones están simultáneamente habilitadas. La transición que tiene asociado el retardo más breve disparará primero. La SPN alcanza un nuevo marcado M’, en el cual algunas transiciones estuvieron habilitadas en el marcado M pero que no fueron disparadas y pueden aun estar habilitadas. Debido a la propiedad de falta de memoria de las variables aleatorias exponencialmente distribuidas, obtenemos una distribución de vida igual a la distribución del retardo de disparo en sí mismo. Se puede asumir que la actividad asociada con cada transición recomienza con cualquier nuevo marcado. Esto es válido inclusive cuando se está modelando actividades que se suceden en forma continua: el modelo no “siente” la repetición de actividades asociadas con una transición.
Una definición formal de una SPN es:
SPN = {P, T, A, M0, L}
donde P, T, A y M0 se definen como antes y
L=(l1, l2,…,lm) es el conjunto de tasas de retardos asociados con las transiciones, posiblemente dependientes del marcado, asociadas con las transiciones de la Red de Petri.
Cuando sea necesario, la dependencia con un marcado dado M se representará como lj(M).
Definiciones 26
Apunte de Redes de Petri
Se puede probar que, debido a la propiedad de falta de memoria de la distribución exponencial de los retardos en los disparos, las SPN son isomórficas a cadenas de Markov de tiempo continuo. En particular, una SPN k-acotada es isomórfica a una MC finita. La misma se puede obtener aplicando las siguientes reglas:
1. El espacio de estados S de la MC corresponde al conjunto de alcance R(M0) de la Red de Petri asociada con la SPN (Mi<->i).
2. La tasa de transición del estado i (correspondiente a M i) al estado j (Mj) es (Mj) es qij = Σk∈Hij lk, donde Hij es el conjunto de transiciones habilitadas por el marcado Mi, cuyos disparos generan el marcado Mj.
Una SPN se dice ergódica si genera una CTMC. Es posible mostrar que una SPN es ergódica si M0, el marcado inicial, es alcanzable desde cualquier Mi que pertenece R(M0).
Si la SPN es ergódica, es posible calcular la probabilidad de distribución de marcados en el estado estacionario resolviendo la ecuación matricial ΠQ = 0 con la restricción adicional ΣΠi = l, donde Q es el generador infinitesimal cuyos elementos se obtienen por el método de construcción de la MC anterior y p es el vector de probabilidades del estado estacionario. A partir de la distribución de probabilidades del estado estacionario es posible obtener estimaciones cuantitativas del comportamiento de la SPN.
Redes de Petri Estocásticas Generalizadas
Frecuentemente no es deseable asociar un tiempo aleatorio a cada transición. Naturalmente se tiende a asociar tiempos con las transiciones más lentas o aquellas que se cree que tienen un mayor impacto en la performance global del sistema y a asumir instantáneas aquellas muy breves o cuya duración se estima que no tendrá impacto en la performance global.
Un ejemplo típico puede ser el caso en el cual las actividades que componen el sistema poseen diferencias en duración de órdenes de magnitud. La opción se convierte en particularmente conveniente si el número de estados de la Cadena de 27arkov asociada se reduce. Las Redes de Petri Estocásticas Generalizadas (GSPN) se obtienen permitiendo que las transiciones pertenezcan a dos clases diferentes: inmediatas y temporizadas. Las transiciones inmediatas disparan en tiempo cero una vez que están habilitadas. Las transiciones temporizadas disparan luego de un tiempo de habilitación aleatorio, exponencialmente distribuido. Una definición formal para las GSPN se obtiene haciendo que los elementos del arreglo L sean solamente elementos m’, aquellos asociados a transiciones temporizadas. Si el conjunto de transiciones habilitadas H incluye solamente transiciones temporizadas, entonces la transición ti (i pertenece H) dispara con probabilidad li / Σk∈Hlk como en el caso de SPN. Si H involucra transiciones temporizadas e inmediatas simultáneamente, únicamente dispararán transiciones inmediatas. Si H involucra cero o más transiciones temporizadas y solamente una transición inmediata, solamente disparará la transición inmediata. Cuando H involucra varias transiciones inmediatas, es necesario especificar la función de densidad de probabilidad en el conjunto de transiciones inmediatas habilitadas de a cuerdo a la cual se obtiene la transición que dispara. El subconjunto H que involucra todas las transiciones
Definiciones 27
Apunte de Redes de Petri
inmediatas habilitadas, junto con las probabilidades de distribución es llamado switch aleatorio (random switch).
Definiciones 28
Apunte de Redes de Petri
Ejercicios
Ejercicio Nº 1:
a. Dada la siguiente RdP, indique cuál es la matriz de incidencia previa y la matriz de incidencia posterior.
Figura 25 Ejercicio 1.
b. Dado el marcado inicial 0 = (0, 1, 0, 0) indique cuáles de los siguientes son marcados son alcanzables desde 0.
a. = (w, 1, 0, 0), w >=0
b. = (w1, 0, 1, w2), w1 >=0, w2 >=0
c. = (0, 1, 1, w), w >=0
d. = (w1, 0, 0, w2), w1 >=0, w2 >=0
Ejercicio Nº 2:
Dadas las siguientes redes de Petri, indicar cuáles de ellas pueden entrar en deadlock. (si al menos existe un marcado en el cual no se puede disparar ninguna transición, entonces la red entra en deadlock)
En caso de que así sea dar una secuencia de disparos que lleve a esta situación.
Definiciones 29
Apunte de Redes de Petri
Figura 26 Ejercicio 2 a.
Figura 27 Ejercicio 2 b.
Ejercicio Nº 3:
Construya una red de Petri para especificar el funcionamiento de una máquina expendedora de bebidas. La misma tiene un depósito de bebidas con una cierta carga inicial, y un depósito de monedas el cual inicialmente se encuentra vacío.
Cuando se le ingresa una moneda y hay bebidas, la máquina entrega una bebida y almacena la moneda en el depósito correspondiente.
¿Cómo modelaría la situación de que cuando no hay más bebidas la máquina retorne la moneda?
Ejercicio Nº 4:
Existen pequeñas diferencias entre los sistemas de luces de tránsito en diferentes países. Por ejemplo, el sistema de luces alemán tiene una fase extra en su ciclo. Las luces no cambian repentinamente de rojo a verde sino que antes de pasar al verde enciende la luz verde junto con la luz amarilla.
Construya una red de Petri que se comporte como el sistema de luces de tránsito alemán. Asegúrese que la red no permita transiciones que no son posibles.
Definiciones
30
Apunte de Redes de Petri
Ejercicio Nº 5:
a. Construya una red de Petri para especificar el funcionamiento de un sistema de control de barreras de un paso a nivel.
Cuando un tren se acerca, éste es detectado por un sensor que ocasiona que se baje la barrera del paso a nivel. Cuando se aleja el tren, es detectado por otro sensor que ocasiona que se eleve la barrera. Si la barrera está elevada, los vehículos que lleguen al paso a nivel pueden pasar a través de él, en caso contrario deben esperar hasta que la barrera sea levantada.
b. Verifique que el modelo construido no permita la situación en la que la barrera se encuentre alta, arribe un tren y un vehículo, y se le dé el paso al vehículo antes de bajar la barrera. Si no es así modifíquelo para que no se dé dicha situación.a. Construya una red de Petri para especificar el funcionamiento de un sistema de control de barreras de un paso a nivel.
Ejercicio Nº 6:
Usando alguna de las extensiones estudiadas, construya una Redes de Petri que describa el siguiente problema: Un proceso despachador de mensajes recibe mensajes provenientes de dos canales diferentes. Verifica la paridad de cada mensaje. Si la paridad es incorrecta, envía un aviso de no-reconocimiento del mensaje a través de un canal de respuesta (existe un canal de respuesta por cada canal de entrada); si la paridad es correcta, coloca el mensaje recibido en un buffer. El buffer puede contener hasta diez mensajes. Cuando el buffer está lleno, el despachador envía todo el contenido del buffer a una unidad de procesamiento a través de otro canal. No se pueden colocar mensajes en un buffer lleno.
Ejercicio 7
Resuelva mediante una RdP el siguiente problema:
Un grupo de 5 filósofos se encuentran 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.
Ejercicio 8
Tres fumadores están representados por los procesos F1, F3 y F3. Tres vendedores están representados por los procesos V1, V2 y V3. Para fumarc cada fumador necesita tabaco, papel para tabaco y un fósforo; cuando dispone de estos recursos, el fumador fuma un cigarrillo hasta terminarlo y entonces queda elegible para fumar de nuevo. F1 tiene tabaco, F2 tiene papel y F3 tiene fósforos. V1 vende tabaco y papel, V2 vende papel para tabaco y fósforos, y V3 vende fósforos y tabaco. V1, V3 y V3 trabajan
Definiciones 31
Apunte de Redes de Petri
en exclusión mutua; sólo uno de los procesos puede trabajar a la vez y el siguiente vendedor no puede trabajar hasta que los recursos suministrados por el vendedor anterior hayan sido consumidos por un fumador.
A partir de este enunciado, dibuje una RdP que represente el problema y sus matrices de incidencia previa y posterior.
Definiciones 32
Apunte de Redes de Petri
Respuestas a los ejercicios
Ejercicio 1
Matriz de incidencia previa (P t)
t1 t2 t3 t4
P1 0 1 0 0
P2 0 1 0 0
P3 0 0 1 0
P4 0 0 0 1
Matriz de incidencia posterior (t P)
t1
t2
t3
t4
P1
1 0 0 0
P2
0 0 1 0
P3
0 1 0 0
P4
0 0 1 0
a. Marcado alcanzable.
b. Marcado alcanzable.
c. Marcado no alcanzable.
d. Marcado no alcanzable.
Ejercicio 2
a) no
b) no
Definiciones 33
Apunte de Redes de Petri
Ejercicio 3
Figura 28
p1t1
t3
p2
p4
p3
t2Ingresa moneda
Depósito provisorio
Bebidas
Depósito de monedas
Salida de monedas
p5
Salida de bebidas
Respuesta al ejercicio 3. Máquina expendedora de bebidas.
Definiciones 34
Apunte de Redes de Petri
Ejercicio 4
Figura 29
p1
t1
p2
p3
t2
p4
p5 t3t4
Rojo
Verde
Amarillo
Verde
Amarillo
Respuesta al ejercicio 4. Semáforo alemán
Definiciones 35
Apunte de Redes de Petri
Ejercicio 5
Figura 30
p1 p2
p3
t1
t2 p4 t3p5
t5
p7
t6 p8
p6 t4
Tren acercándose Sensor A
Sensor B
Barrera en alto
Barrera baja
Tren alejándose
Automóviles para cruzar
Automóviles que cruzaron
Respuesta al ejercicio 5. Sistema de control de barreras de un paso a nivel.
Ejercicio 6
Se utilizaron RdP coloreadas para identificar los mensajes que circulan por distintos canales. En rojo los mensajes del canal A y en azul los mensajes del canal B.
Definiciones 36
Apunte de Redes de Petri
Figura 31
p2
p1
t2
t1
t5p3
p8
p7
t7
p6
t8
t6
t9
t3 p4 t4 p5
Canal A
Canal B
Calcular paridad
Mensajes con errores
BufferK = 10
Unidad de procesamiento
K = 10
Canal A de error
Canal B de error
Respuesta al ejercicio 6. Despachador de mensajes.
Ejercicio 7
Matriz de incidencia previa
V1
V2
V3
F1
F2
F3
1
1 1 1 0 0 0
2 0 0 0 0 0 1
3 0 0 0 1 0 0
4 0 0 0 0 1 0
Matriz de incidencia posterior
V1
V2
V3
F1
F2
F3
1 0 0 0 1 1 1
2 1 0 0 0 0 0
3 0 1 0 0 0 0
4 0 0 1 0 0 0
Definiciones 37
Apunte de Redes de Petri
Ejercicio 8
Figura 32
p2
V1 V2 V3
p2 p2 p2
F3 F1 F2
Respuesta al ejercicio 8.
Definiciones 38
Apunte de Redes de Petri
Glosario
Conjuntos
{e1, e2, . . . , en}
Conjunto formado por los elementos e1, e2, . . . , en, (por extensión)
(e|r) Conjunto formado por los elementos e que cumplen la propiedades r (notación por comprensión)
∈ Pertenencia
No pertenencia
Conjunto vacío
A U B Unión de los conjuntos A y B
A B Intersección de los conjuntos A y B
A X B Producto cartesiano de A por B [conjunto de los pares (a, b), aeA y bEB]
A ⊂ B Inclusión del conjunto A en el conjunto B
A ⊆ B Inclusión o igualdad del conjunto A en el conjunto B
Lógica
∃ Existe (cuantificador existencial)
∀ Para todo (cuantificador universal)
⇒ Implica.
⇔ Sí y solo sí.
Definiciones 39
Apunte de Redes de Petri
Índice de imágenes
FIGURA 1 REPRESENTACIÓN GRÁFICA DE UNA RDP....................................................................4FIGURA 2 LUGAR ACTIVO............................................................................................................4FIGURA 3 TRANSICIÓN SENSIBILIZADA.......................................................................................4FIGURA 4 TRANSICIÓN VALIDADA..............................................................................................5FIGURA 5 RED DE PETRI CON CUATRO LUGARES Y TRES TRANSICIONES....................................5FIGURA 6 EVOLUCIÓN DEL MARCADO DE LA RED DEL EJEMPLO 1.............................................8FIGURA 7 ESTRUCTURA BÁSICA. SELECCIÓN..............................................................................9FIGURA 8 ESTRUCTURA BÁSICA. ATRIBUCIÓN............................................................................9FIGURA 9 ESTRUCTURA BÁSICA. DISTRIBUCIÓN.......................................................................10FIGURA 10 ESTRUCTURA BÁSICA. CONJUNCIÓN.......................................................................10FIGURA 11 ESTRUCTURA BÁSICA. EJECUCIÓN SECUENCIAL.....................................................10FIGURA 12 ESTRUCTURA BÁSICA. SINCRONIZACIÓN................................................................10FIGURA 13 ESTRUCTURA BÁSICA. CONCURRENCIA..................................................................11FIGURA 14 ESTRUCTURA BÁSICA. CONFLICTOS........................................................................11FIGURA 15 EJEMPLO DE UNA RDP NO VIVA..............................................................................13FIGURA 16 EJEMPLO DE UNA RDP PSEUDOVIVA.......................................................................14FIGURA 17 EJEMPLO DE UNA RDP NO REVERSIBLE..................................................................15FIGURA 18 EJEMPLO DE UNA RDP NO ACOTADA......................................................................16FIGURA 19 EJEMPLO DE UNA RDP CON SU GRAFO DE ALCANZABILIDAD.................................17FIGURA 20 EXTENSIONES. RECURSOS COMPARTIDOS...............................................................18FIGURA 21 EXTENSIONES. ARCOS INHIBIDORES.......................................................................18FIGURA 22 VALIDACIÓN DE UNA RDP......................................................................................19FIGURA 23 TÉCNICA ENUMERATIVA DE VALIDACIÓN...............................................................20FIGURA 24 TÉCNICA DE TRANSFORMACIÓN DE VALIDACIÓN....................................................21FIGURA 25 EJERCICIO 1.............................................................................................................26FIGURA 26 EJERCICIO 2 A.........................................................................................................27FIGURA 27 EJERCICIO 2 B..........................................................................................................27FIGURA 28 RESPUESTA AL EJERCICIO 3. MÁQUINA EXPENDEDORA DE BEBIDAS......................30FIGURA 29 RESPUESTA AL EJERCICIO 4. SEMÁFORO ALEMÁN..................................................30FIGURA 30 RESPUESTA AL EJERCICIO 5. SISTEMA DE CONTROL DE BARRERAS DE UN PASO A NIVEL. 31FIGURA 31 RESPUESTA AL EJERCICIO 6. DESPACHADOR DE MENSAJES....................................31Figura 32 Respuesta al ejercicio 8..........................................................................................32
Definiciones 40
Apunte de Redes de Petri
Bibliografía
C. Ramchandan. “Analysis of Asynchronous concurrent systems by timed petri nets”, MIT MAC-TR-120, 1974.
Ing. Jair Cervantes Canales. Representación y aprendizaje de conocimiento con redes de Petri difusas. Mexico 2005.
K. Jensen, “Colored Petri nets and the invariant method”, Theoretical Computer Science, volume 14, 1981, pp. 317-336.
Murata, Tadao. “Petri Nets: properties, analysis and applications”. Proceedings of the IEEE, VOL. 77, No. 4. April 1989.
Definiciones 41