Modelo de tráfico de Biham–Middleton–Levine

El modelo de tráfico de Biham-Middleton-Levine es un modelo de flujo de tráfico de autómata celular autoorganizado . Consiste en varios coches representados por puntos en una red con una posición inicial aleatoria, donde cada coche puede ser de dos tipos: los que solo se mueven hacia abajo (mostrados en azul en este artículo) y los que solo se mueven hacia la derecha (mostrados en rojo en este artículo). Los dos tipos de coches se turnan para moverse. Durante cada turno, todos los coches del tipo correspondiente avanzan un paso si no están bloqueados por otro coche. Puede considerarse el análogo bidimensional del modelo más simple de la Regla 184. Es posiblemente el sistema más simple que exhibe transiciones de fase y autoorganización . ^{[ 1 ]}

El modelo de tráfico de Biham-Middleton-Levine fue formulado por primera vez por Ofer Biham , A. Alan Middleton y Dov Levine en 1992. ^{[ 2 ]} Biham et al. encontraron que, a medida que aumentaba la densidad del tráfico, el flujo de tráfico en estado estacionario pasaba repentinamente de un flujo suave a un atasco completo. En 2005, Raissa D'Souza encontró que, para algunas densidades de tráfico, existe una fase intermedia caracterizada por disposiciones periódicas de atascos y flujo suave. ^{[ 3 ]} Ese mismo año, Angel, Holroyd y Martin fueron los primeros en demostrar rigurosamente que, para densidades cercanas a uno, el sistema siempre se atascará. ^{[ 4 ]} Posteriormente, en 2006, Tim Austin e Itai Benjamini encontraron que, para una red cuadrada de lado N, el modelo siempre se autoorganizará para alcanzar la velocidad máxima si hay menos de N /2 coches. ^{[ 5 ]}

Los coches suelen colocarse en una red cuadrada que es topológicamente equivalente a un toroide : es decir, los coches que se salen del borde derecho reaparecen en el borde izquierdo; y los coches que se salen del borde inferior reaparecen en el borde superior.

También se han realizado investigaciones en redes rectangulares en lugar de cuadradas. Para rectángulos con dimensiones coprimas , los estados intermedios son bandas autoorganizadas de atascos y flujo libre con una estructura geométrica detallada, que se repiten periódicamente en el tiempo. ^{[ 3 ]} En rectángulos no coprimas, los estados intermedios suelen ser desordenados en lugar de periódicos. ^{[ 3 ]}

A pesar de la simplicidad del modelo, presenta dos fases claramente diferenciadas  : la fase de atasco y la fase de flujo libre . ^{[ 2 ]} Con un número reducido de vehículos, el sistema generalmente se organiza para lograr un flujo de tráfico fluido. Por el contrario, si hay un número elevado de vehículos, el sistema se atasca hasta el punto de que ningún vehículo puede moverse. Típicamente, en una red cuadrada, la densidad de transición se alcanza cuando hay aproximadamente el 32 % de los vehículos que ocupan los espacios posibles en la red. ^{[ 6 ]}

A pesar de la simplicidad del modelo, el análisis riguroso es muy complejo. ^{[ 6 ]} No obstante, existen demostraciones matemáticas del modelo de tráfico de Biham-Middleton-Levine. Hasta ahora, las demostraciones se han limitado a los extremos de la densidad del tráfico. En 2005, Alexander Holroyd et al. demostraron que, para densidades suficientemente cercanas a uno, el sistema no tendrá coches moviéndose infinitamente a menudo. ^{[ 4 ]} En 2006, Tim Austin e Itai Benjamini demostraron que el modelo siempre alcanzará la fase de flujo libre si el número de coches es menor que la mitad de la longitud de la arista de una red cuadrada. ^{[ 5 ]}

El modelo se estudia típicamente en el toro orientable , pero es posible implementar la red en una botella de Klein . ^{[ 8 ]} Cuando los coches rojos llegan al borde derecho, reaparecen en el borde izquierdo, pero invertidos verticalmente; los que están abajo ahora están arriba, y viceversa. Más formalmente, para cada${\displaystyle y\in \lbrace 0,\ldots ,N-1\rbrace }$un coche rojo saliendo del lugar${\displaystyle (N-1,y)}$entraría al sitio${\displaystyle (0,Ny-1)}$. También es posible implementarlo en el plano proyectivo real . ^{[ 8 ]} Además de voltear los autos rojos, se hace lo mismo con los autos azules: para cada${\displaystyle x\in \lbrace 0,\ldots ,N-1\rbrace }$un coche azul saliendo del lugar${\displaystyle (x,N-1)}$entraría al sitio${\displaystyle (Nx-1,0)}$.

El comportamiento del sistema en la botella de Klein es mucho más similar al del toro que al del plano proyectivo real. ^{[ 8 ]} Para la configuración de la botella de Klein, la movilidad en función de la densidad comienza a disminuir ligeramente antes que en el caso del toro, aunque el comportamiento es similar para densidades mayores que el punto crítico. La movilidad en el plano proyectivo real disminuye más gradualmente para densidades desde cero hasta el punto crítico. En el plano proyectivo real, pueden formarse atascos locales en las esquinas de la red, aunque el resto de la red fluya libremente. ^{[ 8 ]}

En 2010 se estudió una variante aleatoria del modelo de tráfico BML, denominada BML-R. ^{[ 9 ]} Bajo límites periódicos, en lugar de actualizar todos los coches del mismo color a la vez durante cada paso, el modelo aleatorio realiza${\displaystyle L^{2}}$actualizaciones (donde${\displaystyle L}$(donde es la longitud del lado de la red presumiblemente cuadrada): en cada paso, se selecciona una celda al azar y, si contiene un automóvil, se mueve a la siguiente celda si es posible. En este caso, el estado intermedio observado en el modelo de tráfico BML habitual no existe, debido a la naturaleza no determinista del modelo aleatorio; en cambio, la transición de la fase de atasco a la fase de flujo libre es abrupta.

Bajo condiciones de contorno abiertas, en lugar de tener autos que salen por un borde y se envuelven alrededor del otro lado, se agregan nuevos autos en los bordes izquierdo y superior con probabilidad${\displaystyle \alpha }$y eliminados de los bordes derecho e inferior${\displaystyle \beta }$respectivamente. En este caso, el número de coches en el sistema puede cambiar con el tiempo, y los atascos locales pueden hacer que la red parezca muy diferente del modelo habitual, como por ejemplo, tener coexistencia de atascos y zonas de libre circulación; contener grandes espacios vacíos; o contener principalmente coches de un solo tipo. ^{[ 9 ]}

• Implementación de CUDA por Daniel Lu
• Implementación de WebGL por Jason Davies
• Implementación en JavaScript por Maciej Baron