ES3015448T3 - System and global method for geolocation using imprecise distance and anchor position measurements - Google Patents

Abstract

La invención se refiere a un método global de geolocalización y a su sistema, que permite estimar la posición de los nodos en una red mediante la implementación de un paso en el que se minimiza (303) un criterio global que representa todas las mediciones de distancia entre nodos y las coordenadas de anclaje. La información de posición absoluta en la coordenada k del nodo Mi se obtiene con una incertidumbre (F). Se realiza una estimación conjunta de las coordenadas de los nodos que constituyen el vector de estado mediante la búsqueda del mínimo en el criterio cuadrático global, que considera todas las observaciones, mediciones de distancia y mediciones de anclaje disponibles, así como sus respectivas incertidumbres, traducidas por una matriz de covarianza sobre las mediciones de distancia y las coordenadas de anclaje. (Traducción automática con Google Translate, sin valor legal)

Description

DESCRIPCIÓN

Sistema global y procedimiento de geolocalización mediante mediciones imprecisas de distancias y posiciones de anclajes

La invención se refiere a un procedimiento global y a un sistema que permiten la geolocalización de uno (o más) objeto(s) a partir de mediciones de distancias, obtenidas mediante una función de medición de distancias entre nodos conocida por el término anglosajón "ranging", y de posiciones de anclaje imprecisas. El procedimiento permite determinar la posición de un objeto en un mapa, en un plano, en un sistema de referencia dado utilizando sus coordenadas geográficas, latitud/longitud u otras coordenadas.

La determinación de la posición de un objeto del que se conocen las distancias a otros objetos con posiciones conocidas es un tema clásico en el campo de la localización. En general, utilizamos estaciones de detección cuya posición es perfectamente conocida, o "anclajes". En este caso, la incertidumbre en el resultado de la posición reside principalmente en la precisión de las mediciones de distancia, denominadas a continuación "ranging".

Otro posible enfoque es determinar el posicionamiento relativo de nodos en una red de estaciones, basándose únicamente en información sobre las distancias relativas entre algunos o todos estos nodos. El conocimiento preciso de una cantidad limitada de información posicional a priori sobre determinados nodos puede utilizarse entonces para determinar la posición absoluta de todos los nodos de la red. Sin embargo, hay que superar una serie de obstáculos, entre ellos los siguientes:

• Todas las mediciones de distancia entre nodos no son necesariamente accesibles, debido al alcance de los módulos de ranging,

• Las mediciones de distancia están necesariamente sujetas a errores, lo que hace que la resolución geométrica esté potencialmente sobredeterminada,

• La información necesaria para el posicionamiento absoluto puede distribuirse entre las coordenadas de varios nodos,

• Por último, la información necesaria para el posicionamiento absoluto también puede estar sujeta a errores, potencialmente mayores que los asociados al ranging.

Este último punto es especialmente importante en la práctica, sobre todo en la navegación colaborativa. La información de posicionamiento absoluto de determinados nodos suele obtenerse mediante receptores del sistema de posicionamiento por satélite conocido por la abreviatura comercial GNSS (Global Navigation Satellite System) comerciales, cuyo error de posicionamiento puede, en condiciones de recepción difíciles, superar con creces los errores en las mediciones de distancia (ranging) entre nodos. Ignorar esta situación puede conducir a errores en el posicionamiento de los nodos libres, o incluso al rechazo de mediciones de ranging válidas que son incompatibles con las distancias calculadas a partir de posiciones absolutas que se suponen libres de errores.

Uno de los problemas técnicos planteados es encontrar una solución eficiente para el cálculo de las posiciones de los nodos, de forma que una métrica de las desviaciones entre las medidas de ranging y las distancias entre nodos en la solución sea mínima y teniendo en cuenta la incertidumbre asociada a los errores de ranging y a los errores absolutos de posicionamiento.

El estado de la técnica describe principalmente dos enfoques para abordar este problema.

Un primer enfoque consiste en reconstruir una geometría relativa de los nodos de una red a partir de información de ranging y, posiblemente, información angular entre nodos, por ejemplo mediante goniometría dentro de un nodo. Estos procedimientos suelen denominarse "localización sin anclaje". En este enfoque, que sólo utiliza mediciones de ranging, todas las posiciones de los nodos son libres, a priori, y los procedimientos tratan de ajustarlas de tal manera que el error cuadrático medio entre las distancias calculadas entre los nodos y las mediciones de ranging sea mínimo. Se ha propuesto un gran número de algoritmos, desde simples algoritmos de masa-resorte o “mass-spring” hasta técnicas de optimización más complejas, como la resolución de mínimos cuadrados de Newton-Raphson, el filtrado de partículas, etc. La mayoría de las variantes de este planteamiento intentan evitar la convergencia a un mínimo local, pero no la garantizan.

Un segundo enfoque pretende reconstruir la posición absoluta de los nodos de la red a partir de la información de ranging utilizando un conocimiento a priori de la posición de algunos de ellos, denominados "anclajes". El objetivo también es minimizar la desviación cuadrática media entre la distancia entre las posiciones de los nodos y las mediciones de ranging, con determinadas posiciones fijas y conocidas a priori. El problema consiste entonces en minimizar una función de las coordenadas de los nodos libres, por ejemplo utilizando un algoritmo de descenso más pronunciado. El artículo "Anchor-Based Three-Dimensional Localization Using Range Measurements", Wang, Vue et al, ilustra este enfoque que, sin embargo, no garantiza la obtención de un óptimo global. Otros trabajos teóricos proponen procedimientos de optimización global.

