Download TraficoUrbano - Facultad de Ingeniería

Informe del Trabajo Práctico:
Simulación de Tráfico Urbano.
Materia:
66.26 Arquitecturas Paralelas.
Profesor:
Dr. Ricardo, D. Pantazis.
Integrantes del grupo:
Federico Marino,
75.530 ( Ingeniería en Informática ).
Diego Montaldo,
75.300 ( Ingeniería en Informática ).
Andrés Pollitzer.
69.104 ( Ingeniería en Informática ).
Fecha de entrega : marzo / 2002
Facultad de Ingeniería.
Universidad de Buenos Aires, Argentina.
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Indice de temas:
Abstract
2
Motivación
3
Etapas del trabajo práctico
4
De JPVM a RMI ( Comunicación )
5
Descripcion sintética de la simulación
6
Modelo de la simulación
10
Diseño de la simulación
12
Java
13
Distribución del problema
13
Evaluación de performance : pruebas de Speed Up
14
Conclusiones
15
Propuesta de mejoras
16
Bibliografía, Sitios, Referencias
17
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
1
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Abstract
El Sistema de Simulación de Tráfico Urbano consta de un mapa o grafo que modela la
estructura de una area urbana.
La simulación consiste en poblar el mapa con vehículos de diferentes caraterísticas.
Los cuales siguen rumbos y planes individuales, debiéndose calcular la interacción de
cada uno con el resto de los vehículos en un lapso de tiempo.
Un módulo permite visualizar en tiempo real la evolución del sistema en determinado
sector del mapa.
La finalidad del trabajo práctico es construir un sistema distribuido que utiliza n
computadoras en forma paralela para llevar a cabo la simulación, implementeandolo
en JAVA y comunicando los diferentes componentes mediante RMI ( Remote Method
Invocation).
RMI provee los mecanismos para registrar objetos remotos como recursos
computacionales utilizables en un sistema distribuido y permite alocar tareas en estos
objetos remotos, e invocar métodos remotos en forma transparente para el usuario sin
modificar el código JAVA original.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
2
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Motivación:
La idea surgio al buscar algun tipo de aplicación de calculo intensivo en donde
el problema, por su naturaleza sea paralelilzable. Es decir, la evoluvion del
sistema dependa de la evolución de n elementos individuales que interactuen.
Se eligió como problema a resolver la Simulación de Tráfico Urbano, porque al
ser un sistema multiagentes, su característica es adecuada para un sistema
distribuido necesario para la simulación.
Luego de investigar PVM ( Parallel Virtual Machine ), pensamos que podría ser
factible utilizarlo como software de base.
Encontramos una versión de PVM implementada en JAVA (JPVM : Java
Parallel Virtual Machine ) que resulto interesante.
Consideramos la posibilidad de utilizar la misma.
Java es una tecnología orientada a objetos multiplataforma. Lo que da
flexibilidad para utilizar distintos sistemas operativos como linux o windows, y
facilidad para modelar el problema en cuestión si se piensa en objetos
interactuando en lugar de procedimientos con entrada y salida de datos.
Junto con PVM permitiría distribuir nuestro sistema en máquinas de diversas
características para ejecutar la simulación.
Finalmente comprendimos, a nuestro criterio, que RMI simplifica la
programación, ya que es más versatil en cuanto a funcionalidad para la
comunicación.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
3
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Etapas del trabajo práctico
En base al análisis del problema a resolver, se planificaron las siguientes etapas:
1. Análisis y factibilidad del uso de JAVAPVM.
2. Modelado del tráfico urbano.
3. Diseño de clases y métodos.
4. Codificación del sistema en java ( Visualizador, Simulador, y Agentes ).
Tareas complementarias:
Codificación de una clase vector para facilitar el manejo de vectores.
5. Construcción de un módulo para visualizar los estados de la simulación.
6. Programación del generador del mapa de calles.
7. Testeo del sistema en una sola PC.
8. Paralelización del sistema en más de una máquina.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
4
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
De JPVM a RMI ( Comunicación )
JPVM ( Java Parallel virtual Machine ) es una interfaz que permite lanzar tareas
remotas desarrolladas en Java.
Básicamente usa conexión por sockets en todas las máquinas que integren el
ambiente JPVM.
La idea de JPVM es proporcionar una interfaz análoga al tradicional PVM, pero en el
ambiente de desarrollo de Java, debido a que muchas aplicaciones están
desarrolladas en ese ambiente. La ventaja principal reside en que aquellos
programadores habituados a la plataforma PVM puedan fácilmente abordar PVM en
Java. La curva de aprendizaje es rápida en este caso.
Sin embargo, posee varias desventajas debido al hecho de tratar de implementar una
plataforma que presenta un diseño estructurado en un lenguaje de programación
orientado a objetos.
Las desventajas residen en que no hace uso de las características de herencia y
polimorfismo de Java en su implementación.
Otra de las desventajas importantes es que no aprovecha las facilidades de
comunicación en red que presenta Java tal como lo dice su filosofía “la computadora
es la red y la máquina virtual (JVM) es la computadora”; implementadas en
mecanismos de JRMI (Java Remote Method Invocation), CORBA y otros que brindan
al desarrollador una interfaz de alto nivel para comunicaciones en redes de
computadoras, en una forma muy transparente, prácticamente como si las tareas
residieran en la misma computadora física.
Estos mecanismos primitivos del lenguaje permiten realizar de manera mucho más
eficiente y genérica lo que se haría bajo JPVM y aún más; sin las restricciones que
presenta dicha interfaz, por lo que no existe un argumento favorable para el uso de
JPVM al usar Java como plataforma de desarrollo.
De todas formas se deja en claro que la idea básica de PVM, de reemplazar una
computadora multiprocesador por varias monoprocesador en red; se utilizará en el
diseño del presente trabajo práctico pero usando las facilidades que provee la
plataforma de desarrollo, en lugar de JPVM.
Articulos interesantes relativos al tema:
Tema: Network Parallel Computing in Java. ( JPVM ).
Archivo: jpvm.pdf , y jpvm-java98.pdf
Autor: Adam J. Ferrari, University of Virginia, USA.
Tema: Communication Performance of Java based Parallel Virtual Machines.
Archivo: passing-java98.pdf
Autor: Narendar Yalarnanchilli, y William cohen. University of Alabama, USA.
Tema: JPVM
Link: http://www.cs.virginia.edu/~ajf2j/jpvm.html
Tema: An N-body method based on collaborative system model. (JRMI ).
Archivo: distributed N-body method.pdf
Autor: Yudong Sun
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
5
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Descripcion sintética de la simulación
Introducción: sistemas multiagentes
El objetivo del trabajo es resolver un problema conocido como “problema de N-cuerpos
(N-Body problem) ó sistema multiagentes” mediante un sistema de colaboración
distribuido.
Es un problema que estudia la evolución de cada cuerpo bajo la influencia de todo el
resto.
En este caso particular, se buscará estudiar un modelo que simula la evolución de
“móviles” dentro de una red de calles en un lapso de tiempo dado.
Cada móvil posee una Inteligencia independiente que lo controla con el objetivo de
alcanzar un punto de destino dentro del mapa de calles.
Para implementar el sistema se utilizará el lenguaje JAVA como plataforma; y la
tecnología RMI ( Remote Method Invocation ) para la comunicación de N workstations
conectadas mediante una red.
Simulación :
La simulación consiste de “S” iteraciones (Steps), donde cada iteración representa un
avance en el tiempo de “T” milisegundos.
Un intervalo de tiempo “T” tipico utilizado ronda los 25 mseg.
En cada iteración los móviles evaluan su entorno y definen sus futuras acciones.
Hay 2 clases principales de objetos:
 Calles
 Móviles
