ES2988121T3 - Planificación de ruta para un vehículo no tripulado - Google Patents

Abstract

Así, según algunos ejemplos de la materia objeto de la presente invención, para reducir el tiempo de planificación de la ruta, la información que se ha calculado previamente durante la planificación de una ruta se reutiliza durante la planificación de otras rutas posteriores. El uso de la indicación almacenada reduce el tiempo necesario para la planificación de la ruta y, por lo tanto, permite evaluar un mayor número de rutas opcionales dentro de un período de tiempo determinado. Esto puede ayudar a aumentar la velocidad y la suavidad de la maniobrabilidad del vehículo. (Traducción automática con Google Translate, sin valor legal)

Description

DESCRIPCIÓN

Planificación de ruta para un vehículo no tripulado

Campo técnico

El objeto de la presente descripción se refiere a la planificación autónoma de rutas.

Antecedentes

Un vehículo no tripulado (UV, por sus siglas en inglés), también denominado vehículo sin tripulación o vehículo autónomo (AV, por sus siglas en inglés), comprende una máquina motorizada que se desplaza integrando datos sensoriales con toma de decisiones basadas en ordenador, con el fin de controlar de manera autónoma el vehículo. Un UV se puede utilizar para desplazar personas al trabajo, así como para otras diversas tareas, tal como operar dentro de áreas que sean peligrosas o que no sea posible que los humanos accedan, p. ej., para traer suministros o maquinaria, realizar misiones peligrosas, o similares.

Una cuestión, relacionada con el funcionamiento de los vehículos no tripulados, tiene que ver con la planificación autónoma de una ruta desde un punto de partida, tal como una ubicación actual del UV, hasta un destino determinado, en particular cuando la zona a recorrer comprenda obstáculos infranqueables o zonas problemáticas que deban evitarse.

Un ejemplo de la técnica anterior se puede encontrar enel documento US-2008 059 015 A1,'SOFTWARE ARCHITECTURE FOR HIGH-SPEED TRAVERSAL OF PRESCRIBED ROUTES', donde se describen sistemas, métodos y aparatos para la navegación de alta velocidad. El trayecto y la ruta planificados proporcionan información que permite, además, al robot orientar los sensores para escanear preferentemente las áreas del entorno donde probablemente viajará el robot, reduciendo así la carga computacional impuesta al sistema

Descripción general

La descripción en la presente memoria se refiere a la planificación autónoma y eficiente de una ruta para un UV, y a dirigir el UV según la ruta. La ruta se planifica según un mapa de la zona que se recorre.

En algunas aplicaciones, tal como cuando se planifica una ruta para un UV, el mapa se puede generar en función de los datos obtenidos por uno o más sensores montados en el UV, y puede representar una región que rodee al UV. De este modo, el mapa podrá actualizarse a medida que avance el UV y haya nuevos datos disponibles. Dado que el UV suele estar en movimiento continuo durante la planificación de la ruta, la ruta debe planificarse en tiempo real, o casi en tiempo real, para evitar colisiones con obstáculos, retrasos en el avance del vehículo y otros problemas, que puedan resultar del avance del UV según un mapa anticuado.

Según algunos ejemplos del objeto de la presente descripción, planificar una ruta comprende determinar o recibir un punto de partida y un punto de destino. Entonces, se pueden planificar una multitud de rutas, llevando al vehículo desde su posición actual hasta una dirección deseada (p. ej., del destino), y se puede seleccionar la ruta más adecuada entre las rutas sugeridas. Una ruta adecuada puede ser una ruta que llegue o avance hacia el destino y, en algunos ejemplos, que también cumpla con requisitos, tales como requisitos relacionados con la hora de llegada o con la longitud de la ruta, evitar áreas o lugares prohibidos, y reducir situaciones no deseadas, tales como pendientes pronunciadas, zonas prohibidas, o similares.

Una cuestión relacionada con la planificación autónoma de rutas es que con el fin de evitar colisiones con obstáculos, retrasos en el avance del vehículo, u otros problemas derivados del avance del UV según un mapa anticuado, la ruta debe planificarse en tiempo real, o casi en tiempo real, una vez que esté disponible un mapa actualizado del área recorrida.

Por tanto, la ruta debe planificarse en plazos cortos. Mejorar la eficiencia de la planificación de rutas puede ayudar a lograr un mayor número de rutas opcionales en un período de tiempo predeterminado (p. ej., 0,05 segundos, 0,1 segundos, 0,5 segundos, 1 segundo, o similar), aumentando así la probabilidad de que se encuentren disponibles rutas adecuadas para seleccionar.

Por lo tanto, según el objeto de la presente descripción, con el fin de reducir el tiempo de planificación de la ruta, la información que se ha calculado previamente durante la planificación de una ruta, se reutiliza durante la planificación de otras rutas posteriores.

Según algunos ejemplos, se ejecuta un proceso de evaluación del estado del vehículo. El término “estado del vehículo” , tal como se utiliza en la presente memoria, se refiere a los parámetros de posicionamiento de un vehículo (p. ej., un vehículo terrestre no tripulado - UGV, por sus siglas en inglés), que incluyen una ubicación (posición) específica y el rumbo del vehículo. Durante el proceso de evaluación del estado del vehículo, se determina si ciertos estados del vehículo son viables o no, incluyendo si un vehículo puede posicionarse o no en un determinado estado del vehículo. El estado del vehículo puede considerarse viable si se cumplen determinadas condiciones. Por ejemplo, una condición puede requerir que el vehículo no colisione con un obstáculo cuando esté en el estado de vehículo, y otra condición puede requerir que los ángulos de balanceo y cabeceo del vehículo en el estado de vehículo cumplan con algunos criterios predefinidos (p. ej., se encuentren dentro de algunos valores umbral predefinidos). Si el estado del vehículo es viable, se pueden utilizar parámetros adicionales para evaluar la favorabilidad del estado del vehículo sobre otros estados del vehículo. La favorabilidad del estado de un vehículo se puede expresar en ponderaciones y se puede basar en parámetros tales como: proximidad del vehículo a obstáculos cercanos, ángulos de cabeceo y balanceo asumidos por el vehículo, si el vehículo está ubicado en un área restringida o no deseada, o similares. Después de la evaluación del estado de un vehículo, se pueden asociar una o más ponderaciones con el estado del vehículo, lo que indica la favorabilidad del estado del vehículo.

Se apreciará que cuando se planifican diferentes rutas, algunos segmentos de diferentes rutas pueden superponerse, por lo que se puede asumir el mismo estado del vehículo en tales segmentos de diferentes rutas. En consecuencia, los datos anteriores del estado del vehículo, incluido si el estado del vehículo es viable o no, y las ponderaciones asignadas, si las hay, después de evaluarse para un estado del vehículo en particular, se pueden almacenar para su recuperación futura, ahorrando así un valioso tiempo de cálculo y, opcionalmente, otros recursos informáticos, tales como potencia de procesamiento. La recuperación futura de datos del estado del vehículo se puede realizar al calcular rutas adicionales asociadas al mismo mapa, del cual se debe seleccionar una ruta adecuada. Alternativamente, la recuperación futura puede ejecutarse durante la planificación futura, por ejemplo, cuando se planifiquen rutas adicionales basadas en la misma actualización del mapa, o cuando se planifiquen rutas en un momento posterior después de que se reciban una o más actualizaciones adicionales de mapas.

Por lo tanto, la reutilización de los datos del estado del vehículo (en lo sucesivo, “ reutilización” ) puede contribuir a acortar el tiempo de procesamiento requerido durante la planificación de rutas y, en consecuencia, puede ayudar aún más a aumentar el número de rutas que pueden calcularse y evaluarse durante un período de tiempo asignado para planificar una ruta. Por lo tanto, la reutilización puede aumentar la probabilidad de encontrar una ruta más adecuada, mejorando así la navegación del vehículo, en lugar de no ejercer la reutilización. La reutilización se puede implementar cuando dos o más rutas comprendan al menos un segmento superpuesto.