Un tercer enfoque utiliza fuentes externas o anclajes de posiciones desconocidas. El problema se conoce como "autocalibrado", cuyo objetivo es localizar tanto las fuentes como los sensores que las detectan. Se utilizan las diferencias de tiempo de llegada o TDOA, que proporcionan menos información que una medición directa del ranging, asimilable a un tiempo de llegada o TOA (abreviatura anglosajona de “TimeOfArrival”), y no hacen uso de información a priori sobre las posiciones de las fuentes. El artículo "Calibration-Free TDOA Self-Localization", Wendeberg Johannes et al, en Journal of Location Based Services, Mayo 2013, ilustra una posible implementación de este enfoque mediante varios algoritmos clásicos (del tipo masa-resorte, descenso gradiente, Gauss Newton...) o más específicos (algoritmo "Cone alignment"), siendo estos algoritmos conocidos por el experto en la materia.

Uno de los inconvenientes de la técnica anterior es que supone:

• Que todas las posiciones de los sensores sean libres, proporcionando sólo una geometría potencialmente exacta de todos los nodos, pero coordenadas relativas de los nodos entre sí,

• O bien que la determinación de la posición absoluta de los nodos se basa en el conocimiento externo de la posición de determinados nodos, cuya precisión se supone perfecta.

A priori, el estado de la técnica (véase el artículo << Centralized coopérative positioning and tracking with realistic communications constraints>>, Mensing C, Nielsen JJ, Proceedings of the 2010 7th Workshop on Positioning, Navigation, and Communication (WPNC2010) de 2010) no aborda la integración conjunta de la incertidumbre en la posición de los anclajes y el posible desafío a estas posiciones.

La figura 1 ilustra problemas no resueltos por la técnica anterior. En este ejemplo, las coordenadas de los anclajes asociadas a los nodos M<1>y M<2>se suponen idealmente accesibles, es decir, sin error, por ejemplo mediante levantamientos topográficos, mientras que las coordenadas del anclaje M<3>están en la práctica viciadas por un error d3, por ejemplo medido por un sistema GNSS, posicionando el anclaje M<3>en el punto M'<3>. Otro supuesto de esta ilustración es que la precisión de ranging es perfecta; en la práctica, el error es mucho menor que d3. En la figura 1, las mediciones de ranging se representan con una flecha. Las técnicas de la técnica anterior estiman incorrectamente la posición del nodo libre en M'<4>, la posición real del nodo libre M<4>distribuyendo los errores de ranging asociados a este nodo, lo que resulta en un gran mínimo de error cuadrático medio residual. Además, no se cuestiona la posición del nodo M<3>, que sigue siendo errónea.

El procedimiento según la invención presenta un procedimiento de estimación de posiciones de nodos basado en la minimización global de un criterio, consistente en la desviación cuadrática ponderada entre todas las medidas de distancia entre nodos de la red y las medidas de anclaje disponibles en un instante dado, y un modelo de medidas teóricas asociadas. El procedimiento utiliza un vector heterogéneo de medidas que incluye tanto las medidas de ranging entre nodos (medidas de distancia entre nodos) como las coordenadas de los anclajes, de las que tenemos un conocimiento impreciso. Por lo tanto, introducimos las coordenadas de anclaje como medidas adicionales de covarianza conocida, además de las medidas de ranging entre nodos en el vector de observación (también conocido como "vector de medición"). Al mismo tiempo, las coordenadas de los nodos asociados se introducen en el vector de estado que hay que estimar, para que puedan ser cuestionadas por el algoritmo de minimización. A continuación, el procedimiento consiste en estimar conjuntamente las coordenadas de los nodos que componen el vector de estado buscando el mínimo del criterio cuadrático global que tiene en cuenta todas las observaciones disponibles (medidas de ranging y medidas de anclaje) y sus respectivas incertidumbres (matriz de covarianza sobre las medidas de ranging y sobre las coordenadas de anclaje).

La invención se refiere a un procedimiento según las reivindicaciones independientes 1 y 12. Otras realizaciones se definen en las reivindicaciones dependientes.

Otras características y ventajas de la presente invención resultarán más claras a partir de la siguiente descripción de realizaciones de ejemplo, anexas a las figuras, que muestran:

• La Figura 1, una ilustración de los problemas de la técnica anterior,

• La Figura 2, un diagrama de una red de comunicaciones,

• La Figura 3, un diagrama de flujo que muestra las principales etapas del procedimiento según la invención, • La Figura 4, un ejemplo de implementación del procedimiento según la invención, y

• La Figura 5, un ejemplo del resultado después de implementar el procedimiento según la invención.

Para proporcionar una mejor comprensión del procedimiento según la invención, se da el siguiente ejemplo en el caso de un sistema de comunicación 1 que comprende varios nodos M<i>. Cada nodo Mi comprende, por ejemplo, un medio de comunicación 10, un procesador 12 adaptado para ejecutar las etapas del procedimiento según la invención y una batería 13 o dispositivo de alimentación. Los nodos M<i>se comunican entre sí, por ejemplo, a través de un enlace de radiofrecuencia, de forma inalámbrica, o por otros medios conocidos por el experto en la materia.

