ES2649193T3 - Planificación de ruta - Google Patents

Planificación de ruta Download PDF

Info

Publication number
ES2649193T3
ES2649193T3 ES14736954.0T ES14736954T ES2649193T3 ES 2649193 T3 ES2649193 T3 ES 2649193T3 ES 14736954 T ES14736954 T ES 14736954T ES 2649193 T3 ES2649193 T3 ES 2649193T3
Authority
ES
Spain
Prior art keywords
vertex
vehicle
graph
path
route
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
ES14736954.0T
Other languages
English (en)
Inventor
Richard Edward SIMPSON
Arthur George Richards
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
BAE Systems PLC
Original Assignee
BAE Systems PLC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from EP13275163.7A external-priority patent/EP2827210A1/en
Priority claimed from GB1312586.9A external-priority patent/GB2516229A/en
Application filed by BAE Systems PLC filed Critical BAE Systems PLC
Application granted granted Critical
Publication of ES2649193T3 publication Critical patent/ES2649193T3/es
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/0206—Control of position or course in two dimensions specially adapted to water vehicles
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/20—Instruments for performing navigational calculations

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Traffic Control Systems (AREA)

Abstract

Método de determinación de rutas para al menos dos vehículos (4, 6), comprendiendo el método: medir, mediante un equipo de medida (20), una posición de un primer vehículo (4); medir, mediante el equipo de medida, una posición de un segundo vehículo (6); proporcionar, para uso por uno o varios procesadores (22), una especificación de una región (12), teniendo la región una posición fija con relación al primer vehículo; usar las medidas y la especificación de la región, realizando, por parte del o de los procesadores, un proceso de determinación de rutas para determinar una primera ruta para el primer vehículo (4) y una segunda ruta para el segundo vehículo (6); en que el proceso de determinación de rutas comprende: construir un grafo (34) dentro de un espacio de estado conjunto de los vehículos, comprendiendo el grafo una pluralidad de vértices y una o varias aristas conectando esos vértices; identificar, dentro del grafo construido, un camino desde un primer vértice del grafo a un segundo vértice del grafo, correspondiendo el primer vértice a las posiciones medidas de los vehículos, y correspondiendo el segundo vértice a que el segundo vehículo esté localizado al menos parcialmente dentro de la región; y, usando el camino identificado, determinar rutas para los vehículos, proporcionando con ello las rutas primera y segunda.

Description