Una vez que se ha seleccionado una ruta adecuada, se pueden determinar las instrucciones de dirección, y el vehículo se puede dirigir según la ruta seleccionada.

Por lo tanto, un aspecto del objeto descrito se refiere a un método de planificación de rutas para un vehículo no tripulado (UV), ejecutado en tiempo real mientras recorre un área, comprendiendo el método: operar un dispositivo de escaneo para ejecutar operaciones de escaneo, que incluyen escanear un región dentro del área, para de ese modo generar los respectivos datos de salida de escaneo;

operar al menos una unidad de procesamiento para:

obtener un mapa generado en base a los datos de salida del escaneo, representando el mapa al menos una parte de la región y se divide en celdas, cada celda en el mapa se clasifica en una clase seleccionada entre dos o más clases, que comprenden transitables y no transitables; en base al mapa, planificar una o más rutas para el UV, comprendiendo la planificación: al determinar que dentro de una ruta de las una o más rutas el UV debe asumir un estado de vehículo: consultar una estructura de datos configurada para almacenar datos relacionados con estados del vehículo, caracterizándose cada estado del vehículo por al menos una posición y rumbo del UV respectivos, y es indicativo de si el estado del vehículo es viable o no para el UV; si la estructura de datos comprende una indicación correspondiente al estado del vehículo, utilizar datos almacenados en asociación con el estado del vehículo, para planificar la ruta, en caso contrario, calcular y almacenar los datos asociados al estado del vehículo; y seleccionar una ruta entre las una o más rutas.

El uso de los datos de indicación almacenados, reduce el tiempo necesario para planificar la ruta y, por lo tanto, permite evaluar un mayor número de rutas opcionales dentro de un período de tiempo determinado. Esto puede ayudar a aumentar la velocidad y suavidad de la maniobrabilidad del vehículo.

Además de las características anteriores, el método según este aspecto del objeto de la presente descripción puede comprender, opcionalmente, una o más de las características (i) a (xvii) enumeradas a continuación, en cualquier combinación o permutación técnicamente posibles:

i. En donde la estructura de datos comprende una o más entradas, representando cada entrada un estado del vehículo respectivo, y comprende una indicación de si el estado del vehículo respectivo es viable o no.

ii. En donde una entrada de las una o más entradas comprende, además, una ponderación que indica la proximidad del UGV a un obstáculo cuando el UGV asume el estado de vehículo.

iii. En donde la viabilidad del estado del vehículo requiere que la posición del UV en el estado del vehículo no esté mapeada a celdas no transitables.

iv. En donde una entrada de las una o más entradas comprende, además, una ponderación que indica una inclinación del UGV, cuando el UGV asume el estado de vehículo.

v. En donde una entrada de las una o más entradas comprende, además, una ponderación que indica la presencia del UGV en una ubicación no deseada, cuando el UGV asume el estado de vehículo.

vi. En donde las entradas se mantienen para mapas adicionales generados al recibir datos de salida de escaneo adicionales.

vii. En donde la planificación de las una o más rutas incluye planificar dos o más rutas.

viii. El método comprende, además, girar el UV según la ruta que se ha seleccionado.

ix. En donde el giro lo ejecuta el vehículo de forma autónoma.

x. En donde la viabilidad del estado del vehículo requiere que el uno o más de los ángulos de guiñada, cabeceo y balanceo del UV cumplan con uno o más criterios predefinidos.

xi. El método comprende, además, operar la unidad de procesamiento para generar el mapa.

xii. En donde el vehículo no tripulado es un vehículo terrestre no tripulado (UGV).

xiii. En donde el vehículo no tripulado es un vehículo aéreo no tripulado.

xiv. En donde el vehículo no tripulado es un vehículo marino no tripulado.

xv. El método comprende, además, recibir datos indicativos de un destino del UV, y en donde las una o más rutas se determinan desde la posición actual del UV hasta el destino.

xvi. El método comprende, además, a medida que el UV avanza dentro del área y se generan nuevos datos de salida de escaneo de nuevas regiones dentro del área, obtener un mapa actualizado generado y en base a los nuevos datos de salida de escaneo, y repetir la planificación en base al mapa actualizado.

xvii. El método comprende, además, a medida que el UV avanza dentro del área y se generan nuevos datos de salida de escaneo de nuevas regiones dentro del área:

excluir regiones antiguas del mapa; y eliminar de la estructura de datos los estados del vehículo que correspondan a las regiones antiguas.

Según otro aspecto del objeto de la presente descripción, se proporciona un sistema que se puede montar en un vehículo, comprendiendo el sistema una unidad de procesamiento y al menos un dispositivo de escaneo, estando el sistema configurado para:

operar el al menos un dispositivo de escaneo para ejecutar operaciones de escaneo que incluyen escanear una región dentro de un área que está siendo recorrida por el UV, para generar de ese modo los respectivos datos de salida del escaneo;

operar la unidad de procesamiento para:

obtener un mapa en base a los datos de salida del escaneo, representando el mapa al menos una parte de la región, el mapa se divide en celdas, donde cada celda se clasifica en una clase seleccionada entre dos o más clases, que comprenden transitables y no transitables; y, en base al mapa, planificar dos o más rutas para la UV,

la planificación comprende: al determinar que dentro de una ruta de las dos o más rutas, el UV debe asumir un determinado estado de vehículo dentro de las una o más rutas: consultar una estructura de datos, almacenada en un dispositivo de almacenamiento informático conectado operativamente a la unidad de procesamiento, configurado para mantener una o más entradas, indicando cada una de las entradas si un estado de vehículo respectivo es viable para el UV, estando el estado de vehículo configurado con al menos una posición y rumbo respectivos del UV; si la estructura de datos comprende una indicación correspondiente al estado del vehículo, utilizar datos almacenados en asociación con el estado del vehículo, para planificar la ruta, en caso contrario, calcular y almacenar los datos asociados al estado del vehículo; y seleccionar una ruta entre las dos o más rutas.

Según otro aspecto del objeto de la presente descripción, se proporciona un sistema que se puede montar en un vehículo no tripulado (UV), comprendiendo el sistema una unidad de procesamiento configurada para:

recibir datos de salida de escaneo, los datos de salida de escaneo son producto de las operaciones de escaneo que se ejecutan por un dispositivo de escaneo, e incluyen escanear una región dentro de un área recorrida por el UV;

generar un mapa en base a los datos de salida del escaneo, representando el mapa al menos una parte de la región, y se divide en celdas, clasificándose cada celda en una clase seleccionada entre dos o más clases, que comprende: transitable y no transitable; y, en base al mapa, planificar dos o más rutas para el UV, comprendiendo la planificación:

al determinar que dentro de una ruta de las dos o más rutas, el UV debe asumir un cierto estado de vehículo: consultar una estructura de datos, almacenada en un dispositivo de almacenamiento informático conectado operativamente a la unidad de procesamiento, configurado para mantener una o más entradas, indicando cada una de las entradas si un estado de vehículo respectivo es viable para el UV, estando el estado de vehículo asociado con al menos una posición y rumbo respectivos del UV; si la estructura de datos comprende una indicación correspondiente al estado del vehículo, utilizar datos almacenados en asociación con el estado del vehículo para planificar la ruta; en caso contrario, calcular y almacenar los datos asociados con el estado del vehículo; y seleccionar una ruta entra las dos o más rutas.

El sistema detallado anteriormente descrito según los aspectos del objeto de la presente descripción, puede comprender, opcionalmente, una o más de las características (i) a (xvii) enumeradas anteriormente,mutatis mutandis,en cualquier combinación o permutación técnicamente posible.

Según otro aspecto del objeto de la presente descripción, se proporciona un vehículo no tripulado (UV), que comprende: un dispositivo de escaneo y una unidad de procesamiento; el dispositivo de escaneo está configurado y es operable para escanear una región que rodea el UV dentro de un área recorrida por el UV, para proporcionar de ese modo datos de salida del escaneo, que proporcionan información sobre las distancias entre objetos en la región y el UV, en una multitud de direcciones;

