Wednesday, June 27, 2012

Notas sobre tráfico y simulación

He seguido encontrando maneras de representar el tráfico urbano y trasladarlo a las simulaciones siguiendo varios enfoques dependiendo del objetivo. Planteado de cierta forma el nuestro, no solo es necesaria la simulación del tráfico (sigue pendiente el nivel de detalle que requeriremos) sino posiblemente toda una ciudad o al menos secciones de la misma.

Siguiendo esta idea decidí buscar sobre los entornos urbanos en los videojuegos ya que al final de cuentas es lo más apegado a lo que queremos llegar por lo tanto tenemos que encontrar los elementos que nos sean útiles de otros desarrolladores.

Es así que encontré la siguiente tesis, que aunque no examina en un enfoque computacional sino más bien de diseño (espacios, vistas, elementos dentro del juego), nombra y analiza ciudades creadas para videojuegos recientes y el impacto que tuvieron en ofrecer un buen entorno.

http://smartech.gatech.edu/xmlui/handle/1853/28251

Por otra parte falta definir si esta investigación se hará en base a una ciudad real o si es mejor crear alguna ficticia. De esto también depende si los datos que se quieren modelar deben ser precisos y apegados a la ciudad o si serán generados dependiendo de los elementos que se generen para ocupar la urbe.

Three-dimensional Urban Traffic Simulation with ITranS

Este artículo redacta la construcción de un ambiente que permite diseñar y modelar ambientes que incluyan el tráfico urbano de tal suerte que pueda ser empleado para distintas aplicaciones como lo son: simulaciones de manejo, turismo, juegos, entrenamiento militar o sistemas estratégicos o de entretenimiento en general.

ITranS (Interactive Transit Simulator) se encuentra dividido en tres módulos que interactúan entre si para presentar que el usuario pueda generar el ambiente que desee. La siguiente figura muestra la arquitectura:

image

La interacción de los módulos inicia cuando el Data Configuration System inicializa las entidades del mundo. Los caminos son creados como grafos. Cada arco contiene información sobre el flujo de vehículos por minuto y los tiempos de las luces de los semáforos. Los vehículos, semáforos y el terreno son insertados de acuerdo al flujo del camino y su superficie. Posteriormente el simulador calcula los movimientos y acciones de cada elemento para cada ciclo de simulación. También en cada ciclo se actualiza la interfaz y los comandos de entrada son procesados.

Los vehículos tienen rutas fijas previamente asignadas. Se tiene una velocidad máxima fija para los vehículos y los cambios de carril solo ocurren de manera aleatoria entre secciones adyacentes del camino.

Los vehículos tienen distintos comportamientos dependiendo de la situación en que se encuentren y son los siguientes:

  • Path Following
  • Parking
  • Separation
  • Collision
  • Terrain Following

Un detalle encontrado en el desarrollo del sistema es la inclusión de nivel de detalle (Level of Detail LOD). Dependiendo de los ajustes que se hagan en este aspecto, se puede impactar directamente en el desempeño de la simulación o lo que se desee crear. Esta técnica se aplica a objetos y vehículos para lograr mantener estables los frames por segundo que se despliegan.

A continuación se presenta una imagen con un ejemplo de simulación creada en ITranS:

image

Las conclusiones del trabajo son más pertinentes al desempeño del sistema de manera visual y no tanto sobre la calidad de las simulaciones (en cuanto a que tanto se apegan a la realidad) que se pueden crear usando ITranS.

Barros, P. de, Kelner, J., & Farias, R. (2005). Three-dimensional Urban Traffic Simulation with ITranS. lbd.dcc.ufmg.br. Retrieved from http://www.lbd.dcc.ufmg.br/colecoes/svr/2006/025.pdf

A Solution for Streamlining Intelligent Agent-Based Traffic into 3D Simulations and Games

Las simulaciones de tráfico pueden ser generalmente clasificadas en dos tipos. La primera se refiere a un enfoque top-down en el que se toma al tráfico como un flujo descrito por fórmulas matemáticas. El segundo es una estrategia bottom-up y se le presta a cada individuo o partícipe del tráfico una serie de características que lo definen (enfoque microscópico). Para el caso de las simulaciones detalladas como lo es un ambiente en tres dimensiones, se acostumbra utilizar el segundo enfoque.