El sistema también incluye un dispositivo para determinar la posición absoluta de algunos o todos los nodos. Por ejemplo, todos o algunos de los nodos pueden estar equipados con un receptor 11 que, acoplado a un dispositivo de satélite 20, permite al nodo equipado con el receptor 11 geolocalizarse. Este dispositivo puede ser un sistema de geolocalización GPS (Global Positioning System), un GNSS (Global Navigation Satellite System) o un dispositivo topográfico. En la figura 2, el nodo M<2>está equipado con un receptor 11, mientras que el nodo M<3>no lo está.

También incluye un dispositivo de medición de distancia o dispositivo de ranging 21 coubicado, por ejemplo, en un nodo Mi o en cada uno de los nodos del sistema. Por ejemplo, el dispositivo de medición de la distancia puede adoptar la forma de una tarjeta electrónica que lleva el nodo. En otra realización, esto podría ser una función del sistema de comunicación a nivel de nodo que mide el tiempo que tarda la onda de radio en transitar entre los nodos.

OM ¡ =

Sea un conjunto de N nodosMide posiciones : en tres dimensiones (3D) y ■>í en dos dimensiones (2D), las coordenadas se eligen, por ejemplo; en un sistema de referencia cartesiano siendo O el punto de origen elegido en este sistema de referencia.

La distancia entre dos nodosMi, Mj,d(M/,M/), se define mediante El conjunto de posiciones de los N nodosMien un instante t dado, P<i>(t)={M</>(t)}<¿=o..A>/<-i>se denomina "geometría actual".n¿jes una medida de distancia (ranging) obtenida entre el nodoM¿y el nodoMjmediante un dispositivo de medición específico (un módulo de ranging situado, por ejemplo, en el nodo) y conocido con una incertidumbre o<n>-<j>, correspondiente a una desviación típica de la medición.

