ES2387772T3

ES2387772T3 - Procedimiento de georeferenciación en mapa ("map matching") con integridad garantizada

Info

Publication number: ES2387772T3
Application number: ES08380079T
Authority: ES
Inventors: Ignacio Fernández Hernández; José Caro Ramón; Manuel Toledo López; Miguel Ángel Martinez Olagüe; Miguel Azaola Sáenz
Original assignee: GMV Aerospace and Defence SA
Current assignee: GMV Aerospace and Defence SA
Priority date: 2008-03-11
Filing date: 2008-03-11
Publication date: 2012-10-01
Anticipated expiration: 2028-03-11
Also published as: EP2101148A1; US8032299B2; US20090234580A1; ATE556298T1; EP2101148B1

Abstract

Un procedimiento de determinación de un vial o un conjunto de viales o zonas transitables recorridos por unusuario con una probabilidad mínima asociada o integridad, que comprende:- recibir de un sistema de posicionamiento información relativa a una primera y a una segunda soluciones deposición (PVT) de dicho usuario en un primer instante de tiempo ta y en un segundo instante tb posterior alprimer instante ta, respectivamente, así como sendas elipses de integridad de posición, Ia e Ib (201), consendas probabilidades mínimas asociadas, Pa y Pb, de que el usuario se encuentre en cada una de ellas en tay en tb, respectivamente, y un incremento de posición Δab (209) entre ta y tb con su elipse Iab de integridad deincremento de posición (204) y su probabilidad Pab asociadas;- obtener de un sistema de información geográfica GIS información sobre sendas zonas transitables TGIScorrespondientes a dichas primera y segunda soluciones PVT;- determinar una primera área íntegra transitable Sa (202) y una segunda área íntegra transitable Sb (203)como intersección para cada instante de tiempo de dichas elipses de integridad de posición con dichas zonastransitables TGIS; - propagar dicha primera área íntegra transitable al instante posterior tb mediante el incremento de posiciónΔab (209) entre los primer y segundo instantes de tiempo proporcionados por el sistema de posicionamiento,teniendo en cuenta la incertidumbre asociada a dicho incremento determinada por la elipse de integridad delincremento de posición Iab (204), obteniéndose una área íntegra propagada Sab (208);- eliminar de dicha área íntegra propagada Sab las zonas no transitables, obteniéndose una área íntegra transitable propagada S'ab (206);- determinar una área íntegra transitable final S'b compuesta por un vial o un conjunto de viales transitablesen el segundo instante tb, bien como la menor entre dicha segunda área íntegra transitable Sb (203) y dichaárea íntegra transitable propagada S'ab (206) o bien como la intersección de dicha segunda área íntegratransitable Sb (203) y de dicha área íntegra transitable propagada S'ab (206);- determinándose la probabilidad mínima P'b de que el usuario se encuentre en dicha área íntegra transitablefinal S'b en el segundo instante tb o nivel de integridad de S'b:- en caso de que dicha área íntegra transitable final S'b sea dicha segunda área íntegra transitable Sb(203), como la probabilidad Pb asociada a la elipse de integridad Ib de dicha segunda solución PVT, esdecir, P'b >= Pb; - en caso de que dicha área íntegra transitable final S'b sea dicha área íntegra transitable propagadaS'ab (206), como el producto de la probabilidad Pa asociada a la primera área transitable Sa, dada por laelipse de integridad Ia de dicha primera solución PVT, y la probabilidad asociada a la elipse deintegridad Iab correspondiente al incremento relativo de posición Δab entre ta y tb, es decir, P'b >= Pa . Pab;- en caso de que dicha área íntegra transitable final S'b se determine como la intersección de la segundaárea íntegra transitable Sb (203) y dicha área íntegra transitable propagada S'ab (206), mediante la expresión:P'b >= Pa . Pab + Pb - 1.

Description

Procedimiento de georeferenciación en mapa (“map matching”) con integridad garantizada.

Campo de la Invención

La presente invención pertenece al campo de aplicaciones de posicionamiento, en particular aquellas que requieran

o se beneficien del uso de información geográfica y necesiten una alta garantía de servicio o integridad, como por ejemplo el posicionamiento mediante un sistema de navegación por satélite para usuarios y vehículos terrestres que circulan por una red de calles y carreteras.

La invención puede utilizarse tanto para aplicaciones críticas de seguridad como para aquellas que conlleven responsabilidades legales o contractuales.

Antecedentes de la Invención

El uso de Sistemas Globales de Navegación por Satélite (GNSS), como GPS, para el posicionamiento de vehículos, se encuentra muy extendido en la actualidad. Mediante la recepción y procesado de la señal de varios satélites, un usuario es capaz de determinar su posición y una referencia temporal. Esta información se determina conociendo la posición de los satélites y el tiempo que la señal ha tardado en llegar al usuario. Además es necesario estimar los retrasos que afectan al tiempo de llegada de la señal, como son las desviaciones de los satélites, el retardo atmosférico y los efectos locales y del receptor. Actualmente, un usuario puede determinar su posición con una precisión de unos pocos metros aproximadamente en entornos de buena visibilidad, existiendo errores mayores en entornos no controlados.

Además de la solución de posición y tiempo, existen técnicas que aseguran un nivel de confianza, o integridad, de dicha solución . Dichas técnicas proporcionan un lugar geométrico (elipsoide en el espacio, elipse en el plano) en el que se asegura que se encuentra el usuario con una probabilidad asociada (por ejemplo, 99,99999% en el entorno aeronáutico). Dichas técnicas son ya conocidas y se aplican en sistemas SBAS, como WAAS o EGNOS, o se calculan mediante algoritmos autónomos de RAIM (Receiver Autonomous Integrity Monitoring) o derivados, tanto para aplicaciones críticas de seguridad como para aquellas que tengan implicaciones legales o contractuales. Existen técnicas que proporcionan integridad en entornos de baja visibilidad o no controlados, como cañones urbanos, como se describe en EP1729145, “Method and System for providing GNSS navigation position solution with guaranteed integrity in non-controlled environments”.