5
10
15
20
25
30
35
40
45
50
DESCRIPCION
Planificacion de ruta CAMPO DE LA INVENCION
La presente invencion se refiere a determinar rutas coordinadas para una pluralidad de vehuculos.
ANTECEDENTES
Los vehuculos autonomos son usados a menudo para llevar a cabo tareas peligrosas, repetitivas o que consumen mucho tiempo.
Pueden usarse multiples vehuculos autonomos interactuantes para conseguir un objetivo comun.
Durante ciertas tareas puede ser deseable o necesario que dos o mas de los vehuculos autonomos realicen un enlace, es decir se muevan de tal modo que un vehuculo autonomo este situado dentro de una region que tiene una posicion fija con relacion a un vehuculo autonomo diferente. Un enlace entre dos o mas vehuculos puede tener lugar, por ejemplo, con el fin de una transferencia de combustible o cargamento entre los vehuculos autonomos, de transporte de un vehuculo autonomo por otro, o de la realizacion de reparaciones.
Muchos algoritmos convencionales para determinar caminos o rutas para vehuculos tienden a no ser capaces de determinar rutas que proporcionen enlaces entre multiples vehuculos. El documento US8150621 esta dirigido a un sistema operativo para proporcionar control de un vehuculo no tripulado.
SUMARIO DE LA INVENCION
El presente inventor ha hallado que pueden procurarse enlaces entre multiples vehuculos usando un proceso de planificacion de caminos que tenga en cuenta incertidumbre en la localizacion futura de los multiples vehuculos. El presente inventor ha hallado que pueden procurarse enlaces entre multiples vehuculos usando planificadores de estado de confianza (belief state) para planificar rutas de modo que se tenga en cuenta la incertidumbre de localizacion de multiples vehuculos.
El presente inventor ha hallado que planificando rutas para enlaces entre multiples vehuculos de modo que se tenga en cuenta la incertidumbre de localizacion de multiples vetuculos, la probabilidad de un fallo de las rutas determinadas tiende a reducirse.
En un primer aspecto, la presente invencion proporciona un metodo de determinacion de rutas para al menos dos vehuculos, comprendiendo el metodo: medir, mediante un equipo de medida, una posicion de un primer vehuculo; medir, mediante el equipo de medida, una posicion de un segundo vehuculo; proporcionar, para uso por uno o varios procesadores, una especificacion de una region, teniendo la region una posicion fija con relacion al primer vehuculo; usar las medidas y la especificacion de la region, realizando, por parte del o de los procesadores, un proceso de determinacion de rutas para determinar una primera ruta para el primer vehuculo y una segunda ruta para el segundo vehuculo; en que el proceso de determinacion de rutas comprende: construir un grafo dentro de un espacio de estado conjunto de los vehuculos, comprendiendo el grafo una pluralidad de vertices y una o varias aristas conectando esos vertices; identificar, dentro del grafo construido, un camino desde un primer vertice del grafo a un segundo vertice del grafo, correspondiendo el primer vertice a las posiciones medidas de los vehuculos, y correspondiendo el segundo vertice a que el segundo vehuculo este localizado al menos parcialmente dentro de la region; y, usando el camino identificado, determinar rutas para los vehuculos, proporcionando con ello las rutas primera y segunda.
El metodo puede comprender ademas controlar, por parte de un controlador de vehuculo acoplado operativamente al o los procesadores, los vehuculos de modo que el primer vehuculo siga la primera ruta y el segundo vehuculo siga la segunda ruta, procurando con ello que el segundo vehuculo este localizado al menos parcialmente dentro de la region.
El grafo puede ser un arbol.
El paso de construir el grafo puede comprender inicializar el grafo mediante la determinacion, usando las posiciones medidas de los vehuculos, del primer vertice del grafo, y realizar una o varias veces los pasos (i) a (iii), proporcionando con ello el grafo, en que: el paso (i) comprende muestrear el espacio de estado conjunto de los vehuculos para proporcionar otro vertice; el paso (ii) comprende proporcionar una arista que conecta el otro vertice a un vertice diferente del grafo; y el paso (iii) comprende incluir el otro vertice y las aristas en el grafo.
En algunos aspectos, para cada realizacion de los pasos (i) a (iii), una arista es incluida en el grafico solo si, en caso de que los vehfculos primero y segundo siguieran las rutas de vehuculo definidas por esa arista, cada vehuculo no colisionara con otro vehuculo u otro objeto distinto a un vehuculo.
5
10
15
20
25
30
35
40
45
50
55
El paso de identificar el camino desde el primer vertice al segundo vertice puede comprender: asignar, a uno o varios vertices dentro del grafo, uno o varios valores de confianza; propagar, a lo largo de cada camino en el grafo, los valores de confianza de modo que se asignen a cada vertice en el grafo uno o varios valores de confianza, correspondiendo cada valor de confianza asociado a un vertice en el grafo a un camino unico en el grafo que pasa a traves de ese vertice; y seleccionar, sobre la base de uno o varios de los valores de confianza, un camino desde el primer vertice al segundo vertice.
Un valor de confianza asignado al primer vertice puede ser indicativo de una incertidumbre asociada a las medidas de las posiciones de los vetnculos.
Para cada vertice en el grafo distinto al primer vertice, un valor de confianza asignado a ese vertice puede ser indicativo de una incertidumbre posicional de los vetnculos si los vetnculos siguieran una ruta especificada por un camino en el grafo desde el primer vertice a ese vertice.
El paso de propagar los valores de confianza puede comprender ajustar uno o varios valores de confianza para tener en cuenta otras medidas de una posicion de uno o ambos vetnculos tomadas por el equipo de medida.
Para cada vertice en el grafo distinto al primer vertice, un valor de confianza asignado a ese vertice puede ser indicativo de un valor de coste asociado a que los vetnculos sigan una ruta especificada por un camino en el grafo desde el primer vertice a ese vertice.
El paso de identificar el camino desde el primer vertice al segundo vertice puede comprender identificar, a partir de un conjunto de valores de confianza asignados al segundo vertice, el valor de confianza correspondiente al valor de menor coste, e identificar el camino desde el primer vertice al segundo vertice correspondiente al valor de confianza identificado.
El paso de, usando el camino identificado, determinar rutas para los vetnculos puede comprender aplicar un algoritmo de acortamiento de camino para el camino identificado de modo que sea proporcionado un camino acortado, y determinar rutas para los vetnculos especificadas por el camino acortado, proporcionando con ello las rutas primera y segunda.
El algoritmo de acortamiento de camino puede comprender: seleccionar un vertice a lo largo del camino identificado de modo que sea proporcionado un primer vertice de camino; seleccionar otro vertice a lo largo del camino identificado de modo que sea proporcionado un segundo vertice de camino, estando conectado el segundo vertice de camino al primer vertice de camino por al menos dos aristas; determinar un primer valor de coste, siendo indicativo el primer valor de coste de un coste asociado a un camino dentro del camino identificado desde el primer vertice de camino al segundo vertice de camino; proporcionar una arista adicional, teniendo la arista adicional como su vertice inicial el primer vertice de camino y como su vertice final el segundo vertice de camino; determinar un segundo valor de coste, siendo indicativo el segundo valor de coste de un coste asociado a un camino desde el primer vertice de camino al segundo vertice de camino a lo largo de la arista adicional; y dependiendo de los valores de coste primero y segundo, o bien: descartar la arista adicional y mantener el camino identificado; o bien modificar el camino identificado eliminando, del camino identificado, las aristas y los vertices en el camino identificado por el cual estan conectados el primer vertice de camino y el segundo vertice de camino, e incluyendo, en el camino identificado, la arista adicional.
Uno o varios de los vetnculos pueden ser un vetnculo no tripulado.
El equipo de medida puede comprender uno o varios sistemas de medida seleccionados del grupo de sistemas de medida que constan de: un sistema de radar, y un sistema de posicionamiento global.
El proceso de determinacion de rutas puede comprender un algoritmo de arbol de confianza aleatorio de exploracion rapida (en ingles “Rapidly-exploring Random Belief Tree”) para determinar la primera ruta para el primer vetnculo y la segunda ruta para el segundo vetnculo.
En otro aspecto, la presente invencion proporciona un metodo de determinacion de rutas para al menos dos vetnculos, comprendiendo el metodo: medir, mediante un equipo de medida, una posicion de un primer vetnculo; medir, mediante el equipo de medida, una posicion de un segundo vetnculo; proporcionar, para uso por uno o varios procesadores, una especificacion de una region, teniendo la region una posicion fija con relacion al primer vetnculo; usar las medidas y la especificacion de la region, aplicando, por parte del o de los procesadores, un algoritmo de arbol de confianza aleatorio de exploracion rapida para determinar una primera ruta para el primer vetnculo y una segunda ruta para el segundo vetfculo; en que las rutas primera y segunda son tales que, si el primer veltfculo siguiera la primera ruta, y el segundo vetnculo siguiera la segunda ruta, el segundo vetnculo estana localizado al menos parcialmente dentro de la region.
En otro aspecto, la presente invencion proporciona equipamiento para determinar rutas para al menos dos vetnculos, comprendiendo el equipamiento: un equipo de medida configurado para medir una posicion de un primer vetnculo y una posicion de un segundo vetnculo; y uno o varios procesadores acoplados al equipo de medida y configurados para, usando las medidas y usando una especificacion de una region que tiene una posicion fija con
5
10
15
20
25
30
35
40
45
relacion al primer vehnculo, realizar un proceso de determinacion de rutas para determinar una primera ruta para el primer vehnculo y una segunda ruta para el segundo vehnculo; en que el proceso de determinacion de rutas comprende: construir un grafo dentro de un espacio de estado conjunto de los vehnculos, comprendiendo el grafo una pluralidad de vertices y una o varias aristas conectando estos vertices; identificar, dentro del grafo construido, un camino desde un primer vertice del grafo a un segundo vertice del grafo, correspondiendo el primer vertice a las posiciones medidas de los vehnculos, y correspondiendo el segundo vertice a que el segundo vehnculo este localizado al menos parcialmente dentro de la region; y determinar rutas para los vehnculos especificadas por el camino identificado, proporcionando con ello las rutas primera y segunda.
En otro aspecto, la presente invencion proporciona un programa o una pluralidad de programas organizados de tal modo que cuando son ejecutados por un sistema de ordenador o por uno o mas procesadores, el/ellos hacen que el sistema de ordenador o el o los procesadores operen segun el metodo de cualquiera de los aspectos anteriores.
En otro aspecto, la presente invencion proporciona un medio de almacenamiento legible a maquina que almacena un programa o al menos uno de la pluralidad de programas segun el aspecto precedente.
BREVE DESCRIPCION DE LOS DIBUJOS
La figura 1 es una ilustracion esquematica (no a escala) de un escenario; la figura 2 es una ilustracion esquematica (no a escala) de una estacion de tierra;
la figura 3 es un diagrama de flujo de proceso que muestra ciertos pasos de una realizacion de un metodo para controlar vehnculos;
la figura 4 es un diagrama de flujo de proceso que muestra ciertos pasos de un proceso de determinacion de rutas;
la figura 5 es un diagrama de flujo de proceso que muestra ciertos pasos de un algoritmo de arbol de confianza aleatorio de exploracion rapida;
la figura 6 es una ilustracion esquematica (no a escala) que muestra un espacio de un estado conjunto de los vehnculos;
la figura 7 es una ilustracion esquematica (no a escala) que muestra rutas de vehnculo dentro del escenario; la figura 8 es una ilustracion esquematica (no a escala) que muestra un arbol construido;
la figura 9 es un diagrama de flujo de proceso que muestra ciertos pasos de un algoritmo de acortamiento de ruta; y la figura 10 es una ilustracion esquematica que muestra una parte de un camino con el arbol.
DESCRIPCION DETALLADA
La figura 1 es una ilustracion esquematica (no a escala) de un escenario 1 en el cual hay que implementar una realizacion de un metodo para controlar un grupo de vehnculos.
El escenario 1 comprende una estacion de tierra 2, un primer vehnculo 4, y un segundo vehnculo 6.
En el escenario 1, la estacion de tierra 2 esta localizada en la zona de tierra 8 adyacente a un cuerpo de agua 10 (por ejemplo un mar). La estacion de tierra es descrita en mas detalle mas adelante con referencia a la figura 2.
En el escenario 1, el primer vehnculo 4 es un vehnculo acuatico. En particular, el primer vehnculo 4 es un barco autonomo no tripulado que es controlable por la estacion de tierra 2, como se describe en mas detalle mas adelante con referencia a las figuras 3 a 10. El primer vehnculo 4 esta localizado en la superficie del cuerpo de agua 10 en una posicion que esta alejada de la zona de tierra 8.
En el escenario 1, el segundo vehnculo 6 es un vehnculo acuatico. En particular, el segundo vehnculo 6 es un bote autonomo no tripulado. En este escenario 1, el segundo vehnculo 6 es un vehnculo mas pequeno que el primer vehnculo 4. El segundo vehnculo 6 es el que es controlable por la estacion de tierra 2 como se describe en mas detalle mas adelante con referencia a las figuras 3 a 10. El segundo vehnculo 6 esta localizado en la superficie del cuerpo de agua 10 en una posicion que esta alejada de la zona de tierra 8 y alejada del primer vehnculo 4.
En este escenario 1, inicialmente el segundo vehnculo 6 ha sido transportado a bordo del primer vehnculo 4. El segundo vehnculo ha sido entonces lanzado desde el primer vehnculo 4. Tras ser lanzado desde el primer vehnculo 4, el segundo vehnculo 6 ha sido controlado (por ejemplo por la estacion de tierra 2) para llevar a cabo un estudio hidrografico en las cercamas del primer vehfculo 4. En otras realizaciones, los vehnculos 4, 6 pueden haber sido controlados para realizar un tipo de tarea diferente, tal como una tarea de busqueda y rescate, o una tarea de vigilancia.
5
10
15
20
25
30
35
40
45
50
Tras completar el estudio hidrografico, el segundo vehnculo 6 debe ser devuelto a bordo del primer vehnculo 4. Esto se consigue mediante el recurso de que los vehnculos primero y/o segundo 4, 6 se mueven de tal modo que el segundo vehnculo 6 esta situado completamente dentro de una region, o zona, sobre el cuerpo de agua 10. Esta region o zona es denominada a continuacion como “zona objetivo” y esta indicada en la figura 1 por una caja punteada y el numero de referencia 12. Una vez que el segundo vehnculo 6 esta localizado completamente dentro de la zona objetivo 12, un cabrestante u otro equipo de levantamiento que esta localizado a bordo del primer vehnculo 4 puede operar para levantar el segundo vehnculo 6 llevandolo sobre el primer vehnculo 4.
La zona objetivo 12 es una zona sobre la superficie del cuerpo de agua 10 que tiene una posicion fija con relacion al primer vehfculo 6. La zona objetivo 12 es una region sobre la superficie del cuerpo de agua 10 que esta proxima al primer vehfculo 4. La zona objetivo 12 es una region hacia dentro de la cual debe moverse el segundo vehfculo 6 de modo que el segundo vehfculo 6 pueda ser levantado con cabrestante llevandolo sobre el primer vehfculo 4.
Una realizacion de un metodo para controlar los vehfculos 4, 6 de modo que el segundo vehfculo este situado completamente dentro de la zona objetivo 12 es descrita en mas detalle mas adelante con referencia a la figura 3.
La figura 2 es una ilustracion esquematica (no a escala) que muestra la estacion de tierra 2.
En esta realizacion, la estacion de tierra 2 comprende un sistema de radar 20, un modulo de determinacion de rutas 22, un modulo de control de vehfculo 24 y un transceptor 26.
En esta realizacion, el sistema de radar 20 comprende una antena de radar 28 para transmitir y recibir senales de radar. El sistema de radar 20 esta configurado para transmitir, usando la antena de radar 28, una senal de radar hacia el cuerpo de agua 10 de modo que la senal de radar incida sobre los vehfculos 4, 6. Igualmente, el sistema de radar 20 esta configurado para recibir, usando la antena de radar 28, una senal de radar que ha sido reflejada desde el cuerpo de agua 10 y los vehfculos 4, 6.
El sistema de radar 20 esta conectado al modulo de determinacion de rutas 22 de modo que una senal puede ser enviada entre el sistema de radar 20 y el modulo de determinacion de rutas 22.
En esta realizacion, el modulo de determinacion de rutas 22 esta configurado para procesar una senal recibida por el modulo de determinacion de rutas 22 desde el sistema de radar 20. En esta realizacion, este procesamiento de senal realizado por el modulo de determinacion de rutas 22 es realizado para determinar una ruta para cada uno de los vehfculos 4, 6. El procesamiento de senal realizado por el modulo de determinacion de rutas 22 es descrito en mas detalle mas adelante con referencia a las figuras 3 a 10.
Adicionalmente a estar conectado al sistema de radar 20, el modulo de determinacion de rutas 22 esta conectado al modulo de control de vehfculo 24 de modo que una senal (por ejemplo una senal que especifica una salida del modulo de determinacion de rutas 22, por ejemplo una especificacion de una ruta para un vehfculo 4, 6) puede ser enviada entre el modulo de determinacion de rutas 22 y el modulo de control de vehfculo 24.
En esta realizacion, el modulo de control de vehfculo 24 esta configurado para procesar una senal recibida por el modulo de control de vehfculo 24 desde el modulo de determinacion de rutas 22. En esta realizacion, este procesamiento de senal realizado por el modulo de control de vehfculo 24 es realizado para determinar una senal de control para cada uno de los vehfculos 4, 6.
Adicionalmente a estar conectado al modulo de determinacion de rutas 22, el modulo de control de vehfculo 24 esta conectado al transceptor 26 de modo que una senal (por ejemplo una salida del modulo de control de vehfculo 24, por ejemplo una senal de control de vehfculo) puede ser enviada entre el modulo de control de vehfculo 24 y el transceptor 26.
En esta realizacion, el transceptor 26 esta configurado para transmitir, a los vehfculos 4, 6, senales de control de vehfculo que han sido recibidas por el transceptor 26 desde el modulo de control de vehfculo 24. En esta realizacion, el transceptor 26 transmite senales de control de vehfculo a los vehfculos 4, 6 a traves de un enlace de comunicacion inalambrica entre el transceptor 26 y cada uno de los vehfculos 4, 6.
En esta realizacion, cada uno de los vehfculos 4, 6 comprende equipamiento para recibir una senal de control de vehfculo desde el transceptor 26. Ademas, cada uno de los vehfculos 4, 6 comprende equipamiento para implementar acciones especificadas por una senal de control de vehfculo recibida.
La figura 3 es un diagrama de flujo de proceso que muestra ciertos pasos de una realizacion de un metodo para controlar los vehfculos 4, 6 de modo que el segundo vehfculo 6 este situado completamente dentro de la zona objetivo 12.
En el paso s2, el sistema de radar 20 de la estacion de tierra 2 transmite una senal de radar hacia el cuerpo de agua 10. La senal de radar transmitida incide sobre el primer vehfculo 4 y el segundo vehfculo 6.
En el paso s4, el cuerpo de agua 10, el primer vehfculo 4 y el segundo vehfculo 6 reflejan la senal de radar incidente de vuelta hacia el sistema de radar 20.
5
10
15
20
25
30
35
40
45
En el paso s6, el sistema de radar 20 recibe la senal de radar reflejada.
En el paso s8, el sistema de radar 20 envfa una senal correspondiente a la senal de radar recibida hacia el modulo de procesamiento 22.
En el paso s10, el modulo de procesamiento 22 procesa la senal recibida desde el sistema de radar 20 para determinar una ruta para cada uno de los vehnculos 4, 6.
La ruta determinada para el primer vehnculo 4 es denominada a continuacion “primera ruta”.
La ruta determinada para el segundo vehnculo 6 es denominada a continuacion “segunda ruta”.
En esta realizacion, las rutas primera y segunda son tales que, si el primer vehfculo 4 siguiera la primera ruta y el segundo vehnculo 6 siguiera la segunda ruta, el segundo vehnculo 6 estana completamente localizado dentro de la zona objetivo 12 (que tiene una posicion fija con relacion al primer vehnculo 4).
El proceso de determinacion de rutas que es realizado por el modulo de procesamiento 22 en el paso s10 es descrito en mas detalle mas adelante con referencia a la figura 4.
En el paso s12, el modulo de procesamiento 22 envfa una senal que especifica las rutas primera y segunda determinadas al modulo de control de vehnculo 24.
En el paso s14, el modulo de control de vehnculo 24 procesa la senal recibida desde el modulo de procesamiento 22 para determinar una senal de control de vehnculo respectiva para cada uno de los vehfculos 4, 6.
La senal de control de vehnculo determinada para el primer vehnculo 4 es denominada a continuacion “primera senal de control de vehnculo”.
La senal de control de vehnculo determinada para el segundo vehnculo 6 es denominada a continuacion “segunda senal de control de vehnculo”.
En esta realizacion, la primera senal de control de vehfculo es para controlar el primer vehfculo 4 de modo que el primer vehfculo 4 siga la primera ruta. Por ejemplo, la primera senal de control de vehnculo especifica instrucciones que, si son implementadas por el primer vehnculo 4, hacen que el primer vehnculo 4 siga la primera ruta.
Similarmente, la segunda senal de control de vehnculo es para controlar el segundo vehnculo 6 de modo que el segundo vehnculo 6 siga la segunda ruta. Por ejemplo, la segunda senal de control de vehfculo especifica instrucciones que, si son implementadas por el segundo vehnculo 6, hacen que el segundo vehnculo 6 siga la segunda ruta.
En el paso s16, el modulo de control de vehnculo 24 envfa las senales de control primera y segunda al transceptor 26.
En el paso s18, el transceptor 26 transmite las senales de control de vehnculo a los vehnculos 4, 6 relevantes.
En esta realizacion, el transceptor 26 transmite la primera senal de control al primer vehnculo 4, por ejemplo, a traves de un primer enlace de comunicaciones inalambricas. Similarmente, el transceptor 26 transmite la segunda senal de control al segundo vehfculo 6, por ejemplo, a traves de un segundo enlace de comunicaciones inalambricas.
En el paso s22, los vehnculos 4, 6 reciben las senales de control de vehnculo enviadas a ellos por el transceptor 26.
En el paso s24, cada uno de los vehnculos 4, 6 operan de acuerdo con la senal de control de vehfculo recibida por ese vehfculo.
En otras palabras, en esta realizacion, el primer vehfculo 4 opera de acuerdo con la primera senal de control y se le hace seguir la primera ruta. Similarmente, el segundo vehfculo 6 opera de acuerdo con la segunda senal de control y se le hace seguir la segunda ruta.
Despues de que el primer vehfculo 4 ha seguido la primera ruta y el segundo vehfculo 6 ha seguido la segunda ruta, el segundo vehfculo 6 esta localizado completamente dentro de la zona objetivo 12. De este modo, el segundo vehfculo 6 puede ser levantado llevandolo sobre el primer vehfculo 4 usando un equipo de cabrestante localizado sobre el primer vehfculo 4.
De este modo, se proporciona una realizacion de un metodo para controlar los vehfculos 4, 6 de modo que el segundo vehfculo 6 este localizado completamente dentro de la zona objetivo 12.
Volviendo ahora al paso s10 del proceso de la figura 3, la figura 4 es un diagrama de flujo de proceso que muestra ciertos pasos del proceso de determinacion de rutas realizado por el modulo de procesamiento 22 para determinar las rutas primera y segunda para los vehfculos primero y segundo 4, 6, respectivamente.
5
10
15
20
25
30
35
40
45
En esta realizacion, el proceso de determinacion de rutas es realizado para encontrar, para cada uno de los vehnculos 4, 6, una ruta de mmimo coste que, cuando esas rutas son seguidas por los vehnculos 4, 6, hacen que el segundo vehnculo 6 quede localizado completamente dentro de la zona objetivo 12. Un “coste” de una ruta puede expresarse en terminos de cualquier parametro apropiado, por ejemplo, una longitud de esa ruta (es decir la distancia que tiene que ser recorrida por un vehnculo que recorre esa ruta), un tiempo utilizado por un vehnculo para recorrer esa ruta, una cantidad de combustible usada por un vehnculo para recorrer esa ruta, o cualquier combinacion o funcion de esos parametros.
En esta realizacion, el modulo de procesamiento 22 comprende un filtro de Kalman lineal. Como se describe en mas detalle mas adelante, el modulo de procesamiento implementa 22 el filtro de Kalman para estimar un estado conjunto de los vehnculos 4, 6. Esta estimacion del estado conjunto de los vehnculos 4, 6 usa una serie de medidas de los vehnculos 4, 6 tomadas por el sistema de radar 20 sobre un periodo de tiempo en los pasos s2 a s6. Estas medidas de radar tienden a incluir ruido y otras inexactitudes.
En otras realizaciones, el modulo de procesamiento 22 comprende un filtro no lineal, tal como un filtro de Kalman extendido (EKF, del ingles “Extended Kalman Filter”) o un filtro de Kalman “unscented” (UKF, del ingles “Unscented Kalman Filter”), en vez de o de forma anadida al filtro de Kalman lineal.
En el paso s26, usando la senal correspondiente a la senal de radar recibida, recibida por el modulo de procesamiento 22, el modulo de procesamiento 22 produce una estimacion de un vector de estado conjunto inicial. El vector de estado conjunto inicial es un estado inicial de los vehnculos 4, 6. En esta realizacion, el vector de estado conjunto se define como:
X*=0 =
donde: xVi es un estado del vehnculo i-esimo; t es una dimension temporal universal dentro la que existen todos los estados de vehnculo; y
k es un paso de tiempo discreto del filtro de Kalman del modulo de procesamiento 22. En esta realizacion, k= 0 denota el paso de tiempo inicial del filtro de Kalman.
En esta realizacion, un estado de un vehnculo XVi esta definido como:
imagen1
imagen2
donde: Xi es una coordenada x del vehnculo i-esimo medida a partir de un origen que puede, por ejemplo, estar localizado en la estacion de tierra 2;
yi es una coordenada y del vehnculo i-esimo medida a partir de un origen que puede, por ejemplo, estar localizado en la estacion de tierra 2; y
9i es un rumbo del vehnculo i-esimo medido a partir de un rumbo de referencia, por ejemplo, norte.
En algunas realizaciones, un estado de un vehnculo XVi puede incluir uno o varios otros parametros de vehnculo (tales como una posicion z, una velocidad x, una velocidad y, una velocidad z, una altitud, un balanceo, un cabeceo, una guinada, una velocidad rotacional, un sesgo de sensor) en vez de o de forma anadida a uno o varios de los parametros de vehnculo anteriormente mencionados.
En algunas realizaciones, el parametro de tiempo t puede usarse para procurar que el vehnculo 4, 6 evite obstaculos dinamicos.
En algunas realizaciones, el parametro de tiempo t puede usarse (por ejemplo en sistemas de localizacion variables en el tiempo) para procurar que se tomen medidas de posicion de vehnculos solo en instantes en los que el sistema de localizacion tiende a ser suficientemente preciso.
20
25
30
35
40
Tambien, en realizaciones en las que un coste de una ruta de vetuculo esta relacionado con el tiempo, el parametro de tiempo t puede usarse para determinar un coste de una ruta de vetuculo.
En el paso s28, el modulo de procesamiento 22 calcula una covarianza del estado x*. En esta realizacion, la covarianza del estado x* esta definida como:
imagen3

