Trabajo de Fin de MásterMáster en Geoinformática

Navigational Rule Derivation

Autor:Daniil GALAKTIONOVHODOVANIUK

Director:Miguel A. RODRÍGUEZLUACES

7 de septiembre de 2016

II

«Once men turned their thinking over to machines in the hope that this would setthem free. But that only permitted other men with machines to enslave them.»

Frank Herbert, Dune (1965)

III

Resumen

Los sistemas de navegación terrestres deben disponer de unarepresentación de la red de carreteras que incluya las reglas asociadasa ella tales como direcciones o giros prohibidos. Aunque existennumerosos trabajos para el cartografiado automático de carreteras ypara el inventariado de las señales de tráfico, la asignación de reglas detráfico siempre es un proceso manual costoso.

Se propone por tanto un algoritmo con el fin de producir mapas útiles parauna aplicación de navegación terrestre, embebida con reglas de tráfico, apartir de una red de carreteras que no incorpora esa información y unasseñales de tráfico debidamente detectadas y clasificadas. El funcionamientose basa en simular una navegación real sobre el grafo de carreteras en laque se trata de determinar cuáles son las reglas de tráfico aplicables a cadatramo transitado.

Para probar la eficacia de la solución planteada, se ha realizado unavalidación mediante un entorno de pruebas preparado con datos deOpenStreetMap y de señales previamente inventariadas mediante técnicasLIDAR.

Se aplicó la metodología Scrum durante la elaboración del trabajo,que permitió enfrentarse a este proyecto de investigación de requisitosabstractos que se definían a lo largo del propio desarollo.

Palabras Clave:

SIG, Señales de tráfico, Redes de transporte, Grafos, Navegación,OpenStreetMap

V

AgradecimientosQuería agradecer principalmente a mi director, Miguel Luaces, quien mehabía guiado hasta aquí, y por enfrentarse con paciencia a mi ignorancia.

Gracias también a toda aquella gente que alguna vez me había ayudado ainterpretar las señales: Luis, Sara, Edu, Fernando y muchos otros. . .

VII

Índice general

1. Introducción 11.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Trabajos previos . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3. Organización del trabajo . . . . . . . . . . . . . . . . . . . . . 2

2. Fundamentos teóricos 32.1. Técnicas LIDAR . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2. Geoinformática . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.1. Sistemas de proyección . . . . . . . . . . . . . . . . . 52.2.2. Sistemas de Información Geográfica . . . . . . . . . . 62.2.3. Índices espaciales: R-tree . . . . . . . . . . . . . . . . 62.2.4. Herramientas usadas . . . . . . . . . . . . . . . . . . . 8

2.3. OpenStreetMap . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3. Descripción del problema 113.1. Datos de entrada y resultado deseado . . . . . . . . . . . . . 113.2. Modelo del mundo . . . . . . . . . . . . . . . . . . . . . . . . 11

4. Navigational Rule Derivation 154.1. Aproximación humana . . . . . . . . . . . . . . . . . . . . . . 154.2. Procesamiento de los datos . . . . . . . . . . . . . . . . . . . 164.3. Algoritmo general . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.3.1. Navegación sobre el grafo . . . . . . . . . . . . . . . . 174.3.2. Primera fase: Detección . . . . . . . . . . . . . . . . . 18

Detección desde una intersección . . . . . . . . . . . . 18Detección a lo largo de una calle . . . . . . . . . . . . 19

4.3.3. Segunda fase: Análisis . . . . . . . . . . . . . . . . . . 20Dirección Prohibida . . . . . . . . . . . . . . . . . . . 20Giro Prohibido . . . . . . . . . . . . . . . . . . . . . . 21Dirección Obligatoria . . . . . . . . . . . . . . . . . . 23Giro Obligatorio . . . . . . . . . . . . . . . . . . . . . 24

4.4. Casos problemáticos . . . . . . . . . . . . . . . . . . . . . . . 244.4.1. Detección duplicada . . . . . . . . . . . . . . . . . . . 244.4.2. Reglas contradictorias . . . . . . . . . . . . . . . . . . 254.4.3. Modelo sobresimplificado . . . . . . . . . . . . . . . . 274.4.4. Calidad de los datos . . . . . . . . . . . . . . . . . . . 27

4.5. Otras aproximaciones . . . . . . . . . . . . . . . . . . . . . . . 284.5.1. Análisis sin navegación . . . . . . . . . . . . . . . . . 284.5.2. Detección y análisis por arcos . . . . . . . . . . . . . . 29

5. Trabajo experimental 315.1. Entorno de pruebas . . . . . . . . . . . . . . . . . . . . . . . . 315.2. Resultados obtenidos . . . . . . . . . . . . . . . . . . . . . . . 32

VIII

6. Metodología de desarrollo de Software 336.1. Fase inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346.2. Primera aproximación . . . . . . . . . . . . . . . . . . . . . . 356.3. Segunda aproximación . . . . . . . . . . . . . . . . . . . . . . 366.4. Tercera aproximación . . . . . . . . . . . . . . . . . . . . . . . 366.5. Trabajo experimental . . . . . . . . . . . . . . . . . . . . . . . 36

7. Conclusiones 397.1. Desarrollo futuro . . . . . . . . . . . . . . . . . . . . . . . . . 397.2. Revisión del trabajo . . . . . . . . . . . . . . . . . . . . . . . . 39

A. Diseño de la aplicación 41A.1. Selección de tecnologías . . . . . . . . . . . . . . . . . . . . . 41A.2. Diagrama de clases . . . . . . . . . . . . . . . . . . . . . . . . 41A.3. Diagrama de secuencia . . . . . . . . . . . . . . . . . . . . . . 46

B. Diagrama de Gantt completo 47

C. Glosario de acrónimos 49

IX

Índice de algoritmos

1. Navegación del NRD . . . . . . . . . . . . . . . . . . . . . . . . 172. DetectarSeñalesNodo . . . . . . . . . . . . . . . . . . . . . . . 183. DetectarSeñalesTramo . . . . . . . . . . . . . . . . . . . . . . . 194. AnalizarSeñales . . . . . . . . . . . . . . . . . . . . . . . . . . . 205. MejorDirecciónProhibida . . . . . . . . . . . . . . . . . . . . . 216. MejorGiroProhibido . . . . . . . . . . . . . . . . . . . . . . . . 227. MejorDirecciónObligatoria . . . . . . . . . . . . . . . . . . . . 238. MejorGiroObligatorio . . . . . . . . . . . . . . . . . . . . . . . 249. AñadirRegla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

XI

Índice de figuras

2.1. Un LIDAR móvil montado sobre un vehículo . . . . . . . . . 42.2. Ejemplo de un R-tree . . . . . . . . . . . . . . . . . . . . . . . 7

3.1. Representación gráfica del problema planteado . . . . . . . . 123.2. (izq) Un pequeño ejemplo de una configuración típica de

calles urbanas, con señales de tráfico (der) Su representaciónequivalente en arcos dirigidos y nodos, conservando los signos. 14

4.1. Ejemplo de la operación Ángulo(Tip 1, Tail, Tip 2) . . . . . . 224.2. Ejemplo de señal que sería detectada y analizada de forma

independiente desde dos puntos de intersección . . . . . . . 254.3. Ejemplo de un caso problemático que no se puede resolver

adecuadamente con la información disponible . . . . . . . . 284.4. Aproximación con análisis por señales, sin simular una

navegación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.1. Entorno de pruebas . . . . . . . . . . . . . . . . . . . . . . . . 31

6.1. Fase inicial: investigación y obtención de datos . . . . . . . . 346.2. Primer sprint: aproximación 1 . . . . . . . . . . . . . . . . . . 356.3. Segundo sprint: aproximación 2 . . . . . . . . . . . . . . . . . 366.4. Tercer sprint: aproximación 3 . . . . . . . . . . . . . . . . . . 376.5. Fase final: trabajo experimental . . . . . . . . . . . . . . . . . 37

A.1. Clases del modelo para señales y reglas de tráfico . . . . . . 42A.2. Clases del modelo para la red de carreteras . . . . . . . . . . 43A.3. Clases de lectura y escritura con Hibernate . . . . . . . . . . 44A.4. Clases de navegación, detección y análisis del NRD . . . . . 44A.5. Clases para los dos tipos de detectores que se utilizan . . . . 45A.6. Clases para los filtros usados por los detectores . . . . . . . . 46A.7. Diagrama de secuencia . . . . . . . . . . . . . . . . . . . . . . 46

XIII

Índice de tablas

3.1. Tipos de señales con las que se trabaja . . . . . . . . . . . . . 13

5.1. Precisión de las reglas de tráfico derivadas por el NRD, segúnsu tipo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1

Capítulo 1

Introducción

1.1. Motivación

Cualquier sistema de navegación comercial, como los sistemas GNSSembebidos o Google Maps, incorpora el cálculo de rutas entre susfuncionalidades. Esta funcionalidad consiste en informar al usuario deposibles rutas formadas por caminos sobre una red para llegar a unpunto de destino desde un origen. Se espera que las rutas calculadastengan alguna característica deseable, como ser las más rápidas posibleso las menos congestionadas. Aparte de esto, es más importante que lasrutas tengan ciertas garantías. En especial, que sean física y legalmentenavegables. Para estas garantías, el sistema debe disponer de unarepresentación actualizada de la red de carreteras y de todas las reglasasociadas a ella, como direcciones o giros prohibidos. Algunas reglas, comolos límites de velocidad, también pueden ser útiles para encontrar la rutamás rápida.

A día de hoy, la elaboración de estos mapas enriquecidos con reglasinvolucra una gran cantidad de trabajo manual. En la actualidad existensistemas para la cartografía automática de carreteras navegables (Caoy Krumm, 2009) y para el inventariado de las señales de tráfico (Šegvicet al., 2010) (Maldonado-Bascon et al., 2008). Sin embargo, la adquisiciónautomática siempre es seguida de un proceso manual en el que los expertosidentifican carriles en las carreteras, asignan reglas de tráfico, nombres delas calles y muchas otras características de interés para un mapa útil para lanavegación.

En este trabajo se plantea y se implementa un algoritmo que puede generarun mapa útil para el cálculo de rutas a partir de uno que no disponede la información necesaria o actualizada para tal fin, sólo a partir deinformación de la red de carreteras y de las señales, pudiendo obtenerinformación de ambos tipos de forma automática. Esto permite aliviaren gran medida la cantidad de trabajo manual que se requiere de losexpertos, reduciendo también así el coste asociado a producir y manteneractualizados estos mapas de navegación. Se espera que en un futuro eltrabajo de los expertos se limite a la revisión de la salida de los algoritmos,que trabajarán sobre información recogida de vehículos no tripulados(drones).

2 Capítulo 1. Introducción

1.2. Trabajos previos

No se conoce de otras soluciones existentes para este problema específico.No obstante, existe un gran esfuerzo en la investigación de las técnicaspara sistemas de detección y clasificación de señales de tráfico, pudiendodestacar (Mogelmose et al., 2012) y (Ciresan et al., 2012), entre muchosotros. Las técnicas desarrolladas por estos autores son muy útiles para elinventariado de las señales, ya que permiten obtener de forma automáticagrandes cantidades de datos sobre estas señales, su visibilidad y susposiciones. El trabajo que se presenta aquí puede verse como un segundopaso para las técnicas de detección de señales, que sería determinar elefecto que producen sobre la red de tráfico. Para lograr esto, las señalesdeben estar ya clasificadas, y su información de posición y orientacióndebe ser precisa. Esto puede realizarse mediante sistemas LIDAR comose demuestra en (Takagi et al., 2006), (Zhou y Deng, 2014) y másrecientemente en (Riveiro et al., 2016).