La mayoría de las simulaciones actuales basadas en agentes definen su comportamiento como una serie de reglas de tráfico sencillas. Gran parte de las reglas se basa en la distancia ideal que debe procurar mantener un vehículo respecto al otro dependiendo de factores como velocidad, aceleración y retraso en la respuesta del piloto. Sin embargo, esta serie de fórmulas solo permite tener un comportamiento idealizado de los conductores y no muestran comportamientos que se pueden denominar como “inteligentes” que representen de alguna forma el modo de actuar de las personas.

El modo propuesto por el artículo para simular el comportamiento humano se basa en lógica difusa debido a su naturaleza y sobre todo al poco procesamiento que requiere. Una de las ventajas es la inclusión de los “cascading fuzzy classifiers” que ayudan a incluir elementos como el clima y factores de visibilidad.

El proyecto fue basado según los requerimientos del Virtual Dublin Project que consistía en simular al menos una parte de la ciudad en tres dimensiones con las siguientes consideraciones:

  • Modelos a escala de paisajes urbanos ya existentes.
  • Simulación de grandes áreas urbanas (geométricamente hablando).
  • Debe correr en tiempo real.
  • Interacción con sistemas en 3D (modelos del mundo, peatones).
  • Los requerimientos de procesamiento deben ser acordes a los estándares de CPU y GPU en el mercado.
  • Los puntos en donde se sitúan las cámaras deben ser realistas (a nivel de auto, peatón, vista aérea).

La zona empleada para el artículo se muestra en la siguiente imagen:

image

La representación del sitio se lleva a cabo por medio de grafos ponderados. Agregando elementos como tiempos estimados de viaje entre calles, distancias entre intersecciones o tiempos estimados de retraso por congestión a los costos actuales del grafo se puede construir un grafo efectivo de toda la ciudad pero con poca complejidad. En la siguiente figura se da una muestra de un grafo construido.

image

En la representación, los arcos que no tienen flecha (no dirigidos) son las avenidas y rutas con dos sentidos mientras que las dirigidas lo indican con el sitio a donde apuntan las flechas. Para poder representar fenómenos como el cambio de carriles, vueltas, incorporaciones y otros eventos se utiliza otro grafo que existe en cada camino.

Se llevan a cabo las siguientes dos planeaciones de las rutas de tráfico:

  • Planeación de largas distancias: Se crea una serie de instrucciones a seguir para llegar a un punto rápidamente. En el caso del transporte público las rutas son fijas pero el resto de los vehículos puede modificarlas de manera dinámica para reflejar el cambio en las condiciones de congestión.
  • Planeación a corta distancia: Define los movimientos de un vehículo en una calle. Decide si el vehículo debe rebasar o permanecer detrás de otro vehículo más lento.

Para las representaciones de calles y pequeñas secciones se utiliza un conjunto de nodos que representan el tamaño de un coche de modo que la cantidad de nodos se encuentra definida por la longitud del tramo. Un ejemplo de esto se muestra en la siguiente figura:

image

Para evitar el cálculo continuo de velocidades y distancias relativas entre vehículos, se emplean los nodos para mantener una distancia tal que siempre permita al vehículo trasero frenar de manera segura en caso de que el vehículo al que sigue haga un alto total.

Para que el modelo sea independiente a las simulaciones existentes, se planeó tenerlo como módulos por separado. Esto se muestra en la siguiente figura:

image

Como ambiente de simulación se empleó OGRE3D ya que permite la creación de elementos sencillamente arrastrándolos a escena. La escena empleada fue el campus de Dublin y sus alrededores y se presenta en las siguientes figuras:

image

image  

Queda como trabajo a futuro el escalar este modelo para zonas mucho más amplias y además incluir la interacción entre transeúntes y vehículos dentro del mismo modelo.

Gerdelan, A. (2009). A solution for streamlining intelligent agent-based traffic into 3d simulations and games. Retrieved from http://www.massey.ac.nz/~kahawick/cstn/072/cstn-072.pdf

Wednesday, June 20, 2012

Notas y reflexiones sobre tráfico urbano para nuestro proyecto