Llamaremos "anclaje" o "medida de anclaje"<A>^<*>, información de la posición absoluta en la coordenada ke<•>si<■>ma del ;nodoMi,obtenida con la incertidumbre<J Akicorrespondiente a la desviación típica de esta coordenada. Esta información puede obtenerse por diversos medios, como levantamientos topográficos o receptores GNSS. La información sobre la posición de un anclaje varía en función del instante de la medición. Se trata de una función proporcionada en tiempo real por un dispositivo GPS, por ejemplo. Para simplificar la escritura, no se indica la hora. Un nodo con una medida de posición absoluta se denomina "nodo anclado". ;;Todas las coordenadas de un anclaje pueden ser conocidas a priori, o sólo en parte, por ejemplo, cuando la posición del nodo se determina examinando un mapa: si el nodo está situado en una carretera, podemos saber que el nodo está en una latitud dada sin conocer su longitud. ;;El procedimiento para estimar la posición de nodos, por ejemplo, en un sistema de comunicación implementa una etapa durante la cual se intenta minimizar un criterio global representativo del conjunto de medidas de ranging disponibles entre nodos, así como las coordenadas de los anclajes, la información de posición absoluta sobre la . .a k;pésima coordenada del nodo M¡ obtenida con una incertidumbreA l.;;Realizaremos una estimación conjunta de las coordenadas de los nodos que constituyen el vector de estado buscando el mínimo del criterio cuadrático global que tiene en cuenta todas las observaciones disponibles, medidas de ranging y medidas de anclaje, y sus respectivas incertidumbres traducidas por una matriz de covarianza sobre las medidas de ranging y sobre las coordenadas de anclaje. ;;Antes de detallar un ejemplo de realización, se da la forma del criterio global C(X) a minimizar. C(X) se escribe en la forma general: ;;; ; donde: ;;• T es la matriz transpuesta ;;• X es el vector de estado que contiene las coordenadas de los nodos cuya posición buscamos estimar, correspondientes a todas o algunas de las posiciones P(t)={M<¿>(t)}<¿=o..w-i>. Las coordenadas de los nodos para los que tenemos un anclaje impreciso se introducen en el vector desconocido X que hay que estimar, de forma que las coordenadas puedan modificarse en la búsqueda de la solución, ;;M<A>es = fR);• w<A>es el vector de medidas observadas que contiene todas las observaciones o medidas disponibles en el instante t considerado; en el caso general, se compone de dos vectoresRy A , donde : ;° El vectorRcontiene las mediciones de rangingr¡¡disponibles en ese instante t, ;;° El vectorAcontiene las medidas de anclaje<A>™<"’>disponibles en este instante t; estos datos son coordenadas de ciertos nodos llamados "anclados", coordenadas accesibles por medición, obtenidas por ejemplo por un sensor GNSS por objeto; ;( ü { X A ;MeS ( X ) = \ x ;'A Jes el vector del modelo de medición, que contiene las mediciones teóricas asociadas a las mediciones observadasMesy accesibles mediante cálculo; se compone, por tanto, de dos vectores: ;°D(X)es el vector de distancias teóricas correspondientes a R, calculadas a partir del vectorXy, en su caso, de un conocimiento a priori que se supone perfecto; las componentes de D(X) corresponden a las distancias entre nodos, entre dos nodos,d(Mi,Mj),;;° X<a>es el vector que contiene las coordenadas teóricas de los nodos para los que se dispone de medidas de anclaje; X<a>comprende todas o parte de las componentes del vector de estado X ; ;;• I es la matriz de covarianza global sobre todas las mediciones. Por tanto, incluye : ;;o La matriz de covarianza I<r>en las mediciones de ranging, que cuantifica la incertidumbre en cada medición de ranging y cualquier correlación estadística entre las mediciones de ranging. La precisión de la medición del ranging no es necesariamente idéntica para todas las mediciones (pueden utilizarse diferentes tecnologías para diferentes nodos), y cualquier información disponible sobre estas precisiones se explota explícitamente, ;o La matriz de covarianza I a sobre medidas de anclaje. Los términos diagonales de esta matriz son iguales ;a los cuadrados de las incertidumbresG A k'pero también es posible tener en cuenta las correlaciones entre errores en diferentes coordenadas: la matriz I<a>no es necesariamente diagonal, ;° Una matriz I<ar>que incluye términos cruzados resultantes de una posible correlación entre errores en las mediciones de ranging y en las coordenadas de anclaje. Si no hay correlación, estos términos cruzados son cero ( I AR=0). ;;Por tanto, la matriz de covarianzas se escribe de la siguiente forma general: sabiendo que los términos enI arpueden ser cero, y T denota la matriz transpuesta. ;;A continuación se da un ejemplo detallado de la realización de las etapas del procedimiento según la invención y se ilustra en la figura 3. En primer lugar, necesitamos un vector de estado, un vector de medidas y su matriz de covarianza. ;;• Vector de estado X - el vector X contiene las coordenadas de los nodos que el procedimiento tratará de estimar. En el caso más general, el vector X contiene por tanto las coordenadas de los N nodos de la red asociados a las posiciones P(t)={M</>(t)}</=o..w-i>.. ;;En 3D, el vector X tiene 3N componentes y se escribe X = (x<o>,y<o>,z<o>,x<i>,y<i>,z<i>,...,x<w - i>,y<w -i>,z<w - i>)<T>, ;;En 2D, el vector X tiene 2N componentes y se escribe X = (x<o>,y<o>,x<i>,y<i>,...,x<w - i>,y<w - i>)<T>. ;;En la práctica, puede haber casos especiales en los que no se intente localizar ciertos nodos o estimar ciertas coordenadas. En este caso, el vector X puede contener sólo una parte de las coordenadas de los N nodos. Sin embargo, si queremos que el procedimiento pueda modificar, en su búsqueda de soluciones, las posiciones de los nodos de los que tenemos información imprecisa ("anclajes"), las coordenadas de estos nodos deben introducirse en el vector de estado X a estimar. ;;Para la realización del procedimiento: ;;• Se determina el vector de medidasMes, 301, compuesto a su vez por dos vectores : ;;o El vectorRque contiene las medidas de rangingnjdisponibles en el instante en cuestión: nótese que el vectorRpuede ser sobredimensionado considerando el número máximo de medidas de ranging que pueden estar disponibles en un instante dado, típicamente N(N-1) medidas donde N es el número máximo de nodos (y contando las medidas bidireccionales i-j y j-i, i y j son los índices de dos nodos). En función de las mediciones disponibles, los índices correspondientes pueden completarse o no, ;;o El vector A que contiene las medidas de anclajeA'1, es decir, las coordenadas de los nodos para los quetenemos información a priori de incertidumbre conocida ("nodos anclados"); ;;• Se construye, 302, la matriz de covarianza sobre las medidas I , de : ;;o A partir de la matriz de covarianza I<r>sobre las mediciones de ranging; los términos diagonales de I<r>vienen dados por los valores de incertidumbreo2nj; si las mediciones de ranging no están correlacionadas entre sí, la matriz I<r>será una matriz puramente diagonal, ;o A partir de la matriz de covarianza Z<a>sobre las medidas de anclaje. Los términos diagonales de esta ;matriz son ¡guales a A i, la matriz Za no es necesariamente diagonal, ;o Una matriz Z<ar>que incluya los términos cruzados resultantes de cualquier correlación entre los errores en las mediciones de ranging y los errores en las coordenadas de anclaje. Si no hay correlación, estos términos cruzados son cero (Z<ar>=0), ;;con : ;;; ;;; Se minimiza, 303, el criterio C(X),C(X)=[Mes- Mes(X)TZ-1[Mes-Mes(X)], calculando ; vector del modelo de medición definido anteriormente, y ;Se determinan, 304, las coordenadas de los objetos al final de la etapa de minimización, tomando el vector solución X de la minimización del criterio, X=Arg Min[C(X)], el vector X que contiene las coordenadas de los objetos. ;;Bajo el supuesto de errores de medida gaussianos aditivos centrados de matriz de covarianzas Z conocida, el estimador que minimiza el criterio C(X) no es otro que el estimador de máxima verosimilitud de X, porque minimizarC(X)es equivalente a maximizar la verosimilitudprobabilidad(Mes\X).También se considera robusto, incluso en presencia de mediciones que se desvían de este modelo de error gaussiano. ;;Debido a la no linealidad de Mes(X), la minimización de C(X) no es inmediata y los algoritmos eficientes que minimizanC(X)son algoritmos iterativos conocidos por el experto. ;;Existen muchos algoritmos de minimización de criterio cuadrático que pueden utilizarse para estimar posiciones a partir de mediciones de ranging y anclaje (por ejemplo, algoritmo de gradiente, algoritmo de Newton-Raphson,...). ;Una variante de implementación utiliza algoritmos de Gauss-Newton, de los que se dice que presentan un buen compromiso entre coste computacional, eficiencia y robustez. Utilizan una expansión limitada del criterio a orden dos, pero desprecian uno de los dos términos del hessiano del criterio. La ecuación de iteración se escribe de la siguiente forma general: ;;X k ü = X k - a ( k ) H k ' j k;;donde ;;Xkes el vector de coordenadas de nodos estimado en la iteración k, ;; do en Xk, ;; es la matriz jacobiana sobre el vector de medidas teóricasMes(X),incluyendo el vector de medidas teóricas de distanciaD(X)y el vector Xa que contiene las coordenadas de los nodos "anclados" (e incluyendo todo o parte del vector de estado X), ;•a(k)es una etapa de optimización, constante o variable (a=1 para el algoritmo clásico de Gauss-Newton, pero muchas variantes utilizan etapas adaptativas destinadas a acelerar la convergencia, o bien a evitar quedarse atascado en un mínimo local). ;;Así, la ecuación de iteración del procedimiento para determinar el vector de coordenadas del nodo en la iteración k+1 a partir de la iteración k se expresa como: ;;; ; La nueva estimación Xk+1 resulta de la aplicación de una "fuerza restauradora" sobre el vector de desviación[Mes-Mes(X)]entre las medidas observadas y las medidas teóricas ya sean de ranging o de anclaje. ;;En el caso especial de un criterio cuadrático: ;;• Se aplica una matriz (no cuadrada y no diagonal en el caso general) al vector[Mes- Mes(X)],es decir, la minimización se hace globalmente y no nodo a nodo, o medida a medida. Esta matriz no es constante ni "libre" (salvo el coeficiente alfa), sino que resulta de un cálculo preciso en el que interviene la matriz jacobiana del vector de medidas teóricasMes(X). ;;En la práctica, puede observarse que las mediciones de ranging y las mediciones de coordenadas de anclaje se derivan a priori de sistemas de medición independientes, de modo que estas mediciones respectivas están la mayoría de las veces descorrelacionadas. En este caso particular, la matriz de covarianza es diagonal de bloques y se escribe ;;como ; en este caso, el criterioC(X)consiste en la suma de dos criterios: uno, denominado C<r>, sólo sobre las mediciones de ranging y el otro, C<a>, sólo sobre las mediciones de anclaje, con : ;;; ;;; Según una realización alternativa, la estimación del vector X que minimiza el criterio C(X), (303 figura 3) en su forma general, se obtiene iterativamente aplicando las etapas ilustradas en la figura 4: Etapa de inicialización, 401: la entrada es un vector inicial Xo que contiene las posiciones estimadas de los nodos, que pueden obtenerse de varias maneras: ;;a. Utilizando las posiciones estimadas resultantes de una aplicación anterior del procedimiento, ;b. Utilizando el resultado de un algoritmo de preposicionamiento subóptimo, por ejemplo el procedimiento descrito en la solicitud de patente del solicitante presentada el mismo día y titulada "procedimiento y sistema de geolocalización por cálculo directo de elementos de desplazamiento" o un algoritmo directo subóptimo sobre mediciones de ranging de pseudolinealización de PSL, ;c. De forma determinista, por ejemplo, utilizando información conocida sobre las coordenadas de determinados nodos. Normalmente, si se dispone de datos de anclaje para un nodo determinado, las coordenadas del vector X se inicializan mediante los datos de anclaje, ;d. Aleatoriamente (sorteo); para los nodos para los que no se dispone de mediciones de anclaje, se puede realizar un sorteo aleatorio en una zona o según una geometría predefinida; para los nodos para los que se dispone de datos de anclaje, se puede utilizar un sorteo aleatorio centrado en el anclaje y con una covarianza igual a la covarianza en el anclaje. Esta técnica permite inicializar el procedimiento en otro punto que no sea un cero del criterio C<a>vinculado a los anclajes, y evitar así quedarse atascado en mínimos locales. ;;También es posible mezclar estos enfoques: por ejemplo, utilizar coordenadas de anclaje para inicializar los nodos para los que estas coordenadas están disponibles, y utilizar un algoritmo de tipo PSL explotando mediciones de ranging (localización clásica en mediciones TOA) para los otros nodos. ;;Etapa 402 - el vector X que contiene las coordenadas de los puntos para una iteración k+1 se calcula a partir del vector obtenido en la iteración k anterior y un vector de recuerdo ponderado calculado de manera que disminuya el criterio: ;Calculating Xk+1 fromX k: Xk+1 = Xk a(k)AXk;;° Cálculo de la matriz jacobiana :;;■ la submatriz se obtiene derivando las medidas de distancia teóricas disponibles: así, el término l,mfd D;;de se obtiene derivando la |¡ésima medida de distancia entre objetos con respecto a la més¡ma componente del vector de estado a estimar, ;;La submatriz relativa a las medidas de anclaje sólo contiene ceros y unos. ;o Cálculo del vector "callback"AXk aaplicar minimizando: ;;dMes ;AXt - AMesk- AMe s t;ÓX ; J con AMk = Mes- Mes(Xk).Se trata de un problema lineal ponderado de mínimos cuadrados, cuya solución explícita se ha dado anteriormente: ;;; ;;; Según una realización variante, el problema se resuelve utilizando una descomposición de valor singular (SVD), cuyo detalle es bien conocido por el experto en la materia. Resolver por descomposición SVD tiene la ventaja de ser más ;;estable numéricamente y de tratar el caso de una matriz singular, que puede producirse cuando las mediciones de ranging o los datos de anclaje disponibles no son suficientemente numerosos. En este caso, el algoritmo se adaptará ajustando automáticamente determinadas variables del vector de estado. ;;o Cálculo del escalóna(k):este escalón puede ser : ;;■ Fijado de una vez por todas, cuál es la solución más barata (a=1 en el algoritmo original de Gauss-Newton), ■ Se ajusta en cada iteración, con el fin de converger lo más rápidamente posible: existen varios procedimientos publicados para determinar la etapa, como, por ejemplo, el procedimiento de Brent, el procedimiento de Levenberg-Marquardt, etc. Los procedimientos semiempíricos, que consisten en partir de un valor fijo y luego dividir por un coeficiente P hasta que el criterio disminuya (o se ranging un valor mínimo), suelen ser un buen compromiso entre el coste de cálculo y la rapidez de convergencia. ;;° Actualización estimada del vector:Xk+i = Xk a(k)AXk;;;Etapa 403 - Detención del procedimiento iterativo, que continúa hasta que se cumplen unas condiciones predefinidas, normalmente : ;;■ Criterio C(X) no decreciente de una iteración a la siguiente, es decir. C(Xk+i) > C(Xk), ;■ Disminución relativa del criterioC(X)por debajo de un umbral predefinido, es decir, (C(Xk+i) - C(Xk))Sseuil *C(Xk),■ Número máximo de iteraciones alcanzado,