la unidad de procesamiento está configurada y es operable para:

generar un mapa en base a los datos de salida del escaneo, representando el mapa al menos una parte de la región, y se divide en celdas, clasificándose cada celda en una clase seleccionada entre dos o más clases, que comprenden transitables y no transitables; recibir datos indicativos de un destino del UV; y en base al mapa, ejecutar un proceso de planificación para planificar una o más rutas para el UV,

comprendiendo el proceso de planificación: al determinar que dentro de una ruta de las una o más rutas, el UV debe asumir un estado de UV: consultar una estructura de datos, almacenada en un dispositivo de almacenamiento informático conectado operativamente a la unidad de procesamiento, configurado para mantener una o más entradas, indicando cada una de las entradas si un estado de vehículo respectivo es viable para el UV, estando el estado de vehículo asociado con al menos una posición y rumbo respectivos del UV; si la estructura de datos comprende una indicación correspondiente al estado del vehículo, utilizar datos almacenados en asociación con el estado del vehículo, para planificar la ruta, en caso contrario, calcular y almacenar los datos asociados al estado del vehículo; y seleccionar una ruta entre las una o más rutas.

El uso de la indicación en la estructura de datos ayuda a reducir el tiempo necesario para planificar la ruta del UV, permitiendo de este modo evaluar un mayor número de rutas opcionales dentro de un período de tiempo determinado. Esto puede ayudar a aumentar la velocidad y suavidad de la maniobrabilidad del vehículo.

El UV detallado anteriormente descrito según los aspectos del objeto de la presente descripción, puede comprender, opcionalmente, una o más de las características (i) a (xvii) enumeradas anteriormente,mutatis mutandis,en cualquier combinación o permutación técnicamente posible.

Según otro aspecto del objeto de la presente descripción, se proporciona un medio de almacenamiento no transitorio legible por ordenador que retiene un programa de instrucciones, el programa de instrucciones, cuando lo lee un ordenador, hace que el ordenador realice un método de planificación de ruta para un vehículo no tripulado (UV), que comprende:

obtener un mapa en base a los datos de salida del escaneo; los datos de salida del escaneo son producto de las operaciones de escaneo ejecutadas por un dispositivo de escaneo a bordo del UV, durante el cual se escanea una región dentro de un área recorrida por el UV; el mapa se divide en celdas, cada celda se clasifica en una clase seleccionada entre dos o más clases, que comprenden transitables y no transitables;

planificar, en base al mapa, dos o más rutas hasta un destino del UV, comprendiendo la planificación:

al determinar que dentro de una ruta de las dos o más rutas, el UV debe asumir un estado de vehículo: consultar una estructura de datos configurada para mantener información que indica si un estado de vehículo respectivo es viable para el UV, estando el estado de vehículo asociado con al menos una posición y rumbo respectivos del UV; si la estructura de datos comprende una indicación correspondiente al estado del vehículo, utilizar datos almacenados en asociación con el estado del vehículo, para planificar la ruta, en caso contrario, calcular y almacenar los datos asociados al estado del vehículo; y seleccionar una ruta entre las dos o más rutas.

Según otro aspecto del objeto de la presente descripción, se proporciona un método de planificación de ruta para un vehículo no tripulado (UV) mientras recorre un área, comprendiendo el método: inicializar una estructura de datos configurada para mantener una o más entradas, indicando cada una de las entradas si un estado de vehículo respectivo es viable para el UV, estando el estado de vehículo asociado con al menos una posición y rumbo respectivos del UV; operar un dispositivo de escaneo para ejecutar operaciones de escaneo, que comprende escanear el área, para generar de ese modo los respectivos datos de salida del escaneo; obtener un mapa en base a los datos de salida del escaneo, representando el mapa al menos una parte del área, comprendiendo el mapa un grupo de celdas, representando cada celda en el grupo de celdas una ubicación dentro del área, en donde cada celda del grupo de celdas se clasifica en una clase seleccionada entre dos o más clases, que comprenden transitables y no transitables; recibir datos indicativos de un destino del UV; y, en base al mapa, planificar una o más rutas hacia un destino del UV, comprendiendo la planificación: al determinar que dentro de una de las una o más rutas, el UV debe asumir un estado de vehículo: si la estructura de datos comprende una indicación correspondiente al estado del vehículo, utilizando datos almacenados en asociación con el estado del vehículo para planificar la ruta, en caso contrario, calcular y almacenar los datos asociados con el estado del vehículo; y seleccionar una ruta entre las una o más rutas, mediante lo cual el uso de la indicación reduce el tiempo requerido para planificar la ruta para permitir evaluar más rutas en un período de tiempo predeterminado, por lo que se puede seleccionar una ruta preferible entre las una o más rutas.

El método y producto de programa informático detallados anteriormente descritos según los aspectos del objeto de la presente descripción, pueden comprender, opcionalmente, una o más de las características (i) a (xvii) enumeradas anteriormente,mutatis mutandis,en cualquier combinación o permutación técnicamente posible.

Breve descripción de los dibujos

Para entender la invención y ver cómo puede llevarse a cabo en la práctica, se describirán las realizaciones, como ejemplos no limitativos, con referencia a los dibujos adjuntos, en los que:

LaFigura 1ilustra un diagrama de bloques esquemático de un vehículo no tripulado con planificación automática de ruta, que incluye reutilización de datos, según determinados ejemplos del objeto de la presente descripción;

laFigura 2es una ilustración esquemática de un entorno en el que un UGV ha de navegar;

laFigura 3Ailustra un diagrama de flujo de un método para planificación de rutas, que incluye reutilización de datos, según determinados ejemplos del objeto de la presente descripción;

laFigura 3Bilustra otro diagrama de flujo de operaciones llevadas a cabo durante la planificación de rutas, según determinados ejemplos del objeto de la presente descripción;

lasFiguras 4Ay4Bproporcionan demostraciones gráficas de dos estructuras de datos utilizadas para almacenar datos a reutilizar, según determinados ejemplos del objeto de la presente descripción; y

laFigura 5es una ilustración gráfica de la planificación de rutas, en las que se puede ejercer la reutilización, según determinados ejemplos del objeto de la presente descripción.

Descripción detallada

En la siguiente descripción detallada, se establecen numerosos detalles específicos para proporcionar una comprensión completa de la invención. Sin embargo, los expertos en la técnica entenderán que el objeto actualmente descrito puede ponerse en práctica sin estos detalles específicos. En otros casos, los métodos, procedimientos, componentes y circuitos bien conocidos no se han descrito en detalle para no oscurecer el objeto actualmente descrito.

A menos que se indique específicamente lo contrario, como es evidente de las siguientes análisis, se aprecia que a lo largo de los análisis de la memoria descriptiva al utilizar términos tales como “procesar” , “determinar” , “calcular” , “ representar” , “comparar” , “generar” , “evaluar” , “coincidir” , “actualizar” , “ inicializar” , “obtener” , “ planificar” , o similares, se refieren a la(s) acción(es) y/o proceso(s) de un ordenador que manipula y/o transforma datos en otros datos, representados los datos como cantidades físicas, tales como electrónicas, y/o representando los datos los objetos físicos. El término “ordenador” debe interpretarse de manera amplia para que cubra cualquier tipo de dispositivo electrónico con capacidades de procesamiento de datos, incluyendo, a modo de ejemplo no limitativo, la unidad116de procesamiento descrita en la presente solicitud.