Diagrama 1: Calles con móviles.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
6
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Calle :
Funciona como un contenedor de moviles que se encuentran dentro del
espacio fisico que abarca la calle. Todo movil está incluido en una sola calle.
Móvil :
Consta de los siguientes componentes
MOVIL
Radar
Conductor
Volante
Motor
Diagrama 2: Componentes de un móvil.
Radar :
Genera una “vista de radar” del entorno del móvil, indicando la distancia al objeto más
cercano a lo largo del perímetro.
Para generar la vista,
el móvil solicita a la
calle en la que se
encuentra una lista de
los móviles que se
encuentran dentro del
radio de alcance de su
radar.
Luego para cada uno
de estos, proyecta su
influencia sobre el
vector de distancias.
A modo de
simplificación de los
cálculos se considera
cada móvil como un
círculo.
Diagrama 3: Radar de un móvil.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
7
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Conductor :
El objetivo final es alcanzar un punto de destino ( calle destino ).
El objetivo parcial es alcanzar el centro de la “calle próxima”.
Cuando el móvil es generado o alcanza un waypoin, ejecuta un algoritmo para
determinar hacia cuál de las calles vecinas ( objetivo parcial ), con respecto a la calle
actual, le conviene ir para alcanzar el objetivo final. Este algoritmo memoriza las calles
recorridas para evitar pasar por lugares que ya recorrió.
El conductor en ningún momento dispone de un mapa completo que le indique la ruta.
Solo utiliza como datos de entrada, el vector distancia al punto destino y
conoce cuales son las calles aledaneas a la calle actual.
Una vez decidida cual será la calle próxima (waypoint), el conductor evalua que
dirección y velocidad tomar para alcanzar la misma evitando chocar con otros móviles.
df
Diagrama 4: Objetivos posibles.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
8
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Distribución del sistema :
Tráfico Urbano
SIMULADOR
Mapa de la Ciudad
C2
C1
C3
C4
...
Cc
Servidor
AGENTE 1
AGENTE 2
AGENTE N
M2
M4
M3
M1
...
Cliente 1
Cliente 2
M5
Mx
Cliente N
Diagrama 5: Simulador en servidor, y Agentes en clientes.
Pseudocódigo del Algoritmo Simulación de Tráfico Urbano:
El Simulador de la Ciudad con las Calles corre en el Servidor.
Los Agentes que contienen los Móviles corren en los n Clientes.
Tanto las Calles como los Móviles están publicados en el RMI Registry.
Es posible invocar a los métodos de los móviles mediante: ip:objeto.metodo();
La Ciudad ejecuta dar un STEP. Las Calles ejecutan dar un STEP.
Los Móviles ejecutan dar un STEP.
El Móvil pide a la Calle actual, qué Móviles están cerca.
La Calle dá al Móvil una Lista de Móviles cercanos al mismo.
El Móvil pide a la Calle actual, qué Calle es vecina.
El Móvil evalua el entorno y “decide” velocidad y dirección: pide a la Calle actual,
Agregarlo ó quitarlo de la Calle. La calle pide a cada móvil su nueva posición.
Pseudocódigo del Algoritmo Móvil-Conductor:
Actualizar plan con respecto a objetivo final.
Si no tiene w
Actualizar calles vecinas y recorridas.
Else Decide waypoint próximo.
Obtener móviles cercanos.
Generar vista de radar.
Decidir velocidad y dirección.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
9
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Modelo de la simulación
Clase Calle
Calle vecina 2
Vertice A2
longitud
Calle vecina A
ancho
Dirección
POSICION
Vertice B2
Vertice A1
Calle vecina B
Calle vecina 1
Vertice B1
Clase Móvil:
Vertice A2
longitud
ancho
velocidad
POSICION
Vertice B2
Vertice A1
Vertice B1
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
10
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Las calles llevan una lista de los móviles que estan dentro.
Hay un objeto ciudad que les avisa a las calles que modifiquen su estado T
msegundos.
A su vez las calles piden a los móviles que calculen su nueva posición T msegundos
en el futuro.
Una idea importante es que el objeto móvil va a decir cual es su nueva posición sin
restricciones,
Para tomar esta decisión, la idea es que el móvil simule la inteligencia de un
conductor, o sea:
 El movil tendra inercia, o sea la velocidad no puede variar mas alla de cierto X
