Carlos Gershenson's homepage


Control de Tráfico con Agentes: CRASH



(Car and Road Automated Simulation in Hyperways)



Carlos Gershenson



E-mail: cggunam.mx

http://turing.iimas.unam.mx/%7Ecgg/jlagunez/crash



Fundación Arturo Rosenblueth

"...como que han sido creados

para la vida. ¡No para pensar!"

-Hermann Hesse



Resumen



El simulador CRASH (Car and Road Automated Simulation in Hyperways) usa programación orientada a agentes para modelar el tráfico de una ciudad sin necesidad de semáforos, tratando de demorar los vehículos el menor tiempo posible (y sin que se impacten). Esto se hace por medio de agentes en cada automóvil y en cada cruce, y un control central.

Se hace una breve introducción al modelo de programación orientada a agentes, para después explicar el modelo del simulador. Se describen las clases usadas en la implementación, sus propiedades y sus relaciones, mostrando el diagrama de las clases. Finalmente, se exponen las conclusiones que se llegaron con las simulaciones.



Introducción



Cualquiera que viva en una gran urbe nota fácilmente y lamenta los desastres causados por el tráfico. Se podría resumir que el problema del trafico, al haber exceso de automóviles, es causado por falta de conciencia de los conductores. Al hablar de conciencia, nos referimos a que los conductores no pueden percibir enteramente el medio en el que conducen, y por lo tanto, casi no hay coordinación entre los conductores. Si hubiese coordinación, todos los autos podrían ir a la misma velocidad, guardando una cierta distancia, anulando el congestionamiento. No tenemos la suficiente percepción como para coordinarnos y lidiar con los demás conductores. Una solución: Agentes con el suficiente control y conocimiento del estado de su medio ambiente controlando el tráfico. Estos sí podrían tener la percepción necesaria para saber en qué condiciones se encuentra el medio y los demás agentes, pudiéndose coordinar debidamente. Además, se introduce, el concepto de hipervías, las cuales no necesitan semáforos, ya que tienen en cada cruce un agente que controla a los agentes de los autos, evitando que estos se detengan en el cruce (y que sufran una colisión).

Esta simulación fue creada para observar las ventajas y los problemas que esta solución podría traer. Para ello, el sistema simula autos, calles, cruces, etc. Y cada auto controla su comportamiento. Se utilizó Borland C++ para la implementación.



¿Qué es un agente?



La evolución de la programación y el análisis orientados a objetos dieron lugar al nacimiento de los agentes. Estos fueron diseñados para resolver ciertos tipos de problemas en el área de inteligencia artificial. Dado esto, los agentes tienen ciertos atributos "humanos", como la comunicación entre ellos, la toma de sus propias decisiones y la percepción de su medio ambiente.

Los agentes han sido utilizados en control de tráfico aéreo [9], manejadores de información inteligentes [10], y muchas otras aplicaciones innovadoras que requieren de un sistema capaz de "tomar decisiones".

Pero la gente que estudia a los agentes, tiene un problema similar a los que estudian inteligencia artificial. Así como estos últimos no se ponen de acuerdo en definir inteligencia, los primeros no han creado una definición aceptada universalmente de agente.

Para nosotros un agente deberá cumplir con las siguientes características:



Otros autores definen a un agente con menos características que las recién mencionadas. Pero también hay otros, que les atribuyen otras más complejas, hasta emociones [7]. En esto se ve la diversidad de opiniones que se dan en la teoría de agentes.



El Diseño del CRASH



El CRASH (Simulación Automatizada de Automóviles y Caminos en Hipervías) maneja cinco clases principales: CCar (automóviles), CCross (cruces), CControl (control central), CStreet (hipervías) y CProbe (sonda). Las primeras dos son clases de agentes. Las otras tres son clases de objetos. Esto hace al CRASH un sistema híbrido. Se considera un sistema híbrido como cualquier sistema que mezcla dos o más metodologías en el diseño.

La clase CCar fue basada en la que fue desarrollada en Berkeley por el grupo de Shift [4] para su Simulación de Carreteras Automatizadas (AHS) [5]. Cada auto tiene su estado, el cual está determinado por su posición actual, velocidad (m/s), aceleración (m/s^2), y vecindad con otros agentes de la misma clase ; y sus transiciones. Estas son las reglas para aplicar la aceleración y la velocidad al auto en el tiempo. El estado está determinado por las siguientes reglas, las cuales le dan su autonomía a los agentes:

Si la velocidad está entre la velocidad mínima y la máxima de crucero, la aceleración en 0.

Si no hay un auto en el carril de tu izquierda, cámbiate de carril.

Si hay un auto en el carril de tu izquierda, y no tienes un auto atrás, disminuye la aceleración en 3.

Cada auto tiene coordenadas de destino. Dependiendo de estas, decide si dará vuelta en el siguiente cruce o no (En caso afirmativo, marca con la direccional antes de dar el giro) . Cuando un auto llega a su destino, se desactiva y sale de la simulación. Hay un generador de autos aleatorios para que la simulación tenga más realismo. El generador escoge al azar una posición, velocidad, y aceleración iniciales para el auto, y también sus coordenadas de destino. Dadas estas condiciones, el auto se desenvuelve en su medio tratando de llegar a su destino lo más pronto posible, si estorbar a otros agentes, y sin sufrir colisiones.