Los términos “unidad de procesamiento” , “ordenador” , “dispositivo de procesamiento” , “dispositivo de procesamiento informático” o similares, deben interpretarse de manera amplia para que incluyan cualquier tipo de dispositivo electrónico con sistemas de circuitos de procesamiento de datos, lo que incluye un procesador de ordenador como se describe en la presente memoria (p. ej., una unidad central de procesamiento [CPU, por su siglas en inglés], un microprocesador, un circuito electrónico, un circuito integrado [CI], firmware escrito para o transferido a un procesador específico, tal como un procesador de señales digitales [DSP, por su siglas en inglés], un microcontrolador, una matriz de puertas programables en campo [FPGA, por su siglas en inglés], un circuito integrado de aplicación específica [ASIC, por su siglas en inglés], etc.), y que sea capaz de ejecutar diversas instrucciones informáticas (almacenadas, por ejemplo, en una memoria de ordenador conectada operativamente al mismo).

Las operaciones según las enseñanzas en la presente memoria pueden realizarse por un ordenador especialmente construido para los fines deseados, o por un ordenador de propósito general especialmente configurado para el fin deseado por un programa informático almacenado en un medio de almacenamiento legible por ordenador.

La Figura 1 descrita a continuación, ilustra un diagrama esquemático general de la arquitectura del sistema según una realización del objeto de la presente descripción. Diferentes módulos en la Figura 1 pueden componerse de cualquier combinación de software, hardware y/o firmware que realice las funciones como se definen y explican en la presente memoria. Los módulos de la Figura 1 pueden estar centralizados en una ubicación, o estar dispersos en más de un dispositivo, en donde uno o más de los dispositivos pueden ubicarse en el UGV. En diferentes ejemplos del objeto de la presente descripción, el sistema puede comprender menos, más y/o diferentes módulos que los mostrados en la Figura 1.

Las Figuras 3A y 3B muestran diagramas de flujos de operaciones llevadas a cabo según ejemplos del objeto de la presente descripción. En realizaciones del objeto de la presente descripción, pueden ejecutarse menos, más y/o diferentes etapas que las mostradas en las Figuras 3A y 3B. Además, las operaciones podrán realizarse en un orden diferente al ilustrado.

El término “dispositivo de escaneo” , como se utiliza en la presente memoria, debe interpretarse de manera amplia para que cubra cualquier tipo de dispositivo de escaneo adaptado para identificar que un objeto esté presente a una distancia específica y en una dirección específica con respecto al dispositivo de escaneo. Los dispositivos de escaneo comunes incluyen detección y alcance de luz 3D (Lidar, también conocido como escaneo láser), que se relaciona con la dirección controlada de rayos láser, seguida de la medición de distancia en cada dirección de apunte. Otras tecnologías conocidas incluyen navegación y alcance por sonido (Sonar) o detección y alcance por radio (Radar). Un dispositivo de escaneo puede emitir información relacionada con obstáculos alrededor del dispositivo (360 o) o en un rango parcial, tal como 180 o.

El término “vehículo no tripulado” , como se utiliza en la presente memoria, debe interpretarse de manera amplia para que incluya, además de un vehículo controlado de forma autónoma, un vehículo controlado por un operador remoto o un operador a bordo que no pueda ver el entorno, y dirige el vehículo, utilizando, por ejemplo, un mapa del entorno recorrido (p. ej., un mapa 3D o 2,5D generado en tiempo real en base a datos de salida de escaneo de un dispositivo de escaneo a bordo del vehículo, que proporciona una representación virtual del entorno circundante).

Además, aunque la descripción puede hacer referencia a un vehículo terrestre, lo hace solo a título de ejemplo no limitativo, estando también contemplados dentro de su alcance otro tipo de vehículos. Estos incluyen, por ejemplo, aviones no tripulados (p. ej., vehículos aéreos no tripulados, también conocidos como sistemas aéreos no tripulados o drones) o vehículos marinos no tripulados (incluyendo vehículos submarinos y sobre el agua), que pueden de igual manera comprender un sistema configurado para implementar los métodos de planificación de rutas y navegación autónoma como se describe en la presente memoria. Como ejemplo específico, un dron que vuele a baja altitud en un área con alta densidad de obstáculos (p. ej., en un bosque o un área urbana con edificios y otras estructuras) se puede configurar para ejecutar la planificación de ruta y navegar según los principios descritos en la presente memoria.

Un vehículo según la descripción puede comprender o llevar consigo un dispositivo de escaneo para proporcionar información sobre objetos u obstáculos que rodeen el vehículo, y un sistema de navegación autónomo (SCNS, por sus siglas en inglés). El término sistema de navegación autónomo (SCNS), tal como se utiliza en la presente memoria, incluye un sistema de navegación que no depende de referencias externas para determinar datos de navegación, tales como la posición, la orientación o la velocidad. Esto es diferente, por ejemplo, de la navegación GPS, que depende de la información obtenida de los satélites. Además de un sistema de navegación inercial (INS, por sus siglas en inglés), otros tipos de sistemas de navegación autónomos incluyen, por ejemplo, localización y mapeo simultáneos (SLAM, por sus siglas en inglés) y sistemas de navegación con odómetro.

El término “obstáculo” , como se utiliza en la presente memoria, debe interpretarse de manera amplia para que cubra cualquier tipo de objeto o cambio en la distribución del entorno que impida que un vehículo (p. ej., UGV) pase por la ubicación del obstáculo. Los obstáculos pueden incluir obstáculos positivos, que generalmente están por encima del nivel del suelo, tales como árboles, edificios, personas, rampas pronunciadas o similares, y obstáculos negativos, que generalmente están por debajo del nivel del suelo, por ejemplo, fosas, zanjas, agujeros, grietas o similares.

El término “ mapa” , como se utiliza en la presente memoria, debe interpretarse de manera amplia para que incluya cualquier estructura de datos que represente un área geográfica. Un mapa puede ser absoluto, es decir, comprender indicaciones de coordenadas absolutas de un objeto o una ubicación, o relativo, es decir, comprender información sobre ubicaciones u objetos, independientemente de sus ubicaciones en coordenadas absolutas. En algunas realizaciones, un mapa según la descripción puede estar compuesto de celdas, por ejemplo, en forma de cuadrícula, en donde cada celda se indica como no transitable o transitable, es decir, que comprende o no un obstáculo para un vehículo. Un mapa puede ser un mapa bidimensional, que indique para cada ubicación X-Y si es o no un obstáculo, un mapa tridimensional, que indique para cada ubicación X-Y-Z si es o no un obstáculo, o un mapa de 2,5 dimensiones, que indique para cada ubicación X-Y la altura del obstáculo más bajo sobre ese punto, es decir, la altura libre sobre el punto.

Un mapa puede representarse visualmente en un dispositivo de visualización informático, en papel, o en cualquier otro medio tangible.

A continuación, se hace referencia a la Figura 1, que muestra un diagrama de bloques esquemático de un vehículo (p. ej. UGV), según algunos ejemplos de la descripción.

El vehículo 100 puede comprender, o conectarse operativamente de cualquier otra manera a, un dispositivo 104 de escaneo configurado para escanear un área que rodee el vehículo, y proporcionar datos de salida de escaneo utilizados para generar mapas. Se puede construir un mapa de un área escaneada de tal manera que contenga un área que rodee al vehículo 100, por ejemplo, centrada alrededor del vehículo 100.

Según algunos ejemplos, el vehículo 100 puede comprender, además, un SCNS, tal como un sistema de navegación inercial, que incluya una IMU que proporcione, entre otras cosas, datos de aceleración del UGV y, se utiliza para rastrear la posición, velocidad y orientación de un objeto. Como se mencionó anteriormente, el INS es simplemente un ejemplo, y se pueden utilizar otros sistemas de navegación autónomos, además del INS, o en lugar de éste.

El vehículo 100 puede comprender subsistemas 108 de control de vehículo, que incluyen, por ejemplo, una unidad de control de giro, una unidad de control de marchas, una unidad de control de acelerador, etc. Los subsistemas 108 de control de vehículo están configurados para recibir instrucciones de control de vehículo (p. ej., órdenes de giro) y controlar el vehículo 100 en consecuencia. Las instrucciones pueden ser absolutas o relativas, por ejemplo, una instrucción absoluta puede ser “ ir 20 metros al norte” , mientras que una instrucción relativa puede ser “continuar recto durante 20 metros” o “ acelerar al 30 %, velocidad de guiñada al 50 %” .