El estudio del tráfico urbano no es una tarea trivial, existen varios libros y artículos que se basan sobre el mismo y toman enfoques distintos dependiendo del objetivo de estudio. Se encontraron los siguientes dos enlaces que contienen lecturas sobre los modelos de estudio del tráfico urbano:

Para nuestro caso debemos definir lo siguiente:

  • ¿Qué tan apegado a la realidad debe ser nuestro tráfico?
  • ¿En que escala debe ser generado? (Ciudad completa, calles, manzanas).
  • Variación en el comportamiento del tráfico.
  • Tiempo en que el tráfico será modelado. (Mañana, tarde, noche).
  • Factores que alteran el tráfico. (Clima, accidentes, reparaciones).

Al tener definidos los factores a considerar que requerimos para llevar a cabo la simulación de una porción del tráfico de nuestro ambiente será más fácil elegir el tipo de modelo que se debe llevar y el nivel de detalle que se requiere para el mismo.

Discovering Traffic Bottlenecks in an Urban Network by Spatiotemporal Data Mining on Location-Based Services

El problema más grande que existe en la generación y saturación del tráfico radica en los cuellos de botella. Sin embargo, la mayoría de los enfoques toma a los cuellos de botella como puntos fijos en el espacio (en una ciudad por ejemplo) y estos no varían. En este artículo se plantea la definición de cuellos de botella espacio-temporales que toman en cuenta tanto lugares como horas para definir los puntos en donde se produce y concentra la carga vehicular.

El modelo presentado consta en identificar los puntos espacio-temporales donde se sitúan los cuellos de botella dentro de una ciudad utilizando minería de datos. El diagrama del modelo propuesto se encuentra en la siguiente figura:

image

El proceso principal se divide en las siguientes tres fases:

  • Fase 1: Esta fase se encarga primero de recolectar los datos y limpiarlos para lograr resumirlos en dominios de espacio y tiempo. Debido a la granularidad del problema es imposible tomar a cada elemento como un objeto para ciertos estudios por lo que se agrupan en zonas y es la labor de esta fase llevarlo a cabo mediante el algoritmo desarrollado.
  • Fase 2: En base a los datos obtenidos en la fase 1 y las áreas de la fase 2, se procede a encontrar los siguientes patrones y elementos:
    • COI (Congested Object Item): Indica donde y cuando un objeto de la red se encuentra en un estado de congestión.
    • CDP (Congestion Drop Pattern): Calcula la diferencia de congestion significativa entre un elemento de la red y los objetos que se encuentran río abajo (downstream) de él.
    • IDP (Intesection Delay Pattern): Retraso entre dos enlaces consecutivos causado principalmente por los retrasos de señalización y por las colas.
    • CPP (Congestion Propagation Pattern): Indica la causa fuente para una relación entre dos áreas espacio-temporales congestionadas.
    • DCP (Demand Conflict Pattern): Se construye entre CPP e IDP. Estudia que si existen dos o más CPPs, se pueden encontrar varios cuellos de botellas en el espacio entre ambos.
  • Fase 3: Se aplican las siguientes tres heurísticas para el descubrimiento de cuellos de botella espacio-temporales:
    • CPH (Congestion-Propagation Heuristic): Busca encontrar una relación entre las áreas de congestión. En general si un área de congestión se encuentra en la parte de condiciones de varias reglas encontradas por el algoritmo, entonces se puede poner al área como una causa raíz de la congestión.
    • CCH (Congestion-Converge Heuristic): A diferencia de la anterior esta considera que las áreas de congestión se encuentren en la parte de acción de las reglas, entonces se asume que contiene varios cuellos de botella.
    • CDH (Congestion-Drop Heuristic): La idea principal de esta heurística consta en que si el estado de congestión de un objeto disminuye o desaparece después de que el flujo de tráfico pasa a través de él, entonces puede ser considerado como un cuello de botella.

Los experimentos fueron hechos en la ciudad de Taipei en Taiwan dando como resultado el mapa de la siguiente figura:

image

En conclusión se logró una precisión del 79.6% al encontrar los cuellos de botella durante los días laborales y una del 72.1% en fines de semana.