La clase CCross detecta a los autos que se acercan a ella a un rango determinado por la sonda. Si determina su acercamiento, simula todas las transiciones que tendría el auto hasta llegar al cruce. Si el área y el tiempo que predice están ocupados, el cruce disminuye la aceleración del auto, y evalúa de nuevo, hasta que el auto encuentre un espacio libre. Esta clase también determina si el auto va a dar vuelta a la derecha (sólo se permiten vueltas a la derecha). Estas decisiones le dan a los agentes de esta clase su autonomía y pro-actividad y la habilidad de comunicarse con los agentes de la clase Ccar prueba su sociabilidad. Al determinar si se acercan los autos o no, perciben su medio ambiente. Esto demuestra su reactividad. El carril de la extrema derecha siempre está reservado sólo para las vueltas. Esto es porque en la simulación actual se manejan hipervías de doble sentido, y al haber vueltas a la izquierda se obstaculizaba demasiado el tránsito. Otra solución sería que todas las hipervías fuesen de un sólo sentido, y restringir el carril de la extrema izquierda para vueltas a la izquierda.

Sólo hay un objeto de la clase CControl. Todos los autos le reportan su posición actual, y después el control central les informa si hay un auto cerca de ellos y dónde. Esto evita que los autos choquen los unos con los otros sin la necesidad de que todos se reporten con todos. También indica cuando hay colisiones. Gracias al control central, los agentes de la clase CCar pueden desarrollar su sociabilidad, reactividad, y pro-actividad.

La clase CStreet maneja los cambios de carril, y previene que los autos no se desvíen de las hipervías.

También sólo hay un objeto de la clase CProbe. La idea de la sonda fue tomada del modelo de enjambres del Swarm [6]. La sonda maneja las estadísticas y los parámetros de la simulación.

Por medio de la sonda, se pueden cambiar la escala (pixeles / metro) y el rango de visión para tener acercamientos o una vista general de la simulación. También se pueden modificar las velocidades máximas y mínimas de crucero y los rangos de los radares, tanto de los autos, como de los cruces. Además, lleva una estadística de la simulación: el tiempo transcurrido (en segundos), los autos que han sido creados, los autos activos, el promedio de las velocidades y las aceleraciones, y cuantos autos han chocado. Por último, también se puede decidir qué tan seguido se quiere que se cree un auto aleatorio (segundos / auto).

A continuación, se presenta el diagrama de clases y sus relaciones del CRASH. Este fue extraído del código con ayuda del Rational Rose [11]

En este diagrama se pueden identificar todas las clases que utiliza el simulador, y cómo se relacionan. Se pueden observar las plantillas (templates) que utiliza la clase de la lista ligada, los atributos de las clases que pertenecen a otras clases, etc.

Más abajo se puede apreciar este mismo diagrama, pero con todos los métodos y atributos desplegados.

Con estos elementos, el CRASH puede recrear satisfactoriamente un ambiente propicio para que sus agentes interactúen y el resultado sea óptimo (aunque tiene ciertas limitaciones, más que nada determinadas por la capacidad de la máquina en la que se ejecuta la simulación),

Si desea revisar el código (para Borland C++ 3.1), puede encontrarlo junto con el ejecutable en http://turing.iimas.unam.mx/%7Ecgg/jlagunez/crash/crash.zip (Al ejecutar, presione 'a' para la ayuda).



Conclusiones



Después de varias simulaciones, se pudieron llegar a las siguientes conclusiones.

No hay constantes óptimas para cada variable (rango de los radares de los autos y los cruces, velocidades de crucero, etc.). Estas variables, para que el desempeño de la simulación sea óptimo, varían según la cantidad de autos. Por ejemplo, si hay muchos autos, conviene disminuir los rangos de los radares, ya que estos frenan a los autos, y puede llegar el momento en que haya colisión por que todos los autos estén casi detenidos. Además, casi siempre resulta más óptimo que las velocidades sean altas. Esto agiliza el tránsito, aunque, si por ejemplo, los autos van a alrededor de 50 metros por segundo, y su radar es de 40 metros, es muy probable que haya colisiones, ya que los estados se evalúan cada segundo. De cualquier manera, en la realidad se necesitaría que los estados se evaluasen por lo menos diez veces por segundo, para evitar este tipo de percances. Además se deberían de contar con métodos para sortear imprevistos, como choques o fallas temporales del sistema, así como también el pequeño problema del transporte colectivo, las bicicletas y los peatones.

En fin, este sistema demuestra que son posibles las pretensiones propuestas en la introducción en los próximos años, por más ambiciosas que parezcan.



Agradecimientos



Quisiera agradecer a Miguel Armas, Jaime Lagunez, a mis demás profesores y compañeros, y a todo aquel que me apoyó y soportó en la elaboración de este trabajo.



Bibliografía



  1. Wooldridge, M. and Jennings, N. R. "Intelligent Agents: Theory and Practice" Knowledge Engineering Review, October 1994.
  2. Genesereth, M. R. and Ketchpetl, S. P. "Software Agents" Communications of the ACM 37 (7).
  3. UMBC Agent Web, http://www.cs.umbc.edu/agents/ UMBC.
  4. Shift project, http://www.path.berkeley.edu/shift Berkeley University.
  5. Smart Automated Highway Simulation (Smart-AHS) http://www.path.berkeley.edu/smart-ahs Berekely's PATH.
  6. SWARM http://www.santafe.edu/projects/swarm/ Santa Fe's Institute of Technology.
  7. Bates, J. "The role of emotion in believable agents". Communications of the ACM 37 (7).
  8. Stroustrup, B. "El Lenguaje de Programación C++" 2a ed. Addison-Wesley
  9. Steeb, R. et. al. "Distributed intelligence for air fleet control" Readings in Distributed Artificial Intelligence. Morgan Kaufmann Publishers.
  10. Maes, P. "Agents that reduce work and information overload" Communications of the ACM 37 (7).
  11. Rational Rose http://www.rational.com Rational Corp.

¿y tecnología?

Principal