P/1 0 0

0 p[2 0

0 0 p;
p r'
donde: ^ es una matriz de covarianza del vehiculo i-esimo;
10
T*j. es una matriz de covarianza del parametro de tiempo t; y 0 es una matriz de ceros.
En esta realizacion, una matriz de covarianza del vetuculo i-esimo
imagen4
es definida como:
imagen5
0 0
0 <T* 0
0 0 al
donde: Oxi es una varianza de la coordenada x del vetuculo i-esimo; Oxi es una varianza de la coordenada y del vetuculo i-esimo;
Oei es una varianza del rumbo del vetuculo i-esimo.
En el paso s30, el modulo de procesamiento aplica un algoritmo de arbol de confianza aleatorio de exploracion rapida (RRBT, del ingles “Rapidly-exploring Random Belief Tree”) que es extendido para calcular multiples rutas de vetuculo coordinadas que proporcionan multiples enlaces entre vetuculos. El algoritmo RRBT usado en esta realizacion esta descrito brevemente mas adelante con referencia a la figura 5. Informacion adicional sobre el algoritmo RRBT y un uso de el puede encontrarse, por ejemplo, en “Rapidly-exploring Random Belief Trees for Motion Planning Under Uncertainly", Bry, Adam y Nictiolas Roy, Proceedings of ttie 2011 IEEE International Conference on Robotics and Automation (ICRA 2011), 9-13 de mayo, 2011, que se incorpora aqu por referencia.
En esta realizacion, el algoritmo RRBT es aplicado para determinar una ruta inicial para cada uno de los vetuculos 4, 6 que, si fuera seguida por esos vetuculos, procurana que el segundo vetuculo 6 se moviera tiacia dentro de la zona objetivo 12.
En algunas realizaciones, puede usarse una alternativa al algoritmo RRBT para determinar las rutas de vetuculo iniciales.
En el paso s32, el modulo de procesamiento 22 aplica un “algoritmo de acortamiento de ruta” a una o varias de las rutas de vetuculo determinadas en el paso s30.
En esta realizacion, el algoritmo de acortamiento de ruta es aplicado para “suavizar” una o varias de las rutas de vetuculo iniciales con el fin de determinar las rutas de vetuculo primera y segunda. Este “suavizado” de una ruta de vetuculo inicial tiende a reducir la longitud de esa ruta inicial.
El algoritmo de acortamiento de ruta es descrito en mas detalle mas adelante con referencia a la figura 9.
En esta realizacion, una salida del algoritmo de acortamiento de ruta esta constituida por las rutas primera y segunda que tienen que ser enviadas desde el modulo de procesamiento 22 al modulo de control de vetuculo 24.
5
10
15
20
25
30
35
40
45
De este modo, se proporciona el proceso de determinacion de rutas.
Volviendo ahora al paso s30 del proceso de la figura 4, la figura 5 es un diagrama de flujo de proceso que muestra ciertos pasos del algoritmo RRBT aplicado por el modulo de procesamiento 22 para determinar rutas iniciales para los vetnculos 4, 6. En esta realizacion, este proceso es realizado para determinar las rutas iniciales para los vetnculos 4, 6 que, si fueran seguidas por esos vetnculos 4, 6, procuranan que el segundo vetnculo 6 se moviera hacia dentro de la zona objetivo 12.
En esta realizacion, el proceso de la figura 5 comprende construir un grafo (tal como se entiende en el campo de la teona de grafos). En esta realizacion, el grafo es un grafo dirigido conectado que comprende una pluralidad de vertices conectados entre sf por aristas. En otras realizaciones es construido un tipo apropiado diferente de estructura, por ejemplo, un grafo dirigido no dclico.
En esta realizacion, el grafo es construido en un espacio X de todos los posibles vectores de estado conjunto x.
En el paso s34, el grafo a construir es inicializado con un vertice unico y una confianza unica. Este vertice unico y la correspondiente confianza es un nodo rafz del grafo a construir.
En esta realizacion, el vertice unico que define el nodo rafz del grafo es la estimacion (o medida) del estado conjunto de los vetnculos 4, 6 producida en el paso s20, es decir xo.
En esta realizacion, la confianza que define el nodo rafz del grafo especifica la incertidumbre de la estimacion de xo, es decir Po. Tambien, en esta realizacion, la confianza que define el nodo rafz del grafo especifica un coste de camino inicial. Tambien, en esta realizacion, la confianza que define el nodo rafz del grafo especifica una distribucion de trayectorias que son dependientes de la controlabilidad de los vetnculos.
En esta realizacion, el vertice inicial xo es un punto dentro del espacio X. El vertice inicial xo especifica una posicion (es decir, una coordenada x y una coordenada y), y un rumbo para cada uno de los vetnculos 4, 6.
En el paso s36, un mdica a es igualado a 1, es decir a = 1.
En el paso s38, el espacio X es muestreado aleatoriamente con el fin de proporcionar un vertice a-esimo xa.
En esta realizacion, el vertice a-esimo xa es un punto dentro del espacio X. El vertice a-esimo xa especifica una posicion (es decir una coordenada x y una coordenada y), y un rumbo para cada uno de los vetnculos 4, 6.
En esta realizacion, el vertice a-esimo xa es un punto en el espacio X diferente a cada vertice previamente muestreado y al vertice inicial xo.
En el paso s4o, el vertice a-esimo xa es conectado al vertice distinto mas cercano en el espacio X (o a una pluralidad de vertices distintos mas cercanos en el espacio X). Esta conexion es una posible arista del grafo en construccion y es denominada a continuacion “arista a-esima”.
Por ejemplo, en la primera iteracion del proceso de la figura 5, el primer vertice xi esta conectado al vertice inicial xo. La conexion entre el primer vertice xi que esta conectado al vertice inicial xo es denominada a continuacion “primera arista”.
En esta realizacion, cada uno de los diferentes vertices dentro del espacio X especifica una posicion y rumbo diferentes para cada uno de los vetnculos 4, 6. De este modo, una conexion o arista entre dos vertices diferentes especifica una ruta para cada uno de los vetnculos 4, 6 desde una localizacion a otra localizacion diferente.
La figura 6 es una ilustracion esquematica (no a escala) que muestra una representacion del espacio X, el vertice inicial xo, el primer vertice xi, y la primera arista 3o (entre el vertice inicial xo y el primer vertice xi).
La figura 7 es una ilustracion esquematica (no a escala) que muestra el escenario 1, y rutas de vetnculo 32 para los vetnculos 4, 6 que son especificadas por la primera arista 3o.
En el paso s41, el modulo de procesamiento 22 determina, si los vetnculos 4, 6 siguieran las rutas especificadas por la arista a-esima, si uno o ambos vetnculos 4, 6 fueran o no a colisionar con un objeto (por ejemplo la zona de tierra 8 u otro objeto o terreno que los vetnculos 4, 6 no pueden atravesar) u otro vetnculo.
Por ejemplo, en la primera iteracion del proceso de la figura 5, el modulo de procesamiento 22 determina que los vetnculos 4, 6 son capaces de seguir las rutas de vetnculo 32 definidas por la primera conexion 3o como aquellas rutas 32 que son rutas a traves del cuerpo de agua 1o que evitan objetos que los vetnculos 4, 6 son incapaces de pasar por encima, cruzar o atravesar.
En esta realizacion, el proceso realizado en el paso s38 comprende implementar la siguiente ecuacion de propagacion de estado para estimar un movimiento de vetnculo a lo largo de las rutas de vetnculo:
5
10
15
20
25
30
40
imagen6
donde: F = I define un modelo de movimiento para los vetnculos 4, 6;
B = I define un modelo de control para los vetnculos 4, 6; u es un vector velocidad;
w es una perturbacion de proceso aleatoria para el vector velocidad u. En esta realizacion,
imagen7
En este realizacion, el movimiento y el control son independientes para cada elemento del espacio de estado.
En otras realizaciones, puede usarse un modelo de movimiento diferente para estimar un movimiento de vetnculo a lo largo de las rutas de vetnculo.
Puede usarse cualquier metodo apropiado para determinar si, en el caso de que los vetnculos 4, 6 siguieran las rutas especificadas por la arista a-esima, uno o ambos vetnculos 4, 6 fueran o no a colisionar con un objeto u otro vetnculo. Un metodo a modo de ejemplo para determinar si los dos vetnculos van a colisionar o no es como sigue. Puede usarse un metodo analogo para determinar si un vetnculo colisiona o no con un objeto distinto a un vetnculo.
En esta realizacion, cada vetnculo 4, 6 esta representado por un polfgono YVi respectivo. El polfgono i-esimo YVi representa el vetnculo i-esimo como un obstaculo dinamico.
La estimacion de un estado del vetnculo i-esimo (es decir la estimacion de XVi) se define como el baricentro del polfgono i-esimo YVi.
En esta realizacion, cada polfgono se define como un conjunto de vertices bidimensionales centrados en torno al baricentro de ese polfgono, es decir
imagen8
De este modo, un estado incierto de objeto de vetnculo puede definirse como una tupla, es decir TVi = (x Vi,PViYVi), donde xVi es la estimacion de xVi.
En esta realizacion, se supone que la incertidumbre en posicion de cualquier parte de un polfgono es la misma que la incertidumbre del baricentro de ese polfgono, es decir se asume que la incertidumbre de un punto en el polfgono YVi es PVi.
En esta realizacion se muestrea un borde exterior de cada polfgono. Cada punto muestreado en un borde exterior de un polfgono tiene una incertidumbre en posicion igual a la incertidumbre del baricentro de ese polfgono.
En esta realizacion, una distancia entre dos puntos muestreados adyacentes a lo largo de un borde del polfgono se define como:
imagen9
35
donde: Ai es el valor propio mas grande de la matriz de covarianza posicional del primer vetnculo 4;
42 es el valor propio mas grande de la matriz de covarianza posicional del segundo vetnculo 6; y n es un numero de variaciones estandar respecto a una media x.
En esta realizacion, puede detectarse una colision entre dos polfgonos determinando la distancia de Matialanobis entre dos elipses de covarianza, cada una de las cuales esta centrada en torno a un punto de muestreo a lo largo de un borde de un polfgono diferente.
En esta realizacion, la distancia de Matialanobis entre dos puntos de muestreo es:
imagen10
5
10
15
20
25
30
35
donde: i =1,...,N e x j =1,...,N e x /=1 g Y
m=1,...,
imagen11
N' es el numero de vetuculos;
K es el numero de puntos de muestreo en torno a un borde de un poKgono;
Y
es un vector de puntos de muestreo en torno a un borde de un polfgono; y
dVLV'
Lm es una distancia estadistica entre el punto de muestreo /-esimo en el poligono que representa el vehiculo /- esimo y el punto de muestreo m-esimo en el poKgono que representa el vetuculo j-esimo.
La distancia de Mahalanobis tiene una distribucion chi-cuadrado para variables aleatorias distribuidas normalmente. De este modo, en una realizacion se detecta una colision entre los poligonos i-esimo y j-esimo (es decir una colision
dVhVj < x2
entre los vehiculos i-esimo y j-esimo) si, para cada par (I, m), ^,m Vf. \ donde px es un intervalo de
probabilidad. Similarmente, en esta realizacion, no se detecta ninguna colision entre los poligonos i-esimo y j-esimo
(es decir ninguna colision entre los vetuculos i-esimo y j-esimo) si, para cada par (l, m),
d\
Vi,Vi > 2
m A p
En algunas realizaciones, objetos que tienen que ser evitados por los vetuculos pueden ser modelados como poligonos de un modo similar al descrito anteriormente para los vetuculos 4, 6. De este modo, pueden detectarse colisiones entre un objeto y un vetuculo.
En algunas realizaciones, si, por ejemplo, tiay incertidumbre significativa en una orientacion de vetuculo &, pueden tomarse muestras de polfgono para orientaciones dentro de un rango, por ejemplo
imagen12
donde: Op es un numero de desviaciones estandar respecto a la media x; y
P1'
1 e es la covarianza de la incertidumbre de rumbo del vehiculo i-esimo.
En esta realizacion, el cuerpo de agua 10 no contiene ningun objeto con el que pueda colisionar el vetuculo 4, 6. Sin embargo, en otras realizaciones, objetos asf pueden estar presentes en el cuerpo de agua 10. Ejemplos de objetos asf incluyen, pero no estan limitados a, rocas, islas, plataformas petrolfferas, y otros botes.
Si en el paso s41, el modulo de procesamiento 22 determina que, si los vetuculos 4, 6 siguieran la ruta especificada por la arista a-esima, uno o ambos vetnculos 4, 6 colisionanan con un objeto, el metodo pasa al paso s42.
Sin embargo, si en el paso s38 el modulo de procesamiento 22 determina que, si los vetuculos 4, 6 siguieran la ruta especificada por la arista a-esima, uno o ambos vetuculos 4, 6 no colisionanan con un objeto, el metodo pasa al paso s43.
En el paso s42, el vertice a-esimo Xa y la arista a-esima son descartados por el modulo de procesamiento 22. En esta realizacion, el vertice a-esimo Xa y la arista a-esima no son incluidos en el grafo en construccion.
Tras el paso s42, el metodo pasa de vuelta al paso s38, en el que el espacio X es remuestreado con el fin de proporcionar un nuevo vertice a-esimo xa.
Volviendo atiora al caso en el que el modulo de procesamiento 22 determina que, si los vetnculos 4, 6 siguieran la ruta especificada por la arista a-esima, uno o ambos vetuculos 4, 6 no colisionanan con un objeto, en el paso s43 el vertice a-esimo Xa y la arista a-esima son incluidos en el grafo en construccion.
5
10
15
20
25
30
35
40
45
En el paso s44, despues de que el vertice a-esimo Xa y la arista a-esima han sido anadidos al grafo en construccion, la confianza asociada al nodo ra^z (es decir la confianza asociada al vertice inicial X0) es propagada a lo largo de cada camino diferente dentro del grafo actual, produciendo con ello un arbol de confianzas.
En particular, en esta realizacion, la incertidumbre asociada a X0 (es decir P0) es propagada a traves del grafo actual, desde el vertice inicial X0 a cualquier otro vertice dentro del grafo actual, a lo largo de cada camino diferente dentro del grafo actual. Similarmente, el coste inicial asociado a X0 es propagado a traves del grafo actual, desde el vertice X0 inicial a cada otro vertice en el grafo actual, a lo largo de cada camino diferente dentro del grafo actual.
De este modo, tras la propagacion de confianza, en esta realizacion, cada vertice lleva asociada con el una o varias confianzas.
En particular, en esta realizacion, tras la propagacion de confianza, cada vertice en el grafo actual lleva asociada a el, para cada camino definido por el grafo actual que pasa a traves de ese vertice, una confianza. Una confianza correspondiente a un vertice y a un camino dentro del grafo especifica una incertidumbre de ese vertice (es decir una incertidumbre asociada a las posiciones y rumbos de vetnculo si ese camino fuera seguido por los vetnculos) y un coste de ese camino.
En esta realizacion, las confianzas del grafo y las aristas que conectan estas confianzas definen un “arbol de confianzas”. Cada una de las confianzas asociadas a los vertices del grafo actual es un “nodo de confianza” del arbol de confianzas.
La siguiente informacion es util para entender como una confianza (que en esta realizacion comprende una incertidumbre posicional, una distribucion de control y un coste de camino) es propagada a traves del grafo. Informacion adicional sobre la propagacion de confianzas puede encontrarse, por ejemplo, en el documento anteriormente mencionado “Rapidly-exploring Random Belief Trees for Motion Planning Under Uncertainty', que se incorpora aqrn por referencia.
Puede usarse una “funcion de propagacion” que toma como argumentos una arista y un nodo de confianza en el vertice de inicio para esa arista, y proporciona un nodo de confianza en el vertice final para esa arista.
Puede reducirse una incertidumbre de las posiciones y/o rumbos de los vetnculos 4, 6, por ejemplo, tomando medidas de los vetnculos 4, 6 mediante el sistema de radar 20. De este modo, puede reducirse una incertidumbre correspondiente a un vertice del arbol actual usando medidas de radar de los vetnculos 4, 6.
Tales medidas pueden ser tenidas en cuenta cuando se propagan confianzas a traves del arbol actual. En esta realizacion, un modelo basado en alcance lineal es usado para determinar una varianza del sistema de radar 20. En esta realizacion, el sistema de radar 20 esta localizado en el mismo espacio X que los vetnculos 4, 6. Un estado del sistema de radar 20 Xradar puede, por ejemplo, especificar una posicion global del sistema de radar 20, pero no especificar un rumbo.
En esta realizacion, medidas tomadas por el sistema de radar 20 del estado conjunto de los vetnculos 4, 6 se definen como:
imagen13
donde: H es un modelo de medida lineal; y vt es un ruido de medida.
En esta realizacion, H extrae, desde el espacio de estados, las coordenadas x e y de cada uno de los vetnculos 4, 6. En otras palabras, H elimina la orientacion y el tiempo del espacio de estados. En esta realizacion, el espacio de estados se define como:
imagen14
5
10
20
25
30
35
40
En esta realizacion, el ruido de medida vt esta distribuido como sigue:
imagen15
donde: ctz es una varianza de ruido del modelo de medida. En esta realizacion:
imagen16
Vi
donde " es una varianza de medida del vehiculo i-esimo. En esta realizacion:
imagen17
donde: rs es un factor de escala que puede ser ajustado en funcion de ciertas condiciones, por ejemplo condiciones ambientales del escenario 1 o parametros operativos del sistema de radar 20.
En esta realizacion, la precision del sistema de radar 20 disminuye isotropicamente al aumentar linealmente la distancia respecto al radar 20.
En esta realizacion, un obstaculo puede bloquear que una senal de radar procedente del sistema de radar 20 incida sobre uno de los vehmulos 4, 6. Por ejemplo, el primer vehmulo puede bloquear al menos parcialmente que una senal de radar procedente del sistema de radar 20 incida sobre el segundo vehmulo 6. En otras palabras, el primer vehmulo puede, efectivamente, apantallar el segundo vehmulo 6 respecto a una senal de radar transmitida por el sistema de radar 20.
En esta realizacion, ventajosamente, se tiene en cuenta este bloqueo de senal de radar. Esto puede conseguirse como sigue.
Primero, para cada vehmulo 4, 6 es especificada una lmea desde el sistema de radar 20 a ese vehmulo 4, 6.
Segundo, cada lmea especificada es analizada para ver si esa lmea corta o no un obstaculo, por ejemplo un objeto u otro vehmulo. Esto puede realizarse, por ejemplo, usando un algoritmo de interseccion lmea-lmea para comprobar si la lmea especificada corta un polfgono Y que representa un obstaculo.
En esta realizacion, una lmea entre el sistema de radar y un vehmulo 4, 6 que es cortada por un obstaculo indica que las senales de radar desde del sistema de radar hacia ese vehmulo 4, 6 son bloqueadas por ese obstaculo.
Tercero, para cada vehmulo
bloqueadas, la covarianza de ejemplo
4, 6 para el que las senales de radar procedentes del sistema de
medida para ese vehiculo
es igualada a un numero arbitrariamente
imagen18
radar estan grande, por
De este modo, una incertidumbre posicional puede propagarse a traves del arbol.
La siguiente informacion es util para entender como un coste es propagado a traves del arbol.
5
10
15
20
25
30
35
40
45
50
Un coste o funcion de coste puede ser representativo de un tiempo de recorrido para los vehnculos 4, 6, una distancia recorrida por los vehnculos 4, 6, una cantidad de combustible usada por los vehnculos, cualquier otro tipo apropiado de coste o funcion de coste o combinacion de ellos. Una funcion de coste puede propagarse desde un primer vertice del arbol actual a un segundo vertice del arbol actual, a lo largo de una arista en el arbol actual, tomando la funcion de coste del primer vertice, modificando esa funcion de coste para incluir los tiempos, la distancia, la cantidad de combustible, etc. que pueden ser usados por el vehnculo que recorre rutas especificadas por la arista entre el primer vertice y el segundo vertice, e igualando una funcion de coste del segundo vertice a la funcion de coste modificada.
En el paso s46, se determina si se satisfacen o no uno o varios “criterios de finalizacion”. En esta realizacion, un criterio de finalizacion puede ser cualquier criterio apropiado, por ejemplo, el criterio de que el mdice a es igual a un valor umbral B predeterminado. Tambien, por ejemplo, un criterio de finalizacion puede consistir en que un tiempo de computacion ha excedido un tiempo umbral T. Tambien, por ejemplo, un criterio de finalizacion puede consistir een que el numero de estados muestreados que corresponden a que el segundo vehnculo 6 esta completamente dentro de la zona objetivo 12 exceden un valor umbral M predeterminado.
Si, en el paso s46, se determina que no se satisfacen el o los criterios de finalizacion, el metodo pasa al paso s48.
Sin embargo, si en el paso s46 se determina que se satisface el criterio o cada uno de los criterios de finalizacion, el metodo pasa al paso s50.
En el paso s48, el mdice a es incrementado en 1, es decir a = a + 1.
Tras el paso s48, en esta realizacion, el metodo pasa de vuelta al paso s38, en el que el espacio X es muestreado aleatoriamente con el fin de proporcionar una nueva muestra.
Volviendo ahora al caso en el que se satisface el criterio o cada uno de los criterios de finalizacion, en el paso s50 se proporciona el arbol que ha sido construido, denominado a continuacion como “grafo final”.
La figura 8 es una ilustracion esquematica (no a escala) que muestra el grafo final 34 que ha sido construido en el paso s50. El grafo final 34 comprende una pluralidad de vertices muestreados (indicados por drculos negros uniformes en la figura 8) conectados entre sf por aristas (indicadas por lmeas que conectan los vertices).
En esta realizacion, cada vertice en el grafo final 34 corresponde a un estado x en el espacio X (es decir una posicion y rumbo para cada uno de los vehnculos 4, 6).
En esta realizacion, cada arista en el grafo final 34 corresponde a una ruta para los vehnculos 4, 6 a traves del cuerpo de agua 10 (entre posiciones correspondientes a aquellas representadas por los vertices que esa arista conecta).
De este modo, un camino a traves del grafo final 34, desde un vertice inicial a un vertice final, a lo largo de una serie de aristas del grafo final 34, define una ruta para los vehnculos 4, 6 a traves del cuerpo de agua 10 (entre posiciones correspondientes a aquellas representadas por el vertice inicial y el vertice final).
Tambien en esta realizacion, cada vertice en el grafo final 34 lleva asociado con el una o varias confianzas (o incertidumbres). En esta realizacion, cada confianza asociada a un vertice corresponde a un camino respectivo dentro del grafo final 34 que pasa a traves de ese vertice.
Para cada vertice y cada camino dentro del grafo final 34 que pasa a traves de ese vertice, la confianza asociada especifica una incertidumbre para ese vertice y ese camino (es decir una incertidumbre de las posiciones y rumbos de vetnculo si una ruta especificada por ese camino fuera seguida por esos vehnculos). Tambien, para cada vertice y cada camino dentro del grafo final 34 que pasa a traves de ese vertice, la confianza asociada especifica un coste para ese vertice y ese camino (es decir, un coste en el que incurrinan los vehnculos si recorrieran una ruta especificada por ese camino).
En el paso s52, son identificados el o los vertices en el grafo final 34 que corresponden a un estado en el que el segundo vehnculo 6 esta completamente localizado dentro de la zona objetivo 12.
En esta realizacion, el segundo vehnculo 6 esta completamente localizado dentro de la zona objetivo 12 si el polfgono que representa el segundo vehnculo YV2 esta situado completamente dentro de la zona objetivo 12 y no hay colision entre el polfgono que representa el segundo vehnculo YV2 y un lfmite de la zona objetivo 12. La determinacion de si hay o no una colision entre el polfgono que representa el segundo vehnculo YV2 y el lfmite de la zona objetivo 12 puede, por ejemplo, realizarse usando un metodo analogo al descrito anteriormente para determinar si un vehmulo 4, 6 colisiona o no con un objeto.
En el paso s54, a partir del conjunto de vertices identificados en el paso s52, es identificado el vertice que esta asociado a una confianza que especifica un valor de coste mmimo. La confianza asociada al coste mmimo es tambien identificada.
5
10
15
20
25
30
35
40
45
50
El vertice identificado en el paso s54 es denominado a continuacion “vertice final”.
La confianza identificada en el paso s54 corresponde al vertice final y tambien a un camino espedfico dentro del arbol 34 desde el vertice inicial xo al vertice final.
En el paso s56, es identificado el camino espedfico dentro del grafo final 34 desde el vertice inicial xo al vertice final que corresponde a la confianza identificada en el paso s54.
En el paso s58, son determinadas las rutas para los vehnculos 4, 6 a traves del cuerpo de agua que es especificado por el camino dentro del grafo final 34 que ha sido identificado en el paso s56.
Las rutas determinadas para los vehnculos 4, 6 son las rutas iniciales para los vehnculos 4, 6 que, si fueran seguidas por esos vehnculos 4, 6, procurartan que el segundo vehnculo 6 se moviera hacia dentro de la zona objetivo 12.
De este modo, se proporciona el proceso RRBT.
Volviendo ahora al paso s32 del proceso de la figura 4, la figura 9 es un diagrama de flujo de proceso que muestra ciertos pasos del algoritmo de acortamiento de ruta aplicado por el modulo de procesamiento 22 para reducir la longitud de rutas de vehnculo iniciales. En esta realizacion, el proceso de la figura 9 es realizado por el modulo de procesamiento 22.
En el paso s60, es identificado el camino dentro del grafo final 34 que corresponde a las rutas iniciales para los vehnculos 4, 6 (es decir, el camino identificado en el paso s56 del proceso de la figura 5).
En el paso s62, es seleccionado un vertice previamente no seleccionado a lo largo del camino identificado. En una primera iteracion del proceso de la figura 9, todos los vertices a lo largo del camino identificado son vertices previamente no seleccionados.
El vertice que es seleccionado es denotado por Xp. En esta realizacion, el vertice Xp seleccionado es conectado mediante una arista al siguiente vertice a lo largo del camino identificado, es decir Xp es conectado mediante una arista al vertice Xp+1.
En el paso s64, es seleccionado el vertice Xp+2.
En el paso s66, los vertices seleccionados son conectados mediante una arista. En otras palabras, el vertice Xp y el vertice Xp+2 son conectados mediante una arista. La arista que conecta el vertice Xp y el vertice Xp+2 es denominada a continuacion “nueva arista”.
La figura 10 es una ilustracion esquematica que muestra una parte del camino identificado en el paso s60 (que esta indicado en la figura 10 por el numero de referencia 36), el vertice Xp, el vertice Xp+2 y la nueva arista 38.
En esta realizacion, el camino 36 es un camino desde el vertice inicial Xp hasta el vertice final Xfinai. El vertice final Xfinai corresponde a un estado en el que el segundo vehnculo 6 esta localizado completamente dentro de la zona objetivo 12. Como se muestra en la figura 10, la nueva arista 38 proporciona un camino desde el vertice inicial Xo al vertice final Xfinai que evita el vertice Xp+1, es decir un camino que pasa a traves de los siguientes vertices en orden: X0, ..., Xp, Xp+2, ..., Xfinai.
En el paso s68, se determina si, en el caso de que los vehnculos 4, 6 siguieran las rutas especificadas por la nueva arista 38, uno o ambos vehnculos 4, 6 fueran a colisionar o no con un objeto (por ejemplo, la zona de tierra 8 u otro objeto o terreno a traves de los cuales no se pueden mover los vehnculos 4, 6) u otro vehnculo. En esta realizacion, este proceso de determinacion de colisiones es realizado del mismo modo que se ha descrito anteriormente en el paso s41 del proceso de la figura 5.
Si en el paso s68 se determina que, en el caso de que los vehnculos 4, 6 siguieran la ruta especificada por la nueva arista 38, uno o ambos vehnculos 4, 6 fueran a colisionar con un objeto, el metodo pasa al paso s74. El paso s74 sera descrito en mas detalle mas adelante tras una descripcion de los pasos s70 y s72.
Sin embargo, si en el paso s68 se determina que, en el caso de que los vehnculos 4, 6 siguieran la ruta especificada por la nueva arista 38, uno o ambos vehnculos 4, 6 no fueran a colisionar con un objeto, el metodo pasa al paso s70.
En el paso s70, la confianza asociada al nodo rafz (es decir la confianza asociada al vertice inicial X0) se propaga a traves del camino desde el vertice inicial X0 al vertice final Xfinai que evita el vertice Xp+1 (es decir, el camino desde el vertice inicial X0 al vertice final Xfinai proporcionado por la nueva arista 38). En esta realizacion, este proceso de propagacion de confianza es realizado del mismo modo que se ha descrito anteriormente en el paso s44 del proceso de la figura 5.
En el paso s72, se determina si el camino desde el vertice inicial X0 al vertice final Xfinai que evita el vertice Xp+1 (es decir el camino desde el vertice inicial X0 al vertice final Xfinai proporcionado por la nueva arista 38) es un camino de
5
10
15
20
25
30
35
40
45
50
menor coste que el camino desde el vertice inicial Xo al vertice final Xfinai que incluye el vertice Xp+i. Esto puede realizarse por ejemplo comparando los costes asociados a los dos caminos diferentes.
Si en el paso s72 se determina que el camino desde el vertice inicial Xo al vertice final Xfinai que evita el vertice Xp+i no es un camino de menor coste que el camino desde el vertice inicial Xo al vertice final Xfinai que incluye el vertice XP+i, el metodo pasa al paso s74.
Sin embargo, si en el paso s72 se determina que el camino desde el vertice inicial Xo al vertice final Xfinai que evita el vertice Xp+i es un camino de menor coste que el camino desde el vertice inicial Xo al vertice final Xfinai que incluye el vertice Xp+i, el metodo pasa al paso s76.
En el paso s74, la nueva arista 38 es descartada. Tras el paso s74, el metodo pasa al paso s78 que sera descrito en mas detalle mas adelante tras una descripcion del paso s76.
En el paso s76, la nueva arista 38 es incluida en el camino 36. Tambien, en esta realizacion, el vertice Xp+i es eliminado del camino 36. Tambien, en esta realizacion, las aristas en el camino 36 que estan conectadas al vertice Xp+i son eliminadas del camino 36. En otras palabras, la arista que conecta Xp a Xp+i y la arista que conecta Xp+i a
Xp+2 son eliminadas del camino 36. De este modo, el camino 36 es actualizado.
En el paso s78, se determina si todos los vertices en el camino actual han sido seleccionados previamente o no.
Si, en el paso s78, se determina que no han sido seleccionados todavfa todos los vertices en el camino actual, el metodo pasa de vuelta al paso s62 en el que es seleccionado un nuevo vertice previamente no seleccionado a lo largo del camino actual.
Sin embargo, si en el paso s78 se determina que todos los vertices en el camino actual han sido seleccionados previamente, el metodo pasa al paso s8o.
En el paso s8o, son determinadas las rutas para los vetnculos 4, 6 a traves del cuerpo de agua io que son especificadas por el camino actualizado actual.
Las rutas determinadas para los vetnculos 4, 6 son las rutas primera y segunda que deben ser enviadas por la
unidad de procesamiento 22 para uso por el modulo de control de vetnculo 24 en el paso si2.
De este modo se proporciona el algoritmo de acortamiento de ruta.
Ventajosamente se proporciona un metodo mediante el cual pueden ser controlados una pluralidad de vetnculos autonomos. El sistema y el metodo anteriormente descritos tienden a procurar un control coordinado de vetnculos. El sistema y el metodo anteriormente descritos tienden a permitir que los vetnculos sean controlados de modo que se haga que los vetnculos realicen un “enlace”, es decir que los vetnculos sean controlados de modo que un vetnculo este localizado dentro de una region que tiene una localizacion fija con respecto a otro vetnculo. Esto tiende a estar en contraste con metodos convencionales para controlar vetnculos autonomos que rtpicamente controlan un unico vetnculo de modo que ese vetnculo es movido a una localizacion que tiene una posicion fija global.
De este modo, el metodo y el equipamiento anteriormente descritos tienden ventajosamente a permitir un enlace coordinado entre vetnculos.
Ventajosamente, el sistema y el metodo anteriormente descritos pueden ser extendidos para controlar mas de dos vetnculos.
Ventajosamente, usando el sistema y el metodo anteriormente descritos para controlar vetnculos, tienden a evitarse colisiones entre esos vetnculos y colisiones entre un vetnculo y un objeto distinto a un vetnculo. El metodo anteriormente descrito incluye modelar una huella de vetnculo como un polfgono bidimensional, e incorporar una incertidumbre de localizacion contenida dentro de estados de confianza calculados por el modulo de procesamiento, de modo que son determinadas rutas de vetnculo para asegurar que los vetnculos no colisionan con otros vetnculos u objetos distintos a vetnculos.
Ventajosamente, el metodo y el sistema anteriormente descritos pueden usarse para determinar rutas para vetnculos que minimicen un coste (por ejemplo un coste temporal, un coste de distancia, un coste de combustible, o cualquier otra funcion de coste).
Ventajosamente, el metodo anteriormente descrito incluye usar medidas de las localizaciones de vetnculo (tomadas por el sistema de radar) para reducir la incertidumbre acerca de las localizaciones de vetnculo. Las rutas de vetnculo determinadas usando el sistema y los metodos anteriormente descritos tienden a pasar ventajosamente a traves de regiones en las que pueden hacerse medidas posicionales de los vetnculos de modo que se reduce la incertidumbre asociada a las posiciones de los vetnculos.
Ventajosamente, el sistema y el metodo anteriormente descritos tienden a tener en cuenta el bloqueo de medidas posicionales de un vetnculo, por ejemplo por otros vetnculos u objetos distintos a un vetnculo.
5
10
15
20
25
30
35
40
45
50
55
Ventajosamente, implementar el algoritmo de acortamiento de ruta anteriormente descrito tiende a modificar una ruta inicial de modo que se reduce un coste de distancia, un coste temporal, un coste de combustible, u otro coste de esa ruta inicial. En las realizaciones anteriores, las rutas iniciales son determinadas implementando el algoritmo RRBT. En algunas realizaciones, el algoritmo de acortamiento de ruta puede ser iterado multiples veces de modo que se modifica adicionalmente una ruta inicial para reducir adicionalmente el coste de la ruta.
Ventajosamente, implementar el algoritmo de acortamiento de ruta anteriormente descrito tiende a ser computacionalmente eficiente. De este modo, el algoritmo de acortamiento de ruta tiende a facilitar una planificacion de ruta y un control de vetnculos en tiempo real.
Ventajosamente, el sistema y los metodos anteriormente descritos tienden a tener en cuenta las diferentes dinamicas de cada vetnculo. Por ejemplo, un barco grande tiende a ser capaz de cambiar de direccion de forma relativamente lenta, mientras que un pequeno bote tiende a ser capaz de cambiar de direccion de forma relativamente rapida.
Ventajosamente, el sistema y los metodos anteriormente descritos tienden a ser utilizables con vetnculos que siguen un camino predefinido. El equipamiento, incluyendo el modulo de procesamiento, para implementar la disposicion anterior y realizar los pasos del metodo a describir mas adelante, puede ser proporcionado configurando o adaptando cualquier equipamiento adecuado, por ejemplo uno o varios ordenadores u otro equipamiento de procesamiento o procesadores, y/o proporcionando modulos adicionales. El equipamiento puede comprender un ordenador, una red de ordenadores, o uno o varios procesadores, para implementar instrucciones y usar datos, incluyendo instrucciones y datos en la forma de un programa de ordenador o una pluralidad de programas de ordenador almacenados en o sobre un medio de almacenamiento legible a maquina tal como una memoria de ordenador, un disco de ordenador, una memoria ROM (del ingles “Read-Only Memory”, memoria de solo lectura), una memoria PROM (del ingles “Programmable Read-Only Memory”, memoria programable de solo lectura), etc., o cualquier combinacion de estos u otros medios de almacenamiento.
Debe observarse que pueden omitirse algunos de los pasos de proceso representados en los diagramas de flujo de las figuras 3, 4, 5 y 9 y descritos anteriormente, o que tales pasos de proceso pueden realizarse en orden diferente al presentado anteriormente y mostrado en esas figuras. Ademas, aunque todos los pasos de proceso, por conveniencia y facilidad de comprension, han sido representados como pasos discretos temporalmente secuenciales, sin embargo algunos de los pasos de proceso de hecho pueden ser realizados simultaneamente o al menos solapandose en alguna medida temporalmente.
En las realizaciones anteriores, el metodo para controlar un grupo de vetnculos es implementado en el escenario descrito con referencia a la figura 1. Sin embargo, en otras realizaciones el metodo es implementado en un escenario diferente.
En las realizaciones anteriores, son calculadas rutas para dos vetnculos y son controlados esos dos vetnculos. Sin embargo, en otras realizaciones son determinadas rutas para un numero diferente de vetnculos (por ejemplo mas de dos vetnculos). Esos vetnculos pueden ser controlados entonces de modo que sean seguidas las rutas determinadas para esos vetnculos.
En las realizaciones anteriores, el metodo para controlar un grupo de vetnculos es implementado para mover los vetnculos de modo que el segundo vetnculo este completamente localizado dentro de la zona objetivo que tiene una localizacion fija con respecto al primer vetnculo. El tiectio de que el segundo vetnculo este completamente localizado dentro de la zona objetivo puede considerarse como un “estado objetivo” del sistema. Sin embargo, en otras realizaciones tiay un estado objetivo diferente. Por ejemplo, en otras realizaciones, el estado objetivo es un estado en el que el segundo vetnculo esta completamente localizado dentro de una primera zona objetivo que tiene una localizacion fija con respecto al primer vetnculo, y tambien el primer vetnculo esta completamente localizado dentro de una segunda zona objetivo que tiene una localizacion fija con respecto al segundo vetnculo. En otras realizaciones, puede tiaber multiples zonas objetivo definidas con respecto a multiples vetnculos diferentes. En algunas realizaciones, un estado objetivo puede ser un estado en el que cualquier numero apropiado de vetnculos estan localizados parcial o completamente dentro de una zona objetivo al mismo tiempo, o en instantes diferentes.
En las realizaciones anteriores, los vetnculos son vetnculos acuaticos (por ejemplo marinos) no tripulados. Sin embargo, en otras realizaciones, uno o varios de los vetnculos son un tipo de vetnculo diferente, por ejemplo, un vetnculo acuatico tripulado, un vetnculo terrestre tripulado o no tripulado, o una aeronave tripulada o no tripulada. En algunas realizaciones, uno o varios de los vetnculos pueden ser un tipo diferente de entidad, por ejemplo, un no vetnculo, por ejemplo un brazo o cabrestante robotico.
En las realizaciones anteriores, las medidas de los rumbos y posiciones de vetnculos son tomadas por el sistema de radar. Sin embargo, en otras realizaciones pueden usarse uno o varios tipos diferentes de medidas de los vetnculos en vez de o adicionalmente a las medidas de radar. Por ejemplo, en algunas realizaciones puede usarse una medida de GPS (del ingles “Global Positioning System”, sistema de posicionamiento global) de una posicion de vetnculo. Otros ejemplos de sensores apropiados que pueden usarse para tomar medidas de vetnculos incluyen, pero no estan limitados a, una camara de luz visible, una camara infrarroja, un sistema de LIDAR (del ingles “LIgtit raDAR”,
radar de luz), radiobalizas, una unidad de medida inercial, una brujula, un velodmetro marino, y un sensor ultra- sonico.
En algunas realizaciones, las medidas de los veldculos pueden ser tomadas desde multiples localizaciones diferentes. Por ejemplo, en algunas realizaciones, una pluralidad de sistemas de radar diferentes pueden tomar 5 medidas de los rumbos y posiciones de vehfculos. En algunas realizaciones, una medida puede ser tomada usando un sistema montado en vehfculo.
En las realizaciones anteriores, el escenario comprende una unica estacion de tierra. Sin embargo, en otras realizaciones se usan multiples estaciones de tierra.
En las realizaciones anteriores, la determinacion de las rutas de vehfculo es realizada en la estacion de tierra. sin 10 embargo, en otras realizaciones la determinacion de las rutas de vehfculo es realizada en una o varias localizaciones diferentes en vez de o adicionalmente a la estacion de tierra. Por ejemplo, en algunas realizaciones, la determinacion de las rutas de vehfculo puede ser realizada a bordo de uno o varios de los vehuculos. En algunas realizaciones, el proceso para determinar las rutas de vehfculo puede estar distribuido a traves de un numero de sistemas de procesamiento diferentes localizados en localizaciones diferentes.
15 En las realizaciones anteriores, el metodo para controlar los vehfculos comprende implementar el algoritmo de acortamiento de ruta anteriormente descrito. Sin embargo, en otras realizaciones, es omitido el algoritmo de acortamiento de ruta.

Claims (15)

  1. 5
    10
    15
    20
    25
    30
    35
    40
    45
    REIVINDICACIONES
    1. Metodo de determinacion de rutas para al menos dos vetnculos (4, 6), comprendiendo el metodo:
    medir, mediante un equipo de medida (20), una posicion de un primer vetnculo (4); medir, mediante el equipo de medida, una posicion de un segundo vetnculo (6);
    proporcionar, para uso por uno o varios procesadores (22), una especificacion de una region (12), teniendo la region una posicion fija con relacion al primer vetnculo;
    usar las medidas y la especificacion de la region, realizando, por parte del o de los procesadores, un proceso de determinacion de rutas para determinar una primera ruta para el primer vetnculo (4) y una segunda ruta para el segundo vetnculo (6); en que
    el proceso de determinacion de rutas comprende:
    construir un grafo (34) dentro de un espacio de estado conjunto de los vetnculos, comprendiendo el grafo una pluralidad de vertices y una o varias aristas conectando esos vertices;
    identificar, dentro del grafo construido, un camino desde un primer vertice del grafo a un segundo vertice del grafo, correspondiendo el primer vertice a las posiciones medidas de los vetnculos, y correspondiendo el segundo vertice a que el segundo vetnculo este localizado al menos parcialmente dentro de la region; y,
    usando el camino identificado, determinar rutas para los vetnculos, proporcionando con ello las rutas primera y segunda.
  2. 2. Metodo segun la reivindicacion 1, en el que el metodo comprende ademas controlar, por parte de un controlador de vetnculo (24) acoplado operativamente al o los procesadores (22), los vetnculos de modo que el primer vetnculo siga la primera ruta y el segundo vetnculo siga la segunda ruta, procurando con ello que el segundo vetnculo este localizado al menos parcialmente dentro de la region (12).
  3. 3. Metodo segun la reivindicacion 1 o 2, en el que el grafo (34) es un arbol.
  4. 4. Metodo segun cualquiera de las reivindicaciones 1 a 3, en el que el paso de construir el grafo comprende:
    inicializar el grafo mediante la determinacion, usando las posiciones medidas de los vetnculos, del primer vertice del grafo; y
    realizar una o varias veces los pasos (i) a (iii), proporcionando con ello el grafo; en que
    el paso (i) comprende muestrear el espacio de estado conjunto (X) de los vetnculos para proporcionar otro vertice;
    el paso (ii) comprende proporcionar una arista que conecta el otro vertice a un vertice diferente del grafo; y el paso (iii) comprende incluir el otro vertice y las aristas en el grafo.
  5. 5. Metodo segun la reivindicacion 4, en el que, para cada realizacion de los pasos (i) a (iii), una arista es incluida en el grafo solo si, en caso de que los vetnculos primero y segundo siguieran las rutas de vetnculo definidas por esa arista, cada vetnculo no colisionara con otro vetnculo u objeto.
  6. 6. Metodo segun cualquiera de las reivindicaciones 1 a 5, en el que el paso de identificar el camino desde el primer vertice al segundo vertice comprende:
    asignar, a uno o varios vertices dentro del grafo, uno o varios valores de confianza;
    propagar, a lo largo de cada camino en el grafo, los valores de confianza de modo que se asignen a cada vertice en el grafo uno o varios valores de confianza, correspondiendo cada valor de confianza asociado a un vertice en el grafo a un camino unico en el grafo que pasa a traves de ese vertice;
    y seleccionar, sobre la base de uno o varios de los valores de confianza, un camino desde el primer vertice al segundo vertice.
  7. 7. Metodo segun la reivindicacion 6, en el que:
    un valor de confianza asignado al primer vertice es indicativo de una incertidumbre asociada a las medidas de las posiciones de los vetnculos;
    5
    10
    15
    20
    25
    30
    35
    40
    45
    para cada vertice en el grafo distinto al primer vertice, un valor de confianza asignado a ese vertice es indicativo de una incertidumbre posicional de los vetnculos si los vetnculos siguieran una ruta especificada por un camino en el grafo desde el primer vertice a ese vertice; y
    el paso de propagar los valor de confianza comprende ajustar uno o varios valores de confianza para tener en cuenta otras medidas de una posicion de uno o ambos vetnculos tomadas por el equipo de medida.
  8. 8. Metodo segun la reivindicacion 6 o 7, en el que:
    para cada vertice en el grafo distinto al primer vertice, un valor de confianza asignado a ese vertice es indicativo de un valor de coste asociado a que los vetnculos sigan una ruta especificada por un camino en el grafo desde el primer vertice a ese vertice; y
    el paso de identificar el camino desde el primer vertice al segundo vertice comprende:
    identificar, a partir de un conjunto de valores de confianza asignados al segundo vertice, el valor de confianza correspondiente al valor de menor coste; e
    identificar el camino desde el primer vertice al segundo vertice correspondiente al valor de confianza identificado.
  9. 9. Metodo segun cualquiera de las reivindicaciones 1 a 8, en el que el paso de, usando el camino identificado, determinar rutas para los vetnculos (4, 6) comprende:
    aplicar un algoritmo de acortamiento de camino para el camino identificado de modo que sea proporcionado un camino acortado; y
    determinar rutas para los vetnculos especificadas por el camino acortado, proporcionando con ello las rutas primera y segunda;
    en que el algoritmo de acortamiento de camino comprende:
    seleccionar un vertice a lo largo del camino identificado de modo que sea proporcionado un primer vertice de camino;
    seleccionar otro vertice a lo largo del camino identificado de modo que sea proporcionado un segundo vertice de camino, estando conectado el segundo vertice de camino al primer vertice de camino por al menos dos aristas;
    determinar un primer valor de coste, siendo indicativo el primer valor de coste de un coste asociado a un camino dentro del camino identificado desde el primer vertice de camino al segundo vertice de camino;
    proporcionar una arista adicional, teniendo la arista adicional como su vertice inicial el primer vertice de camino y como su vertice final el segundo vertice de camino;
    determinar un segundo valor de coste, siendo indicativo el segundo valor de coste de un coste asociado a un camino desde el primer vertice de camino al segundo vertice de camino a lo largo de la arista adicional; y
    dependiendo de los valores de coste primero y segundo, o bien:
    descartar la arista adicional y mantener el camino identificado; o bien
    modificar el camino identificado eliminando, del camino identificado, las aristas y los vertices en el camino identificado por el cual estan conectados el primer vertice de camino y el segundo vertice de camino, e incluyendo, en el camino identificado, la arista adicional.
  10. 10. Metodo segun cualquiera de las reivindicaciones 1 a 9, en el que uno o varios de los vetnculos (4, 6) es un vetnculo no tripulado.
  11. 11. Metodo segun cualquiera de las reivindicaciones 1 a 10, en el que el equipo de medida comprende uno o varios sistemas de medida seleccionados del grupo de: un sistema de radar, y un sistema de posicionamiento global.
  12. 12. Metodo segun cualquiera de las reivindicaciones 1 a 11, en el que el proceso de determinacion de rutas comprende aplicar un algoritmo de arbol de confianza aleatorio de exploracion rapida para determinar la primera ruta para el primer vetnculo y la segunda ruta para el segundo vetnculo.
  13. 13. Equipamiento para determinar rutas para al menos dos vetnculos, comprendiendo el equipamiento:
    10
    15
    20
    un equipo de medida (20) configurado para medir una posicion de un primer vetnculo y una posicion de un segundo vetnculo; y
    uno o varios procesadores (22) acoplados al equipo de medida y configurados para, usando las medidas y usando una especificacion de una region (12) que tiene una posicion fija con relacion al primer vetnculo, realizar un proceso de determinacion de rutas para determinar una primera ruta para el primer vetnculo y una segunda ruta para el segundo vetnculo;
    en el que
    el proceso de determinacion de rutas comprende:
    construir un grafo (34) dentro de un espacio de estado conjunto (X) de los vetnculos, comprendiendo el grafo una pluralidad de vertices y una o varias aristas conectando estos vertices;
    identificar, dentro del grafo construido, un camino desde un primer vertice del grafo (34) a un segundo vertice del grafo (34), correspondiendo el primer vertice a las posiciones medidas de los vetnculos, y correspondiendo el segundo vertice a que el segundo vetnculo este localizado al menos parcialmente dentro de la region (12); y
    determinar rutas para los vetnculos especificadas por el camino identificado, proporcionando con ello las rutas primera y segunda.
  14. 14. Programa o pluralidad de programas organizados de tal modo que cuando son ejecutados por un sistema de ordenador o por uno o varios procesadores, el/ellos hacen que el sistema de ordenador o el o los procesadores operen de acuerdo con el metodo de cualquiera de las reivindicaciones 1 a 12.
  15. 15. Medio de almacenamiento legible a maquina que almacena un programa o al menos uno de la pluralidad de programas segun la reivindicacion 14.
ES14736954.0T 2013-07-15 2014-07-07 Planificación de ruta Active ES2649193T3 (es)

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
EP13275163.7A EP2827210A1 (en) 2013-07-15 2013-07-15 Route planning
GB1312586.9A GB2516229A (en) 2013-07-15 2013-07-15 Route planning
EP13275163 2013-07-15
GB201312586 2013-07-15
PCT/GB2014/052066 WO2015008033A1 (en) 2013-07-15 2014-07-07 Route planning

Publications (1)

Publication Number Publication Date
ES2649193T3 true ES2649193T3 (es) 2018-01-10

Family

ID=51162852

Family Applications (1)

Application Number Title Priority Date Filing Date
ES14736954.0T Active ES2649193T3 (es) 2013-07-15 2014-07-07 Planificación de ruta

Country Status (4)

Country Link
US (1) US9696160B2 (es)
EP (1) EP3022619B1 (es)
ES (1) ES2649193T3 (es)
WO (1) WO2015008033A1 (es)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
ES2649193T3 (es) 2013-07-15 2018-01-10 Bae Systems Plc Planificación de ruta
WO2019139815A1 (en) * 2018-01-12 2019-07-18 Duke University Apparatus, method and article to facilitate motion planning of an autonomous vehicle in an environment having dynamic objects
TWI822729B (zh) 2018-02-06 2023-11-21 美商即時機器人股份有限公司 用於儲存一離散環境於一或多個處理器之一機器人之運動規劃及其改良操作之方法及設備
WO2019183141A1 (en) 2018-03-21 2019-09-26 Realtime Robotics, Inc. Motion planning of a robot for various environments and tasks and improved operation of same
CN108717302B (zh) * 2018-05-14 2021-06-25 平安科技（深圳）有限公司 机器人跟随人物方法、装置及存储介质、机器人
US10809732B2 (en) * 2018-09-25 2020-10-20 Mitsubishi Electric Research Laboratories, Inc. Deterministic path planning for controlling vehicle movement
WO2020117958A1 (en) 2018-12-04 2020-06-11 Duke University Apparatus, method and article to facilitate motion planning in an environment having dynamic objects
CN109669459B (zh) * 2018-12-28 2022-05-10 西北工业大学 一种采用不变集的动态反馈路径规划方法
US11747149B2 (en) * 2019-04-01 2023-09-05 Robert Bosch Gmbh Method for operating a track guidance system
JP7511259B2 (ja) 2019-04-17 2024-07-05 リアルタイム ロボティクス， インコーポレーテッド モーション計画グラフ生成ユーザインターフェース、システム、方法、および物品
TWI873149B (zh) 2019-06-24 2025-02-21 美商即時機器人股份有限公司 用於多個機械手臂於共用工作空間中之移動規劃系統及方法
JP2023518071A (ja) 2020-03-18 2023-04-27 リアルタイム ロボティクス， インコーポレーテッド ロボットの動作計画に有用なロボット操作環境のデジタル表現
US11592843B2 (en) 2020-04-08 2023-02-28 Lockheed Martin Corporation Autonomous aircraft local planning to avoid obstructions
WO2021211420A1 (en) 2020-04-14 2021-10-21 Realtime Robotics, Inc. Configuration of robot operational environment including layout of sensors
WO2023074014A1 (ja) * 2021-10-29 2023-05-04 古野電気株式会社 船舶監視装置、船舶監視方法、及びプログラム

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040052239A1 (en) 2002-08-29 2004-03-18 Nesbitt David W. Automated route determination
US6819982B2 (en) * 2002-11-26 2004-11-16 The Boeing Company Uninhabited airborne vehicle in-flight refueling system
US7447593B2 (en) * 2004-03-26 2008-11-04 Raytheon Company System and method for adaptive path planning
US7228227B2 (en) * 2004-07-07 2007-06-05 The Boeing Company Bezier curve flightpath guidance using moving waypoints
US20070179685A1 (en) * 2005-09-29 2007-08-02 Mark Milam Trajectory generation using non-uniform rational B-splines
DE602006010988D1 (de) 2006-06-13 2010-01-21 Harman Becker Automotive Sys Bestimmung einer optimalen Route mittels einer Schätzungsfunktion
US8145369B1 (en) * 2007-11-01 2012-03-27 Vehicle Control Technologles, Inc. Docking apparatuses and methods
US8301318B2 (en) * 2008-03-05 2012-10-30 Robotic Research Llc Robotic vehicle remote control system having a virtual operator environment
US8150621B1 (en) * 2009-04-07 2012-04-03 The United States of America as represeneted by the Secretary of the Navy Command and control of autonomous surface vehicle
US8275493B2 (en) 2009-07-30 2012-09-25 Ruffa Anthony A Bow riding unmanned water-borne vehicle
US8930129B2 (en) 2009-11-18 2015-01-06 Telenav, Inc. Navigation system with multiple users and method of operation thereof
US8463534B2 (en) * 2010-11-13 2013-06-11 The Boeing Company Position/time synchronization of unmanned air vehicles for air refueling operations
ES2649193T3 (es) 2013-07-15 2018-01-10 Bae Systems Plc Planificación de ruta

Also Published As

Publication number Publication date
US9696160B2 (en) 2017-07-04
EP3022619B1 (en) 2017-09-27
US20160161257A1 (en) 2016-06-09
WO2015008033A1 (en) 2015-01-22
EP3022619A1 (en) 2016-05-25

Similar Documents

Publication Publication Date Title
ES2646269T3 (es) Planificación de rutas
EP3022619B1 (en) Route planning
Vasiljević et al. High-accuracy vehicle localization for autonomous warehousing
Paull et al. Sensor-driven area coverage for an autonomous fixed-wing unmanned aerial vehicle
Bonetto et al. irotate: Active visual slam for omnidirectional robots
Chakrabarty et al. Real-time path planning for multi-copters flying in UTM-TCL4
Pritzl et al. Cooperative navigation and guidance of a micro-scale aerial vehicle by an accompanying UAV using 3D LiDAR relative localization
Wheeler et al. Relative navigation of autonomous GPS-degraded micro air vehicles
Butzke et al. State lattice with controllers: Augmenting lattice-based path planning with controller-based motion primitives
Madridano et al. Obstacle avoidance manager for UAVs swarm
US10360805B2 (en) Operation control apparatus of movable body, method of controlling operation of movable body, and computer readable medium
Obermeyer et al. Sampling-based roadmap methods for a visual reconnaissance UAV
EP2827210A1 (en) Route planning
Weiss et al. Global real-time path planning for UAVs in uncertain environment
Yang et al. Omnidirectional-vision-based estimation for containment detection of a robotic mower
KR20210007064A (ko) LiDAR가 탑재된 FPGA 기반 드론 비행제어 시스템
Tang et al. Research on autonomous obstacle avoidance for indoor UAVs based on vision and laser
Newaz et al. Exploration priority based heuristic approach to uav path planning
Xie et al. Development of navigation system for autonomous vehicle to meet the DARPA urban grand challenge
Muthumanikandan Routing and Navigation among Aerial Obstacles Using Deep Learning and Depth Maps for Obstacle Routing in Unmanned Aerial Vehicles
Fitzgerald et al. Towards flight trials for an autonomous uav emergency landing using machine vision
GB2516230A (en) Route planning
Wretlind Design Specification Search and Rescue-Land
Raminedi Implementation Of Path Planning Methods To Detect And Avoid GPS Signal Degradation In Urban Environments
Semiriakov KEY PRINCIPLES OF TECHNOLOGY TRANSFER OF A SLAM-ORIENTED UAV PLATFORM FOR LIDAR MONITORING IN AGRICULTURAL SYSTEMS AND RADIATION CONTAMINATION ZONES