Lee, W.-H., Tseng, S.-S., Shieh, J.-L., & Chen, H.-H. (2011). Discovering Traffic Bottlenecks in an Urban Network by Spatiotemporal Data Mining on Location-Based Services. IEEE Transactions on Intelligent Transportation Systems, 12(4), 1047-1056. doi:10.1109/TITS.2011.2144586

A Mathematical Model for Urban Traffic and Traffic Optimization Using a Developed ICA Technique

El principal problema mostrado en este artículo es la falta de parámetros para la representación del tráfico, en los modelos actuales se queda como algo unidimensional que continuamente deja fuera características relevantes del tráfico.

Se propone el uso de ICA (Imperialist Competitive Algorithm) que optimiza la función objetivo bajo el concepto de competencia imperialista. Se utiliza la política de asimilación que ha sido empleada por los países imperialistas desde el siglo XIX. Esta política consta en que los imperialistas busquen ganarse la lealtad de sus colonias mejorando su economía, cultura y situación política. Según esta teoría, un imperialista con sus colonias se le puede denominar como imperio. El poder de un imperio se basa en el poder de sus imperialistas y colonias. En competencia, los imperialistas débiles pierden sus colonias frente a los fuertes y al final cuando un imperio débil pierde todas sus colonias termina convirtiéndose en colonia de otro imperio. Eventualmente solo quedará un imperio que contenga todas las colonias. El proceso se muestra en la siguiente figura:

image

En cuanto a optimización del tráfico, las variables son el tiempo en las intersecciones en la ciudad. Entonces el tiempo en luz verde determina el poder de cada país en el ICA para optimizarlo utilizando el modelo presentado como función objetivo.

Se mapean cada una de las intersecciones de la ciudad y se les asignan los siguientes números:

  • N indica el número de vehículos disponibles en cada camino
  • R, L, D: Son la probabilidad de que el automóvil doble a la derecha, doble a la izquierda o continúe de frente.

Una muestra de esto se presenta en la siguiente figura:

image

Hicieron dos tipos de pruebas, una que no es en tiempo real en la que se usa la secuencia de luces verdes para calcular el ritmo de la siguiente secuencia y por otro lado en tiempo real, la información se usa constantemente para calcular el ritmo.

Los resultados muestran que este tipo de algoritmos pueden controlar el tráfico de manera eficiente. La principal aportación fue que permite al modelo tomar en cuenta la concentración de vehículos a lo largo de la ciudad. Se puede mantener en un nivel óptimo la cantidad de vehículos que se encuentran en la calle debido a la forma en que se optimiza la sincronización de los semáforos.

Khorani, V., Razavi, F., & Disfani, V. R. (2011). A Mathematical Model for Urban Traffic and Traffic Optimization Using a Developed ICA Technique. IEEE Transactions on Intelligent Transportation Systems, 12(4), 1024-1036. doi:10.1109/TITS.2011.2127475

A shockwave profile model for traffic flow on congested urban arterials

Este trabajo se encuentra basado en modelos de flujo continuo de tráfico. Se menciona que este tipo de modelos ha tenido críticas debido a la falta de incorporación de la aceleración y desaceleración del flujo de tráfico pero también se ha argumentado que los modelos simples continuos son suficientes para describir el comportamiento del tráfico en redes señalizadas debido a que la dinámica del flujo de tráfico se encuentra dominada por eventos externos (como las luces rojas en semáforos) en lugar de la dinámica de flujo inherente.

Uno de los retos de lograr este tipo de modelado radica en los errores numéricos y la eficiencia computacional debido a que las soluciones conlleva la discretización del tiempo y espacio para describir las variaciones espacio-temporales del flujo de tráfico y su densidad.

Para explicar el uso del SPM (Shockwave Profile Model) hacen uso del siguiente diagrama:

image

Para que el modelo actúe de forma correcta se debe conocer el estado inicial de la red. Se deben derivar los flujos hacia afuera y hacia dentro de la red en todas las intersecciones además de las trayectorias de las filas en cada nodo. Similar a otros enfoques macroscópicos, el SPM utiliza una la ley de conservación de flujo con la siguiente fórmula:

image