El vehículo 100 puede, además, comprender, o estar conectado operativamente de otro modo al dispositivo 112 de almacenamiento informático para almacenar información tal como uno o más mapas, estructura(s) de datos descritas a continuación, un punto de destino, información sobre obstáculos, instrucciones de navegación, módulos binarios, o similares.

El vehículo 100 puede, además, comprender o conectarse operativamente de cualquier otra manera a una o más unidades de procesamiento, tal como una unidad 116 de procesamiento para controlar y ejecutar diversas operaciones, como se describe en la presente memoria. Cada unidad de procesamiento comprende un circuito de procesamiento respectivo que comprende al menos un procesador informático que puede, por ejemplo, conectarse operativamente a un dispositivo de almacenamiento legible por ordenador, que almacene instrucciones informáticas almacenadas para ser ejecutadas por el procesador informático (p. ej., dispositivo 112 de almacenamiento informático).

Según algunos ejemplos, pueden implementarse diferentes elementos funcionales (unidades, módulos, ejecutables) en el vehículo 100 como una unidad de procesamiento dedicada que comprenda un procesador informático dedicado y almacenamiento informático para ejecutar operaciones específicas.

De forma adicional o alternativamente, uno o más elementos funcionales pueden conectarse operativamente a una unidad de procesamiento común configurada para ejecutar operaciones según las instrucciones almacenadas en los elementos funcionales. Por ejemplo, la unidad 116 de procesamiento puede comprender uno o más ordenadores o unidades de procesamiento, que pueden configurarse para ejecutar varios módulos funcionales según instrucciones legibles por ordenador almacenadas en un medio legible por ordenador no transitorio (p. ej., el dispositivo 112 de almacenamiento) conectado operativamente a un procesador informático. Con fines ilustrativos, a dichos módulos funcionales se hace referencia en lo sucesivo como que se comprenden en la unidad 116 de procesamiento.

En algunos ejemplos, la unidad 116 de procesamiento puede comprender o estar conectada operativamente de otro modo al módulo 120 de obtención de mapas. El módulo 120 de obtención de mapas puede funcionar para generar un mapa en base a las lecturas recibidas del dispositivo 104 de escaneo u otra fuente de información. El tamaño del área representada por el mapa puede ser según el rango en el que el dispositivo 104 de escaneo pueda escanear. En realizaciones alternativas, el módulo 120 de obtención de mapas puede funcionar para recibir un mapa desde una fuente externa, por ejemplo, a través de un canal de comunicación.

En algunos ejemplos, la unidad 116 de procesamiento puede comprender un módulo 124 de recepción de destino, para recibir, por ejemplo, desde una fuente externa a través de un canal de comunicación, una ubicación de un destino. En algunas realizaciones, se puede recibir una ruta inicial, con el fin de que sirva como base para planificar la ruta.

Según algunos ejemplos, la unidad 116 de procesamiento puede comprender un módulo 128 de generación de rutas, configurado para generar una o más rutas desde un punto de partida, tal como la ubicación actual, hasta un destino. La ruta puede generarse de cualquier manera necesaria, por ejemplo, como se describe en la solicitud de patente israelí núm. 253769, presentada el 31 de julio de 2017, y particularmente como se explica en la Figura 3 y se ejemplifica en la Figura 4, y en la descripción asociada: de la página 16, línea 18, a la página 23, línea 25 de la solicitud 253769.

Como parte de la planificación de una ruta, se puede realizar un proceso de evaluación del estado del vehículo, incluida la determinación de si un estado del vehículo es viable. La determinación de si un estado de vehículo es viable o no, puede basarse en, pero sin limitarse a, uno cualquiera o más de los siguientes: si el vehículo colisionaría con un obstáculo cuando se encuentre en el estado de vehículo, y si uno o más de los ángulos de balanceo y cabeceo del vehículo en un estado de vehículo están dentro de algunos valores umbral predefinidos o cumplen con otros criterios predefinidos. Si el estado del vehículo es viable, se pueden asignar una o más ponderaciones al estado del vehículo. Por ejemplo, la ponderación puede ser indicativa de un grado de favorabilidad de un determinado estado del vehículo (p. ej., en base a la proximidad a un obstáculo detectado).

La evaluación del estado del vehículo puede ser un proceso computacional intensivo y, en consecuencia, puede consumir una cantidad significativa de tiempo y otros recursos informáticos. Con el fin de ahorrar recursos, según ejemplos del objeto de la presente descripción, se puede mantener una estructura de datos (p. ej., una estructura 136 de datos de transitabilidad almacenada en el dispositivo 112 de almacenamiento), que se utilice para almacenar información indicativa de si se ha considerado un estado específico del vehículo. La estructura de datos puede comprender, además, para cada estado del vehículo considerado, datos indicativos de si el estado del vehículo es viable, y sus ponderaciones asociadas. Cuando es necesario examinar el estado del vehículo como parte de la planificación de una ruta, primero se puede determinar si el estado del vehículo ya ha sido analizado y, si es así, se pueden recuperar y utilizar los resultados de viabilidad y las ponderaciones calculadas para el estado del vehículo. Si el estado del vehículo no se ha comprobado previamente, se puede comprobar, y los resultados se pueden almacenar para planificar rutas adicionales. La reutilización de los resultados del cálculo puede permitir generar más rutas en un período de tiempo determinado, en comparación con un caso en donde el proceso de evaluación del estado del vehículo se repita para los mismos estados del vehículo.

El módulo 132 de selección de ruta está configurado para seleccionar la ruta más adecuada una vez que dos o más rutas estén disponibles, cuando haya transcurrido el tiempo designado para este fin. Se apreciará que como la técnica de planificación de rutas descrita en la presente memoria permite la reducción del tiempo y otros recursos necesarios para calcular rutas, se pueden generar más rutas durante el tiempo asignado para calcular rutas, lo que a su vez aumenta la probabilidad de obtener una ruta más adecuada.

En algunos ejemplos del objeto de la presente descripción, se calcula el nivel de una ruta según si es viable cada uno de los diferentes puntos a lo largo de la ruta, y en función de las ponderaciones asociadas a cada punto. El nivel se puede calcular, por ejemplo, en base a uno o más de: suma; promedio; valor máximo o mínimo de una o más de las ponderaciones; etc.

La selección de una ruta mediante el módulo 132 de selección de rutas, puede basarse, por ejemplo, en una o más de las siguientes características de ruta: la ruta más corta, la ruta más rápida, la ruta que tenga ponderaciones mínimas o máximas, o según algún otro criterio adecuado.

A continuación, se hace referencia a la Figura 2, que muestra una ilustración esquemática de un ejemplo de un entorno en el que un vehículo (UGV 200) tiene que navegar desde una ubicación actual 201 hasta el destino 212. El entorno puede comprender obstáculos, tales como el edificio 207, obstáculos del terreno, incluyendo el obstáculo positivo 204, que está por encima del nivel del suelo y puede tener una pendiente pronunciada; el obstáculo negativo 208, que está por debajo del nivel del suelo; el obstáculo elevado 205, tal como un árbol o un puente, que el UGV 200 puede pasar por debajo de algunas partes del obstáculo; y el terreno empinado 206, que puede ser, por ejemplo, una pendiente trasera, lateral o frontal. Todos estos obstáculos no son transitables para el UGV 200 y, por lo tanto, una ruta hacia el destino 212 debería evitarlos. Además, áreas tales como la pendiente 203 pueden ser posibles, pero no se recomiendan para que el UGV las recorra. Concretamente, algunos objetos pueden significar un obstáculo cuando se acceda a los mismos desde un lado, pero no cuando se acceda a los mismos desde otro lado. Por ejemplo, una rampa puede significar un obstáculo cuando se acceda a la misma desde un lado, pero no cuando se acceda a la misma desde la parte delantera o desde la parte trasera. El UGV 200 puede asumir, por ejemplo, la posición y dirección actuales como se muestra, pero no puede asumir una ubicación más alejada en la dirección de la flecha 215, ya que esto implicará una pendiente significativa que puede no estar permitida para el UGV.

