localización, planificación de rutas y guiado visual en interiores
DESCRIPTION
Localización, planificación de rutas y guiado visual en interiores.TRANSCRIPT
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