Sin embargo para describir el estado completo del tráfico se requieren de otras relaciones además de la ecuación de conservación de flujo como lo es la relación flujo-densidad o una ecuación que describa la evolución de la velocidad del tráfico (momentum). El SPM divide el estado del tráfico en: libre (free-flow), saturado (saturated) y embotellado (jammed conditions). El SPM toma ventaja de los estados simplificados para describir la dinámica del tráfico basada en perfiles de ondas expansivas (shockwave).

La representación de los tramos físicos se lleva a cabo mediante nodos y arcos. Mientras los nodos representan secciones del camino, los arcos indican la dirección de la transferencia vehicular. Los nodos guardan la información sobre las características físicas del segmento como longitud, densidad del embotellamiento (jam density), índice de saturación (saturation rate) y el tiempo o sincronización entre señales. La información guardada se utiliza para crear los perfiles de onda expansiva para derivar los índices de salida (departure rates) y para determinar los arribos para los nodos río abajo. Los arcos se reducen a simplemente indicar la dirección en que pueden viajar los vehículos. Un ejemplo de esta representación se muestra en las siguientes figuras:

image

image

El modelado del flujo de tráfico utilizando el enfoque presentado resulta altamente apropiado para aplicaciones en redes a gran escala y en tiempo real especialmente cuando el tráfico se encuentra sobresaturado. Se hicieron pruebas comparándolo con datos del corredor arterial TH55 en Minneapolis aunque se hicieron las pruebas utilizando “loop detectors” y se menciona el futuro uso de otros medios como cámaras de tráfico para tener resultados más aproximados a la realidad.

Wu, X., & Liu, H. X. (2011). A shockwave profile model for traffic flow on congested urban arterials. Transportation Research Part B: Methodological, 45(10), 1768-1786. doi:10.1016/j.trb.2011.07.013

Sunday, June 10, 2012

Modeling Traffic’s Flow-Density Relation: Accommodation of Multiple Flow Regimes and Traveler Types

El flujo de vehículos depende y se acomoda dependiendo del tipo de camino que se diseñó. En Estados Unidos se utiliza un manual llamado Highway Capacity Manual (HCM – 1998) en el que se definen la capacidad de los caminos y los niveles de servicio experimentados en ellos dependiendo de la cantidad de tráfico que se experimente.

En el HCM se tienen varias fórmulas que lidian con el tráfico (lo representan) aunque la mayoría se basa en el diseño físico del camino pero también consideran la inclusión de transportes pesados.

El modelo de tráfico explicado tiene en consideración dos situaciones: cuando no existe congestionamiento y cuando existe. El problema del uso del HCM es que sus cálculos y datos se encuentran basados en condiciones ideales en los que no existe el congestionamiento además de no tener una relación paramétrica entre sus cálculos.

El reto para la creación del modelo creado en este artículo fue la inclusión de los parámetros requeridos para llevar a cabo el ajuste del modelado del tráfico dependiendo de las condiciones de densidad del mismo y otros factores que caracterizan el tipo de usuarios de las vías.

El resto del artículo se somete más al ajuste de los parámetros y fórmulas usadas para las pruebas en una zona de San Francisco, California.

Remarks on Traffic Flow Modeling and its Applications

Un punto importante para el modelado del tráfico se centra en los cuellos de botella ya que son elementos que constantemente se encuentran asociados a la concentración de flujo vehicular.

El tráfico se puede clasificar como fluido o sin congestión si se logran introducir pequeñas perturbaciones que disminuyan la velocidad en algunos puntos y que esto no se vea reflejado “río arriba (upstream)” de ese sitio. De otra forma se considera que existe congestión en el tráfico.

Otro punto que puede ocasionar cuellos de botella se encuentra en las salidas e incorporaciones de carriles, dependiendo de la carga vehicular estas pueden aumentar con el tiempo y formar colas que obstruyen el tráfico como se muestra en la siguiente figura:

image

Si el flujo que pasa por los caminos excede su capacidad puede provocar que las filas crezcan con el tiempo. Otro fenómeno que afecta el comportamiento en este tipo de situaciones radica en el grosor de las salidas, si es angosto se crea una situación FIFO (First In First Out) ocasionando que todos los que quieran utilizarla deban acceder al carril. Por otra parte si es ancha, puede ocasionar problemas dependiendo del comportamiento de los usuarios que transiten por el lugar.