Por otra parte, es muy común el uso combinado de posicionamiento GNSS y Sistemas de Información Geográfica (GIS), es decir, mapas cartográficos digitales que modelan el entorno, de forma que la información de posición del usuario pueda ser relacionada con el mundo real, con el fin de proporcionar guiado en ruta o cualquier otro tipo de información.

En aplicaciones para el transporte terrestre, la combinación de navegación por satélite y GIS se suele realizar mediante técnicas de georeferenciación en mapa o Map Matching (término inglés que se usará de ahora en adelante en el presente texto, o su abreviatura ‘MM’). Dichas técnicas identifican cuál es el segmento o vial (calle, carretera, autopista) por el que más probablemente circula el usuario, así como su posición a lo largo del mismo. En caso de no existir errores ni en la posición GNSS ni en la información GIS, el proceso sería inmediato, ya que la posición coincidiría con un punto en el vial determinado por el que el usuario se encontrase circulando. Sin embargo, la realidad es bien distinta, ya que existen fenómenos causantes de error en la posición GNSS –errores relativos a los satélites, retardos atmosféricos, reflejos de la señal o multicamino, particularmente importante en entornos urbanos–, que pueden causar errores de hasta centenares de metros, así como errores en el proceso de creación de los mapas digitales, debidos principalmente al factor de escala, la transformación de coordenadas, la traslación de una superficie curva a un plano (generalización), la referencia de posición (datum) y el proceso de digitalización.

Los procedimientos de MM existentes en el estado de la técnica abarcan desde los algoritmos más sencillos, en los que se aproxima la posición al segmento o vial más cercano en ese instante, hasta otros mucho más complicados. Una de las principales referencias en algoritmos de MM es “An Introduction to Map Matching for Personal Navigation Assistants”, Bernstein D. Kornhauser A., 1996, donde se presentan las primeras aproximaciones al uso de MM con un sistema de posicionamiento. Los procedimientos propuestos se dividen en geométricos y topológicos. Los primeros solo tienen en cuenta la geometría de los segmentos que definen el mapa GIS, mientras los segundos además tienen en cuenta la forma en que dichos segmentos están conectados. Posteriormente se han desarrollado procedimientos más avanzados, en los que se compara la trayectoria en el tiempo con las posibles trayectorias en el mapa mediante reconocimiento de patrones, filtros de Kalman, o lógica difusa para seleccionar el vial apropiado. Sin embargo, la precisión de estos procedimientos no está garantizada, ni se proporciona al usuario un valor de confianza, o integridad, de la solución adoptada, sino que están enfocados al ajuste de la posición a un segmento de la mejor manera posible en la mayor parte de los casos.

El procedimiento probabilístico de MM, descrito en “Vehicle Location and Navigation System”, Zhao Y., 1997 y en “High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications” Quddus M., 2006, podría

considerarse un antecedente a la presente invención, ya que genera una elipse a partir de la matriz de covarianza de la posición, y analiza como posibles segmentos solamente aquellos que se encuentran dentro de dicha elipse, descartando aquellos cuya orientación no coincide con la de la marcha del vehículo. El uso de esta elipse basada en la covarianza de la posición es similar al concepto de integridad descrito anteriormente. Sin embargo, el procedimiento probabilístico tiene algunas pegas:

-: por ejemplo, que no se basa en la integridad de la posición que proporciona el sistema de navegación, sino que usa la matriz de covarianza solamente para seleccionar los posibles viales dentro de una zona de mayor probabilidad, que no es suficiente para garantizar la integridad de la posición;

-: o por ejemplo, que propone usar el sentido de la marcha para descartar segmentos, exponiéndose a descartar el vial correcto en caso de giro, cambio de carril, o error en el cálculo del sentido de la marcha, por lo que, al usar procedimientos no íntegros para seleccionar el vial, la integridad inicial, si la hubiera, perdería su validez.

En los últimos años se han desarrollado procedimientos que han intentado proporcionar un valor de integridad a la solución de MM, y que se describen a continuación. No obstante el concepto de integridad usado no se corresponde al que rigurosamente se usa en esta patente, que está basado en los conceptos introducidos por la aviación civil. De hecho, en ningún caso se garantiza la probabilidad de que el segmento identificado sea el correcto, lo cual es esencial para el concepto de integridad.

En “Integrity of map-matching algorithms”, Quddus M., Ochieng W., Noland B., 2006 y en “High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications” Quddus M., 2006 se propone un algoritmo de MM íntegro basado en un indicador global de integridad (0-100) para soluciones dadas por procedimientos ya existentes (topológico, probabilístico y de lógica difusa). Dicho indicador se determina mediante la combinación de los siguientes tres criterios:

-: Integridad basada en la incertidumbre asociada a la solución de posición: se determina una desviación típica (O) basada en las incertidumbres del mapa (Omap) y de la posición GPS (On y Oe) y se la multiplica por un coeficiente K, calculado mediante resultados empíricos y en función del número de carriles del vial. Este indicador da una medida de la incertidumbre de la posición GPS y del mapa, pero en ningún caso una garantía de integridad en sí mismo.

-: Integridad basada en la habilidad para identificar correctamente el vial: Se calcula el ángulo que forman el segmento seleccionado por el algoritmo de MM y la trayectoria del vehículo a partir de GPS o GPS + sensores inerciales, y se considera la solución más íntegra cuanto menor sea este ángulo. Sin embargo, además de que este indicador no proporciona ninguna garantía de integridad en sí mismo, dará una falsa alarma en caso de que el vehículo se encuentre girando o cambiando de carril, y el sentido no coincida con el del segmento, o no detectará un fallo si se selecciona un vial erróneo que coincide con el sentido de la marcha por cualquier motivo.

-: Integridad basada en la habilidad para determinar la posición del vehículo de forma precisa: A la distancia entre la posición GPS y la posición dada por el algoritmo de MM, se le resta un indicador de incertidumbre (R3dms) basado en la covarianza de la posición GPS más el ancho típico de vial. En caso de que el resultado sea positivo, se asume que la probabilidad de integridad es menor. Este indicador no proporciona una medida de integridad cuantificable, y tampoco garantiza integridad en caso de que el resultado sea negativo o próximo a cero.

