E=mc2

Viernes, 24 de marzo de 2006

Redes de Petri

Recientemente en la asignatura de Simulación he descubierto un formalismo matemático que me dejó con la boca abierta. Dejadme explicaros cómo se construyen y su cometido.

Las redes de Petri (Petri nets) se trata de un conjunto de la forma PN = (S,T,F,M0,W,K). Os remito a la wikipedia para que echéis un vistazo a los aspectos más formales de este álgebra.

La representación estándar es así:

Si observáis la imagen anterior, veréis que hay unas "bolitas", tokens, que van viajando de pelota grande en pelota grande en el sentido de las flechas. Estas pelotas grandes las podéis interpretar como nodos de un grafo dirigido y las flechas como las aristas. Existe otro tipo de estructura rectangular que se trata de la transición.

Una red de Petri es, por tanto, un grafo dirigido bipartido donde toda transición (la estructura rectangular) tiene una arista que se comunica con un estado y no con otra transición.

La potencia del modelo viene dada por la propia estructura. En la primera transición, son creados los tokens respecto de cualquier función de distribución que queremos imaginar (uniforme, poison, constante, ...). A su vez, cada arista tiene un peso. Cuando no se dice explícitamente el peso, por convenio es 1. Este peso se trata de una condición (que a su vez también puede ser una función booleana, de distribución, constante,...) que ha de cumplirse para pasar al estado siguiente. Por ejemplo, imaginemos una arista con peso igual a 2. Hasta que no son creados dos tokens en la anterior transición, estos tokens no podrán viajar en la dirección de la arista y no podrán pasar al siguiente estado. Los tokens una vez llegan a la última transición son destruidos a no ser que sean guardados en un estado.

Una primera ojeada a una red de Petri nos recordará a un modelo de colas. Un estado puede jugar el papel de cola en la que se acumulan tokens hasta que se cumple la condición de salida, la de la arista.

En simulación, cada transición es un evento en el modelo del sistema simulado y en cada estado podemos calcular todo tipo de estadísticos que representarán la validez de los datos de nuestro modelo.

Si observáis la figura de nuevo, podréis pensar que se trata de un modelo secuencial, pero no es así. Algunas aristas más abajo en el camino pueden ser condición de transiciones anteriores. El modelo como podréis pensar, es increíblemente potente. Existen algunas extensiones que explotan muchos aspectos nuevos y le dan nuevos matices para convertirlo en modelos más a medida del problema.

No me extenderé por el momento más, pero en breve intentaré explicaros algunos de mis últimos modelos paso por paso.