1.3. Organización del trabajo

La organización de este trabajo es la siguiente:

En el Capítulo 2 se da un repaso exhaustivo de los conocimientostécnicos necesarios para poder comprender todas las partes deltrabajo que se ha realizado.

En el Capítulo 3 se da una visión más específica sobre los datos conlos que se trabaja y el planteamiento del problema.

En el Capítulo 4 se explica en gran detalle la solución final alcanzada yel funcionamiento de los algoritmos desarrollados, con fuerte apoyoen los pseudocódigos. También se discute otras posibles solucionesque se habían descartado.

En el Capítulo 5 se aplica esta solución sobre un entorno de pruebasreal y se discuten los resultados obtenidos.

En el Capítulo 6 se habla de los procesos de investigación y desarrollodel proyecto, de los aspectos metodológicos y de la planificación.

En el Capítulo 7 se evalúa el cumplimiento de los objetivos que sehabían planteado y se discuten posibles líneas de trabajo futuro.

El Apéndice A está dedicado a la documentación de la solución, conobjeto de facilitar el desarrollo sobre el sistema ya implementado, asícomo la reutilización de sus componentes.

El Apéndice B muestra un diagrama de Gantt completo del proyecto.

3

Capítulo 2

Fundamentos teóricos

Además de los conocimientos básicos de geometría y programación quese requieren para poder comprender este trabajo, también es útil teneruna visión fundamental del conocimiento especializado que ha permitidollevar a cabo el proyecto. A continuación se dará un breve resumen de estosfundamentos, con referencias recomendadas para un mayor detalle.

2.1. Técnicas LIDAR

Mientras que las técnicas basadas en el análisis de imágenesbidimensionales son suficientes para extraer automáticamente la posiciónde una señal (Arnoul et al., 1996), la orientación precisa de la señalrequiere de un modelo tridimensional, como el que se puede reconstruircon técnicas Light Imaging, Detection And Ranging (LIDAR). Este tipo dereconstrucción se realiza en trabajos como (Pu et al., 2011), (Takagi et al.,2006) o (Riveiro et al., 2016).

Los sistemas LIDAR se basan en la emisión de rayos láser para estimar lasdistancias a los objetos mediante la medición del tiempo de retorno y enocasiones también de la fase de la onda devuelta. En concreto, para estetrabajo son útiles los dispositivos portátiles que se pueden montar sobre unvehículo, como el que se muestra en la Figura 2.1.

El sensor realiza barridos circulares continuos en los que mide la distanciaa miles de puntos a su alrededor por segundo. Los puntos medidosen diferentes instantes de tiempo se sincronizan con la posición delvehículo en cada instante (que es obtenida mediante tecnologías GlobalNavigation Satellite System (GNSS) e Inertial Navigation System (INS)),para ser posteriormente integrados en una nube de puntos en un espaciotridimensional, donde la superficie externa de los objetos del mundo quedarepresentada mediante puntos de muestra. Una mayor resolución significatener una mayor densidad de puntos por superficie, lo cuál es deseable paratener una mayor precisión en los datos. Sin embargo, también implica unmayor tiempo de procesamiento, por lo que las nubes de puntos tambiénse suelen simplificar para reducir su resolución. Es habitual que cadapunto también tenga asociado un valor de intensidad, que depende engran medida de la reflectividad del material escaneado. En ocasiones, lainformación geométrica sola no es suficiente para cubrir los requerimientosde información, especialmente respecto de la visualización de los datos.Por ello, es común realizar una adquisición de imagen digital junto con la

4 Capítulo 2. Fundamentos teóricos

FIGURA 2.1: Un LIDAR móvil montado sobre un vehículo.1

medición con láser escáner, de manera que se obtenga la mayor precisióngeométrica (láser escáner) y la mayor resolución radiométrica (fotografía)de cara a la generación del producto final. Ambas fuentes de información sepueden combinar para colorear la nube de puntos (Naroditsky et al., 2011).

Es también frecuente reconstruir geometrías a partir de nubes de puntos,con técnicas como la triangulación de (Delaunay, 1934), aunque no esrequerido por todas las técnicas de segmentación y clasificación de lasseñales de tráfico.

El método de (Riveiro et al., 2016) es el que permitió obtener las señales quese habían usado en este trabajo. La segmentación de las señales tiene dosfases en las que segmenta los puntos por intensidad, ya que las señales sonhabitualmente más reflectantes que su entorno. Después de este filtrado porintensidad, se realiza un clústering mediante el algoritmo DBSCAN (Esteret al., 1996) para encontrar grupos de puntos cercanos entre sí. Los puntoscorrespondientes a una señal pueden proyectarse sobre un plano, así quea cada uno de estos grupos se le aplica un análisis basado en autovectoressobre una matriz de covarianza (Belton y Lichti, 2006) para encontrar ladirección de la normal al plano formado por los puntos. En caso de que lospuntos se alejen demasiado del plano, el grupo es descartado.

Por último, los puntos son proyectados sobre el plano obteniendo unaimagen en dos dimensiones, y se aplican filtros morfológicos paramejorarla. La forma de la señal se determina ajustando el contorno de lacurva que se obtiene al contar el número de píxeles blancos para cadacoordenada en el eje de las ordenadas.

Aunque los autores no lo mencionan, a partir de aquí se puede analizartambién el contenido de la señal, lo cuál se habrá tenido que realizar paraeste trabajo. Nótese por tanto que esta aproximación permite extraer tresatributos importantes de la señal: su tipo, su posición y su orientación.

1Autor: Whoisjohngalt de Wikipedia en Inglés, con licencia CC BY-SA 3.0, descargado enWikimedia Commons

2.2. Geoinformática 5

2.2. Geoinformática

La geoinformática es la aplicación de las técnicas informáticas sobrediferentes áreas científicas que incluyen la geografía, la cartografía y lasciencias espaciales. La geoinformática presenta aplicaciones a diversoscampos de actividad, como por ejemplo la inteligencia geoespacial,gestión urbanística, gestión del medio natural, gestión de infraestructuras,geomarketing, geosalud, análisis espacial, geoestadística, y otros camposen los que existe la necesidad de gestionar información georreferenciada deforma eficaz, ordenada y estructurada para su utilización correcta, y dondela accesibilidad, estandarización e interoperatividad resultan claves para eldesarrollo de la actividad.

A continuación describimos los aspectos de la Geoinformática másrelevantes para nuestro trabajo: los sistemas de proyección, los sistemas deinformación geográfica, los índices espaciales y las herramientas softwareutilizadas.

2.2.1. Sistemas de proyección

Uno de los problemas de la geodesia es la definición de un geoide con lasformas y dimensiones del globo terrestre. Probablemente el geoide másextendido en las aplicaciones informáticas sea el elipsoide WGS 842. Enestas representaciones del mundo se trabaja con coordenadas geográficasde longitud y latitud, siendo por tanto complejo y poco intuitivo medirdistancias desde un punto a otro, tanto desde un punto de vista manualcomo automático.

La cartografía se encarga por tanto de representar todo o parte de ungeoide en un plano, para poder producir un mapa y trabajar en un espaciode dos dimensiones, habitualmente euclidiano. Para este fin se puedenemplear distintas técnicas de proyección sobre superficies que se puedendesarrollar, como un cilindro, un cono o un plano. Las diferentes ventajase inconvenientes de cada uno de los sistemas de proyección no tieneespecial relevancia en este trabajo, sobre todo debido a que se opera sobreescalas grandes que no son especialmente afectadas por la deformación.Simplemente es recomendable elegir una única proyección que se adaptea las necesidades de la geografía de interés. En el caso de este trabajo,se ha considerado útil usar diferentes proyecciones Universal TransverseMercator (UTM)3 dependiendo de la zona geográfica sobre la que hade funcionar el sistema. Las proyecciones UTM presentan un sistema decoordenadas cartesianas métrico, como es habitual en las proyeccioneslocales, lo cuál resulta de utilidad para medir distancias y ángulos como sehace repetidamente en el Capítulo 4. Se puede encontrar más informaciónsobre los diferentes sistemas de proyección existentes en (Snyder, 1997).

2https://es.wikipedia.org/wiki/WGS843https://en.wikipedia.org/wiki/Universal_Transverse_Mercator_

coordinate_system

6 Capítulo 2. Fundamentos teóricos

2.2.2. Sistemas de Información Geográfica

Un Sistema de Información Geográfica, también conocido comoGeographic Information System (GIS), es como se denomina a un sistemaque manipula datos espaciales o geográficos. Se considera una parteimportante de la geoinformática (Foote y Lynch, 1996), y gran parte delos estudios se centran en las técnicas para la obtención de información útilpara estos sistemas, su presentación y su explotación.

Hay por tanto multitud de aplicaciones GIS con las que es posible integrary analizar diferentes tipos de datos espaciales, mediante abstraccionescomo capas. Una aplicación que se ha usado repetidamente duranteel desarrollo de este proyecto es QGIS4, de software libre, que ofrecenumerosas facilidades para gestionar datos desde varias fuentes comobases de datos espaciales o directamente desde la web mediante un WebMap Service (WMS) o Web Feature Service (WFS) (Scharl y Tochtermann,2009). La información puede ser fácilmente clasificada mediante estilos devisualización, como por ejemplo usar diferentes colores para representardiferentes tipos de señal de tráfico. También hace muy simple la mediciónde ángulos y distancias sobre un mapa proyectado, lo cuál ha ayudado engran medida el desarrollo de los algoritmos de este proyecto.

2.2.3. Índices espaciales: R-tree

Para acceder de forma eficiente a la información de los objetos espaciales esnecesario disponer de un índice espacial sobre el que se puedan realizarbúsquedas. Existen diversos tipos de índices espaciales para diferentespropósitos. El más utilizado para los objetos vectoriales es el R-tree(Guttman, 1984), así como índices derivados del R-tree.

La idea detrás del R-tree es es agrupar los objetos cercanos yrepresentarlos con un Minimum Bounding Rectangle (MBR), el rectángulomás pequeño posible que encierre a este grupo de objetos. Al estar todoslos objetos contenidos en el rectángulo, una consulta que no resulte enuna intersección con el rectángulo tampoco intersecará con ninguno de losobjetos contenidos. La estructura se organiza en forma de árbol, dondelas hojas se asocian con los rectángulos que describen un único objeto,y los niveles superiores de la jerarquía agrupan un número variable derectángulos5.

En la Figura 2.2 se puede observar un ejemplo de una estructura R-tree. Losobjetos correspondientes a los rectángulos R9 y R10 se encuentran cercanosentre sí, por lo que son agrupados por el rectángulo R3. A la vez, R3 esuno de los tres rectángulos contenidos en R1, que se encuentra en el nivelsuperior de la jerarquía. Si se quisiera buscar qué objetos intersecan en unazona, basta con empezar comprobando si alguno de los rectángulos en elnivel superior interseca con la zona consultada. En caso positivo, descenderpor el subárbol adecuado y repetir el proceso.