Una vez determinado el índice de confianza o integridad (0-100) mediante los criterios anteriores usando un algoritmo de lógica difusa, se determina un valor límite (70) por debajo del cual se da una alarma al usuario. Dicho límite está basado en resultados empíricos, con el fin de optimizar las prestaciones del algoritmo en el experimento realizado.

Por lo expuesto anteriormente, se concluye que la integridad proporcionada por este algoritmo no puede considerarse fiable en todos los ámbitos, ya que no es cuantificable ni está basada en fundamentos teóricos, por lo que no puede extrapolarse a otras situaciones más allá de los experimentos realizados. Por lo tanto no proporciona la confianza necesaria para aplicaciones críticas de seguridad o de implicaciones legales o contractuales. Por otra parte, el nivel de prestaciones obtenido (98,2% en el mejor de los casos) no parece suficiente para aplicaciones críticas, y está muy por debajo del índice de confianza del procedimiento aquí propuesto.

Syed S. y Cannon E. en “Linking vehicles and maps to support location-based services”, 2005; GPS World presentan un procedimiento novedoso que combina información GIS, GPS y navegación por estima o Dead Reckoning (término inglés que se usará de ahora en adelante en el presente texto, o su abreviatura ‘DR’) con el fin de mejorar la precisión y fiabilidad del posicionamiento en entornos urbanos. No obstante, dicho procedimiento no proporciona ningún indicador de integridad.

También en “Improving integrity and reliability of map matching techniques” Yu M.et al, 2006 se proponen diversas técnicas de detección de fallos en la selección de un vial (mismatch), combinando GPS, INS y MM, y mediante reconocimiento de curvas. Aunque mejora la fiabilidad del algoritmo, aún queda un 31.8% de fallos sin detectar, de acuerdo a los resultados del experimento realizado, y además el procedimiento no define ni calcula un valor de confianza a las soluciones obtenidas, sino que se reduce a mejorar la fiabilidad de las técnicas actuales de MM.

En “Tightly-coupled GIS data in GNSS fix computations with integrity testing” Fouquet C., Bonnifait Ph., 2007, se propone un procedimiento de MM con GPS usando una estrategia tight coupling en la que, por cada solución GPS, se determina un conjunto de segmentos candidatos, basados en ciertos criterios, y se evalúan por separado mediante un procedimiento similar a RAIM. En caso de existir varios candidatos finales, se selecciona el que minimiza el residual de posición de la solución de mínimos cuadrados. A pesar de dicho chequeo de fiabilidad, este procedimiento no garantiza la confianza de la solución seleccionada. Por otra parte, no tiene en cuenta la información procedente de instantes anteriores.

La solicitud de patente europea publ. EP-1526357-A1 describe un procedimiento para detectar la posición de un vehículo en un sistema de navegación mediante map matching, que usa la técnica clásica de la proyección ortogonal de la posición en el segmento más cercano. Al igual que los antecedentes ya citados, no garantiza integridad.

La solicitud de patente europea EP-1492072-A describe también un procedimiento y sistema de map matching, que consiste en una optimización de procesado de capas de los mapas. Se refiere a mejorar la determinación del vial en tiempo real y no garantiza integridad.

Descripción de la Invención

La invención se refiere a un procedimiento de determinación de un vial o un conjunto de viales o zonas transitables recorridos por un usuario con una probabilidad mínima asociada, o integridad, de acuerdo con la reivindicación 1, y el uso de dicho procedimiento de forma recurrente en el tiempo, con el fin de determinar la trayectoria seguida por el usuario con integridad, de acuerdo con la reivindicación 2. Realizaciones preferidas del procedimiento se describen en las reivindicaciones dependientes.

De acuerdo con un primer aspecto de la invención, ésta proporciona un procedimiento de determinación de un vial o un conjunto de viales o zonas transitables recorridos por un usuario con una probabilidad mínima asociada, o integridad, que comprende:

-: recibir de un sistema de posicionamiento información relativa a una primera y a una segunda soluciones de posición PVT de dicho usuario en un primer instante de tiempo ta y en un segundo instante tb posterior al primer instante ta, respectivamente, así como sendas elipses de integridad de posición, Ia y Ib, cada una con una probabilidad mínima asociada Pa y Pb de que el usuario se encuentre en ellas en ta y en tb, respectivamente, y un incremento de posición fab entre ta y tb con una elipse de integridad de incremento de posición Iab y su probabilidad Pab asociadas;

-: obtener de un sistema de información geográfica GIS información sobre sendas zonas transitables TGIS correspondientes a dichas primera y segunda soluciones PVT;

-: determinar una primera área íntegra transitable Sa y una segunda área íntegra transitable Sb como intersección para cada instante de tiempo de dichas elipses de integridad de posición con dichas zonas transitables TGIS;

-: propagar dicha primera área íntegra transitable al instante posterior tb mediante el incremento de posición fab entre el primer y segundo instantes de tiempo, proporcionado por el sistema de posicionamiento, teniendo en cuenta la incertidumbre asociada a dicho incremento determinada por la elipse de integridad Iab del incremento de posición, obteniéndose una área íntegra propagada Sab;

-: eliminar de dicha área integra propagada Sab las zonas no transitables, obteniéndose una área íntegra transitable propagada S’ab;

-: determinar el área íntegra transitable final S’b en el segundo instante tb, bien como la menor entre dicha segunda área íntegra transitable Sb y dicha área íntegra transitable propagada S’ab o bien como la intersección de ambas áreas S’ab y Sb;

-: determinar el nivel de integridad de S’b, esto es, la probabilidad mínima de que el usuario se encuentre en dicha área íntegra transitable final S’b en el segundo instante tb:

i. En caso de que el área íntegra transitable final S’b se determine como la menor entre Sb y S’ab, el nivel de integridad será la probabilidad asociada al área que haya resultado elegida:

�: si se trata de Sb será la probabilidad Pb asociada a la elipse Ib;

�: si se trata de S’ab, será el producto de la probabilidad Pa asociada a la elipse Ia y la probabilidad Pab asociada a la elipse Iab.

ii. En caso de que el área íntegra transitable final S’b se determine como la intersección de S’ab y Sb, la

probabilidad de que el usuario se encuentre fuera de dicha intersección está superiormente acotada por la suma de las probabilidades de encontrarse fuera de las áreas S’ab y Sb, luego el nivel de integridad (o probabilidad de que el usuario se encuentre dentro de dicha intersección) está acotado inferiormente por Pa . Pab+Pb -1.

Es decir, la presente invención se refiere a un procedimiento de Map Matching Íntegro mediante el uso combinado de información cartográfica (mapas digitales donde se especifican las zonas transitables por el usuario, mediante los segmentos que definen los viales y sus anchuras, o mediante cualquier otra forma, con una precisión dada y conocida) con información íntegra de posicionamiento (posición, incremento de posición, tiempo, integridad de posición absoluta e integridad del incremento de posición).

La invención se refiere principalmente a posicionamiento GNSS, aunque también es válida para procedimientos de posicionamiento alternativos, siempre y cuando éstos sean íntegros, como Sistemas de Navegación Inercial (INS), radiofrecuencia (UMTS, Wifi, UWB, etc), o un sistema GNSS hibridado con un sistema inercial Dead Reckoning, u otros sistemas mediante comunicaciones inalámbricas y/o balizas u otros procedimientos, siempre y cuando dicho sistema de posicionamiento proporcione la información y la integridad necesaria y el procedimiento siga los pasos definidos en lo anterior.

En caso de que el sistema de posicionamiento usado sea un sistema GNSS, el incremento de posición entre dos instantes de tiempo y su integridad se determinan mediante el incremento de la medida de fase de portadora de los satélites entre tales instantes, y su incertidumbre asociada.

Preferiblemente, la invención también se refiere a la recursividad del procedimiento propuesto; así el procedimiento de la invención se repite para cada nueva solución PVT proporcionada en cada nuevo instante ti, basándose en la propagación del área íntegra transitable desde un instante anterior tj, sea el inmediatamente anterior ti-1 u otro, determinando las zonas transitables y su probabilidad asociada en varios instantes consecutivos a lo largo de una trayectoria.

Preferiblemente además se realiza un procesado adicional o post-procesado, con una periodicidad configurable y a lo largo de un arco de instantes configurable m, en el que, para cada instante ti de dicho arco:

-: se realiza la propagación del área transitable del instante ti, al instante inmediatamente anterior ti-1, mediante el incremento de posición entre ambos instantes, tomado en sentido contrario, y su elipse de integridad asociada, eliminando las zonas no transitables, y se compara con el área transitable anteriormente calculada en ti-1, seleccionando la más pequeña entre las dos, o se realiza la intersección, tal y como ha descrito anteriormente;

-: se realizan los pasos anteriores sobre todos los instantes del arco –de ti-1 a ti-2, de ti-2 a ti-3, etc., hasta ti-m–, tal y como se ha definido anteriormente la recursividad del procedimiento, con el fin de incluir a posteriori la información de zonas transitables en ti en los instantes anteriores.

El objetivo de la invención es asegurar con un nivel de integridad requerido, no sólo la posición del usuario sino también en qué vial y tramo del mismo se encuentra en un instante dado, así como la mejora de dicha solución y preferiblemente la determinación de su trayectoria y el conjunto de viales que ha recorrido mediante el procesado hacia atrás en el tiempo.

La invención se basa en los siguientes principios:

1) La definición inicial de las zonas transitables, a partir de una base de datos GIS, en la que se determinan los segmentos que forman los viales circulables, y su anchura, o los polígonos que separan las zonas transitables de las que no lo son. La definición de zonas transitables preferiblemente tiene en cuenta la incertidumbre o error máximo de la información cartográfica definido por el proveedor de mapas y siendo dicha información considerada como una entrada al proceso. Para asegurar el uso íntegro de la información cartográfica se podrá aumentar el área transitable tanto como sea necesario para evitar descartar zonas debido a la imprecisión del mapa.

2) La determinación del área íntegra transitable por el usuario en cada instante, a partir de la posición dada, por ej., por un sistema GNSS, y su elipse de integridad (definida por ej., mediante los Niveles de Protección , por ejemplo tal y como se definen en la patente EP1729145) y las zonas transitables dentro de la misma.

3) La determinación del incremento de posición del usuario entre dos instantes de tiempo y su integridad. En el caso de posicionamiento GNSS, para estimar el incremento de posición entre dos instantes, se utiliza como entrada el incremento en la medida de fase de la portadora de los satélites entre ambos instantes. La incertidumbre de la estimación es representada mediante una elipse de integridad de incremento de posición, obtenida de manera similar a la integridad de posición absoluta, pero sin estar asociada a un punto fijo, sino a un vector. Dadas las características del error de la medida de incremento de fase, el incremento de posición relativo se puede determinar de forma mucho más precisa que la posición absoluta, con una incertidumbre generalmente del orden de centímetros, incluso en entornos urbanos.

4) La traslación del área transitable del instante anterior al instante posterior, basándose en dicho incremento de posición y su incertidumbre asociada, expandiendo el área trasladada lo necesario para mantener la integridad, de acuerdo a la elipse de integridad de incremento de posición.

5) La determinación de la nueva área transitable como (a) la menor entre el área transitable propagada desde un instante anterior, y el área transitable en el instante actual o (b) la intersección entre el área transitable propagada desde un instante anterior, y el área transitable en el instante actual. Del primer modo, el área transitable resultante (donde podría encontrarse la verdadera posición del usuario) será mayor que del segundo modo, pero en cambio, el nivel de integridad obtenido con el primer modo será mayor que el obtenido con el segundo. Se puede adoptar cualquiera de las dos estrategias en función de las necesidades y requisitos de la aplicación concreta, pero son esencialmente equivalentes por cuanto que el grado de incertidumbre acerca de la posición del usuario es esencialmente el mismo (un gran área con una gran probabilidad o un área más reducida con una probabilidad también más reducida).