■ Las posiciones estimadas ya no cambian lo suficiente de una iteración a la siguiente (|AX| < umbral), etc.

Se considera como solución final el vector X correspondiente al mínimo encontrado del criterio C(X) al final de las iteraciones, conteniendo las coordenadas estimadas de los nodos que intentábamos geolocalizar.

El procedimiento puede incluir una etapa adicional que compruebe la validez de esta solución final a partir del vector residual, por ejemplo comparando el criterio cuadrático residual C(X) con un umbral (prueba de "residuales" convencional que implica una prueba chi2), o buscando si el componente máximo del vector residual es mayor que un umbral (norma L1 del vector residual conocida por el experto).

Sin apartarse del ámbito de la invención, las etapas detalladas anteriormente se aplican en redes de comunicación en las que un nodo desempeña un papel maestro y también, en redes de comunicación descentralizadas, en las que cada uno de los nodos realiza las etapas del procedimiento.

La Figura 5 muestra el resultado del procedimiento aplicado al problema de juguete (Figura 1) con cuatro nodos Mi, M2, M3y M4, para los que sólo Mi, M2, M3 disponen a priori de información de posicionamiento ("anclajes"); en esta figura, los cuatro nodos están representados en un sistema de coordenadas cartesianas graduadas en metros. Los puntos Mi y M2 están anclados con gran precisión (por ejemplo, mediante un levantamiento topográfico con una precisión de 10 cm), el punto M3 está anclado pero su posición de anclaje se mide incorrectamente con un error de 20 m (por ejemplo, utilizando GNSS con una incertidumbre de 15 m en la desviación estándar) y el punto M4 no está anclado (no hay medios locales para medir la posición absoluta). En este caso, todos los nodos están equipados con un dispositivo de ranging local para medir la distancia a los demás nodos, con una incertidumbre de 50 cm de desviación estándar. Estos valores son meramente ilustrativos del procedimiento. En esta figura 5 :