por unidad de tiempo ( excepto en un choque ).
 Para tomar la decisión de cuál será su nueva posición, tendrá en cuenta la
situación de los vehículos cercanos y debera estimar cual será la reacción de
estos, para obtener los datos necesarios, el móvil pregunta a la calle actual
quiénes estan en un radio de su posición, luego con estos datos, el móvil
puede preguntar a los otros móviles cuál es su posición y velocidad actual, en
base a eso puede predecir en que dirección se va a mover y asi evitar un
choque.
 Además la velocidad no podra cambiar de ángulo más alla de cierto límite (
radio de giro de las ruedas ).
 El móvil no puede salir de la calle por los lados donde no hay vecinos ( o sea,
no puede subir a las veredas)
Aprovechando la herencia del lenguaje JAVA se generalizó las clases Calle y Móvil, en
la clase Bloque para optimizar el código y reutilizarlo.
Clase Bloque:
Representa un rectangulo oritentado en un plano, con una posicion,dirección,
ancho y largo.
largo
Vertice 2
ancho
dirección
Vertice 3
posición
Vertice 1
Vertice 4
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
11
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Diseño de la simulación
Bloque
Calle
Móvil
posición : vector
dirección : vector
longitud : real
ancho : real
posición : vector
longitud : real
ancho : real
velocidad : vector
peso : real
radioDeGiro : real ( max angulo / tiempo )
getVertices( )
incluyePunto( vector )
agregarMovil( móvil, posición )
quitarMovil( móvil )
getMovilesCercanos( móvil, radio )
getCallesVecinas( )
update( t : time )
getVertices( )
avanzarPosicion( tiempo )
detenerPorChoque( tiempo )
getPosicion( )
getDirección( )
Diagrama de Clases en UML.
Métodos de la Calle:
getVertices( ) : devuelve los 4 vertices.
incluyePunto( vector ) : indica si un punto cae dentro de la calle.
agregarMovil( movil,posición ) : agrega un móvil a la calle en una posición.
quitarMovil( movil ) : cuando el móvil sale de la calle.
getMovilesCercanos( movil,radio ) : indica móviles en un radio r.
getCallesVecinas( ) : indica las calles vecinas a la calle actual.
Métodos del móvil:
getVertices( ) : devuelve los 4 vertices.
avanzarPosicion( tiempo ) : avanza el móvil a una posición en función del tiempo.
detenerPorChoque( tiempo ) : detiene el móvil por un tiempo luego de un choque.
getPosicion( ) : obtiene posición del móvil.
getDirección( ) : obtiene dirección del móvil.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
12
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Diagrama de Secuencia del Móvil
rdp :Conductor
m5: Móvil
c1 :Calle
HacerStep( )
getMovilesCercanos( )
getCallesVecinas( )
avanzarPosicion( T )
quitarMovil( móvil )
Diagrama de Secuencia en UML.
Java
El código del sistema se encuentra en el disquette adjunto a la carpeta del informe.
Distribución del problema
La distribución de la carga es estática y el sistema es sincronizado en cada step.
Las variables que determinan el tamaño del problema están dadas por la granularidad
del tiempo y la cantidad de autos.
La cantidad de mensajes intercambiados entre los objetos crece según n al cuadrado
siendo n la cantidad de moviles y crece según (1/dt)*n siendo dt la cantidad de
tiempo que representa cada step
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
13
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Evaluación de performance: Pruebas Speed Up
Tiempo Total para 50 Iteraciones = 1250 milisegundos.
Tiempo Total para 100 Iteraciones = 2500 milisegundos.
Step
Móviles
Agentes
50 Iteraciones
100 Iteraciones
25
108
Versión standalone
100 seg
198 seg
25
108
1
89 seg
180 seg
25
108
2
121 seg
243 seg
25
108
4
230 seg
455 seg
25
108
8
260 seg
521 seg
600
500
segundos
400
50 iteraciones
300
100 iteraciones
200
100
0
1
2
4
8
agentes
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
14
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Consideraciones técnicas:
8 workstations ( 6 con red de 100Mbps. y 2 con 10 Mbps. )
1 workstation más para el server ( Duron 1.2 Ghz 256 Ram y 100Mbps de red )
El uso de CPU es muy bajo en todos los Agentes : 5 a 15%.
La máquina más potente es un 200% más rápida que la más lenta.
Teniendo en cuenta esto, se repartió la cantidad de Móviles a calcular por cada
Agente.
Para la prueba de 4, se dividió las 8 en 2 grupos de similares a caraceristicas ( 4
grupos de pares de pcs del mismo modelo, 2 Celeron 1.7, 2 Celeron 500 Mhz, 2 Duron
1000 Mhz, y 2 Celeron 466 Mhz )
Observaciones
Se puede observar que el sistema no funciona de la manera esperada.
Al aumentar la cantidad de procesadores el tiempo de ejecución aumenta en lugar de
reducirse.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
15
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Segunda Evaluación de performance: Pruebas Speed Up
Se corrigieron errores de diseño de la versión incial. Se detectó que el procesamiento
realizado por los agentes no se estaba ejecutando realmente en forma paralela, sino
de manera secuencial, sumando a eso el Overhead propio de la comunicación entre
agentes, lo cual incrementa los tiempos de ejecución.
Solucionado este problema, se consiguió un speed UP positivo como lo muestra la
siguiente tabla:
Móviles
Agentes (PCs)
50 iteraciones
100 Iteraciones
Speed UP
40
1
54 segundos
112 segundos
1
40
2 (20 moviles c/u)
40 segundos
83 segundos
1,34
40
4 (10 moviles c/u)
34 segundos
72 segundos
1,55
40
8 (5 moviles c/u)
31 segundos
65 segundos
1,72
120
100
segundos
80
50 iteraciones
60
100 iteraciones
40
20
0
1
2
4
8
agentes (PCs)
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
16
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Propuesta de mejoras
Distribución de la carga de procesamiento:
1) Estudiar el uso de Algoritmo de distribución de la carga dinámico
2) Repartir Tareas mediante Colas de trabajos
3) Un módulo que controle las tareas a realizar en cada máquina ajustando
según del tiempo de respuesta de cada una.
4) Revisar politica de distribución:
1. Autos de calles cercanas en un mismo procesador.
2. Particionar mapa en forma dinámica según densidad de autos
Mejora en performance:
1) Darle capacidad de memorización a las calles, para que almacenen los
ultimos cálculos realizados que generalmente son reiterativos.
2) Optimizar tamaño de mensajes entre nodos para reducir el Ovehead de
comunicación y reducir la frecuencia de mensajes.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
17
- Simulación de tráfico Urbano Federico Marino, Diego Montaldo, Andrés Pollitzer.
Bibliografía, Sitios, Referencias
Multiagent Systems ( A Modern Approach to Distributed Artificial Intelligence )
Gerhard Weiss, 2000. The MIT Press.
PVM
http://www.csm.ornl.gov/pvm/pvm_home.html
JAVA PVM
http://www.cs.virginia.edu/~ajf2j/jpvm.html
Simulation of Traffic Systems - An Overview
http://publish.uwo.ca/~jmalczew/gida_5/Pursula/Pursula.html#Con
Tema: Dynamical systems,Individual-based modeling, and self organization.
Archivo: dynamical systems, individual based Modeling.pdf . Punto 7.6 traffic.
Autor: Edwin D. de Jong, y Bart G. de Boer.
Artificial Intelligence Laboratory, Vrije Universiteit Brussel.
http://arti.vub.ac.be
Archivo: performance of particle tracking system.pdf
Tema: evaluacion de performance de java en simulacion de control de particulas
Autor: Ryoichi Hajima, Univ.Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo,113-8656 Japan.
- Ingeniería en Informática, Universidad de Buenos Aires. Argentina, Noviembre de 2003.
18