4http://www.qgis.org/en/site/5Se puede configurar un máximo y un mínimo de entradas por nodo

2.2. Geoinformática 7

FIGURA 2.2: Ejemplo de un R-tree: En la parte superior sepuede ver el espacio de los objetos indexados. En la parteinferior se encuentra el árbol en el que los rectángulos se

agrupan por jerarquías.

8 Capítulo 2. Fundamentos teóricos

Una vez creado, se pueden añadir más objetos a un R-tree o eliminaralgunos existentes, para lo cuál puede llegar a ser necesario reestructurar elárbol. Mientras que se trata de una estructura actualizable, existen métodosmás eficientes para construirla desde cero (Leutenegger et al., 1997).

2.2.4. Herramientas usadas

Para la manipulación de los datos geográficos se usaron así mismo variasherramientas que se comentarán a continuación:

PostGIS6 es una conocida extensión del DBMS PostgreSQL7 queañade soporte para objetos espaciales y geográficos. Implementa laespecificación de Simple Features del Open Geospatial Consortium(OGC)8, y dispone de funciones para manipular datos espacialesy realizar operaciones sobre ellos en el lenguaje SQL. Tambiénimplementa índices espaciales GiST9 para mayor eficiencia en lasoperaciones.

Java Topology Suite (JTS)10 es una librería en Java que ofrece unmodelo para la manipulación de geometría vectorial euclidiana enmemoria. Su modelo de datos es muy similar al de PostGIS11,lo que permite una fácil integración e interoperatividad entre lasdos herramientas. Hibernate Spatial integra esta librería en suestándar para su modelo12.

2.3. OpenStreetMap

Siendo los términos de uso de servicios como Google Maps13 demasiadorestrictivos para las intenciones de uso de muchos programadores,científicos, activistas, cartógrafos y ciudadanos en general, surgió unproyecto conocido como OpenStreetMap (OSM)14.

OSM es un mapa del mundo libre y editable que se construye y se mantienepor voluntarios. Su licencia permite un acceso libre a sus mapas y a todoslos datos subyacentes, que son el principal producto de OSM desde elpunto de vista de un desarrollador. Su formato es una estructura de datostopológica15 con tres tipos de elementos:

6http://postgis.net/7https://www.postgresql.org/8http://www.opengeospatial.org/resource/products/details/?pid=

5099https://www.postgresql.org/docs/9.4/static/gist-intro.html

10http://www.vividsolutions.com/jts/JTSHome.htm11Dicen implementar el mismo estándar, pero a día de hoy no están oficialmente

certificados12http://hibernatespatial.org/13https://developers.google.com/maps/terms14http://www.openstreetmap.org15https://wiki.openstreetmap.org/wiki/Elements

2.3. OpenStreetMap 9

Nodos: Puntos con una posición geográfica en el sistema WGS 84(latitud y longitud). Son la unidad de información básica en OSM ypueden encontrarse solos o como parte de una vía o relación.

Vías: Listas ordenadas de nodos, formando polilíneas. Se usantanto para representar estructuras lineales (carreteras, etc. . . ) comopolígonos (edificios, parques, etc. . . ).

Relaciones: Listas ordenadas de nodos, vías y otras relaciones. Cadamiembro de una relación puede tener un rol. Las relaciones se usanpara representar varios tipos de datos compuestos, como líneas detransporte público.

Toda la información restante puede ir asociada a los nodos, vías o relacionesen forma de etiquetas, que son pares de clave-valor de cadenas detexto arbitrario. Por tanto, el formato no restringe qué etiquetas puedecontener un elemento. Nuevas claves son inventadas de forma diaria y sondocumentadas16 para mantener cierta uniformidad en la información.

Con este formato se describe todo el contenido de OSM, que puedeser descargado o actualizado mediante su API17 en formato ExtensibleMarkup Language (XML), aunque existen servicios que proporcionan unacceso fácil a trozos manejables de los datos para zonas interesantes comociudades18.

Existen herramientas como Osmosis19 que permiten procesarautomáticamente estos datos y sincronizarlos con una base de datosPostGIS. Las calles en OSM se definen habitualmente como una sola vía,que comparte nodos con otras calles en sus intersecciones. Esto hace quesea poco práctico calcular rutas sobre estos datos en crudo, así que debenser tratados con una herramienta como osm2pgrouting20 o osm2po21,que particionan en tramos las vías correspondientes a calles o carreteras yexportan estos tramos a una tabla de PostGIS.

16https://wiki.openstreetmap.org/wiki/Map_Features17https://wiki.openstreetmap.org/wiki/API18https://mapzen.com/data/metro-extracts/19https://wiki.openstreetmap.org/wiki/Osmosis20http://pgrouting.org/docs/tools/osm2pgrouting.html21http://osm2po.de/

11

Capítulo 3

Descripción del problema

3.1. Datos de entrada y resultado deseado

A alto nivel, existen dos bloques fundamentales de información preparadade la que se parte: una red de carreteras navegable1 y una colección deseñales detectadas y clasificadas. Concretamente, necesitamos la posiciónde las señales, su tipo y su orientación con respecto al norte.

Como se muestra en la Figura 3.1, ésta es toda la información de la quese dispone en nuestro problema, siendo el objetivo etiquetar la red decarreteras con reglas de tráfico obtenidas a partir de las señales, de formaque pueda ser usada para el cálculo de rutas en un sistema de navegación.

El etiquetado puede realizarse en cualquier formato estándar que estépreparado para soportar tal tipo de información. Dos ejemplos sonel formato de OSM y el de INSPIRE Data Specification on TransportNetwork2.

3.2. Modelo del mundo

Al no existir trabajos previos por los que guiarse, se ha decidido simplificarel problema y limitarse a trabajar con un conjunto pequeño de señales, quese enumeran en la Tabla 3.1. Se trata de señales muy comunes que controlanlos aspectos más básicos del flujo de tráfico, lo cuál las hace interesantespara un comienzo. Además, estas señales son usadas en prácticamente todoel mundo. Al trabajar directamente con el tipo de una señal en lugar de suimagen, las mismas soluciones pueden aplicarse para diferentes países, conmuy poca o ninguna adaptación.

También se trabaja sobre un modelo simplificado del mundo de tráfico enel que se hacen las siguientes asunciones:

Existen como mucho dos carriles para cada tramo de calle o carretera,uno para cada sentido navegable.

1El término “navegable” aquí se refiere a que las intersecciones estén marcadas de formaprecisa. Una simple proyección plana de las líneas de las carreteras no es suficiente, ya quepodrían cruzarse en el espacio sin existir un punto de intersección.

2http://inspire.jrc.ec.europa.eu/documents/Data_Specifications/INSPIRE_DataSpecification_TN_v3.2.pdf

12 Capítulo 3. Descripción del problema

(A) Calles y señales

(B) Calles etiquetadas con reglas

FIGURA 3.1: (A) Representación gráfica de la informaciónde entrada: una red de calles y señales

(B) Problema a resolver: etiquetar la red de calles con reglasde tráfico obtenidas de las señales.

3.2. Modelo del mundo 13

R-101 R-302 R-303 R-400cDirecciónprohibida

Giro a laderechaprohibido

Giro a laizquierdaprohibido

Sentidoobligatoriohacia delante

R-400a R-400b R-400d R-400eSentidoobligatoriohacia laderecha

Sentidoobligatoriohacia laizquierda

Giroobligatoriohacia laderecha

Giroobligatoriohacia laizquierda

TABLA 3.1: Tipos de señales con las que se trabaja. Fuente:DGT3

Todas las carreteras y señales se sitúan a la misma altura y no existenedificios ni otros obstáculos para la visibilidad de una señal.

Las señales de tráfico verticales detectadas son completas y suficientespara inferir todas las reglas de tráfico que se deben aplicar. Estoimplica que todas las demás fuentes de información, como las señaleshorizontales, pueden ser ignoradas sin consecuencias.

Conceptualmente, la red de carreteras se puede ver como un grafo dirigido,ejemplificado en la Figura 3.2. Un arco representa un sólo tramo de unacalle o carretera, mientras que un nodo es una intersección de dos o más(habitualmente más) tramos. La dirección de un arco corresponde al sentidosobre el que se permite navegar por ese tramo. Un tramo de dos sentidos serepresenta con dos arcos, uno para cada dirección. Tanto la representaciónen grafo como la terminología de arcos y nodos se usará extensivamente enel Capítulo 4.

3http://www.dgt.es/Galerias/seguridad-vial/formacion-vial/cursos-para-profesores-y-directores-de-autoescuelas/doc/XIV_Curso_24_NormasYSeniales.pdf

14 Capítulo 3. Descripción del problema

FIGURA 3.2: (izq) Un pequeño ejemplo de unaconfiguración típica de calles urbanas, con señales de

tráfico(der) Su representación equivalente en arcos dirigidos y

nodos, conservando los signos.

15

Capítulo 4

Navigational Rule Derivation

El algoritmo que conforma la solución propuesta recibe el nombre deNavigational Rule Derivation (NRD). El NRD está basado en la ideade imitar el comportamiento de los conductores reales cuando necesitanderivar reglas de tráfico a partir de las señales. Es el resultado finaldespués de otras numerosas aproximaciones, con el objetivo de maximizarla eficacia y minimizar la complejidad.

4.1. Aproximación humana

Cuando los conductores humanos conducen vehículos por porcionesdesconocidas de una ciudad, están resolviendo efectivamente y en tiemporeal el problema planteado, ya que consiguen asignar reglas de tráficosobre una red de carreteras a partir de la información que han recogidode las señales de tráfico, además de otras muchas fuentes de informaciónde las que se carece. Para la mayoría de los conductores humanos,este procedimiento está tan interiorizado que su explicación en formaalgorítmica no es una tarea fácil, y ningún algoritmo diseñado para taltarea lo podrá imitar de la forma suficientemente precisa como para quecualquier conductor lo reconozca como correcto.

Aún así, se puede hablar de dos procesos mentales que se realizanrepetidamente para derivar reglas de tráfico:

1. Atención a toda señal que se pueda ver mientras se circula una calle.Tras analizar brevemente su significado intrínseco, se valora si la señalestá dirigida para el conductor concreto. Podría no ser así por elmensaje de la señal, ya que una señal podría aplicarse a un tipo devehículo específico, o por estar posicionada o orientada de tal formaque resulte obvio que está dirigida para los vehículos que circulen enotra calle o sentido.

2. En caso de ser la señal aplicable, se valora su significado extrínseco,con respecto a las calles alrededor de la misma y a otras señales.Si se consigue determinar la regla de tráfico en este momento, elconductor la asocia mentalmente a las calles por las que navega. P.ej.“No se puede girar por aquí”. En caso de no encontrar un significadoinmediato, es posible que haya una limitación a la visibilidad que seespera resolver más adelante. P.ej., podría resultar que la calle a la quese prohíbe girar no esté visible hasta llegar a la siguiente intersección.

16 Capítulo 4. Navigational Rule Derivation

Es esperable que los conductores realicen ambos procesos simultáneamentede alguna forma, al mismo tiempo que partes de su mente consciente oinconsciente se ocupan de vigilar a otros elementos del entorno por el quecircula y de manejar el propio vehículo. Sin embargo, está claro que ladetección y el análisis de las señales pueden ser dos procesos separadose incluso ser aplicados de forma secuencial sin conllevar esto a ningúnproblema aparte de un posible retardo en estos procesos, que sólo esimportante si se desea circular en tiempo real.