Se puede generar un mapa del entorno, que represente el área con una resolución determinada, en base a los datos de salida del escaneo recibidos de un escáner (dispositivo de escaneo). Luego se pueden planificar una o más rutas hacia un punto de destino según el mapa, mientras se reutiliza la información como se detalló anteriormente. A continuación, se puede seleccionar un ruta a recorrer entre las una o más rutas planificadas.

A continuación, se hace referencia a la Figura 3A, que muestra un diagrama de flujo de un método para planificar una ruta en un entorno con obstáculos, y a las Figuras 4A y 4B, que muestran la representación gráfica de estructuras de datos según algunos ejemplos.

Según un ejemplo, en el bloque 300, se inicializa una estructura de datos, en donde la estructura de datos está configurada para almacenar para cada uno de múltiples estados del vehículo (cada estado del vehículo está definido por determinados parámetros de navegación del vehículo, que incluyen, por ejemplo, al menos una posición y rumbo específicos del UV, y en el caso de un vehículo aéreo o submarino, también puede incluir la orientación), una o más indicaciones, que comprenden, por ejemplo, banderas de viabilidad, y una o más ponderaciones.

Según algunos ejemplos, la estructura de datos puede comprender algunos o todos los siguientes campos para cada estado del vehículo que se haya considerado:

Una bandera “considerado” , que indica si se ha considerado el estado del vehículo;

Un campo de “ posible ubicación” , que indica si el vehículo puede asumir el estado de vehículo sin colisionar con un obstáculo;

Un campo de “ posible inclinación” , que indica si el vehículo puede asumir el estado de vehículo sin que sus ángulos de balanceo o cabeceo excedan un umbral o violen de otro modo un criterio;

En algunos ejemplos del objeto de la presente descripción, los campos “posible ubicación” y “ posible inclinación” pueden combinarse en un solo campo.

Un campo de “ponderación de proximidad” , que indica qué tan cerca está el vehículo de un obstáculo. El campo “ponderación de proximidad” puede almacenar una distancia en unidades de longitud, tal como centímetros. En otros ejemplos, la proximidad de la ruta a uno o más obstáculos se puede expresar como un índice. Esta medida puede determinarse aumentando virtualmente el tamaño del vehículo mediante una o más envolturas virtuales, también denominadas “capas virtuales” , que rodean el vehículo, cada una teniendo una anchura predeterminada. En un ejemplo en el que se consideran una capa interna y una externa, una situación en la que la capa externa golpee con un obstáculo, indica que el vehículo se encuentra a una distancia del obstáculo que está entre el ancho de la capa interna y la suma de los anchos de las dos capas. Un ruta planificada en la que la capa interna golpee contra un obstáculo, indica que el vehículo se encuentra a una distancia del obstáculo que es como máximo la anchura de la capa interna. Así, en el último caso, el vehículo se encuentra más cerca del obstáculo que en el primer caso. Las capas virtuales permiten forzar la ruta para mantener el vehículo al menos a una distancia predeterminada de un obstáculo, asegurando así que el vehículo no entre en contacto con el obstáculo, incluso en presencia de algunos errores de planificación o de navegación. La proximidad del vehículo a los obstáculos puede discretizarse utilizando el índice de capa virtual, por ejemplo, 1 para la capa interna, y 2 para la capa externa, en lugar de la distancia exacta entre el vehículo y el obstáculo.

Un campo de “ponderación de inclinación” , que comprende una o más indicaciones de los ángulos de balanceo y cabeceo que el vehículo asume en el estado del vehículo. Este campo se puede implementar como dos campos, indicando los ángulos. Alternativamente, se puede almacenar una discretización de los ángulos, por ejemplo, en el rango de 1 a 5, en donde 1 indica un ángulo pequeño, tal como de 0 a 2 grados, y 5 indica un rango de ángulos con un límite superior igual al máximo ángulo permitido. Alternativamente, los ángulos pueden almacenarse como un campo que contenga una combinación de los dos valores, como una suma, un máximo, un promedio o similares.

Un campo de “ ponderación de área permitida” , indica hasta qué punto el vehículo se encuentra en un área definida como no deseada o restringida, al asumir el estado del vehículo. Por ejemplo, un césped, una propiedad privada, un área protegida (p. ej., una reserva natural), rutas pavimentados, aceras, o similares. Según un ejemplo no limitativo, esta ponderación puede discretizarse a uno de varios valores, tales como de 1 a 5.

La Figura 4A muestra un primer ejemplo de la estructura de datos, que comprende la tabla 404 con una entrada para cada estado del vehículo que comprende una ubicación, expresada, por ejemplo, en coordenadas X e Y, con alguna resolución predefinida (p. ej., 10 cm), y una dirección, expresada, por ejemplo, en una resolución de 1 grado. Por ejemplo, cada fila de la tabla 404 comprende los campos mencionados anteriormente, incluido si se ha considerado el estado del vehículo. Si se ha considerado el estado del vehículo, los demás campos son indicativos de si la ubicación es posible, si la inclinación es posible, y las ponderaciones de proximidad, inclinación y área permitida.

La Figura 4B muestra una segunda realización ilustrativa de la estructura de datos, que comprende una tabla hash. Cada entrada 408, 412, 416, 420 está asociada a un valor hash calculado utilizando algún o algunos valores únicos relacionados con el estado del vehículo. Por ejemplo, los valores pueden ser la posición y dirección del estado del vehículo, donde la entrada respectiva se crea cuando el estado del vehículo se encuentra por primera vez. Por tanto, la simple existencia de una entrada con un valor correspondiente al estado del vehículo, es una indicación de que se ha considerado el estado del vehículo. T ras el primer encuentro con un estado de vehículo, se crea una entrada hash, que comprende los campos relevantes, como se describió anteriormente. Una vez que se calculen los valores relevantes, se pueden almacenar mientras se vinculan (asocian) a la entrada hash relevante.

Se apreciará que una tabla y una tabla hash son simplemente dos ejemplos de dicha estructura de datos, y que de igual manera se pueden utilizar otros tipos de estructuras de datos.

Haciendo referencia de nuevo a la Figura 3A, en algunos ejemplos, en el bloque 304, el dispositivo 104 de escaneo se opera para escanear el entorno y generar datos de salida de escaneo.

En el bloque 308, se puede obtener un mapa, por ejemplo, mediante el módulo 120 de obtención de mapas. En algunos ejemplos, el mapa se genera por la unidad 116 de procesamiento en base a los datos de salida del escaneo. En otros ejemplos, el mapa se recibe desde otra plataforma informática a través de un canal de comunicación. El mapa se puede representar, por ejemplo, como una cuadrícula, en donde cada celda de la cuadrícula se clasifique como no transitable o transitable, es decir, que comprende o no un obstáculo para un UGV. Un ejemplo de un método de generación de mapas se describe en la solicitud PCT núm PCT/IL2018/050208, titulada “ Method of navigating an unmanned vehicle and system thereof” (véanse, por ejemplo, las Figuras 3 y 4 en PCT/EL2018/050208). En algunos ejemplos, la estructura de datos se construye de tal manera que la resolución de sus entradas sea la misma que la resolución del mapa, de tal modo que la estructura de datos se relacione con cada ubicación en el mapa (y en todas las direcciones).

