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

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

Upload: arturo-san-feliciano-martin

Post on 01-Jul-2015

423 views

Category:

Documents


3 download

DESCRIPTION

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

TRANSCRIPT

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

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

Page 2: 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

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

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

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

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

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…

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

Introducción

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

Introducción

Page 8: Localización, planificación de rutas y guiado visual en interiores
Page 9: Localización, planificación de rutas y guiado visual en interiores

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

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.

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

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

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.

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

Estado Actual

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

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

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

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

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

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

Solución Funcional

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

Solución Tecnológica

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

Solución Tecnológica

App Routing

IndoorGpsNav

Mapping

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

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

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

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

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

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

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:

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

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:

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

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.

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

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

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

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

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.

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

• Introducción

• Objetivos

• Estado actual

• Solución Funcional y Tecnológica

• Estudio algoritmos de caminos mínimos

• Conclusiones y trabajo futuro

• Demo

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

DEMO - IndoorGpsNav

Page 31: Localización, planificación de rutas y guiado visual en interiores
Page 32: Localización, planificación de rutas y guiado visual en interiores

DEMO – App Routing Server

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

DEMO - Mapping

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

¿Preguntas?

¿Dudas?

Muchas gracias

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

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

Arturo San Feliciano Martín