Obsérvese también que no todas las señales están pensadas para ser vistasdesde el mismo punto. De la Tabla 3.1, las señales R-302, R-303, R-400dy R-400e se colocan a lo largo de una calle, para ser vistas antes de unaintersección. Las señales R-101, R-400a, R-400b y R-400c, por otra parte, sesuelen colocar en las intersecciones para indicar cuáles son las calles sobrelas que se aplican.

Estas ideas sugieren que es posible realizar un algoritmo que navegue porun grafo, como navegaría un conductor por unas carreteras, detectando yanalizando cada señal a medida que se realiza la navegación a fin de derivarreglas de tráfico.

4.2. Procesamiento de los datos

El NRD necesita poder empezar con una representación de la red decarreteras en forma de un grafo navegable, donde cada nodo representaríauna intersección o el final de una calle sin salida, y los arcos serían tramosnavegables que conectan estos nodos. De aquí en adelante, se usará laterminología de los arcos y nodos propia de los grafos.

OSM ofrece una adecuada fuente de datos para este tipo de información,si bien su definición de vías que se explica en la Sección 2.3 no es útilpara la navegación como tal, ya que no marca de ninguna forma quénodos de los que integran una vía forman parte de una intersección conmás vías. Utilizando osm2po se obtiene una tabla en PostGIS de tramosparticionados (arcos). En este caso, no es necesario tener una tabla separadapara los puntos de intersección, basta con asignar un identificador de origeny destino a cada tramo en función de su nodo de OSM. Los puntos deintersección son aquellos nodos que aparecen como inicio o final de másde dos arcos1. La información de las señales también reside en una tablade en PostGIS, indicando su identificador, tipo, posición y orientacióncon respecto al norte, también llamada azimut. Ambas tablas son leídas amemoria mediante Hibernate, donde se construye un grafo con arcosy nodos, y también un índice espacial sobre la colección de las señales.El grafo es dirigido, queriendo decir que un tramo de carretera generados arcos, uno para cada sentido. Se espera que tener todo el grafo enmemoria sea perfectamente asumible, incluso para una ciudad grande. Portanto, todo el funcionamiento del NRD que se detallará a continuación seimplementa mediante operaciones e índices en memoria gracias a la libreríaJTS.

1Necesario más de dos al ser los arcos dirigidos.

4.3. Algoritmo general 17

4.3. Algoritmo general

Se simula una navegación por arcos sobre el grafo. Para cada arco navegadoexisten dos fases de procesamiento:

Primera fase: Detección. Se determina cuáles son las señales que sedeberían detectar (ver) desde el arco navegado, así como desde elnodo de destino.

Segunda fase: Análisis. Cada señal obtenida en la fase anterior esanalizada para tratar de determinar las reglas de tráfico que generaen su contexto.

Las reglas obtenidas después de la segunda fase son añadidas a lacolección actual de reglas y los arcos salientes del nodo de destino sonnavegados a continuación, siempre que no exista una regla que lo prohíba.A continuación se estudiará cada paso del NRD en detalle.

4.3.1. Navegación sobre el grafo

Como se puede apreciar en el Algoritmo 1, la navegación del NRD se realizapor anchura, usando una cola que se llama frontera, en la que se añaden losarcos que suceden a cada arco navegado. El algoritmo termina cuando lafrontera queda vacía, significando que no quedan arcos por visitar.

Algoritmo 1: Navegación del NRDentrada: grafosalida : reglas

frontera← cola vacía;arco_inicial← ArcoAleatorio(grafo);Encolar(frontera, arco_inicial);

mientras ColaNoVacía(frontera) hacerarco_actual← Desencolar(frontera);nodo← NodoDestino(arco_actual);

señales← DetectarSeñalesTramo(arco_actual);señales← señales ∪ {DetectarSeñalesNodo(nodo)};reglas← AnalizarSeñales(señales, arco_actual, nodo, frontera,

reglas);

para cada arco en ArcosSalientes(nodo) hacersi no ArcoVisitado(arco) y noNavegaciónProhibida(arco_actual, arco, reglas) entoncesArcoVisitado(arco)← Sí;Encolar(frontera, arco);

fin sifin para cada

fin mientras

devolver reglas;

18 Capítulo 4. Navigational Rule Derivation

Tras aplicar las de detección y análisis que se explicarán más adelante,se añaden a la frontera todos los arcos salientes del nodo de destino delarco por el que se acaba de navegar, siempre que no exista una reglaque prohíba la navegación a alguno de estos arco desde el arco actual(como una dirección prohibida o un giro prohibido), comprobación quese realiza en NavegaciónProhibida. También se evita volver a procesararcos que ya fueron encolados antes a la frontera, ya que supondría repetirinnecesariamente el procesamiento.

4.3.2. Primera fase: Detección

Como se ha explicado en la Sección 4.1, podemos hablar de dos clases deseñales según el lugar desde el que se espera que sean vistas: desde unaintersección o a lo largo de la calle por la que se está navegando.

Detección desde una intersección

Las señales R-101, R-400a, R-400b y R-400c son colocadas para ser vistasdesde una intersección, lo que significa que su detección se debe hacer conrespecto al nodo de destino, como se hace en el Algoritmo 2. Se obtienentodas las señales situadas en un radio de 15 metros alrededor del nodo yse descartan aquellas que no están claramente orientadas en dirección a laintersección.

Algoritmo 2: DetectarSeñalesNodoentrada: nodosalida : señales

señales_de_interés← {R-101, R-400a, R-400b, R-400c};señales← {};

para cada señal en señales a 15m de nodo hacerorientación_señal← CalcularOrientación(nodo, señal);si Tipo(señal) ∈ señales_de_interés y

abs(Normalizar(orientación_señal + Azimut(señal))) ≤ 80◦

entoncesseñales← señales ∪ {señal };

fin sifin para cada

devolver señales;

Para obtener de forma eficiente las señales por su ubicación esnecesario utilizar un indice espacial, como el R-tree (mencionado en laSección 2.2.3) que incorpora la librería JTS. Se introducen en el Algoritmo 2varias funciones de utilidad:

CalcularOrientación devuelve la orientación en grados delsegundo punto con respecto al primer punto. Si el segundo punto seencontrara exactamente al norte del primero, se devolvería 0◦; si fueraal oeste, −90◦; etc. . .

4.3. Algoritmo general 19

Normalizar traslada el valor de un ángulo al rango de (−180◦, 180◦].

Nótese por tanto que cuando una señal está exactamente orientada haciala intersección, su azimut es el opuesto de orientación_señal, y portanto su suma resultará en 0◦. Cuanto más se aleje de ese valor, más giradaestá la señal. Se considera que si la señal está girada a más de 80◦ (es decir,orientada casi perpendicularmente a la intersección) significa que no estápensada para ser vista desde esa intersección y puede ser ignorada.

Detección a lo largo de una calle

Las señales R-302, R-303, R-400d y R-400e son colocadas para ser vistasa lo largo de la calle por la que se está navegando. Por tanto, necesitanun tratamiento diferente y más complejo, como el que se muestra en elAlgoritmo 3. La clave reside en encontrar el punto más cercano del tramo ala señal, y considerar que la señal espera ser vista 10 metros antes de llegar aese punto. Conocida esa posición, se aplica el mismo criterio que el descritoen el algoritmo anterior.

Algoritmo 3: DetectarSeñalesTramoentrada: arcosalida : señales

señales_de_interés← {R-302, R-303, R-400d, R-400e};señales← {};

para cada señal en señales a 10m de arco hacersi Tipo(señal) ∈ señales_de_interés entonces

señal_proy← Índice(arco, MásCercano(arco, señal));mi_posición← Proyección(arco, max(0, señal_proy − 10m));orientación_señal← CalcularOrientación(mi_posición,

señal);

si señal_proy > 0 y señal_proy <Longitud(arco) yabs(Normalizar(orientación_señal + Azimut(señal))) ≤ 80◦

entoncesseñales← señales ∪ {señal };

fin sifin si

fin para cada

devolver señales;

Siendo la geometría de un tramo siempre lineal, es por tanto posibleobtener las coordenadas de un punto situado en una longitud dada deltramo, como el punto en el metro 10 del tramo con la operación denominadaProyección. También existe la operación inversa Índice, en la que apartir de las coordenadas de un punto de la línea se obtiene su índice enla línea correspondiente. En numerosas implementaciones, como la de JTS,aplicar Índice sobre un punto fuera de la línea da el mismo resultado queaplicarlo sobre el punto de la línea más cercano al dado. En el Algoritmo 3se hace explícito ese comportamiento con la operación MásCercano.

20 Capítulo 4. Navigational Rule Derivation

No se devuelve la señal si su punto más cercano al tramo es su inicio o sufin, puesto que una señal de este tipo no se encuentra antes ni después deltramo desde el que debe ser vista.

4.3.3. Segunda fase: Análisis

Una vez conocidas las señales que podrían aplicarse al arco actual, cada unade ellas debe ser analizada independientemente2 para tratar de obtener susignificado a partir de su tipo, posición y orientación en el contexto del arcoactual y los sucesores. Conocido su significado se genera una nueva reglade tráfico a devolver. En el Algoritmo 4 se puede ver que dependiendo deltipo de la señal, se aplican diferentes criterios y se usa diferente informaciónpara generar una regla.

Algoritmo 4: AnalizarSeñalesentrada: señales, arco_actual, nodo, frontera, reglassalida : reglas derivadas a partir de señales

para cada señal en señales hacersi Tipo(señal) ∈ {R-101} entonces

nueva_regla← MejorDirecciónProhibida(señal, nodo);sinó, si Tipo(señal) ∈ {R-302, R-303} entonces

nueva_regla← MejorGiroProhibido(señal, arco_actual);sinó, si Tipo(señal) ∈ {R-400a, R-400b, R-400c} entonces

nueva_regla← MejorDirecciónObligatoria(señal, nodo);sinó, si Tipo(señal) ∈ {R-400d, R-400e} entonces

nueva_regla← MejorGiroObligatorio(señal, arco_actual);fin si

reglas← AñadirRegla(reglas, señal, nueva_regla, frontera);fin para cada

devolver reglas;

Aunque más adelante se explicará en detalle el funcionamiento deAñadirRegla, por ahora se puede asumir que es simplemente reglas ←reglas ∪ {nueva_regla}. A continuación se hablará los criterios seguidospara derivar una regla a partir de cada tipo de señal.

Dirección Prohibida

Esta es una señal pensada para ser vista desde una intersección, y se colocaa la entrada de una calle por la que no se debe entrar desde la mencionadaintersección. En el Algoritmo 5 se asigna una puntuación a cada arcosaliente del nodo en base a lo parecida que sea su dirección a la direcciónde la señal, cuando se observa desde el nodo, y se genera una hipotéticaregla de dirección prohibida con esa puntuación y el arco correspondiente.Finalmente se devuelve aquella regla que tenga la mayor puntuación.

2En una futura versión se buscará un mecanismo para tratar varias señales situadas enel mismo poste que puedan tener un significado compuesto.

4.3. Algoritmo general 21

Algoritmo 5: MejorDirecciónProhibidaentrada: señal, nodosalida : nueva_regla derivada de señal desde nodo

Puntuación(nueva_regla)← −∞;ArcosProhibidos(nueva_regla)← ∅;

para cada arco en ArcosSalientes(nodo) hacerseñal_proy← Índice(arco, MásCercano(arco, señal));si señal_proy ≤ 0 entonces señal_proy← 10m ;

α← Ángulo(señal, nodo, Proyección(arco, señal_proy));si α < −10◦ entonces α← α − 30◦ ;

puntuación_actual← 90 − abs(α);si puntuación_actual > Puntuación(nueva_regla) entonces

Puntuación(nueva_regla)← puntuación_actual;ArcosProhibidos(nueva_regla)← {arco };

fin sifin para cada

devolver nueva_regla;

La regla que se desea generar va a tener asociada un conjunto de arcosprohibidos, que en este caso solamente va a contener un arco, y unapuntuación que se va a calcular. Para calcular la orientación a la que estácada arco con respecto al nodo se toma el punto más cercano del arco a laseñal. En caso de que ese punto sea el principio del arco, se toma su décimometro en su lugar3.

Posteriormente se calcula el ángulo entre la señal y el arco con respectoal nodo, utilizando la operación Ángulo, que toma tres puntos comoargumento, devolviendo al ángulo α entre los dos vectores: uno formadocon el segundo y primer punto y otro formado con el segundo y tercerpunto, como se ejemplifica en la Figura 4.1. Esta operación se usarárepetidamente en algoritmos similares. Cuando α es negativo y menor que−10◦, significa que la señal está claramente a la izquierda del arco. No eshabitual que una señal se sitúe a la izquierda de la calle a la que aplica, asíque se exagera esa diferencia para penalizar ese caso. Se establece un valorarbitrario4 como 90 para la puntuación máxima que puede tener una regla.

Giro Prohibido

La principal propiedad que se considera para el Algoritmo 6 es que ungiro prohibido se aplica a una calle situada de forma aproximadamenteperpendicular a la calle actual. Es una interpretación abierta a debate, yen el futuro se valorará buscar la calle que represente el giro más cerradoen la dirección apropiada, en lugar del giro más perpendicular.

3Nótese que si tal cosa pasa, la señal se encuentra antes del arco, lo que suele significarque no se debe aplicar sobre él

4Más adelante se verá su verdadera utilidad

22 Capítulo 4. Navigational Rule Derivation

FIGURA 4.1: Ejemplo de la operación Ángulo(Tip 1, Tail,Tip 2)

Algoritmo 6: MejorGiroProhibidoentrada: señal, arco_actualsalida : nueva_regla derivada de señal desde arco_actual

Puntuación(nueva_regla)← −∞;ArcoOrigen(nueva_regla)← arco_actual;ArcosProhibidos(nueva_regla)← ∅;nodo← NodoDestino(arco_actual);señal_proy← Índice(arco_actual, MásCercano(arco_actual, señal));si señal_proy ≥ Longitud(arco_actual) entonces

señal_proy← Longitud(arco_actual) − 10m;fin si

para cada arco en ArcosSalientes(nodo) hacerα← Ángulo(Proyección(arco_actual, señal_proy), nodo,Proyección(arco, Índice(arco, 10m)));

si Tipo(señal) es R-302 entonces α← α − 90◦ ;sinó, si Tipo(señal) es R-303 entonces α← α + 90◦ ;

puntuación_actual← 60 − abs(α);si puntuación_actual > Puntuación(nueva_regla) entonces

Puntuación(nueva_regla)← puntuación_actual;ArcosProhibidos(nueva_regla)← {arco };

fin sifin para cada

devolver nueva_regla;

4.3. Algoritmo general 23

Para este tipo de reglas también interesa asociar el arco donde se origina, yaque un giro prohibido siempre implica un origen y un destino, al contrarioque una dirección prohibida. Si la señal es un giro prohibido a la derecha seresta 90◦ a α para el cálculo de la puntuación. Si es un giro prohibido a laizquierda, se deberá sumar. Esta vez la posición de la señal se utiliza paraelegir un punto del arco actual, mientras que del candidato a arco prohibidose toma siempre su décimo metro para el cálculo de α.

Dirección Obligatoria

Una dirección obligatoria se puede ver como varias direcciones prohibidas,una por cada calle saliente de la intersección, con excepción de lacorrespondiente a la dirección obligatoria. Es por este motivo que en la reglagenerada en el Algoritmo 7 también se establecen arcos prohibidos. Tenertemporalmente esta redundancia de información simplifica la resolución deNavegaciónProhibida del Algoritmo 15 y también la posterior escrituraen ciertos modelos de datos.

Algoritmo 7: MejorDirecciónObligatoriaentrada: señal, nodosalida : nueva_regla derivada de señal desde nodo

Puntuación(nueva_regla)← −∞;ArcosProhibidos(nueva_regla)← ∅;ArcoDestino(nueva_regla)← ∅;

para cada arco en ArcosSalientes(nodo) hacerα← Ángulo(nodo, señal, Proyección(arco, Índice(arco, 10m)));si Tipo(señal) es R-400a entonces α← α − 90◦ ;sinó, si Tipo(señal) es R-400b entonces α← α + 90◦ ;/* En caso de R-400c no se debe ajustar */

puntuación_actual← 90 − abs(α);si puntuación_actual > Puntuación(nueva_regla) entonces

Puntuación(nueva_regla)← puntuación_actual;ArcoDestino(nueva_regla)← arco;ArcosProhibidos(nueva_regla)←ArcosSalientes(nodo) − {arco };

fin sifin para cada

devolver nueva_regla;

Es interesante señalar que a diferencia de otros algoritmos similares, enel Algoritmo 7 se calcula α como el ángulo formado por los vectoresseñal-nodo y señal-arco. Se cree que es la mejor aproximación parainterpretar este tipo de señales a partir de la información disponible y sinrecurrir a heurísticas más complejas.

5En la implementación realmente se guarda la marca de prohibido como atributo delpropio arco

24 Capítulo 4. Navigational Rule Derivation

Giro Obligatorio

La derivación de la regla en el Algoritmo 8 se puede ver como un crucede las ideas usadas en los Algoritmos 6 y 7, siendo por tanto muy similara ambos. Se deriva una regla de giro obligatorio que aplica al tramo másperpendicular al actual, en la dirección apropiada, y se considera que existeun giro prohibido a todos los demás tramos.

Algoritmo 8: MejorGiroObligatorioentrada: señal, arco_actualsalida : nueva_regla derivada de señal desde arco_actual

Puntuación(nueva_regla)← −∞;ArcoOrigen(nueva_regla)← arco_actual;ArcoDestino(nueva_regla)← ∅;ArcosProhibidos(nueva_regla)← ∅;nodo← NodoDestino(arco_actual);señal_proy← Índice(arco_actual, MásCercano(arco_actual, señal));si señal_proy ≥ Longitud(arco_actual) entonces

señal_proy← Longitud(arco_actual) − 10m;fin si

para cada arco en ArcosSalientes(nodo) hacerα← Ángulo(Proyección(arco_actual, señal_proy), nodo,Proyección(arco, Índice(arco, 10m)));

si Tipo(señal) es R-400d entonces α← α − 90◦ ;sinó, si Tipo(señal) es R-400e entonces α← α + 90◦ ;

puntuación_actual← 60 − abs(α);si puntuación_actual > Puntuación(nueva_regla) entonces

Puntuación(nueva_regla)← puntuación_actual;ArcoDestino(nueva_regla)← arco;ArcosProhibidos(nueva_regla)←ArcosSalientes(nodo) − {arco };

fin sifin para cada

devolver nueva_regla;

4.4. Casos problemáticos

A continuación se hablará de los problemas más comunes que se presentancuando el NRD es utilizado en un caso real. Cada problema se acompañaráde la solución propuesta, o de una breve discusión en caso de noencontrarse solución clara.

4.4.1. Detección duplicada

En la Figura 4.2 se puede apreciar una situación donde una señal, en estecaso de dirección prohibida, sería detectada desde dos iteraciones distintas

4.4. Casos problemáticos 25

FIGURA 4.2: Ejemplo de señal que sería detectada yanalizada de forma independiente desde dos puntos de

intersección

del NRD, generando dos reglas diferentes en cada caso.

Por este motivo se usa el procedimiento descrito en el Algoritmo 9 cadavez que se quiere añadir una nueva regla a la colección final. Dado queuna señal sólo debería generar una regla, se asocia la nueva regla a la señaldesde la que fue derivada. Al tener también una puntuación asociada acada regla, éstas pueden ser comparadas entre ellas, de forma que si unaseñal tenía ya una regla asociada, la nueva sólo reemplaza a la antigua si supuntuación es mayor.

En caso de que no hubiera una regla asociada anteriormente, tambiénse aplica un umbral mínimo que obliga a que la nueva regla tenga unapuntuación positiva. Gracias a esto se evita devolver reglas espúreascuando no hay buenos arcos candidatos, debido probablemente a algunode los problemas que se mencionan en las siguientes secciones. Tambiénes importante controlar el caso en el que se sustituye una regla que teníaprohibida la navegación a unos arcos por los que nunca se ha navegadoantes. En ese caso se debe garantizar que el arco que estaba prohibido seavisitado en algún momento, así que se añade a la frontera.

Por tanto, con la solución planteada en el Algoritmo 9, una vez que hayansido visitados ambos nodos en el ejemplo de la Figura 4.2, la colección finalde reglas acabaría teniendo sólo la regla de dirección prohibida aplicada alarco inferior, que tendría una mayor puntuación debido a que la señal estásituada a su derecha.

4.4.2. Reglas contradictorias

Mientras que en la Sección 4.4.1 se muestra la solución para reglasgeneradas de una misma señal, todavía existe un problema cuando hay dosreglas generadas de señales diferentes que se contradicen entre sí. Aunque

26 Capítulo 4. Navigational Rule Derivation

Algoritmo 9: AñadirReglaentrada: reglas, señal, nueva_regla, fronterasalida : reglas con nueva_regla si no existía antes una regla con mayor

puntuación para señal

puntuación_mínima← 0;

si ∃Regla(señal) entoncesvieja_regla← Regla(señal);puntuación_mínima← Puntuación(vieja_regla);si Puntuación(nueva_regla) > puntuación_mínima entonces

reglas← reglas − {vieja_regla };

para cada arco en ArcosProhibidos(vieja_regla) hacersi no ArcoVisitado(arco) y noNavegaciónProhibida(arco_actual, arco, reglas)entoncesArcoVisitado(arco)← Sí;Encolar(frontera, arco);

fin sifin para cada

fin sifin si

si Puntuación(nueva_regla) > puntuación_mínima entoncesRegla(señal)← nueva_regla;reglas← reglas ∪ {nueva_regla };

fin si

devolver reglas;

4.4. Casos problemáticos 27

no se haya encontrado tal caso en los experimentos, es esperable que sepresente al usar el NRD sobre mayores conjuntos de datos.

No obstante, es complicado encontrar una respuesta genérica adecuadapara este caso. Con la información disponible y la derivada, el NRD podríahacer que una regla prevalezca sobre otra por su puntuación, pero estaopción podría no ser la adecuada, bien por un fallo del algoritmo, porquelos datos sobre los que se trabaja estén incorrectos o incompletos o inclusoporque pudiera existir tal contradicción en el mundo real, en cuyo caso lasolución queda al margen de las capacidades del NRD.

La mejor aproximación, por tanto, podría ser tener un mecanismo dedetección para estos casos que notifique al usuario cuando se produce. Si lainteractividad es una opción razonable, permitirle conservar ambas reglas,suprimir una o examinar la situación. En otro caso, escribir ambas reglas.

4.4.3. Modelo sobresimplificado

El modelo con las limitaciones impuestas en la Sección 3.2 no es adecuadopara tratar con la complejidad que se puede esperar en un entorno real,donde se debe tener en cuenta información adicional del mundo:

Carriles que forman las carreteras. Algunas reglas de tráfico sólo seaplican a determinados carriles, y en el cálculo de rutas es habitualindicar el carril por el que se debe conducir.

Coordenadas tridimensionales tanto para la red de carreteras comopara las señales, o alguna otra información que permita separarlos elementos por niveles de altura. De otra forma, es esperableencontrarse con señales detectadas indebidamente donde existanpuentes o túneles.

Señalización horizontal, que puede complementar o sustituir lainformación aportada por las señales verticales que se utilizan en elNRD. En algunos casos, también aportan información para la que noexisten señales verticales, como los tramos en los que se puede darmedia vuelta.

Información de visibilidad, destacando los edificios que puedenobstaculizar la visualización de una señal desde determinados puntoso incluso aportar información útil para decidir la regla que se genera.

Mientras no se disponga de esta información adicional y no se prepareel NRD para manejarla, existirán casos como el que se puede ver en laFigura 4.3, donde la señal está colocada de forma inusual a la izquierda de lacalle a la que se aplica, pero no induce a confusión a un conductor humanoal disponer de la información que proporciona la fotografía (edificio, cochesaparcados, etc. . . ).

4.4.4. Calidad de los datos

Ninguna metodología de reconocimiento de señales de tráfico en carreterases perfecta, por lo que no se puede contar con disponer de datos

28 Capítulo 4. Navigational Rule Derivation

FIGURA 4.3: Ejemplo de un caso problemático que nose puede resolver adecuadamente con la información

disponible6

correctos de todas las señales. Esto puede provocar que falten reglaspor derivar o, menos frecuentemente, que se deriven reglas incorrectas.Desafortunadamente, incluso si se proporcionara una representaciónperfectamente fiel de las señales existentes en un determinado instante, lared de carreteras sobre la que se trabaja seguramente pertenezca a una fechadiferente, o podría estar incompleta ella misma. Mientras que se puedenimplementar mecanismos en el NRD para facilitar la revisión manual y laactualización de los datos, su eficacia depende en última instancia de lasfuentes de información y de la diligencia de los usuarios.

4.5. Otras aproximaciones

El diseño del algoritmo que se ha presentado en la Sección 4.3 es elresultado de un largo proceso de pruebas y refinamiento de multitudde ideas para maximizar la eficacia manteniendo la menor complejidadposible, ya que esto último facilitará su posterior adaptación y extensión.A continuación se hablará de las principales alternativas que se habíanconsiderado y finalmente descartado.

4.5.1. Análisis sin navegación

En una de las primeras aproximaciones que se habían considerado, se habíaintentado derivar reglas de señales analizando cada señal y las calles quela rodean, sin simular una navegación. Se asumía que las calles afectadaspor una regla se encontraban a una distancia máxima de la señal quela generaba, lo que llevó a proyectar conos de búsqueda de la señal yconsiderar las calles que intersecaban con esos conos. Para una señal R-101se proyectaba un cono de búsqueda hacia la dirección opuesta de la señal.

6Fuente: Google Street View

4.5. Otras aproximaciones 29

FIGURA 4.4: Aproximación con análisis por señales, sinsimular una navegación

Para una señal R-303 se proyectaba un cono en la misma dirección y otro a90◦. Existían dos problemas principales con esta aproximación:

La premisa de que las calles afectadas deben estar cerca de una señales falsa, sobre todo para las señales que se detectan a lo largo deuna calle, como las de giro prohibido. Ampliar el radio de búsquedasupondría tener más posibles calles candidatas y aumentaría el riesgode derivar una regla incorrecta.

Al no tener en cuenta la conectividad de la red, se consideraban callesque no debían ser consideradas. En el ejemplo de la Figura 4.4, sederivaría una regla de giro prohibido hacia la calle que se encuentrainconexa, ya que tiene preferencia según cualquier criterio basado enla geometría (más cerca de la señal, supone un giro más perpendiculary más cerrado, etc. . . ).

Al no encontrar una solución fácil para estos problemas, se decidió apostaren su lugar por alternativas basadas en explorar la conectividad de la redde carreteras y simular una navegación.

4.5.2. Detección y análisis por arcos

Los primeros algoritmos basados en la navegación se diseñaban siguiendootra falsa premisa: la de que un conductor humano se fijaba primero enlas calles que existen y después buscaba las señales que le podrían prohibiresa navegación. Por tanto, en estas versiones se seguían proyectando conos,esta vez considerados como conos de visión, desde un nodo de intersecciónhacia cada uno de los arcos salientes. Se creía que si el cono se hacía losuficientemente ancho, las señales que se refieren a él quedarían dentrode ese cono y se podrían analizar sólo considerando ese arco. Esto no eracierto con señales como las del giro prohibido, pero se trataba de paliarproyectando más conos de visión en un punto del arco actual, antes dellegar a la intersección.

30 Capítulo 4. Navigational Rule Derivation

La complejidad de esta aproximación se incrementó gradualmentegradualmente para cubrir cada vez más casos, pero finalmente fuereconocida como poco práctica cuando se quisieron soportar señales comola R-400a, que no tenía por qué estar en ningún sentido cerca del arco al quesu regla afecta. La proyección de los conos fue generalizada y sustituida poruna fase de detección donde se buscan todas las señales, tanto a lo largo deltramo actual como en un radio alrededor del nodo de destino, tal y comose hace en el NRD actual.

31

Capítulo 5

Trabajo experimental

5.1. Entorno de pruebas

Para validar el correcto funcionamiento del algoritmo se ha seleccionadopara un entorno de pruebas la parte antigua de la ciudad de Ávila. Se tratade una sección rodeada de murallas, con seis puertas, fácilmente aislabledel resto de la ciudad. Además, las calles interiores carecen de rotondasy de carriles adicionales, teniendo un máximo de un carril por dirección.Esto hace que sea perfecto para probar los conceptos desarrollados en estaversión del NRD, sin introducir demasiadas complicaciones que todavía nose contemplan.

En total, consiste de 486 tramos de calles, con 243 señales detectadas. Enla Figura 5.1 se proporciona una vista cartográfica de todas las señalesdisponibles. Nótese que solamente se trabaja con señales dentro de lamuralla. Se dispone también de la señalización correspondiente a lasrotondas que ese encuentran fuera de la muralla, pero estas señales sonignoradas, y las rotondas son marcadas como calles de dos sentidos.

Las señales se habían obtenido mediante la metodología propuesta en(Riveiro et al., 2016), que está brevemente descrita en la Sección 2.1. Porproblemas técnicos, no se han podido utilizar técnicas LIDAR para extraertambién información de las calles navegables, así que se había usadola red extraída de OSM. En muchos casos, las calles extraídas de OSMtienen también asociada información sobre las direcciones prohibidas en

FIGURA 5.1: (izq.) Parte amurallada de Ávila con las callesnavegables marcadas en negro.

(der.) Colección de señales en la parte amurallada,coloreadas según sus tipos.

32 Capítulo 5. Trabajo experimental

Tipo de regla Reglas derivadas Reglas incorrectas PrecisiónDir. prohibidas 35 4 88.57 %Giros prohibidos 32 1 96.88 %

TABLA 5.1: Precisión de las reglas de tráfico derivadas porel NRD, según su tipo.

las calles, permitiendo así validar el NRD y dar una medida de su eficacia.Desafortunadamente, no existían reglas de giros prohibidos en OSM paraÁvila, y muchos giros prohibidos estaban marcados indebidamente comodirecciones prohibidas, lo que complicaba la validación. Se ha optado ensu lugar por hacer una inspección manual de cada regla de giro prohibidoderivada.

5.2. Resultados obtenidos

Para facilitar la validación contra los datos de OSM, se han generadolas reglas de direcciones obligatorias como direcciones prohibidas, ygiros obligatorios como giros prohibidos respectivamente, siguiendo lasequivalencias descritas a lo largo de la Sección 4.3.3.

En la Tabla 5.1 se muestra el número de reglas derivadas de cada tipo ysu precisión. Es complicado estimar cuántas reglas deberían haber sidoobtenidas en total, ya que eso depende en gran medida de la calidad ycoherencia de los datos disponibles. Por tanto, no se ha tratado de medirla cobertura o “recall” de las reglas. Como curiosidad, se detectaron 5instancias de direcciones prohibidas marcadas de forma incorrecta en OSMdebido bien a un error humano o bien a la falta de actualización. Se haprocedido a corregir cada uno de estos casos antes de volver a sacar losresultados.

Estos experimentos sirven como una prueba de concepto para losalgoritmos desarrollados, demostrando que se pueden obtenerbuenos resultados sin recurrir a heurísticas complejas para imitar elcomportamiento humano real. En el futuro se espera realizar experimentossobre mayores conjuntos de datos‘ para dar una mejor medida de laversatilidad del algoritmo, así como de su rendimiento espacial y temporal.

33

Capítulo 6

Metodología de desarrollo deSoftware

Se ha decidido adoptar la metodología Scrum (Schwaber y Beedle, 2002)para este proyecto de investigación. Se trata de una metodología ágilpensada para adaptarse en la medida de lo posible a los problemas realesque se encuentran durante el desarrollo del Software, como los constantescambios impredecibles o la poca fiabilidad de las estimaciones a largoplazo. Sin embargo, dado a la naturaleza del proyecto, se han debidoconsiderar dos principales adaptaciones a la metodología:

Mientras que Scrum es una metodología para el trabajo en equipo,todo el trabajo relacionado directamente con el proyecto se harealizado de forma individual. Esto implica también que el DailyScrum no se ha podido realizar.

En ningún momento ha existido un Product Backlog, tan sólo unobjetivo abstracto para el proyecto. Al tratarse de un proyecto deinvestigación, los requisitos eran formulados de forma dinámica,adaptándose a las posibilidades.

Teniendo en consideración estas adaptaciones, la planificación se realizó anivel de sprint. Mientras que la primera y la última fase no podían tratarsecomo sprint debido a que no se podían restringir a un bloque de tiempofijo ni terminaban en un producto entregable, las dos aproximacionesdiscutidas en la Sección 4.5, al igual que el propio NRD, se desarrollaronen tres sprints con una duración de tres semanas cada uno. Al final de cadasprint se llevaba a cabo una reunión de Sprint Review con el director delproyecto para revisar el trabajo completado y definir los objetivos para elnuevo sprint.

En un proyecto de investigación en el que existe un objetivo abstracto enlugar de unos requisitos precisos parece más evidente que la necesidadde roles es menor. Es también complicado separar las tareas según lashabilidades requeridas. Si se tratara de repartir el trabajo entre los rolesde un Data Scientist para obtener y procesar los datos de entrada, un DBApara la integración en una base de datos y un investigador, uno se daríacuenta de que se requiere compartir el mismo conocimiento entre los tresroles para resolver cada tarea según las necesidades del proyecto.

Se necesitaron un total de 65.75 días para la realización del proyecto, que serepartieron en 3 meses como se detalla en la siguientes secciones. También

34 Capítulo 6. Metodología de desarrollo de Software

FIGURA 6.1: Fase inicial: investigación y obtención de datos

se puede encontrar un diagrama de Gantt completo en el Apéndice B. Altener que compartir el tiempo dedicado al proyecto con otras tareas norelacionadas (estudios, otros proyectos, etc. . . ), se dedicaban habitualmente4 horas en cada día laborable, con algunas variaciones dependiendo defactores externos. Por este motivo, se ha considerado más informativomedir la duración de las tareas en días en lugar de horas. Para elcálculo del presupuesto ha sido complicado encontrar información sobreel salario medio de un investigador especializado en Computación enEspaña, debido probablemente a la poca demanda existente. Por tanto, elpresupuesto se puede calcular teniendo en cuenta el salario medio de uningeniero Software, que corresponde aproximadamente a 14.90 AC la hora1:

65,75 dıas× 4 horas/dıa× 14,90 AC/hora = 3918,70 AC

6.1. Fase inicial

En las primeras dos semanas la preocupación principal era evaluar lausabilidad de los datos disponibles, tanto de la red de calles como de lasseñales. Mientras que se esperaba poder usar los datos obtenidos mediantetécnicas LIDAR desde el principio, éstos resultaron ser inadecuadosen un principio. La orientación de las señales estaba mal calculada,mientras que en las intersecciones existían “huecos” de hasta 10 metroso más, imposibles de detectar automáticamente de forma fiable. Además,se trataba simplemente de una proyección en dos dimensiones de lascalles, obligando a considerar como punto de intersección todo puntodonde dos calles (líneas) se cruzaban. Esto no se corresponde con larealidad y se necesitaba una cartografía donde las intersecciones quedarancorrectamente indicadas.

Es por este motivo que, como se puede ver en la Figura 6.1, gran parte delesfuerzo inicial fue dedicado a las herramientas para explotar e integrar los

1https://www.glassdoor.com/Salaries/spain-software-engineer-salary-SRCH_IL.0,5_IN219_KO6,23.htm

6.2. Primera aproximación 35

FIGURA 6.2: Primer sprint: aproximación 1

datos de OSM, ya que éstos sí disponían de una red de calles que podía serútil.

6.2. Primera aproximación

Las primeras ideas consideraban la posibilidad de trabajar con una redde calles que no fuera transformable a un grafo navegable, por lo queen este sprint se desarrolló el prototipo sin navegabilidad descrito en laSección 4.5.1. En la Figura 6.2 se muestran las tareas asociadas a este sprint,donde se empezó por la creación de señales sintéticas (marcando sobre unmapa a partir del conocimiento propio y de las fotografías de Google StreetView). Estas señales fueron muy útiles para poder realizar pruebas tantosobre ésta aproximación como la siguiente. También se puede destacar quea partir de este sprint se empezó a dedicar un importante tiempo al estudiode las señales de tráfico y a su interpretación por parte de los conductoreshumanos.

Al tratarse de un prototipo para evaluar la viabilidad del proyecto,no se utilizaba ningún lenguaje de programación tradicional. Todos losalgoritmos necesarios eran implementados en PL/pgSQL sobre una basede datos de PostGIS. Al final del sprint la aproximación fue consideradapoco viable por los motivos expuestos en la Sección 4.5.1, y el prototipo fueabandonado.

36 Capítulo 6. Metodología de desarrollo de Software

FIGURA 6.3: Segundo sprint: aproximación 2

6.3. Segunda aproximación

En el siguiente sprint, que se puede observar en la Figura 6.3, se empezópor investigar sobre tecnologías Java para la integración de los datosdisponibles desde las tablas PostGIS, y el desarrollo de una representaciónen grafo conveniente para poder navegar por la red de calles de OSM.

El producto de esta aproximación con navegabilidad se detalla en laSección 4.5.2, al igual que las razones por las que también fue abandonadaal final del sprint. Sin embargo, el resultado del desarrollo de este sprint nofue completamente descartado, ya que se pudieron reutilizar partes e ideaspara la siguiente aproximación.

6.4. Tercera aproximación

En lugar de empezar este sprint inmediatamente tras haber terminadoel anterior, se decidió esperar hasta tener los datos reales de las señalesde tráfico, esta vez actualizados y de una calidad aceptable. Se puedecomprobar en la Figura 6.4 que la espera supuso una semana en la queno se dedicó esfuerzo en el proyecto.

Los nuevos datos de las señales fueron tratados para suprimir errorespuntuales como señales duplicadas. Al final del sprint se diseñó ydesarrolló el NRD final, con fase de detección y análisis.

6.5. Trabajo experimental

Habiendo terminado el NRD, se consideró necesario validar sufuncionamiento en un entorno real para dar medidas de su eficacia. Lasúltimas dos semanas, reflejadas en la Figura 6.5, fueron dedicadas en gran

6.5. Trabajo experimental 37

FIGURA 6.4: Tercer sprint: aproximación 3

FIGURA 6.5: Fase final: trabajo experimental

parte a la selección del entorno de pruebas y a la evaluación del NRD,ambas partes explicadas en el Capítulo 5.

Estas últimas tareas llevaron más tiempo del esperado, ya que la calidad delos datos de OSM no era la suficiente y se tuvo que comprobar cada casomanualmente, corrigiendo los datos de OSM donde fuera necesario.

39

Capítulo 7

Conclusiones

7.1. Desarrollo futuro

A partir de este punto, existen muchas posibles extensiones y mejoraspara el NRD para mejorar el procesamiento de las señales en algunoscasos complicados y para soportar tipos de señales más variados, comolas rotondas y los límites de velocidad. Cuando los conductores humanosven un límite de velocidad, recuerdan ese límite hasta que alcanzan algúnpunto donde es anulado, como podría ser una señal de ceda al pasou otro límite de velocidad. Esta idea se puede incorporar fácilmente alNRD introduciendo el concepto de estado, que se transfiere durante lanavegación, pudiendo así marcar cada arco con un límite de velocidad amedida que es visitado.

Una aplicación real necesitaría también trabajar en un nivel superior decomplejidad que el restringido en la Sección 3.2. Hace falta informaciónen tres dimensiones de las señales y carreteras, para distinguir cuándo unaseñal está a una altura razonable y evitar generar reglas sobre un puentea partir de señales que están situadas debajo de él. Es necesario soportarmúltiples carriles y señales horizontales, para complementar o verificar lasreglas que se derivan de las señales verticales. Una geometría simplificadade los edificios que rodean las calles también sería de mucha ayuda parapoder encontrar correctamente las calles a las que afecta una regla. Todasestas mejoras requieren de datos que resultaron ser complejos de conseguire incorporar, pero se espera poder disponer de ellos en algún futuro.

Si se dispusiera de información sobre un gran conjunto de trayectoriasreales sobre una red, ésta podría ser analizada para detectar giros quenunca son tomados, velocidad media por tramo, y mucha informaciónútil con la que se podría derivar reglas sin necesidad de analizar lasseñales de tráfico. Incluso un conjunto de millones de trayectorias sobreuna ciudad grande se podría manejar eficientemente en memoria con unarepresentación compacta, adaptando por ejemplo el Compressed SuffixArray (CSA) (Sadakane, 2003).

7.2. Revisión del trabajo

Se ha presentado un primer escalón para un problema complejo, y unaprueba de concepto válida para los algoritmos de derivación de reglas

40 Capítulo 7. Conclusiones

de tráfico basados en la simulación de un conductor virtual. A pesar delas restricciones del tiempo para el proyecto y de la poca cantidad deinformación disponible, se ha propuesto un algoritmo que es fácilmenteextensible y versátil para poder ser usado en entornos más complejos yrealistas, adaptándose a las necesidades propias de cada organización.

Se cree que es técnica y económicamente viable construir una plataformabasada en algoritmos similares para agilizar en gran medida el etiquetadode las reglas de tráfico, ahorrando costes de producción para los mapasusados en sistemas de navegación.

41

Apéndice A

Diseño de la aplicación

A.1. Selección de tecnologías

Tras haber considerado varias alternativas, se ha elegido desarrollar laaplicación en el lenguaje Java y su ecosistema asociado, ya que se trata deuno de los lenguajes más ampliamente usados, siendo sencillo encontrarcomponentes ya desarrollados para muchas tareas y documentaciónasociada.

Tras los procedimientos explicados en la Sección 4.2, existe una tablade PostGIS que contiene información sobre los arcos y otra tabla coninformación sobre las señales disponibles. Para construir un grafo y uníndice espacial para las señales, es necesario leer ambas tablas en memoria.Hibernate 51 proporciona muchas facilidades para esto, siempre ycuando se hayan configurado correctamente las clases para ser manejadaspor el ORM. Además, Hibernate 5 está preparado para trabajar condatos espaciales con el módulo Hibernate Spatial y la librería JTS.

A.2. Diagrama de clases

A continuación se describirán las clases principales que suponen laimplementación del NRD, así como las relaciones que existen entreellas. Es importante destacar que la implementación pasó por numerososcambios estructurales en muy rápida sucesión, en los que no era posiblecontar con tener código que fuera siempre reusable, ya que incluso lastecnologías usadas podían cambiar en cualquier momento. Por tanto, losobjetivos principales del diseño de las clases era su facilidad de manejoy reutilización en contextos diferentes. Por este motivo se han tomadodecisiones de diseño que no se consideran estándar en este lenguaje,como tener atributos públicos en lugar de usar setters y getters sin lógicapropia. El principal propósito de esta sección es proporcionar algunadocumentación para que un desarrollador sea capaz de entender mejor elcódigo y de hacer cambios. Si se alcanza cierta estabilidad en una versiónfutura, sería conveniente realizar varias refactorizaciones sobre el diseño declases.

1http://hibernate.org/orm/documentation/5.0/

42 Apéndice A. Diseño de la aplicación

FIGURA A.1: Clases del modelo para señales y reglas detráfico

En primer lugar, se han implementado las reglas de tráfico que se puedenver en la Figura A.1:

BannedEdge es una dirección prohibida, en la que se marca un arcoentero como prohibido.

TurnRestriction es un giro prohibido, con un arco de origen y un arcode destino.

OneTurn es un giro obligatorio, con un arco de origen y un arco dedestino.

OneWay es una dirección obligatoria. En la Sección 4.3.3 se explicaque una dirección obligatoria equivale a una colección de direccionesprohibidas. Para nuestra aplicación se considera más práctica estasegunda representación, y por este motivo simplemente se guarda elconjunto de arcos por los que no se debe navegar.

Cada regla tiene el método breakDown, que descompone la regla actualen otras reglas más simples: OneTurn se descompone en una colecciónde reglas TurnRestriction y OneWay se descompone en una colecciónde reglas BannedEdge. TurnRestriction y BannedEdge no se puedendescomponer más, por lo que devuelven una colección Singleton con ellasmismas.

Inspirándose en el patrón Active Record descrito en (Fowler, 2002), se haconsiderado interesante delegar la lógica de escritura a cada regla, que serealiza en el método writeRule.

Una señal de tráfico es representada por la clase TrafficSign, queestá diseñada para ser mapeada2 con una tabla de PostGIS medianteHibernate. Aparte de un identificador y de los campos de tipo, posicióny azimut, puede estar asociada a una regla de tráfico con una puntuación,necesario para la implementación del Algoritmo 9.

2Todo informático es capaz de entender este término, y no se han encontrado palabrasen castellano para sustituirlo. “Asignación de corresponencias” no es una palabra.

A.2. Diagrama de clases 43

FIGURA A.2: Clases del modelo para la red de carreteras

En la Figura A.2 se presenta el modelado para el grafo de carreteras,formado por arcos y nodos.

La clase Edge, como TrafficSign, también fue diseñada tanto para sermapeada mediante Hibernate, pero también para su fácil manejo tantocomo componente de una estructura de grafo como objeto geográfico.Además de los atributos esperables para almacenar la geometría del tramoque representa (en forma de línea), su nodo de inicio y su nodo de fin,tiene un flag llamado banned, utilizado como atajo para marcar un arcoprohibido para la navegación. Dispone así mismo de un constructor auxiliarpara definir un arco inverso a partir de otro y de un método para devolveruna versión indexada por longitud de su geometría, como se exige enmuchos casos de la Sección 4.3.

La clase Node hereda de una clase de JTS pensada para tal fin, por lo quetiene los métodos y atributos necesarios para proporcionar coordenadas deposición y una colección con los arcos salientes del nodo.

Por último, la clase Graph incorpora dos índices: un simple índice de todoslos arcos por sus identificadores y un índice espacial para las señales. Lacolección de señales también se almacena en un HashMap en lugar de unHashSet porque la segunda clase no permite fácilmente obtener el objetooriginal de la colección a partir de una copia “igual”, operación que podríaresultar útil para algunos casos.

En la Figura A.3 (derecha) se puede ver la clase encargada de construirel grafo en memoria. Como su nombre indica, utiliza Hibernate paraleer las tablas necesarias. La escritura de las reglas generadas deberáser en el formato adecuado a las necesidades del usuario, aunquese proporciona una clase de ejemplo llamada PSQLRuleWriter, de laFigura A.3 (izquierda), que utiliza un modelo de datos ad-hoc y puede servirde referencia para futuras implementaciones.

Las implementaciones de los algoritmos que detallaron en la Sección 4.3se encuentran en las clases de la Figura A.4. BreadthFirstNavigator, comosu nombre sugiere, tiene un método para navegar un grafo por anchuray utiliza dos detectores: uno para señales a lo largo del arco y otro paralos nodos. La fase de análisis se realiza enteramente en el propio métodonavigate.

44 Apéndice A. Diseño de la aplicación

FIGURA A.3: Clases de lectura y escritura con Hibernate

FIGURA A.4: Clases de navegación, detección y análisis delNRD

A.2. Diagrama de clases 45

FIGURA A.5: Clases para los dos tipos de detectores que seutilizan

Para suplir las necesidades de los dos detectores, existen dosimplementaciones de SignDetector, como se muestra en la Figura A.5.Ambos son inicializados con el grafo sobre el que se quiere trabajar y conlos tipos de señales que se quieren capturar, mediante argumentos variablesen el constructor (String...). Los detectores difieren en su funcionamientoy en los argumentos que se esperan en su método detect. CircleDetectorimplementa el Algoritmo 2, para lo que necesita las coordenadas del nodoy el radio de búsqueda, habitualmente de 15 metros. DistanceDetector,por otra parte, implementa el Algoritmo 3, necesitando el arco sobre el quebuscar y pudiendo ser parametrizado con la distancia de búsqueda y ladistancia del retroceso, por defecto 10 metros para ambas.

Para la implementación de los detectores se ha decidido usar el patrónpuente (Gamma et al., 1995), donde la implementación de un detector seconstruye mediante una aplicación secuencial de clases implementadoras,en este caso llamadas filtros, que aparecen en la Figura A.6. La únicafunción de un filtro al ser aplicada sobre un conjunto de señales es devolverun subconjunto de estas señales que cumplen una cierta condición. Para losdetectores del NRD se usan cuatro filtros:

SignsOfInterestFilter: Conserva sólo aquellas señales cuyo tipo seencuentra dentro de los tipos especificados.

DistanceFilter: Conserva sólo aquellas señales que se encuentran auna distancia máxima de un objeto geográfico concreto, como unpunto o una línea.

LookAtMeFilter: Conserva sólo aquellas señales que están orientadaspara poder ser vistas desde un punto especificado.

AlongTheRoadFilter: Conserva sólo aquellas señales que pueden servistas a lo largo de una carretera. En cierta medida es parecido al filtroanterior, sólo que éste encuentra el punto de vista de referencia deforma automática.

La idea en ambos detectores es obtener primero un conjunto inicial deseñales candidatas3, que después se refinan aplicando los siguientes filtros:

3La implementación del R-Tree usada sólo permite hacer consultas sobre una regiónrectangular, por lo que se debe refinar posteriormente si, por ejemplo, se quiere una regióncircular

46 Apéndice A. Diseño de la aplicación

FIGURA A.6: Clases para los filtros usados por losdetectores

FIGURA A.7: Diagrama de secuencia

Para el CircleDetector: SignsOfInterestFilter, DistanceFilter yLookAtMeFilter.

Para el DistanceDetector: SignsOfInterestFilter, DistanceFiltery AlongTheRoadFilter.

A.3. Diagrama de secuencia

Se puede ver un diagrama de secuencia en la Figura A.7, que muestrauna iteración normal del NRD. El grafo es construido a partir de los datosde las tablas de arcos y señales, y el algoritmo de navegación es llamadosobre él. En este algoritmo se aplican los dos detectores para cada uno delos arcos navegados, que después se analizan dentro del propio métodode navegación. Las reglas resultantes finalmente se escriben mediante laimplementación de PSQLRuleWriter, que delega la estructura a las propiasreglas, como se explica en la Seccion A.2.

47

Apéndice B

Diagrama de Gantt completo

49

Apéndice C

Glosario de acrónimos

NRD Navigational Rule Derivation

OSM OpenStreetMap

JTS Java Topology Suite

LIDAR Light Imaging, Detection And Ranging

GNSS Global Navigation Satellite System

CSA Compressed Suffix Array

INS Inertial Navigation System

XML Extensible Markup Language

API Application Programming Interface

GIS Geographic Information System

DBMS Database Management System

SQL Structured Query Language

OGC Open Geospatial Consortium

UTM Universal Transverse Mercator

WMS Web Map Service

WFS Web Feature Service

MBR Minimum Bounding Rectangle

ORM Object Relational Mapping

DBA Database Administrator

51

Bibliografía

Arnoul, P et al. (1996). «Traffic signs localisation for highways inventoryfrom a video camera on board a moving collection van». En:Intelligent Vehicles Symposium, 1996., Proceedings of the 1996 IEEE. IEEE,págs. 141-146.

Belton, David y Derek D Lichti (2006). «Classification and segmentation ofterrestrial laser scanner point clouds using local variance information».En: The International Archives of the Photogrammetry, Remote Sensing andSpatial Information Sciences 36.Part 5, págs. 44-49.

Cao, Lili y John Krumm (2009). «From GPS Traces to a Routable Road Map».En: Proceedings of the 17th ACM SIGSPATIAL International Conference onAdvances in Geographic Information Systems. GIS ’09. Seattle, Washington:ACM, págs. 3-12. ISBN: 978-1-60558-649-6. DOI: 10.1145/1653771.1653776. URL: http : / / doi . acm . org / 10 . 1145 / 1653771 .1653776.

Ciresan, Dan et al. (2012). «Multi-column deep neural network for trafficsign classification». En: Neural Networks 32, págs. 333-338.

Delaunay, Boris (1934). «Sur la sphere vide». En: Izv. Akad. Nauk SSSR,Otdelenie Matematicheskii i Estestvennyka Nauk 7.793-800, págs. 1-2.

Ester, Martin et al. (1996). «A density-based algorithm for discoveringclusters in large spatial databases with noise.» En: Kdd. Vol. 96. 34,págs. 226-231.

Foote, Kenneth E y Margaret Lynch (1996). «Geographic informationsystems as an integrating technology: context, concepts, and definitions».En: Austin, University of Texas, págs. 40-44.

Fowler, Martin (2002). Patterns of enterprise application architecture.Addison-Wesley Longman Publishing Co., Inc.

Gamma, Erich et al. (1995). Design patterns. Addison-Wesley.Guttman, Antonin (1984). R-trees: a dynamic index structure for spatial

searching. Vol. 14. 2. ACM.Leutenegger, Scott T, Mario A Lopez y Jeffrey Edgington (1997). «STR: A

simple and efficient algorithm for R-tree packing». En: Data Engineering,1997. Proceedings. 13th International Conference on. IEEE, págs. 497-506.

Maldonado-Bascon, S et al. (2008). «Traffic sign recognition system forinventory purposes». En: Intelligent Vehicles Symposium, 2008 IEEE. IEEE,págs. 590-595.

Mogelmose, Andreas, Mohan Manubhai Trivedi y Thomas B Moeslund(2012). «Vision-based traffic sign detection and analysis for intelligentdriver assistance systems: Perspectives and survey». En: IEEETransactions on Intelligent Transportation Systems 13.4, págs. 1484-1497.

Naroditsky, Oleg, Alexander Patterson y Kostas Daniilidis (2011).«Automatic alignment of a camera with a line scan lidar system». En:Robotics and Automation (ICRA), 2011 IEEE International Conference on.IEEE, págs. 3429-3434.

52 BIBLIOGRAFÍA

Pu, Shi et al. (2011). «Recognizing basic structures from mobile laserscanning data for road inventory studies». En: ISPRS Journal ofPhotogrammetry and Remote Sensing 66.6, S28-S39.

Riveiro, Belén et al. (2016). «Automatic Segmentation and Shape-BasedClassification of Retro-Reflective Traffic Signs from Mobile LiDAR Data».En: IEEE Journal of Selected Topics in Applied Earth Observations and RemoteSensing 9.1, págs. 295-303.

Sadakane, Kunihiko (2003). «New text indexing functionalities of thecompressed suffix arrays». En: Journal of Algorithms 48.2, págs. 294-313.

Scharl, Arno y Klaus Tochtermann (2009). The geospatial web: howgeobrowsers, social software and the Web 2.0 are shaping the network society.Springer Science & Business Media.

Schwaber, K y Mike Beedle (2002). Agilè Software Development with Scrum.Šegvic, Siniša et al. (2010). «A computer vision assisted geoinformation

inventory for traffic infrastructure». En: Intelligent Transportation Systems(ITSC), 2010 13th International IEEE Conference on. IEEE, págs. 66-73.

Snyder, John P (1997). Flattening the earth: two thousand years of mapprojections. University of Chicago Press.

Takagi, Kiyokazu et al. (2006). «Road environment recognition usingon-vehicle LIDAR». En: 2006 IEEE Intelligent Vehicles Symposium. IEEE,págs. 120-125.

Zhou, Lipu y Zhidong Deng (2014). «LIDAR and vision-based real-timetraffic sign detection and recognition algorithm for intelligent vehicle».En: 17th International IEEE Conference on Intelligent Transportation Systems(ITSC). IEEE, págs. 578-583.