En algunos ejemplos, se puede recibir un destino del vehículo (bloque 302), por ejemplo, a través de un canal de comunicación, deducido mediante análisis de imágenes o análisis de vídeo, al buscar una señal o gesto predeterminado en una imagen o vídeo capturado, o similares. Según otros ejemplos, el destino puede estar ya disponible (p. ej., almacenado en el almacenamiento informático 112). Según otros ejemplos, el destino del vehículo se proporciona en coordenadas globales, y su posición respecto a la posición del vehículo se determina en base a datos de GPS recibidos desde el GPS a bordo del vehículo. Como se explica en detalle en PCT PCT/IL2018/050208, el vehículo se puede configurar para navegar hacia su destino global utilizando el GPS, mientras navega para evitar obstáculos utilizando el SCNS (p. ej., INS) y los datos cartográficos, donde la planificación de ruta se ejecuta como parte de la navegación SCNS, para evitar obstáculos.

En el bloque 316, se están planificando (o simulando) rutas. Como parte de la planificación de ruta, se determinan los estados de los vehículos a lo largo de la ruta. Como se explica en la solicitud de patente israelí núm. 253769, y se ilustra en la Figura 5 de la solicitud 253769, una ruta puede componerse de una pluralidad de segmentos. El comienzo de cada segmento empieza con un punto donde se determinan los estados del vehículo. La longitud de los segmentos, que corresponde a la frecuencia de los puntos en los que se determinan los estados del vehículo, se puede seleccionar según diferentes reglas predefinidas. Por ejemplo, se puede seleccionar una longitud de segmento de la mitad del tamaño del UGV. En otros ejemplos, se puede seleccionar una longitud de segmento de entre aproximadamente 1 metro y aproximadamente 10 metros.

Por lo tanto, durante la planificación de la ruta, diferentes estados del vehículo a lo largo de la ruta (p. ej., al comienzo de cada segmento), que están definidos por una ubicación y dirección del UV, se analizan utilizando la estructura de datos de transitabilidad. Se consulta la estructura de datos de transitabilidad, y si comprende una indicación correspondiente al estado del vehículo, los datos almacenados según el estado del vehículo se utilizan en lugar de calcularse. Si no existe tal indicación, los datos se calculan y almacenan para uso futuro.

A continuación, se hace referencia a la Figura 5, que muestra un ejemplo de dicha reutilización de datos previamente calculados. Se debe planificar una ruta desde la ubicación actual 500 de un UGV hasta el destino 536. Un posible ruta está se compone de los segmentos 504, 512, 524 y 532, y otra posible ruta se compone de los segmentos 520, 524 y 532.

Se apreciará que las dos rutas tienen los segmentos 524 y 532 en común, de modo que en la ubicación 528 el UGV asume la misma ubicación y la misma dirección, independientemente de si el UGV viaja según la primera o la segunda ruta. Por lo tanto, cuando se calcula una primera de las dos rutas, las banderas de viabilidad y las ponderaciones se calculan para un estado de vehículo que comprende la ubicación 528 y la dirección en la que el UGV llega a la ubicación 528 desde el segmento 524. El cálculo comprende determinar si la ubicación y la inclinación son viables para el UGV. Por ejemplo, una ubicación puede que no esté indicada como un obstáculo, sino que un obstáculo puede que esté ubicado a una breve distancia de la ubicación, de modo que cuando el UGV se coloque en la ubicación y dirección, una parte del mismo se superpone al obstáculo o parte del mismo, lo que hace que la ubicación y la dirección sean inviables. En otro ejemplo, el nivel del suelo puede ser tal que el UGV tenga que asumir un ángulo de balanceo o cabeceo que exceda un umbral predeterminado o viole de otro modo algunos criterios predefinidos. La evaluación puede comprender, además, determinar la ponderación de inclinación, la ponderación de proximidad o la ponderación de área permitida, u otros parámetros almacenados en asociación con el estado del vehículo.

En el bloque 320, se puede seleccionar una ruta entre las rutas generadas (p. ej., mediante el módulo 132 de selección de rutas). Si hay una ruta disponible, entonces se selecciona esta ruta; en caso contrario, se puede realizar la selección entre las rutas, por ejemplo, si ningún punto a lo largo de la ruta es inviable, y en base a una mínima (o máxima, donde mayores ponderaciones proporcionan una indicación más positiva) ponderación acumulada de los puntos a lo largo del recorrido, ponderación media o máxima, ponderación promedio u otros criterios.

La Figura 3B es otro diagrama de flujo de operaciones llevadas a cabo según algunos ejemplos del objeto de la presente descripción. La Figura 3B muestra las operaciones divididas en tres respectivos procesos asíncronos que se ejecutan mientras el vehículo avanza por un área. A las operaciones correspondientes a las descritas anteriormente con referencia a la Figura 3A se les asignan los mismos números de referencia.

Un primer proceso es un proceso de generación de mapas. Como se mencionó anteriormente, se puede generar un mapa en base a los datos de salida del escaneo obtenidos por un dispositivo de escaneo ubicado a bordo del vehículo. A medida que el vehículo avanza, el mapa se actualiza continuamente en base a nuevos datos de salida de escaneo de las regiones que rodeen el vehículo. Como se describe en detalle en la solicitud PCT núm. PCT/IL2018/050208 (véase, por ejemplo, la descripción con respecto a la Figura 4 en la página 21), el mapa se puede generar alrededor del vehículo, de manera que, a medida que el vehículo avanza dentro del área, el mapa se actualiza a medida que se escanean y agregan nuevas regiones al mapa, y otras regiones ubicadas en la dirección opuesta al avance del vehículo se excluyen del mapa.

El mapa actualizado se utiliza en el segundo proceso: planificación de rutas. La información del mapa actualizado se utiliza durante la generación de rutas, el proceso de evaluación del estado del vehículo y la selección de una ruta preferida como se describió anteriormente con referencia a los bloques 316 y 320.

En el tercer proceso -proceso de control del vehículo- el vehículo avanza a lo largo de la ruta que se ha seleccionado. En algunos ejemplos, el vehículo procede generando instrucciones de forma autónoma a los diversos subsistemas (108) de control del vehículo con el fin de dirigir el vehículo a lo largo de la ruta seleccionada (bloque 324).

A medida que el vehículo avanza (a lo largo de la ruta seleccionada) y se generan nuevas actualizaciones de mapas en base a nuevos datos de salida del escaneo, las rutas también se actualizan continuamente. Así, según algunos ejemplos, se generan una o más rutas para recorrer una región del área recorrida como se representa en una determinada actualización del mapa, y luego, cuando la región recorrida cambie con el avance del vehículo, se generan/simulan rutas actualizadas para recorrer las nuevas regiones.

Como se mencionó anteriormente, los tres procesos se ejecutan de forma asincrónica. Según un ejemplo, se puede proporcionar una actualización del mapa aproximadamente diez veces por segundo (10 Hz), se genera una ruta aproximadamente dos veces por segundo (2 Hz), y se generan ordenes de control aproximadamente veinte veces por segundo (20 Hz). Al ejecutar la planificación de rutas, se utiliza el mapa más actualizado disponible, y al generar órdenes de control, se utiliza la ruta disponible más actualizada.

Según algunos ejemplos, en respuesta a las actualizaciones realizadas en el mapa, y siguiendo las respectivas actualizaciones realizadas en las rutas, en base a las actualizaciones del mapa, la estructura de datos de transitabilidad también se actualiza. Mientras se generan nuevas rutas que comprenden nuevos segmentos y se insertan nuevos estados de vehículos que pertenecen a nuevos segmentos en la estructura de datos de transitabilidad, los estados de vehículos anticuados que pertenecen a segmentos pasados de regiones que han sido excluidas del mapa, se eliminan de la estructura de datos de transitabilidad. Esto ayuda a mantener una estructura de datos de baja transitabilidad y, por lo tanto, reduce los recursos de memoria y, en algunos casos, reduce el tiempo de procesamiento.

Los resultados experimentales realizados por el solicitante han mostrado una reducción del 30 % o más en el tiempo promedio necesario para planificar rutas, al reutilizar la información del estado del vehículo. Esta reducción se traduce en una ganancia del 40 % o más en el número de rutas que se pueden planificar en un período de tiempo determinado.