La invención también prevé la posibilidad de repetir los pasos 2) a 5) para cada nueva solución de posición en cada nuevo instante, basándose en la propagación de la zona transitable desde un instante anterior, que puede o no ser el inmediatamente anterior, de forma que se vayan determinando a lo largo de la trayectoria del usuario las nuevas zonas transitables teniendo en cuenta las anteriores, con el fin de reducir progresivamente las zonas posibles.

De forma similar, también es posible la repetición periódica del proceso, cada cierto tiempo, hacia instantes anteriores, con una periodicidad configurable y a lo largo de un arco de instantes configurables, propagando de forma recursiva el área transitable en cada instante al instante anterior, mediante el incremento de posición descrito en el paso 3) tomado en sentido contrario, y determinando el área transitable según el criterio anteriormente expuesto, con el fin de eliminar áreas que fueron consideradas como posibles, pero que con la información presente se pueden descartar.

De esta forma, se puede determinar por qué segmento o vial circula el usuario en un instante determinado, así como la trayectoria seguida en el tiempo, manteniendo el alto nivel de confianza dado por la probabilidad asociada a la integridad en cada instante.

Adicionalmente el procedimiento puede incorporar los siguientes aspectos:

-: Estimación directa de la trayectoria: en el caso de posicionamiento GNSS, además del procesado de las medidas de fase de portadora de los satélites, que permite calcular el incremento de posición entre dos instantes, también se puede añadir opcionalmente el procesado de las medidas de Doppler, de las que se obtiene la velocidad instantánea, incorporando un modelo dinámico de usuario teniendo en cuenta las restricciones en el movimiento del usuario en términos de velocidad y aceleración lineal y angular máximos posibles. De esta forma, sólo se seleccionan las áreas por las que se recorre un camino transitable en todo momento, pudiendo obtener una trayectoria en el mapa continua, precisa e íntegra.

-: Algoritmos de conectividad entre viales: se pueden tener en cuenta las restricciones topológicas en la propagación entre instantes, eliminando zonas que, aunque son transitables, no existe un camino plausible entre ambos instantes que el usuario haya podido recorrer, teniendo en cuenta las restricciones en la dinámica del mismo.

-: El procedimiento puede usar diversos criterios para seleccionar el instante desde el cual se propaga el área transitable (ta), como, por ejemplo, almacenar la información de un instante de máxima observabilidad y elipse de integridad de tamaño mínimo, o zona íntegra transitable mínima, con el fin de reducir las zonas transitables de instantes futuros, o simplemente propagar el área del instante anterior al actual. Se debe tener en cuenta que la incertidumbre en el incremento de la medida de la fase, y por lo tanto del incremento de posición, aumenta con el tiempo, lo que aumentará el área en la propagación.

-: La generación de las áreas transitables en el mapa se puede realizar a priori, de forma que el procedimiento parta de un mapa íntegro de zonas transitables (proporcionadas por el sistema GIS), o bien se puede ir generando a medida que el usuario va recorriendo el mapa, convirtiendo sucesivamente zonas del mismo definidas por segmentos y anchuras en áreas transitables (Sa). Asimismo, las zonas transitables se pueden definir de varias maneras, como por ejemplo polígonos, celdas o segmentos. La invención es independiente de la forma en que se determinen las zonas transitables.

-: Teniendo en cuenta el cálculo de integridad usando información de los instantes anteriores, el procedimiento puede incorporar un chequeo en el que el algoritmo se reinicie y considere solamente la información desde el instante actual o en curso cuando la probabilidad de integridad se haya degradado hasta encontrarse por debajo de un umbral de confianza.

-: Extrapolación del procedimiento a entornos de tres dimensiones (3D), mediante el uso del mismo concepto de propagación de zonas íntegras, y utilizando elipsoides de integridad en lugar de elipses e intersecando con volúmenes transitables, en lugar de superficies.

Breve descripción de los dibujos

Para complementar la descripción que se está realizando y con objeto de ayudar a una mejor comprensión de las características de la invención, de acuerdo con un ejemplo preferente de realización práctica de la misma, se acompaña, como parte integrante de dicha descripción, un juego de dibujos en donde, con carácter ilustrativo y no limitativo, se ha representado lo siguiente:

La Figura 1 muestra un ejemplo de base de datos con zonas transitables (blanco) y no transitables (negro) determinado a partir de una base de datos GIS.

Las Figuras 2A-2C muestran gráficamente un ejemplo del proceso seguido para determinar la trayectoria correcta seguida por un vehículo.

La Figura 3 muestra el diagrama de flujo de la implementación preferida del procedimiento.

La Figura 4 muestra un ejemplo de propagación de una celda transitable a las celdas transitables en un instante posterior.

En la Figura 5 se muestra un ejemplo de eliminación de zonas transitables por conectividad, al propagar la zona transitable de t1 a t2.

La Figura 6 muestra un ejemplo concreto de determinación de trayectoria mediante la invención.

Descripción detallada de una realización preferida de la invención

A continuación se describe una implementación preferida de la invención, basada en una división del mapa en celdas. Esta implementación es de carácter ilustrativo y no limitativo, siendo la invención genérica y pudiendo ser aplicados sus principios sobre otras implementaciones basadas en información geográfica expresada en otros formatos, como tramos de segmentos representando los viales, y su anchura asociada.

La figura 1 muestra un ejemplo en el que en un mapa 101 se han indicado en blanco las zonas transitables 102 y en negro las zonas no transitables 103 a partir de la información proporcionada por una base de datos GIS.

A continuación se explica el procedimiento de la invención paso por paso, en base a las figuras 2A, 2B y 2C explicativas del proceso. Así, partiendo del mapa GIS en el que se definen las zonas transitables (por ejemplo, zonas blancas 102 del mapa 101, en adelante TGIS), en una época o instante ta dado:

1) Se determina la zona íntegra del usuario en ese instante, por ejemplo, a partir de la posición estimada Xa y la elipse de integridad Ia 201 asociada a esa posición e instante de tiempo, tal y como se muestra en la Figura 2A.

2) Se determina la superficie transitable por el vehículo dentro de la zona íntegra o zona íntegra transitable Sa en ese instante ta 202 como Sa = Ia n TGIS, siendo TGIS la zona transitable definida a partir de la base de datos GIS.

En un instante posterior tb:

3) Se calcula la zona íntegra transitable Sb en dicho instante tb 203 de la misma forma que se hizo en ta (en el caso particular representado en las figuras 2A-2C la elipse de integridad de la posición en el instante tb coincide en tamaño con la elipse de integridad en el instante ta, pero no necesariamente tiene que ser así).

4) Se determina (figura 2B), mediante el incremento en la medida de fase de portadora de los satélites, el incremento de posición de usuario fab entre ta y tb. También se estima la incertidumbre asociada a dicho incremento, o integridad, dando lugar a una elipse de integridad Iab 204, generalmente de mucho menor tamaño que la obtenida para la posición absoluta. En caso de que no existan medidas suficientes para determinar el incremento de posición con integridad respecto a una posición anterior, el algoritmo se reinicia.

5) Se determina una superficie propagada en ese instante posterior tb de la siguiente forma:

a.: Se propaga la superficie Sa con el incremento de posición fab 209, obteniéndose el área 205 (señalada en sombreado claro en la parte superior de la figura 2B).

b.: Se aumenta esa área obtenida 205 con Iab, de forma que la propagación se realice manteniendo la integridad, obteniendo el área íntegra propagada Sab 208 (delimitada por el sombreado oscuro en la parte superior de la figura 2B). Dicha área corresponde a la zona íntegra en tb a partir de la información en ta.

c.: Se eliminan las zonas no transitables de Sab, obteniendo S’ab 206.

6) Se determina la nueva zona transitable S’b:

a.: O bien como la menor área entre S’ab y Sb.

b.: O bien como la intersección entre S’ab y Sb.

En el ejemplo representado (figura 2C), como S’ab es menor que Sb, entonces S’b corresponde a S’ab.

7) Se realiza este proceso para cada nueva posición, de forma que la zona transitable tiende a reducirse al vial en el que se encuentra el usuario. En caso de que al realizar la intersección no existan zonas transitables, se da una alarma y el algoritmo se reinicia. En caso de que no se haya podido calcular Ib, y por lo tanto tampoco Sb, por falta de medidas, se determinará S’b como S’ab. En caso de que no se haya podido calcular fab y por lo tanto tampoco S’ab, se determinará S’b como Sb.

8) Cada cierto tiempo se realiza el mismo procesado hacia atrás, tomando un arco determinado de instantes, de forma que a partir de la información actual se reduzcan a posteriori posibles zonas transitables pasadas, con el fin de obtener la zona íntegra S’a en la época ta 207 (obteniendo la trayectoria correcta desde el principio).

Cuando la obtención del área transitable se realiza según la opción 6.a, y en caso de que S’b se determine como S’ab, hay que tener en cuenta que el nivel de integridad de S’ab, es decir, la probabilidad mínima garantizada de que el vehículo se encuentre en esta área, depende tanto de la probabilidad de integridad de Sa como de la probabilidad de integridad de fab, siendo igual a (o estando acotada inferiormente por) el producto de ambas:

P’b = P’ab ;Pa .Pab

donde

-: P’b es la probabilidad final de que el usuario se encuentre en S’b

-: P’ab es la probabilidad final de que el usuario se encuentre en S’ab

-: Pa es la probabilidad de que el vehículo se encuentre en Sa (o en Ia)

-: Pab es la probabilidad de que el error de estimación del incremento relativo de posición del vehículo entre ta y tb (es decir, el error cometido al calcular fab) esté acotado por su correspondiente elipse de integridad Iab. Por ejemplo, si Pa = 0,99 y Pab = 0,99 la probabilidad final P’ab es:

P’b = P’ab ;Pa · Pab = 0,9801.

Generalizando el cálculo de probabilidad anterior al caso en que el área de una única época se haya ido propagando y seleccionando sucesivamente durante N épocas, su probabilidad de integridad asociada es:

N-1

P't+N =P't,t+N =Pt .IPt+j,t+j+1 j=0

Si, además, los niveles de integridad de las posiciones de las distintas épocas son siempre los mismos, digamos iguales a una cierta probabilidad PX, y los niveles de integridad de los incrementos de posición son también constantes, digamos iguales a una cierta probabilidad Pf, la fórmula anterior se puede reescribir como:

P' =P' =P .��N

P

t+N t,t+NX�

En caso de que S’b se determine como Sb, la probabilidad de integridad asociada P’b corresponde automáticamente a Pb:

P’b = Pb

En caso de 6.b, es decir, cuando la implementación de la nueva zona transitable S’b se determine mediante la intersección entre S’ab y Sb, se ha de calcular la probabilidad de que el vehículo se encuentre en el área intersecada. Para ello se asume una distribución de probabilidad en ambas áreas, obteniendo la probabilidad final de la intersección o, más propiamente, de que la posición del usuario se encuentre en la intersección de las áreas, la cual será como mínimo la complementaria de la suma de las probabilidades de que la posición del usuario se encuentre fuera de cada una de las dos áreas, S’ab y Sb. Por tanto:

P’b ;Pa .Pab + Pb - 1

Por lo tanto, el procedimiento es capaz de proporcionar un valor de probabilidad mensurable mínimo (o nivel de integridad mínimo) asociado a cada época, basado en un fundamento teórico, usando información de integridad de épocas anteriores.

La Figura 3 muestra el diagrama de flujo de una implementación preferida de la invención, que se realiza mediante los siguientes pasos:

-: Inicialización 301, introducción de la configuración y del mapa GIS: Se divide el mapa GIS con zonas transitables íntegras en una retícula de celdas de una dimensión configurable (por ejemplo, 1 metro x 1 metro). Se determina si cada celda es transitable o no transitable en función del mapa GIS, de forma conservadora; es decir, basta con que un punto de la celda sea transitable para declararla como tal (pasos 302 y 303).

-: Para cada época t, que en lo que sigue denotaremos por tb por consistencia con la notación utilizada en el resto del texto:

a.: Se obtiene la información de posición Xb, incremento de posición fab desde una época anterior ta, elipse de integridad de posición Ib y elipse de integridad del incremento de posición Iab (paso 304). A este conjunto de información nos referiremos en adelante como solución PVTI.

b.: Se comprueba que existe solución PVTI (paso 305); en caso de no existir se inicializa de nuevo el proceso.

c.: Se determinan las celdas transitables Sb dentro del área íntegra para la época tb (paso 306). En caso de que parte de una celda se encuentre dentro de la zona íntegra y parte fuera, se considerará la celda completa para mantener la integridad. Si no se obtiene celda transitable alguna (paso 307) se inicializa el proceso y se genera una alarma.

d.: Se comprueba si existe información Sa de celdas transitables de la época anterior ta así como trayectoria relativa fab entre dicha época y la actual con su correspondiente incertidumbre asociada Iab(paso 308). Si no se dispone de alguno de estos elementos, se actualizan la información de posición y de integridad para comenzar a procesar la época siguiente (paso 308-B). En caso contrario, es decir, si se tienen todos los elementos mencionados, se propaga el área Sa según la trayectoria relativa fab obteniendo el área propagada S’ab (paso 309):

i. Cada celda de Sa se propaga según la trayectoria relativa fab

ii. A la celda propagada se le unen las celdas adyacentes correspondientes al área de incertidumbre asociada a la propagación, y medida por la elipse de integridad Iab del incremento de posición (tal y como se muestra en la figura 4, mediante la celda original 401 y las celdas propagadas 402)

iii. Del conjunto de celdas resultante se eliminan las no transitables

iv. Opcionalmente, para cada una de las celdas restantes se realiza un chequeo de conectividad, de forma que ésta se descarta si no existe ninguna forma en que el vehículo pueda haber transitado de la celda inicial a la propagada, dadas las restricciones topológicas, de velocidad del vehículo y temporales.

e.: Una vez realizado este proceso para todas las celdas, se determina la nueva zona íntegra transitable S’b como la intersección de Sb y S’ab (paso 310). Se comprueba que la solución existe (paso 311), en caso de no existir se inicializa el proceso y se genera una alarma, y en caso de existir se actualizan la posición y la información de integridad para la época siguiente (paso 311-B).

-: Se comprueba si se va a realizar un post-procesado (paso 312), y en caso afirmativo, con una periodicidad 'n' (donde 'n' puede ser igual a 1, es decir, cada vez que se proporciona una solución PVTI a partir de información GNSS, típicamente un segundo), se toma un arco de 'm' épocas (donde ‘m’ puede ser desde 1 hasta la totalidad del tiempo del recorrido), y se realiza el mismo procesado hacia atrás en el tiempo (paso 313), es decir, desde la época actual (t) hasta (t-m). De esta forma se eliminarán zonas que no se hayan podido descartar anteriormente.

En la figura 4 se muestra un ejemplo de cómo una celda transitable 401 se propaga a las celdas transitables 402 en una época posterior mediante el incremento de posición fab y su incertidumbre asociada correspondiente a la elipse de integridad Iab del incremento de posición.

En la Figura 5 se muestra un ejemplo de cómo se eliminarían o descartarían ciertas zonas transitables por razones de conectividad, al propagar la zona transitable entre dos épocas t1 y t2.

Así, teniendo en cuenta las restricciones en la dinámica del vehículo y la topología de las calles, se considera que el vehículo no ha podido recorrer el camino más corto existente entre el área transitable en t1 y el área propagada en t2 correspondiente a 501, por lo que dicha área se descarta. El área en t2 correspondiente a 502 se considera válida, ya que existe un camino que permite al vehículo haber transitado desde la zona en t1 hasta dicha zona.

En la figura 6 se muestra un ejemplo concreto de determinación de trayectoria mediante la invención:

-: El área 601 muestra el conjunto de celdas transitables a lo largo de la trayectoria, a partir del Nivel de Protección de posición.

5 -El área 602 muestra las celdas transitables (marcadas con una “x”) proporcionadas por la invención, antes del post-procesado. Se puede observar que la incertidumbre inicial, que abarca varios posibles viales, se va reduciendo a medida que se recorre la trayectoria.

-: El área 603 muestra las celdas transitables íntegras tras el post-procesado, junto con la trayectoria a lo largo de la calle (dada sin integridad).

10 La invención ha sido descrita según una realización preferida de la misma, pero para el experto en la materia resultará evidente que otras variaciones pueden ser introducidas sin exceder el objeto de la invención reivindicada.

Claims

REIVINDICACIONES

1. Un procedimiento de determinación de un vial o un conjunto de viales o zonas transitables recorridos por un usuario con una probabilidad mínima asociada o integridad, que comprende:

-

recibir de un sistema de posicionamiento información relativa a una primera y a una segunda soluciones de posición (PVT) de dicho usuario en un primer instante de tiempo ta y en un segundo instante tb posterior al primer instante ta, respectivamente, así como sendas elipses de integridad de posición, Ia e Ib (201), con sendas probabilidades mínimas asociadas, Pa y Pb, de que el usuario se encuentre en cada una de ellas en ta y en tb, respectivamente, y un incremento de posición fab (209) entre ta y tb con su elipse Iab de integridad de incremento de posición (204) y su probabilidad Pab asociadas;

-

obtener de un sistema de información geográfica GIS información sobre sendas zonas transitables TGIS correspondientes a dichas primera y segunda soluciones PVT;

-

determinar una primera área íntegra transitable Sa (202) y una segunda área íntegra transitable Sb (203) como intersección para cada instante de tiempo de dichas elipses de integridad de posición con dichas zonas transitables TGIS;