• Los círculos llenos son las posiciones reales de los nodos M1, M2, M3, M4,

• Los diamantes huecos son las posiciones de los anclajes:

° las células de los nodos M1, M2 son casi idénticas a las posiciones verdaderas (muy poco error de posicionamiento, obtenido por ejemplo mediante un levantamiento topográfico),

° la del anclaje A<3>correspondiente a la posición del nodo M<3>está desplazada hacia abajo respecto a la posición real del nodo (alta incertidumbre en la medida del anclaje),

• Los cuadrados huecos son las posiciones estimadas por el procedimiento al final del procedimiento iterativo, • La cruz es la posición del nodo M<4>obtenida por un algoritmo clásico de localización de M<4>mediante medidas de ranging en los nodos M<1>, M<2>, M<3>(localización por TOA, con un algoritmo iterativo de Gauss-Newton) sin tener en cuenta las incertidumbres sobre las posiciones de estos "anclajes", que se suponen perfectamente conocidas. La posición estimada para el nodo M<4>con este algoritmo clásico está lógicamente sesgada debido al error de posicionamiento del nodo M<3>.

Se puede observar que la posición estimada del nodo M<4>al final del procedimiento está bien situada sobre la posición verdadera, al igual que las posiciones estimadas de los otros tres nodos, incluido el nodo M<3>cuyos datos de anclaje proporcionados eran sin embargo muy erróneos. Al introducir y explotar la noción de incertidumbre en las coordenadas de los anclajes, el procedimiento según la invención permite modificar la posición de los anclajes para lograr, en este caso teórico ideal, un error cuadrático muy bajo en las mediciones de ranging. En esta simulación, el procedimiento convergió en cinco iteraciones, partiendo de una inicialización realizada del siguiente modo:

• Para los nodos M<1>, M<2>, M<3>, inicialización en sus posiciones de anclaje (correcta para M<1>y M<2>, incorrecta para M<3>), • Para el nodo M<4>para el que no se dispone de información a priori, inicialización automática mediante un algoritmo subóptimo pseudo-lineal directo que utiliza mediciones de ranging en las posiciones de anclaje de los otros tres nodos.

El procedimiento descrito anteriormente permite calcular una solución para un conjunto dado de medidas de ranging R, y unas coordenadas de anclaje dadas recogidas en un vector A. Puede aplicarse de nuevo en cuanto se reciba un nuevo lote de nuevas medidas de ranging o nuevas coordenadas de anclaje, e incluso si las nuevas medidas disponibles no corresponden a los mismos nodos que los utilizados en el instante anterior. Gracias sobre todo a la utilización de la SVD, el algoritmo se adapta automáticamente a la naturaleza de las mediciones realmente disponibles en un instante dado.