Cabe señalar que las enseñanzas del objeto de la presente descripción no están limitadas por los pasos descritos en referencia a la Figura 3, ni a los bloques descritos en referencia a la Figura 1. Una funcionalidad equivalente y/o modificada puede consolidarse o dividirse de otra forma, y puede implementarse en cualquier combinación apropiada de software, firmware y hardware, y ejecutarse en un dispositivo adecuado.

Claims (14)

1. REIVINDICACIONES

   i. Un método de planificación autónoma de rutas a bordo de un vehículo no tripulado (UV) que recorre un área, comprendiendo el método:

   operar un dispositivo de escaneo para ejecutar operaciones de escaneo, que comprende escanear una región dentro del área, para generar de ese modo los respectivos datos de salida del escaneo; generar un mapa en base a los datos de salida del escaneo, representando el mapa al menos una parte de la región, el mapa se divide en celdas, cada celda se clasifica en una clase seleccionada entre al menos dos clases, que comprenden transitables y no transitables;

   en base al mapa, planificar múltiples rutas para el UV, en donde en cada una de las múltiples rutas el UV debe asumir una pluralidad de estados de vehículo respectivoscaracterizados poruna posición y rumbo respectivos del UV; comprendiendo la planificación:

   evaluar cada una de las múltiples rutas, que comprende:

   para cada ruta, consultar una estructura de datos; la estructura de datos está configurada para mantener una o más entradas, cada una de las entradas representa un estado de vehículo respectivocaracterizado poral menos una posición y rumbo respectivos del UV, e incluye datos relacionados con la viabilidad del estado de vehículo;

   determinar si la estructura de datos comprende datos correspondientes a los respectivos estados del vehículo a lo largo de la ruta y, en caso afirmativo, utilizar datos almacenados en asociación con el respectivo estado del vehículo para planificar la ruta; de lo contrario, calcular y almacenar los datos asociados con el estado del vehículo; y

   seleccionar una ruta preferible entre las múltiples rutas;

   en donde el uso de los datos permite evaluar más rutas en un período predeterminado, y mejorar así la selección de una ruta preferible.
2. 2. El método de la reivindicación 1, en donde la planificación de una o más rutas incluye la planificación de dos o más rutas.
3. 3. El método de una cualquiera de las reivindicaciones anteriores, que comprende, además, dirigir el UV según la ruta que se haya seleccionado.
4. 4. El método de una cualquiera de las reivindicaciones anteriores, en donde la viabilidad del estado del vehículo requiere cualquiera de uno o más de:

   la posición del UV en el estado del vehículo no esté mapeada a una celda no transitable; y los ángulos de guiñada y cabeceo del UV cumplan con uno o más criterios predefinidos.
5. 5. El método de una cualquiera de las reivindicaciones anteriores, en donde las una o más entradas se mantienen para mapas adicionales generados al recibir datos de salida de escaneo adicionales.
6. 6. El método de una cualquiera de las reivindicaciones anteriores, en donde el vehículo no tripulado es cualquiera de:

   un vehículo terrestre no tripulado;

   un vehículo aéreo no tripulado; y

   un vehículo marino no tripulado.
7. 7. El método de una cualquiera de las reivindicaciones anteriores, que comprende, además: a medida que el UV avance dentro del área y se generen nuevos datos de salida de escaneo de nuevas regiones dentro del área, obtener un mapa actualizado generado y en base a los nuevos datos de salida de escaneo, y repetir la planificación en base al mapa actualizado.
8. 8. El método de la reivindicación 7, que comprende, además: a medida que el UV avance dentro del área y se generen nuevos datos de salida de escaneo de nuevas regiones dentro del área, excluir las regiones anticuadas del mapa; y eliminar de la estructura de datos los estados del vehículo que correspondan a las regiones antiguas.
9. 9. Un sistema que se puede montar en un vehículo no tripulado (UV), que comprende:

   una unidad de procesamiento configurada y operable para:

   recibir datos de salida de escaneo, los datos de salida de escaneo son un producto de operaciones de escaneo ejecutadas por un dispositivo de escaneo a bordo del UV, e incluyen escanear una región dentro de un área recorrida;

   generar un mapa en base a los datos de salida del escaneo, representando el mapa al menos un segmento de la región, el mapa se divide en celdas, cada celda se clasifica en una clase seleccionada entre al menos dos clases, que comprenden transitables y no transitables;

   en base al mapa, planificar múltiples rutas para el UV, en donde en cada una de las múltiples rutas el UV debe asumir una pluralidad de estados de vehículo respectivoscaracterizados poruna posición y rumbo respectivos del UV; comprendiendo la planificación:

   evaluar cada una de las múltiples rutas, que comprende:

   para cada ruta, consultar una estructura de datos configurada para mantener una o más entradas, cada una de las entradas representa un estado de vehículo respectivocaracterizado poral menos una posición y rumbo respectivos del UV, e incluye datos relacionados con la viabilidad del estado de vehículo;

   determinar si la estructura de datos comprende datos correspondientes a los respectivos estados del vehículo a lo largo de la ruta, y en caso afirmativo, utilizar datos almacenados en asociación con el respectivo estado del vehículo para planificar la ruta; de lo contrario, calcular y almacenar los datos asociados con el estado del vehículo; y

   seleccionar una ruta preferible entre las múltiples rutas;

   en donde el uso de la estructura de datos reduce el tiempo necesario para evaluar las múltiples rutas y, por lo tanto, permite evaluar más rutas en un período predeterminado.
10. 10. El sistema de la reivindicación 9, en donde la unidad de procesamiento está configurada, además, para generar ordenes de giro para girar el UV según la trayectoria.
11. 11. El sistema de una cualquiera de las reivindicaciones 9 a 10, en donde la unidad de procesamiento está, además, configurada y operable para generar el mapa en tiempo real en base a los datos de salida del escaneo.
12. 12. Un vehículo no tripulado (UV), que comprende: un dispositivo de escaneo y una unidad de procesamiento que comprende uno o más circuitos de procesamiento; el dispositivo de escaneo está configurado y operable para escanear una región que rodea el UV dentro de un área recorrida por el UV, para proporcionar de ese modo datos de salida del escaneo que proporcionan información sobre distancias entre objetos en la región y el UV en múltiples direcciones; la unidad de procesamiento está configurada y es operable para:

    generar un mapa en base a los datos de salida del escaneo, representando el mapa al menos un segmento de la región, el mapa se divide en celdas, cada celda se clasifica en una clase seleccionada entre al menos dos clases, que comprenden transitables y no transitables;

    en base al mapa, planificar múltiples rutas para el UV, en donde en cada una de las múltiples rutas el UV debe asumir una pluralidad de estados de vehículo respectivoscaracterizados poruna posición y rumbo respectivos del UV; comprendiendo la planificación:

    evaluar cada una de las múltiples rutas, que comprende:

    para cada ruta, consultar una estructura de datos configurada para mantener una o más entradas, cada una de las entradas representa un estado de vehículo respectivocaracterizado poral menos una posición y rumbo respectivos del UV, e incluye datos relacionados con la viabilidad del estado de vehículo;

    determinar si la estructura de datos comprende datos correspondientes a los respectivos estados del vehículo a lo largo de la ruta, y en caso afirmativo, utilizar datos almacenados en asociación con el respectivo estado del vehículo para planificar la ruta; de lo contrario, calcular y almacenar los datos asociados con el estado del vehículo; y

    seleccionar una ruta preferible entre las múltiples rutas;

    en donde el uso de la estructura de datos permite evaluar más rutas en un período predeterminado.
13. 13. El UV de la reivindicación 12 es uno cualquiera de: un vehículo terrestre no tripulado; un vehículo aéreo no tripulado; un vehículo marino no tripulado.
14. 14. Un medio de almacenamiento legible por ordenador no transitorio, que retiene instrucciones, las instrucciones cuando las lee un ordenador, hacen que el ordenador lleve a cabo el método según una cualquiera de las reivindicaciones 1 a 8.