Redes de Petri

June 7, 2018 | Author: fateway | Category: Time, Model Theory, State (Polity), Analogy, Knowledge
Report this link


Description

www.vb-mundo.com Redes De Petri 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 precondiciones 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. La PN puede ser considerada también como un modelo de flujo de información.p2. p3.I(t2))=1 T={t1. Los tokens son representados por pequeños puntos . P T= I.I. un número de ellos reside en los nodos y se mueve entre ellos.p3.T.I. p5} I(t3) ={p3} I(t4) ={} I(t5) ={p4} Donde: #(p3.O) es una función U: P N.O: T P Un nodo pi es un nodo de entrada de la transición tj sí pi I(tj).p2.T. Escribimos esto como: #(p i. Dicho de otra manera la información depende de lo que la PN esta modelando.t3.O(tj)). 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. su número puede variar entre nodos y son los que determinan la situación de la red en un momento determinado. Un token es un concepto primitivo de una PN. De igual forma para la salida lo cual escribimos: #(pi.t2. t5} O(t1)={p2. el nodo será una salida de esa transición.I. Ejemplo: P=(P.t2. vk P. con n 0.T.O) es una gráfica múltiple bipartita dirigida G=(V.t2. Definición: Una gráfica G de una PN P=(P. las transiciones. …. Definición: Una marca U de una PN P=(P. 3. en donde el comportamiento dinámico de los tokens representan el flujo. una barra representa una transición. Estructura de una red de Petri.T. an} es un conjunto de arcos dirigidos ai=(vj. los tokens son la parte dinámica de la PN. t4. pi es un nodo de salida sí pi O(tj).vk) vj P. La estructura de una PN es definida por los nodos.O(t1))=1 Una marca U es una característica de la PN. t5} I(t1) ={p1} O(t1)={p2. vk T. p3} #(p5. v2. p4. Las funciones de entrada y salida relacionan a los nodos y a las transiciones. la función de entrada y la función de salida. T={t1. p5} T={t1. Los arcos o curvas conectan los nodos y las transiciones.…. p5} I(t1) ={p1} I(t2) ={p2. Un circulo representa un nodo.O) P={p1. t4.I.pn} es un conjunto finito de nodos.vk) con vj. Es decir el nodo pi tiene U(pi) tokens.2.I(tj)). p4.…. Representación gráfica de una red de Petri. a2. marca U es una asignación de tokens a la PN. V=P T para cada ai A se cumple aj=(vj. p3.O) donde: P={p1. …. Las PN se componen de cuatro partes:  Un conjunto de nodos.t3.A) donde V={ v1. La multiplicidad de un nodo de entrada p i para una transición tj es el número de ocurrencias del nodo en el bag de entrada de la transición. p5} . Definición: La estructura de la PN P=(P. Ahora consideremos la PN vista anteriormente: P=(P. 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. vn} es un conjunto de vértices y A={ a1.p2.O) P={p1.I.tm} es un conjunto finito de transiciones con m 0. Las entradas y salidas de una transición son conjuntos que tienen elementos repetidos o múltiples ocurrencias de nodos (bags). 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.p3.  Una función de entrada y  Una función de salida.T. p5} O(t2)={p5} O(t3)={p4} O(t4)={p2. p3. vk V. ó vj T.  Un conjunto de transiciones. p3} O(t5)={p2. La transición t2 no puede ser disparada p2 • p1 t1 p5 t2 • t4 p4 •• p3 t3 porque no hay tokens en el nodo p2. 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.I(tj)). remueve tokens de cada entrada y los deposita en cada salida.O(t1))=1 p2 • p1 t1 •• p5 t2 t5 t4 • p4 p3 t3 4.I.0). U(pj)>=#( pj. p3. p3} #(p5. entonces remueve un token de p4 y deposita un . 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.I(t2))=1 O(t2)={p5} O(t3)={p4} O(t4)={p2.O) con una marca U es ENABLED si para todo pj P. deben tener al menos el mismo número de tokens. t3 y t4 son ENABLED cualquiera de ellas puede ser disparada. Una PN se activa disparando transiciones. Reglas de disparo para una PN. p5} I(t3) ={p3} I(t4) ={} I(t5) ={p4} Donde: #(p3. para que ésta sea disparada. el cual es entrada de ella.1. Sí la transición t4 es disparada.2. La ejecución en una PN es controlada por el número y distribución de los tokens que tiene. Podemos asociar de manera natural un vector u enlistando los valores de U. t3. Consideremos la siguiente PN: Sólo 3 transiciones están en un estado ENABLED t1. Una transición es disparada removiendo tokens de los nodos de entrada y creando tokens de salida.I(t2) ={p2. Así para la PN mostrada tenemos u=(1. Dado que t1. Es decir por cada arco de salida es liberado un token. 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. depositaria un token en cada uno de ellos). De aquí podemos obtener la primera condición de disparo en una transición: todos los nodos de entrada de la transición. t4. que de arcos que van hacia la transición. Los tokens presentes en los nodos controlan la ejecución de las transiciones de la red.0. p3} O(t5)={p2. • p2 • p1 t1 p5 t2 • •• t4 p4 p3 t3 Las transiciones pueden seguir disparándose indefinidamente hasta llegar a un estado deseado o hasta que ninguna pueda ser disparada. una transición para cada nodo es la que se encarga de quitar unidades en los sumandos y poner unidades en el resultado.token en p2 e incrementa el número de tokens en p3 de dos a tres. Pensemos en un ejemplo concreto: queremos sumar cuatro números cualesquiera por medio de una PN. Extensiones al Modelo de Redes de Petri . 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. en la siguiente figura notamos que t 1 y t2 pueden dispararse. si es necesario definir dos atributos entonces surge la idea de colores compuestos. Esto es conocido como un conflicto y nos ayuda a modelar problemas de sincronización. la realizan t5 y t6.O de la PN.0) y el estado de la red se mueve a como se muestra en la siguiente figura. cuando se efectúan las dos sumas. estas redes manejan una función asociada para los elementos de las funciones I. • •• t1 p1 t2 p5 p2 t5 •• •• p3 ••• •• t3 t4 p4 p7 p6 t6 5. p2. Entonces además del concepto de color. la diferencia viene marcada por las consideraciones en CPN de colores y de funciones lineales asociadas a sus arcos. el vector u sería (1. Dependiendo de cada número se ponen tantos tokens en los nodos correspondientes p 1. 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. no podremos disparar t1.1. se realiza una tercera suma.0. Los primeros resultados parciales se almacenan en p5. pero si t1 es disparada. su resultado se pone en p7. y los últimos en p6. 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. 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. t2 dejará de ser ENABLED y si disparamos t2. Los tokens de color pueden representar un atributo o distintivo. p3 y p4.3. Redes de Petri Coloreadas Las redes de Petri coloreadas (CPN) pertenecen a la familia de las PN. ya que los tokens indican si esta condición se cumple o no. La transición. Así por ejemplo la siguiente figura disparará cuando p1 tenga un token. Es una consideración importante ya que los sistemas reales casi siempre es indispensable considerarlo en la sincronización de los procesos. Las ordenes requieren de dos procesos. en el sentido de que una condición es verdadera para una cierta cantidad de tiempo. 6. Los nodos. Redes de Petri Temporales. son representadas por los nodos. p1 p2 t1 p3 Este tipo de redes son las que consideran el tiempo en el modelo. 7. en el sentido de que un evento toma una cierta cantidad de tiempo en ocurrir. 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 1.M2 y M3. Se toma como referencia que las condiciones que se dan en un sistema. y p2 no tenga tokens. El operador O1 puede trabajar las máquinas M1 y M2 y el operador O2 las máquinas M1 y M3.Un arco inhibidor es otro componente de una PN. y los eventos con las transiciones. simplemente se estiman límites dentro de los cuales el evento puede ocurrir. y dos operadores O1 y O2. dividiendo el sistema en eventos y condiciones y de esta manera encontrar la analogía con la PN. 3. 2. Cuando la duración de los eventos no son fijos. que necesitan de condiciones para poder ser disparadas. Consideremos el siguiente sistema: Un taller que tiene tres máquinas. El modelo más simple es el que asigna duración a: 1. 6. 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 . Podemos modelar sistemas complejos con PN. Modelado con Redes de Petri Eventos y condiciones. o no pueden ser expresados con valores nominales. 8. éste va de un nodo a una transición y es representado con un pequeño circulo al final del arco. 5. 4. M1. En general las extensiones a la teoría de PN dependen del modelo o la aplicación donde se estén usando. 2. 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. D. H. H. el problema consiste de cinco filósofos que en forma alternada piensan y comen. Este problema puede dar una idea clara del potencial de una PN. 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. D 6 B.9. para comer comida china necesitamos dos palillos. E 8 B. h Eventos Precondiciones Postcondiciones 1 Ninguna A 2 A. G. B 4 A. G. D J 5 J B. 10. f . El operador O2 termina la orden en M3 La orden es terminada y liberada Precondiciones y postcondiciones de cada evento Condiciones Iniciales: d. H 10 c Ninguna La PN se muestra a continuación: g • 2 i 3 6 a 1 5 j 4 • h El problema de los cinco filósofos. e. 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. g. D I 3 I G. lo que producirá que los otros filósofos no puedan comer (cayendo en un estado de inanición). E K 7 K C. H I 9 L C. 8 • d b l 10 f • 9 k c e • 7 . cada filósofo tiene frente a él un plato donde servirse y entre cada uno de ellos un palillo chino. otro problema puede surgir y es el que un filósofo obtenga siempre los dos palillos y se mantenga comiendo. entonces cada filósofo para comer debe tener dos palillos en su poder. Están sentados en una mesa circular donde ha sido depositada comida china. Como sabemos. F. f. G. 2 y 4 pueden modelarse con un sólo nodo. 2. 7 1. Cada filósofo es representado por dos nodos M y C representan los estados meditando y comiendo respectivamente. 5 Eventos Precondiciones 1 6 2 3.. al inicio cuando todos los filósofos piensan.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 1.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. 4.5 Postcondiciones 1. 4. entonces sus dos nodos deben tener un token y de esta manera poder comer. Para que un filósofo coma es necesario que tenga los dos palillos en sus manos.P5 representan los palillos. cada nodo tiene un token. las condiciones 1 y 3. El problema para cinco filósofos es modelado como se muestra en la siguiente figura. 8 Como sabemos las condiciones corresponden a nodos y los eventos a transiciones. 5 Eventos Precondiciones 1 6 2 1. 7 Postcondiciones 3. 2.2.2. 4. 4.5 3. 6 3.4. Los nodos P1. 5 3 8 4 3.2. . 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. siendo la principal. aplicados principalmente hacia el control y proceso. Conclusiones Podemos concluir diciendo de que las Redes de Petri son una alternativa de modelado de sistemas. un circulo representa un nodo y una barra representa una transición. que número de arcos van . Cuentan con una asignación de tokens que es la parte dinámica de las Redes de Petri. y los tokens son representados por pequeños puntos . la que dice: "todos los nodos de entrada de la transición. Las Redes de Petri tienen reglas de disparo. deben tener al menos el mismo número de tokens.C1 P5 • P1 C5 • C2 M1 M5 M2 • P4 M4 • • P2 M3 • • C4 P3 C3 7. Las Redes de Petri se pueden representar gráficamente. por su facilidad de manejo en el problema de la sincronización de procesos. com .hacia la transición para que ésta sea disparada". Redes de Petri Estocásticas. Trabajo enviado por: Mabel Gonzales Urmachea mabelgonzalesu@hotmail. las Redes de Petri Temporales. Podemos modelar los sistemas dividiéndolos en eventos y condiciones. y los eventos por las transiciones. Las condiciones son representadas por los nodos. Existen extensiones a las Redes de Petri: por ejemplo las Redes de Petri Coloreadas (PNC). Cuando la transición cumple dicha condición se dice que es ENABLED. Documents Similar To Redes de PetriSkip carouselcarousel previouscarousel nextModelos de Dependenciauploaded by robertoEnsayouploaded by Victor MateoEvolución de la Educación occidentaluploaded by dsenihInforme de Desarrollo Integraluploaded by Josha Perez4 foucault-omnes-et-singulatimuploaded by David San Martín SeguraResolviendo Gibbard y Varianuploaded by Ariel Leandro ZagareseTMA2013T4-Sandoval Germánuploaded by Germán Sandoval AndradeModelado de Sistemas Redes de Petriuploaded by Luis PolancoCalculo de capacidadesuploaded by GustavoMatiasScozzinaConceptos Identificacion experimental métodos.pptuploaded by Marcelo Alejandro Alvarez30 Clase Modelamientouploaded by Kael Kael Wbrunner Lo_Publico_de_la_Universidad_a_la_luz_de.pdfuploaded by pgsandoval4974Grafoidesuploaded by Nicolas Martin Valera la TorreGuia de Ejerciciosuploaded by martulandia44612Murillo Astopillo Javier Obidio_tarea 6_1633uploaded by Daniel Enrique Gutierrez SamaniegoModelo Urbanouploaded by lam_12_4Guia Mundos Narrativosuploaded by Carolina Alvarado HernandezRegistro 5to b 2017uploaded by Javier Tristan Santetiempuploaded by juansinn2924-Omnes et singulatm- Hacia una crítica de la razón política.docuploaded by Dondo CarricartAct 1uploaded by Katrina MillerSistemas Lineales Iuploaded by Jesus Castañon AlcalaOmnes Et Singulatimuploaded by Cynthia DaibanMatriz de Consistenciauploaded by Anonymous X9vx0dL2balance.pptuploaded by Alan Robert Moran CahuanaHilary Cooper Didactica de La Historiauploaded by Daney Llerena DominguezFoucault-5.Tecnologias del Yo. pdf.pdfuploaded by CapazEsiQue Es La Gramaticauploaded by mahosujb3822Foucault, Michel - Omnes Et Singulatim (Castellano)uploaded by vicvalenFoucault Omnesuploaded by salvadormarinaroMore From fatewaySkip carouselcarousel previouscarousel next_d42515e180a089a7ca87f642fae26be8_Article_Entrepreneurial_Selling.pdfuploaded by fatewayArticle_Entrepreneurial_Selling.pdfuploaded by fatewayUMLNotationSummary.pdfuploaded by fatewayUML Notation Summaryuploaded by fatewayProyectos Feria.txtuploaded by fatewayComandos Linuxuploaded by fatewayUMLNotationSummary.pdfuploaded by fatewayMetodología de Sistemas Blandosuploaded by fatewayBuild Your Own DS-1 Distortionuploaded by fatewayBloc de Notasuploaded by fatewayConta Bili Dad Plan Till Auploaded by fatewayFour Secrets Project Successuploaded by fatewayTaller 3uploaded by fateway2010_2_guia08uploaded by fatewayMenú del pie de páginaVolver arribaAcerca deAcerca de ScribdPrensaNuestro blog¡Únase a nuestro equipo!ContáctenosRegístrese hoyInvitar amigosObsequiosAsistenciaAyuda / Preguntas frecuentesAccesibilidadAyuda de compraAdChoicesEditoresLegalTérminosPrivacidadCopyrightRedes socialesCopyright © 2018 Scribd Inc. .Buscar libros.Directorio del sitio.Idioma del sitio: English中文EspañolالعربيةPortuguês日本語DeutschFrançaisTurkceРусский языкTiếng việtJęzyk polskiBahasa indonesiaUsted está leyendo una previsualización gratuita.DescargarCerrar diálogo¿Está seguro?This action might not be possible to undo. Are you sure you want to continue?CANCELARAceptar


Comments

Copyright © 2024 UPDOCS Inc.