You are here:GeoTux»Geo-Blogs»Razonamiento espacial cualitativo»Cálculo de rutas con razonamiento espacial cualitativo

Estadísticas

Invitados: 41
Usuarios registrados: 3126
Usuarios en línea:
-
Registrados hoy:
-

Registro

Redifusión (RSS)

Blogs y Noticias:
Recibe las actualizaciones en Geo-Noticias y Geo-Blogs

Recibir por e-mail
Recibir Geo-Noticias y Geo-Blogs por e-mail

¿Qué es esto?

Domingo 23 de Octubre de 2011 13:00

Cálculo de rutas con razonamiento espacial cualitativo

Written by  German Carrillo
Rate this item
(1 Vote)

El siguiente es un algoritmo de ejemplo para calcular rutas en una red utilizando únicamente razonamiento espacial cualitativo a través del razonador SparQ y QGIS para visualizar el resultado.

For English click here.

 

Este post es ahora obsoleto pues es la base del artículo 'Navigation with the Dipole Calculus'. Para leer el artículo y ver la presentación asociada, haz click en este enlace.

 

Qualitative Spatial Reasoning for routing

¿Qué es razonamiento espacial cualitativo?

Según (Renz y Nebel, 2007), el razonamiento cualitativo es una aproximación para tratar con conocimiento de "sentido común" sin emplear computación numérica. La principal motivación de esta rama, agregan, es que se considera más cercana a la manera en que los humanos representamos y razonamos acerca de conocimiento de "sentido común". Para ello se representa el conocimiento utilizando vocabularios limitados (como relaciones cualitativas entre entidades) o categorías cualitativas de valores numéricos.

Freksa y Röhrig (1993) establecen que el razonamiento cualitativo es basado en conocimiento comparativo, en lugar de información métrica.

En cuanto al espacio, este tipo de razonamiento involucra relaciones entre entidades espaciales, considerando aspectos como topología, orientación y distancia.

El razonamiento espacial cualitativo es usado en inteligencia artificial, aplicado generalmente en robots y es un campo abierto de investigación en el área de la ciencia cognitiva.

¿Qué es un cálculo espacial cualitativo?

Según en manual de SparQ (pág.7), un cálculo cualitativo consiste de un conjunto de relaciones entre objetos de un determinado dominio y operaciones definidas sobre esas relaciones.

Por ejemplo, el cálculo propuesto por Moratz, Renz y Wolter (2000), el cálculo de dipolos, se basa en relaciones entre pares de segmentos orientados. Dichas relaciones son exhaustivas y mutuamente excluyentes, de tal forma que contienen todo el universo y solo una a la vez puede mantenerse entre un par de objetos (dipolos). Las relaciones definidas en este cálculo son (Fuente: Moratz et al. 2000):

Dipole calculus relations

 

A través de verificaciones de consistencia entre escenarios dados (constraints) puede razonarse descartando situaciones contradictorias y adoptando situaciones posibles. Este enfoque es presentado por los mismos autores (sección 6.) en una pequeña demostración de navegación y constituye la base del presente ejemplo.

¿Qué es SparQ?

SparQ es un framework de razonamiento espacial cualitativo que recopila diversos tipos de cálculo propuestos por la comunidad QSR (Qualitative Spatial Reasoning) como Cardinal Direction Calculus, OPRA, Panorama y Dipole Calculi. Está escrito en C++, tiene licencia GNU GPL y es desarrollado por las universidades de Bremen y Freiburg en Alemania.

Objetivo

El objetivo del ejercicio es partir de una red de dipolos (bordes con nodo de inicio y fin) y obtener una ruta empleando razonamiento espacial cualitativo, específicamente a través de cálculos con dipolos (Dipole Calculi).

El algoritmo

En general, se trata de validar escenarios en los que existe un dipolo actual, un conjunto de dipolos candidatos y un dipolo de llegada:

Escenarios para validar consistencia

 

Si uno de los dipolos candidatos genera un escenario de consistencia, es tomado posteriormente como dipolo actual, y se repite el proceso. Más explícitamente:

Dados:

  • Un conjunto de dipolos (estructurados como grafo).
  • Dipolo de inicio (sd) para definir la ruta.
  • Dipolo de llegada (td) para definir la ruta.
  • Módulos de SparQ: Qualify, Consistency.
  • Restricción "(ells errs lere rele)" para validar la consistencia de escenarios en los que exista la posibilidad de que un dipolo candidato esté conectado al "td".

 

  1. Crear conjunto next_dipoles y agregar el "sd".
  2. Si next_dipoles tiene más de 0 dipolos, tomar el último (la primera vez que se ejecuta, el último dipolo corresponde a "sd"), si no, retroceder un paso para tomar un dipolo alternativo como dipolo actual (current dipole) "cd".
  3. Tomar uno de los nodos de "cd" como nodo actual (current node) "cn".
  4. Obtener la relación entre "cd" y "td": Qualify(cd, td)
  5. Obtener los dipolos conectados al "cn" (dipolos candidatos): graph.getEdges()
  6. Verificar si alguno de los dipolos candidatos corresponde a "td", si es así, terminar y devolver la ruta.
  7. Si solo hay un candidato inicializar next_dipoles como ese candidato (Ir a 11.). Si hay más de un candidato ir a 8.
  8. Inicializar next_dipoles.
  9. Para cada dipolo candidato "c" obtener la relación "c"-"cd": Qualify(c,cd).
  10. Validar la consistencia del escenario dado por: 4., 8. y restricción "ells errs lere rele" entre el candidato actual y "td". Si el escenario es consistente, agregar el dipolo candidato a next_dipoles.
  11. Volver a  2.

 

Implementación

Se cuenta con un shapefile de prueba que corresponde a una porción de la red vial de Münster, Alemania. A través de Python y QGIS se extraen las coordenadas que definen cada dipolo y se llevan a una estructura de grafo que se contruyó para facilitar la ejecución del algoritmo.

Después de recibir el identificador del dipolo de inicio y final se procede a ejecutar comandos en el razonador SparQ para describir la situación inicial de los dipolos y descartar dipolos candidatos con base en la consistencia de escenarios posibles. La ruta calculada es transformada a un shapefile en memoria y visualizada en QGIS como una nueva capa en el mapa.

En resumen, se generó un plugin de QGIS sin interfaz gráfica de usuario, que recibe una capa con la red vial y los dipolos de inicio y fin, ejecuta comandos de SparQ para obtener la ruta y finalmente la visualiza en QGIS.

Qualitative Spatial Reasoning for routing

 

Al ejecutar el plugin la capa de la red vial debe estar en la primera posición de la tabla de contenido de QGIS. Alguna información acerca del proceso puede verse en la consola de Python en QGIS.

Python console

Descargas

El plugin "Qualitative Spatian Reasoning for routing" puede descargarse desde este enlace. Requiere indicar el directorio de instalación de SparQ en el archivo algorithm.py

SparQ puede descargarse desde el sitio web http://www.sfbtr8.uni-bremen.de/project/r3/sparq/, en donde además se encuentra el manual de usuario que indica el proceso de instalación.

El archivo de la red vial de prueba se encuentra en este enlace.

Limitaciones conocidas

La ruta obtenida no es necesariamente la más corta o la más simple, es simplemente una ruta posible.

El cálculo no tiene en cuenta el sentido de los dipolos y recibe los dipolos de inicio y final con base en identificadores en lugar de facilitar la selección de manera gráfica o incluso, de aceptar puntos en lugar de dipolos.

El tiempo que tarda realizando los cálculos es considerable, si se tiene en cuenta que a partir de la misma información se pueden emplear algoritmos mucho más eficientes como el Dijkstra o el A* (A-Star).

Desafortunadamente, no se realizaron pruebas exhaustivas sobre el algoritmo, únicamente se trabajó con la red expuesta y los dipolos seleccionados. Mayor énfasis en hacer el algoritmo más general podría realizarse por demanda. Aún así, el algoritmo representa una base para posteriores trabajos en el área.

Co-autores

Christoph Mülligann, Joao Blasques, Jafar Hafiz, Sergio Clark, Talakisew Binor, Dian Melati, Avit Bhowmik, Yitea Getahun, Minu Limbu, Germán Carrillo.

Este ejercicio se realizó en el marco del curso "Qualitative Spatial Knowledge Reasoning and Representation", impartido por Malumbo Chipofya en el Institut für Geoinformatik (ifgi) de la Universität Münster, Alemania.

Referencias

  • Freksa, C. and Röhrig, R. (1993). Dimensions of qualitative spatial reasoning, In N. P. Carrete and M. G. Singh, editors, Qualitative reasoning and decision technologies, Proc. QUARDET93, 483-492, Barcelona.
  • Moratz, R., Renz, J. & Wolter, D. (2000). Qualitative spatial reasoning about line segments. ECAI, 2000, pp 234-238.
  • Renz, J. and Nebel, B. (2007). Qualitative spatial reasoning using constraint calculi, In: Handbook of Spatial Logics, M. Aiello and I. E. Pratt-Hartmann and J. F.A.K. van Benthem (eds), pp. 161-215, Springer.
  • Wallgrün, J., Frommberger, L., Dylla, F. and Wolter, D. (2010). SparQ User Manual V0.7. SFB/TR 8 Spatial Cognition - Project R3-[Q-Shape].

 

Last modified on Martes 04 de Septiembre de 2012 15:15

Escribir un comentario


Código de seguridad
Refescar

 

¿Dónde nos leen?