En los casos en los que las posiciones de ciertos nodos son perfectamente conocidas (levantamientos topográficos precisos por ejemplo) o en los que no se desea cuestionarlas estimándolas, es posible sin embargo introducirlas en el vector de estados y en el vector de medidas como se ha descrito anteriormente, tomando la precaución de utilizar un valor de covarianza muy bajo sobre las coordenadas de estos anclajes en la matriz I<a>. En la práctica, esto llevará mecánicamente al algoritmo a no cuestionar estas coordenadas, ya que bastará una ligera desviación para aumentar drásticamente el subcriterio vinculado a las medidas de anclaje (C<a>en el caso no correlacionado). Un procedimiento menos costoso, que implica vectores y matrices de menor tamaño que los utilizados en el procedimiento general, consiste simplemente en no introducir estas coordenadas de nodos perfectamente conocidos en el vector de estados X que se desea estimar y en el vector de medidas A. Estos datos forman entonces parte de los parámetros fijos del algoritmo implicado en la función D(X) (vector de distancias teóricas), como en un procedimiento convencional que utiliza anclajes con posiciones que se suponen perfectamente conocidas. Estos datos forman entonces parte de los parámetros fijos del algoritmo implicado en la función D(X) (vector de distancias teóricas), como en un procedimiento convencional que utiliza anclajes de posición que se suponen perfectamente conocidas.

En ausencia de datos a priori, por imprecisos que sean, sobre las posiciones absolutas de cualquiera de los nodos de la red, el vector de mediciones se reduce entonces únicamente a las mediciones de ranging y las coordenadas georreferenciadas (absolutas) de los nodos no son observables; sólo pueden estimarse las posiciones relativas de los nodos entre sí. Sin embargo, el procedimiento descrito anteriormente sigue siendo aplicable, ya que el uso de la SVD en el cálculo del desplazamiento permite proporcionar una solución en la que determinados componentes permanecen fijos en el valor de inicialización. Sin embargo, en tal caso, una alternativa, menos costosa y que permite un mejor control de los nodos utilizados como puntos de referencia, consiste en reducir el vector de estado únicamente a componentes observables. Por ejemplo, en 2D, la capacidad de observación determinista del problema es tal que la solución de posicionamiento a partir únicamente de mediciones de ranging es indeterminada:

o Hasta un origen (x<0>,y<0>) (traslación),

o Hasta una rotación alrededor de X<o>,y<0>(simetría de revolución),

o Hasta de una simetría axial.

Así, para que el problema de estimación a partir de mediciones de ranging solo sea observable, podemos, por ejemplo, elegir dos nodos (0 y 1) como referencias del sistema de referencia local y considerar un vector de estado X que comprenda 2N-3 componentes :

■ Las coordenadas 2(N-2)=2N-4 de los (N-2) otros nodos (todos excepto los nodos 1 y 2) cuyas posiciones (x,y) en el sistema de referencia local serán estimadas,

■ La abscisa x1 (u ordenada y1) del nodo 1.

Así, el vector X a estimar corresponderá a las posiciones de los nodos 1 a N-1 en un sistema de referencia que tiene como origen el nodo 0 y como eje de abscisas (respectivamente de ordenadas) el eje que pasa por los nodos 0 y 1; se escribirá de la forma X =(x1,x2,y2,x3,y3,..xN-1,yN-1)T

Con esta elección del vector X, el problema se hace observable en 2D (si disponemos de las medidas de ranging adhoc), aunque siga siendo ambiguo debido a la simetría, lo que significa que la solución encontrada por el procedimiento tendrá una solución dual, simétrica respecto al eje de referencia fijo.

El procedimiento según la invención se basa en una formalización rigurosa de la optimización de los desplazamientos hacia la solución que minimiza el error cuadrático ponderado global, y la solución propuesta es óptima en el sentido de máxima verosimilitud bajo hipótesis no restrictivas (errores gaussianos centrados de covarianzas conocidas). Además, el procedimiento aprovecha al máximo la información disponible sobre la precisión de las mediciones de ranging, por lo que permite utilizar recursos de ranging muy heterogéneos dentro de la misma red. Del mismo modo, mediante el uso de matrices de covarianza en las coordenadas de anclaje, el procedimiento es capaz de tener en cuenta incertidumbres y correlaciones muy dispares entre las coordenadas de anclaje, que es el caso práctico de las coordenadas que emanan de receptores GNSS muy diferentes, o colocados en condiciones de recepción muy diferentes.

Claims (13)

REIVINDICACIONES

1. - Procedimiento para determinar la posición de uno o más objetos Mi capaces de moverse en una red, estando uno o más objetos provistos de una capacidad para medir la distancia a otros objetos de la red,caracterizado porquecomprende al menos las siguientes etapas:

-tienen coordenadas de puntos Ai y la incertidumbre sobre estas coordenadas que describen información sobre la posición de todos o algunos de los objetos a localizar, conocidos como objetos anclados,

- medir al menos una distancia entre objetos entre al menos uno o más pares de objetos Mi, Mj, con un valor de incertidumbre asociado a cada medición y realizar las etapas siguientes:

- Calcular un vector inicial de un vector de estado X que contenga las coordenadas de los objetos cuya posición buscamos estimar correspondientes a todas o parte de las posiciones P(t)={M/(t)}=<0..>w<-i>en un instante t ; - Calcular un criterioC(X)utilizando :

■ un vector de medidas observadasMes(301) que contiene todas las observaciones disponibles en el instante t considerado, está compuesto por:

° mediciones de distancia entre objetos disponibles para los objetos de posición que deben estimarse y,

° coordenadas de los llamados objetos anclados,

■ una matriz de covarianzas I (302) que represente la variación estadística sobre el vector de medidas, que comprenda al menos:

° una matriz de covarianzas que contiene las incertidumbres en las mediciones de distancia entre objetos disponibles para los objetos de posición a estimar y,

° una matriz de covarianza que contiene las incertidumbres sobre las coordenadas de los denominados objetos anclados,

■ un vector modelo de medicionesMes(X) que contiene las mediciones teóricas asociadas al vector de mediciones observadasM es,

- Minimizar este criterio C(X) (303) y determinar las coordenadas de la posición de uno o varios de dichos objetos correspondientes a este mínimo, (304) X=Arg Min[C(X)].

2. - Procedimiento según la reivindicación 1,caracterizado porquese utiliza un criterio C(X) definido como sigue:

i- A -ir r A -<C (X ) =>M es-M es(X)<XT>1Mes-Mes(X)

donde:

■ T es la matriz transpuesta,

( R s

Mes =

\.A J(301) es el vector de medidas observadas compuesto por:

o Un vectorRque contiene las medidas de rangingn¡disponibles en ese instante t,

$

o Un vectorAque contiene las medidas de anclaje ^ disponibles en ese instante, correspondientes a la

información de posición absoluta en la coordenada kés¡ma del nodoMi,obtenida con incertidumbreAi, correspondiente a la desviación típica de esta coordenada,

el vector modelo de medición compuesto por dos vectores D(X) y Xa donde :

° las componentes de D(X) corresponden a las distancias entre nodos, entre dos nodosd(Mi,Mj),° Xa comprende todos o algunos de los componentes del vector de estado X,

(302) es la matriz de covarianzas que comprende la matriz de covarianzas Xr que contiene las incertidumbres en las mediciones de ranging y la matriz de covarianzas I a que contiene las incertidumbres en las mediciones de anclaje, así como la matriz rectangular Z<ar>que contiene las covarianzas cruzadas entre estos dos tipos de mediciones.

3. - Procedimiento según la reivindicación 2,caracterizado porquepara definir la matriz de covarianzas Z<a>se tienen&

en cuenta las incertidumbres 4' en cada coordenada de los anclajes y su posible correlación, para definir la matriz de covarianza Z<r>se tienen en cuenta las incertidumbres en cada medida de ranging y su posible correlación y para definir la matriz Z<ar>se tienen en cuenta las posibles correlaciones entre los errores en las medidas de ranging y los errores en las coordenadas de los objetos anclados.

4. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porqueel vector de estados X se inicializa utilizando al menos uno de los procedimientos siguientes:

o de forma arbitraria y determinista,

o aleatoriamente, extrayendo valores para las coordenadas de los nodos,

o utilizando las posiciones estimadas resultantes de una aplicación anterior del procedimiento,

o utilizando la solución de procedimientos de resolución subóptima, como la pseudolinealización de PSL, u otros algoritmos de bajo coste,

o explotando elementos conocidos sobre las coordenadas de determinados nodos, como las coordenadas de anclaje de los objetos "anclados".

5. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porquela información de posición de los objetos anclados se obtiene mediante levantamientos topográficos o mediante un sistema GNSS en tiempo real.

6. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porqueel criterio C(X) se minimiza implementando un algoritmo de Gauss-Newton.

7. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porqueel vector X(k+1) para una iteración k+1 se obtiene a partir del vector X(k) obtenido en la iteración k anterior realizando un procedimiento lineal de mínimos cuadrados mediante descomposición de valores singulares.

8. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porquela condición de parada del procedimiento utiliza uno de los criterios siguientes:

- CriterioC(X)no decreciente de una iteración a la siguiente,

- Disminución relativa del criterio C(X) por debajo de un umbral predefinido,

- Número máximo de iteraciones alcanzado,

- Las posiciones estimadas ya no cambian lo suficiente de un instante a otro (|AX| < umbral).

9. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porqueun objeto se designa como maestro yporquedicho objeto está adaptado para ejecutar las etapas del procedimiento según una de las reivindicaciones 1 a 8 y centralizar los resultados.

10. - El procedimiento de una de las reivindicaciones 1 a 8,caracterizado porquecada objeto de la red está adaptado para realizar las etapas del procedimiento según una de las reivindicaciones 1 a 8.

11. - Procedimiento según una de las reivindicaciones precedentes,caracterizado porqueel objeto cuya posición se busca es un nodo de un sistema de comunicación.

12. - Dispositivo para determinar la posición de uno o más objetos Mi capaces de moverse en una red, estando uno o más objetos provistos de un dispositivo para medir la distancia entre nodos (21), comunicándose los nodos entre sí mediante un medio de comunicación (10),caracterizado porquecomprende al menos un procesador (12) adaptado para ejecutar las etapas del procedimiento según una de las reivindicaciones 1 a 11, un dispositivo (11,20) para medir la posición de los nodos.

13. - Dispositivo según la reivindicación 12,caracterizado porquelos nodos comprenden un módulo de comunicación por radiofrecuencia y la red es un sistema de comunicación (1).