-

propagar dicha primera área íntegra transitable al instante posterior tb mediante el incremento de posición fab (209) entre los primer y segundo instantes de tiempo proporcionados por el sistema de posicionamiento, teniendo en cuenta la incertidumbre asociada a dicho incremento determinada por la elipse de integridad del incremento de posición Iab (204), obteniéndose una área íntegra propagada Sab (208);

-

eliminar de dicha área íntegra propagada Sab las zonas no transitables, obteniéndose una área íntegra transitable propagada S’ab (206);

-

determinar una área íntegra transitable final S’b compuesta por un vial o un conjunto de viales transitables en el segundo instante tb, bien como la menor entre dicha segunda área íntegra transitable Sb (203) y dicha área íntegra transitable propagada S’ab (206) o bien como la intersección de dicha segunda área íntegra transitable Sb (203) y de dicha área íntegra transitable propagada S’ab (206);

-

determinándose la probabilidad mínima P’b de que el usuario se encuentre en dicha área íntegra transitable final S’b en el segundo instante tb o nivel de integridad de S’b:

-

en caso de que dicha área íntegra transitable final S’b sea dicha segunda área íntegra transitable Sb (203), como la probabilidad Pb asociada a la elipse de integridad Ib de dicha segunda solución PVT, es decir, P’b = Pb;

-

en caso de que dicha área íntegra transitable final S’b sea dicha área íntegra transitable propagada S’ab (206), como el producto de la probabilidad Pa asociada a la primera área transitable Sa, dada por la elipse de integridad Ia de dicha primera solución PVT, y la probabilidad asociada a la elipse de integridad Iab correspondiente al incremento relativo de posición fab entre ta y tb, es decir, P’b = Pa . Pab;

-

en caso de que dicha área íntegra transitable final S’b se determine como la intersección de la segunda área íntegra transitable Sb (203) y dicha área íntegra transitable propagada S’ab (206), mediante la expresión: P’b ; Pa . Pab + Pb – 1.
2.

Un procedimiento según la reivindicación 1, que además comprende repetir el procedimiento definido en la reivindicación 1 para cada solución PVT proporcionada en cada instante ti, propagando el área íntegra transitable desde un instante anterior tj, determinando viales o zonas transitables y su probabilidad asociada en varios instantes consecutivos a lo largo de una trayectoria.
3.

Un procedimiento según las reivindicaciones 1 y 2, que además realiza un procesado adicional o post-procesado, con una periodicidad configurable y a lo largo de un arco de instantes configurable m, que comprende, para cada instante ti de dicho arco:

-

realizar la propagación del área transitable del instante ti, al instante inmediatamente anterior ti-1, mediante el incremento de posición entre ambos instantes, tomado en sentido contrario, y su elipse de integridad asociada, e intersecar con la zona transitable anteriormente calculada en ti-1, tal y como se define en la reivindicación 1;

-

realizar los pasos anteriores sobre todos los instantes del arco, de ti-1 a ti-2, de ti-2 a ti-3, ..., hasta ti-m, tal y como se define en la reivindicación 2, para así incluir a posteriori la información de zonas transitables en ti en los instantes anteriores.
4.

Un procedimiento según cualquiera de las reivindicaciones 1-3, en el que el sistema de posicionamiento es un

sistema GNSS, en el que el incremento de posición entre dos instantes de tiempo y su integridad son determinados mediante el incremento de la medida de fase de portadora de los satélites entre ambos instantes.
5.

Un procedimiento según la reivindicación 4, en el que el sistema de posicionamiento usado es un sistema GNSS hibridado con un sistema inercial Dead Reckoning.
6.

Un procedimiento según cualquiera de las reivindicaciones 1-3, en el que el sistema de posicionamiento es un sistema basado en comunicaciones inalámbricas y/o balizas, y configurado para proporcionar dicha información relativa a soluciones de posición (PVT), a incrementos de posición entre dos instantes de tiempo e información relativa a integridad asociada a tales soluciones PVT e incrementos de posición.
7.

Un procedimiento según cualquiera de las reivindicaciones 1-6, que además comprende realizar un chequeo de conectividad al propagar entre instantes y obtener el área transitable propagada, descartando aquella zona transitable (501) dentro de dicha área transitable propagada a la que no se puede haber accedido teniendo en cuenta restricciones temporales y de conectividad entre zonas.
8.

Un procedimiento según cualquiera de las reivindicaciones anteriores 1-7, en el que, si la probabilidad de que el usuario se encuentre en la zona transitable se ha degradado al cabo del tiempo y está por debajo de un umbral preestablecido, se reinicia el procedimiento y determina la zona transitable y su probabilidad asociada considerando solamente información relativa al instante en curso.
9.

Un procedimiento según cualquiera de las reivindicaciones 4, 5 o 7, que además comprende proporcionar una trayectoria continua recorrida por el usuario, basándose en medidas Doppler de los satélites GNSS, que determinan la velocidad instantánea del usuario y las restricciones de la dinámica del mismo.
10.

Un procedimiento según cualquiera de las reivindicaciones 1-9, que proporciona una solución en entornos de tres dimensiones, usando mapas 3D y las zonas en el espacio definidas por el elipsoide de integridad y su probabilidad asociada.
11.

Un procedimiento según cualquiera de las reivindicaciones 1-8, en el que se propagan las zonas transitables posibles mediante división de la zona transitable proporcionada por el sistema de información geográfica GIS en celdas transitables y no transitables.
12.

Un procedimiento según cualquiera de las reivindicaciones 1-8, en el que se propagan las zonas transitables posibles mediante división de la zona transitable proporcionada por el sistema de información geográfica GIS en polígonos que delimitan las áreas transitables.
13.

Un procedimiento según cualquiera de las reivindicaciones 1-8, en el que se propagan las zonas transitables posibles mediante traslación de segmentos, a los que se asigna una anchura determinada, y cuya distancia a otros segmentos se evalúa para determinar intersecciones y áreas transitables.