Los cuellos de botella se sitúan dentro de una autopista básicamente en cualquier punto donde se cambian las características normales del camino (recto) como pueden ser: curvas, túneles, serpenteos, senderos, etc.

Para poder crear estrategias para el tráfico se aconseja mantener un modelo de tráfico simple y razonable pero que refleje la mayoría de las situaciones que aparecen en los caminos reales.

Las simulaciones son particularmente útiles para casos de estudio bien delimitados por ciertas situaciones como pueden ser: secciones delimitadas del camino, cruces, lugares con senderos, etc.

Daganzo, C. (1998). Remarks on traffic flow modeling and its applications. Dept. of Civil and Environmental Engeneering. Retrieved from http://www.ce.berkeley.edu/~daganzo/PAPER.PDF

Simulation models of traffic flow

El modelado de tráfico urbano y su flujo sirve para llevar a cabo tareas de planeación urbana y no urbana, el gobierno y consultoras se basan en los datos arrojados por dichos modelos para tomar a cabo decisiones.

La primera tarea para llevar a cabo un modelo es la identificación de todas las rutas razonables entre dos puntos. Las rutas razonables son aquellas cuyas distancias son las menores (en cuanto a tiempo de viaje) entre su punto de origen y destino. Posteriormente se asignan a los vehículos las rutas que usarán, sean siempre la mejor ruta o una distribución normal entre las rutas siendo esto usado principalmente para entornos no urbanos.

En un entorno real, al saturarse las rutas los viajeros (ocupantes de la ruta) buscarán alternativas para trasladarse a su destino, este comportamiento debe ser replicado en el modelo. En general, el entorno se basa en un conjunto de personas persiguiendo sus propios objetivos (llegar a su destino en el menor tiempo posible).

Existen diversas formas de modelar el tráfico y para llevar a cabo una decisión sobre cual es la adecuada para utilizar, se creó un cuadro que permite de cierta forma elegir la correcta y depende de dos entradas que son la red de tráfico y las demandas. La figura que ilustra el proceso se presenta a continuación:

image

Los modelos presentados se dividen en lo siguiente:

  • Modelos estáticos
    • No toman en cuenta el cambio respecto al tiempo y se asume que están en un punto estable después de que los individuos han hecho sus ajustes.
  • Modelos adaptativos
    • Se adaptan a los cambios en el tráfico entre días y utilizan transiciones de Markov que representan el aprendizaje y la modificación de las elecciones.
  • Modelos dinámicos
    • Toman en cuenta los cambios en horarios teniendo en cuenta posibles cambios en turnos de trabajo, viajes de negocios, tiempos de congestión, picos en la congestión y cambios en las rutas. Sin embargo, el llevar a cabo un modelado de todos esos elementos se puede convertir en un problema intratable.
  • Microsimulación
    • En su punto más detallado, este tipo de simulación toma a cada elemento como un individuo con características propias. Las interacciones entre los elementos se pueden llevar a cabo de manera detallada. El tomar en cuenta tanto nivel de detalle se basa en poder llevar a cabo un modelado preciso de las condiciones reales del tráfico.
  • Modelos combinados
    • Son modelos que combinan tanto el comportamiento en grupo como el comportamiento individual de los participantes en un entorno de tráfico.

Taplin, J. (1999). Simulation models of traffic flow. Department of Information Management and Marketing,. Retrieved from http://www.orsnz.org.nz/conf34/PDFs/Taplin.pdf

Notas sobre tráfico urbano

El estudio en general del tráfico urbano no se centra en el tráfico como tal sino en otro objetivo como puede ser su impacto en la naturaleza, estres, tiempo perdido y otros rubros. El modelado del tráfico depende directamente del enfoque del estudio a seguir. Según lo revisado existen varias fuentes que pueden colaborar con el estudio del tráfico, varias de estas son totalmente académicas y tienen que ver con Ingeniería Civil y Arquitectura aunque hay escuelas que dan temas sobre tráfico como diplomados y otro tipo de cursos.

Algunas de las posibles fuentes que se podrían utilizar son: