localización, planificación de rutas y guiado visual en interiores

Localización, planificación de rutas y guiado visual en interiores

Índice

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

Introducción

GPS exterior ok

Uso extendido y amplio

Problemática

Línea visual de satélites

No permiten la localización en interiores

90% en interiores

Posicionamiento en interiores

Foco de estudio

Sin estos sistemas no hay funcionalidades asociadas a los mismos

Introducción

Problemas encontrados:

Tecnológico Avanzado gracias a estudios

Económico Solucionado Reducción de costes de dispositivos

Eliminados los problemas Desarrollo de funcionalidades!

Principal uso civil de GPS es la navegación

Guiado desde un punto origen a un destino de la mejor manera

Apliquemos esta funcionalidad a interiores…

Introducción

Introducción

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

Objetivos

Plantear solución técnica y funcional para el guiado en interiores

Desarrollo de una solución apta para movilidad

Generación de rutas en servidor remoto y exposición de las mismas mediante servicios

Estudio de rendimiento de algoritmos de enrutado.

Implantación del mejor algoritmo estudiado en el sistema de cálculo de rutas.

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

Estado Actual

Pocos avances en desarrollos funcionales

Enfoque principal técnicas de localización

No existe estándar

Diferentes tecnologías (WiFi, ZigBee…)

Primeras aproximaciones a navegación en interiores:

Nokia: Pionero en investigación y posicionamiento en interior.

Desplegado ensayo en sus sedes y algunos edificios de EEUU y Japón

Google:Incorpora enrutado mediante Google Maps (versión 6.7)

Solo disponible en algunas localizaciones de EEUU y Japón

Proporciona soluciones de valor añadido: Google Offers y Google Business Photos.

Estado Actual

Estado Actual

Referentes en navegación (exteriores)

Tomtom: Sistema de navegación GPS por excelencia. Más reconocido.

Incorpora valor añadido al cálculo de rutas/navegación

Información de radares

Obtención de información de webs (Google, Expedia, Trip Advisor)

Navegación 2.0: Conexión con redes sociales como Twitter

Funcionalidades Live: Conocimiento del estado del tráfico en tiempo real y recalculo de las rutas basándose en este parámetro.

Optimización de rutas

Otro uso interesante del cálculo de rutas.

Enfocado a flotas de transportes

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

Solución Funcional

Desarrollo de 3 componentes que permiten:

App Routing: Aplicación desplegada en servidor que proporciona la información necesaria al dispositivo sobre el mapa en el que se encuentra y calcula la ruta entre dos puntos si se solicita por parte de los clientes. Desarrollo basado en teoría de grafos y cálculo de caminos entre dos nodos.

IndoorGpsNav: Este aplicativo se despliega en un cliente con sistema operativo Android. En esta aplicación se indicaran los parámetros de búsqueda y visualizará la ruta de manera intuitiva.

Mapping: Herramienta de soporte que permite generar información de mapas para su posterior explotación en App Routing. Permite la generación de los caminos de un mapa en concreto y su exportación a fichero apto para el aplicativo de Routing

Solución Funcional

Solución Tecnológica

Solución Tecnológica

App Routing

IndoorGpsNav

Mapping

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

Estudio algoritmos de caminos mínimos

Objetivo: Búsqueda de la mejor ruta Camino más corto

Algoritmos de caminos mínimos sobre los que se aplica el estudio comparativo:

En concreto el estudio consta de:

2 Implementaciones del algoritmo de Dijkstra (Lars Vogel y Ryan Stansifer (Florida IT))

1 Implementación del algoritmo de Bellman-Ford (universidad de Princeton)

1 Implementación del algoritmo de Ford (MIT)

Única fuente origen

Dijkstra

Bellman Ford

Todos los orígenes

Floyd - Warshall

Estudio algoritmos de caminos mínimos

Datos de entrada:

Matrices de adyacencia desde 10x10 hasta 4000x4000

Entorno:

Equipo de escritorio, procesos controlados y máquina virtual java versión 1.6.0_33-b03

Sin alterar los parámetros por defecto de tamaño inicial y máximo de heap.

Ejecución:

En bucle y toma de medidas de tiempo y memoria

Estudio algoritmos de caminos mínimos

Presentación de resultados

Algoritmos “Punto a punto”

Se estudian los tiempos medios de ejecución obteniendo los siguientes resultados:

Estudio algoritmos de caminos mínimos

Presentación de resultados

Algoritmo “Todos contra todos”

Se estudian los tiempos medios de ejecución obteniendo los siguientes resultados:

Estudio algoritmos de caminos mínimos

Conclusiones del estudio:

Algoritmo de Floyd – Warshall es válido para poca densidad de nodos.

Se descartan los datos de memoria por no ser significativos Garbage Collector

Se determina que la implementación que mejor responde es la implementación 1 del algoritmo de Dijkstra (Lars Vogel) Se incorpora al desarrollo del servidor como núcleo del cálculo de rutas.

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

Conclusiones

El desarrollo propuesto cumple con los objetivos identificados al inicio del trabajo.

Se facilita el cálculo de rutas basando el desarrollo en teoría de grafos.

Se determina, de los incluidos en el estudio, la mejor implementación de algoritmo de enrutamiento.

El algoritmo Floyd-Warshall válido pero solo para un número limitado de nodos.

Imposible validar y estudiar de datos de memoria consumida por los algoritmos

Trabajo Futuro

Realizar nuevas implementaciones y ampliar el catálogo de servicios proporcionados por el servidor.

En el apartado de comunicaciones, migrar del protocolo SOAP de comunicación entre servidor y dispositivo móvil a enfoque REST.

Estudiar mecanismos de control y medición de memoria consumida por los algoritmos.

Ampliar el número de implementaciones de los algoritmos y estudiar otros modelos como A* (A-Estrella) o Johnson.

Mejorar la aplicación del dispositivo móvil e integrarla con los sistemas de posicionamiento.

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

DEMO - IndoorGpsNav

DEMO – App Routing Server

DEMO - Mapping

¿Preguntas?

¿Dudas?

Muchas gracias

Localización, planificación de rutas y guiado visual en interiores

Arturo San Feliciano Martín