ES2989944T3 - Encaminamiento de vehículos de manipulación de contenedores que operan en un sistema automatizado de almacenamiento - Google Patents

Abstract

Un método, sistema de control (500) y programa de computadora para enrutar y redirigir vehículos de manipulación de contenedores (201) que manipulan contenedores de almacenamiento (106) en un sistema de almacenamiento y recuperación automatizado que comprende una estructura de armazón (100) que forma una estructura de rejilla de almacenamiento tridimensional (104) para almacenar los contenedores de almacenamiento 106 en columnas de almacenamiento (105), incluyendo la estructura de armazón un sistema de rieles basado en rejilla (108) dispuesto por encima de las columnas de almacenamiento (105) con el sistema de rieles (108) proporcionando rutas disponibles para los vehículos de manipulación de contenedores (201) que manipulan y transfieren los contenedores de almacenamiento (106) hacia y desde las columnas de almacenamiento (105), y en donde cada vehículo de manipulación de contenedores (201) comprende un primer conjunto de ruedas configuradas para mover el vehículo a lo largo de una primera dirección lateral (X) del sistema de rieles basado en rejilla y un segundo conjunto de ruedas configuradas para mover el vehículo a lo largo de una segunda dirección lateral (Y) del sistema de rieles basado en rejilla (108), siendo la segunda dirección (Y) perpendicular a la primera dirección (X), los movimientos del contenedor vehículos de manipulación de contenedores controlados por un sistema de control (500), que determina qué tareas deben realizar los vehículos de manipulación de contenedores (201) especificados, las ubicaciones de destino para realizar las tareas y qué rutas deben recorrer los vehículos de manipulación de contenedores (201) en el sistema ferroviario (108). El método comprende los siguientes pasos realizados por el sistema de control (500) al ejecutar el programa informático: ejecutar (410) un algoritmo de búsqueda de ruta de múltiples agentes, MAPF, en el sistema de control (500) para establecer y asignar rutas en el sistema ferroviario (108) para los vehículos de manipulación de contenedores (201) desde sus ubicaciones actuales hasta las tareas asignadas en las ubicaciones de destino; determinar (420) qué distancia pueden recorrer los vehículos de manipulación de contenedores (201) en una primera parte de las rutas asignadas dentro de un intervalo de tiempo establecido, siendo la primera parte más corta que las rutas asignadas a los destinos; bloquear (430) las primeras partes de las rutas asignadas que pueden recorrer los vehículos de manipulación de contenedores (201) dentro del intervalo de tiempo establecido; instruir (440) a los vehículos de manipulación de contenedores (201) para que se muevan desde sus ubicaciones actuales a una ubicación final en las rutas bloqueadas asignadas; repitiendo los pasos anteriores. (Traducción automática con Google Translate, sin valor legal)

Description

DESCRIPCIÓN

Encaminamiento de vehículos de manipulación de contenedores que operan en un sistema automatizado de almacenamiento

CAMPO DE LA INVENCIÓN

La presente invención se refiere a un sistema automatizado de almacenamiento y recuperación de contenedores de almacenamiento manipulados por vehículos de manipulación de contenedores que circulan por un sistema de rieles, basado en una cuadrícula, del sistema de almacenamiento y recuperación, y más específicamente a un método, sistema y programa informático para encaminar y reencaminar los vehículos de manipulación de contenedores de acuerdo con las rutas disponibles en el sistema de rieles.

ANTECEDENTES

La figura 1 revela un sistema automatizado de almacenamiento y recuperación 1, típico de la técnica anterior, con una estructura de armazón 100 y con vehículos de manipulación de contenedores 201, también conocidos como robots, que operan en el sistema 1.

La estructura de armazón 100 comprende miembros verticales 102, miembros horizontales 103 y un volumen de almacenamiento que comprende columnas de almacenamiento 105 dispuestas en filas entre los miembros verticales 102 y los miembros horizontales 103. En estas columnas de almacenamiento 105, los contenedores de almacenamiento 106, también conocidos como recipientes, se apilan uno encima del otro para formar pilas 107. Los elementos 102, 103 pueden estar hechos normalmente de metal, por ejemplo, perfiles de aluminio extruido.

La estructura de armazón 100 del sistema automatizado de almacenamiento y recuperación 1 comprende un sistema de rieles 108 dispuesto a lo largo de la parte superior de la estructura de armazón 100, sobre cuyo sistema de rieles 108 se hacen funcionar una pluralidad de vehículos de manipulación de contenedores 201 para elevar los contenedores de almacenamiento 106 desde las columnas de almacenamiento 105 y bajar los contenedores de almacenamiento 106 hasta las mismas, y también para transportar los contenedores de almacenamiento 106 por encima de las columnas de almacenamiento 105.

El sistema de rieles 108 comprende un primer conjunto de rieles paralelos 110 dispuestos para guiar el movimiento de los vehículos de manipulación de contenedores 201 en una primera dirección X a través de la parte superior de la estructura de bastidor 100, y un segundo conjunto de rieles paralelos 111 dispuestos perpendicularmente al primer conjunto de rieles 110 para guiar el movimiento de los vehículos de manipulación de contenedores 201 en una segunda direcciónYque es perpendicular a la primera dirección X.

También se muestra en la figura 1 un primer riel 110a en una primera dirección X, un segundo riel 110b en una primera dirección X, un primer riel 111a en una segunda dirección Y, y un segundo riel 111b en una segunda direcciónY. Los vehículos de manipulación de contenedores 201 se mueven lateralmente por encima de las columnas de almacenamiento 105, es decir, en un plano que es paralelo al plano horizontalX-Y.

El tipo de vehículo de manipulación de contenedores 201 utilizado puede ser cualquiera conocido en la técnica, por ejemplo, uno de los vehículos automatizados de manipulación de contenedores descritos en los documentos WO2014/090684A1 o WO2015/193278A1 que tienen una superficie que cubre una o dos columnas de almacenamiento 105. El sistema de rieles 108 puede disponerse en configuraciones de vía simple y/o doble.

Los contenedores de almacenamiento 106 se almacenan en las columnas 105 que definen una tercera direcciónZque es ortogonal a la primera dirección X y la segunda dirección Y. Los vehículos de manipulación de contenedores 201 acceden a los contenedores de almacenamiento 106 a través de aberturas de acceso 112 en el sistema de rieles 108, es decir, el sistema de rieles 108 está dispuesto sobre la estructura de armazón 100 definiendo la circunferencia de cada abertura de acceso 112 en la parte superior de cada columna de almacenamiento 105. Los elementos verticales 102 de la estructura de armazón 100 se pueden utilizar para guiar los contenedores de almacenamiento cuando estos salen de las columnas 105 y cuando bajan hasta ellas. Las pilas 107 de contenedores 106 son típicamente autoportantes.

El volumen de almacenamiento de la estructura de armazón 100 se ha denominado a menudo cuadrícula 104, donde las posibles posiciones de almacenamiento dentro de las columnas de almacenamiento 105 en esta cuadrícula se denominan celdas de almacenamiento. Cada columna de almacenamiento 105 puede identificarse mediante una posición en una direcciónX-Y,mientras que cada celda de almacenamiento puede identificarse mediante un número de contenedor en la dirección X,YyZ.

En la estructura de armazón 100, la mayoría de las columnas 105 son columnas de almacenamiento 105, es decir, columnas 105 en las que los contenedores de almacenamiento 106 se almacenan en pilas 107. Sin embargo, algunas columnas 105 pueden tener otros propósitos.

En la figura 1, las columnas 119 y 120 son columnas de propósito especial utilizadas por los vehículos de manipulación de contenedores 201 para dejar y/o recoger contenedores de almacenamiento 106 de modo que puedan ser transferidos a una estación de acceso (no mostrada), donde se puede acceder a los contenedores de almacenamiento 106 desde fuera de la estructura de armazón 100, o ser transferidos fuera o dentro de la estructura de armazón 100. Una estación de acceso es típicamente una estación de selección o almacenamiento donde artículos de producto se retiran o se colocan en los contenedores de almacenamiento 106.

Dentro de la técnica, las columnas para transferir un contenedor de almacenamiento dentro y fuera del sistema de almacenamiento normalmente se denominan columna de puerto 119, 120 o columna de transferencia. Un contenedor de almacenamiento se transfiere hasta y desde una columna de puerto 119, 120 a través de unos puertos 119', 120' ubicados típicamente en una abertura en un extremo de la columna de puerto 119, 120, es decir, donde los contenedores de almacenamiento ingresan o salen de las columnas de puerto 119, 120. Un puerto también puede estar ubicado en otras ubicaciones, como por ejemplo en un nivel medio o a nivel del suelo de una columna de puerto 119, 120.

El transporte y transferencia del contenedor de almacenamiento 106 a una estación de acceso puede realizarse en cualquier dirección, es decir horizontal, inclinada y/o vertical. Por ejemplo, los contenedores de almacenamiento 106 pueden ser colocados en una columna aleatoria o dedicada 105 dentro de la estructura de armazón 100, luego ser recogidos por cualquier vehículo de manipulación de contenedores 201 y transportados a una columna de puerto 119, 120 para su posterior transporte a una estación de acceso. Obsérvese que el término "inclinado" significa transporte de contenedores de almacenamiento 106 que tienen una orientación de transporte general en algún lugar entre horizontal y vertical.

En la figura 1, la primera columna de puerto 119 puede ser, por ejemplo, una columna de puerto de descarga dedicada donde los vehículos de manipulación de contenedores 201 pueden dejar contenedores de almacenamiento 106 para ser transportados a un acceso o una estación de transferencia, y la segunda columna de puerto 120 puede ser una columna de puerto de recogida dedicada donde los vehículos de manipulación de contenedores 201 pueden recoger contenedores de almacenamiento 106 que han sido transportados desde un acceso o una estación de transferencia.

Al operar un sistema automatizado de almacenamiento y recuperación 1, a cada vehículo de manipulación de contenedores 201 se le asigna una tarea mediante la recepción de instrucciones. Una tarea puede ser, por ejemplo, recuperar un contenedor de almacenamiento 106 específico de una columna de almacenamiento 105 y entregarlo en una columna de puerto 119 para su posterior transporte a una estación de acceso, o mover un contenedor de almacenamiento 106 de una celda de almacenamiento a otra. Esto significa que a cada vehículo de manipulación de contenedores 201 se le ordena seguir una ruta establecida sobre los rieles 111 desde su ubicación actual hasta una ubicación objetivo.

Cuando se debe recuperar un contenedor de almacenamiento 106 específico, almacenado en una de las columnas 105 descritas en la figura 1, a uno de los vehículos de manipulación de contenedores 201 se le asigna la tarea y se le instruye para que recupere el contenedor de almacenamiento 106 de su ubicación y lo transporte al puerto 119' de la columna de puerto 119. Esta operación implica mover el vehículo de manipulación de contenedores 201 a una ubicación por encima de la columna de almacenamiento 105 en la que se encuentra el contenedor de almacenamiento 106, recuperar el contenedor de almacenamiento 106 de la columna de almacenamiento 105 utilizando un dispositivo de elevación (no mostrado) del vehículo de manipulación de contenedores 201 y transportar el contenedor de almacenamiento 106 al puerto 119' de la columna de puerto 119.

Si el contenedor de almacenamiento 106 objetivo está ubicado profundamente dentro de una pila 107, es decir, con uno o una pluralidad de otros contenedores de almacenamiento 106 posicionados por encima del contenedor de almacenamiento 106 objetivo, la operación también implica mover temporalmente los contenedores de almacenamiento posicionados por encima antes de levantar el contenedor de almacenamiento 106 objetivo de la columna de almacenamiento 105. Esta etapa, que a veces se denomina excavación dentro de la técnica, se puede realizar con el mismo vehículo de manipulación de contenedores 201 que se utiliza posteriormente para transportar el contenedor de almacenamiento objetivo a la columna de puerto de descarga 119, o con uno o una pluralidad de otros vehículos de manipulación de contenedores 201 cooperantes. Alternativamente, o además, el sistema automatizado de almacenamiento y recuperación 1 puede tener vehículos de manipulación de contenedores 201 específicamente dedicados a la tarea de retirar temporalmente contenedores de almacenamiento de una columna de almacenamiento 105. Una vez que el contenedor de almacenamiento 106 objetivo ha sido retirado de la columna de almacenamiento 105, los contenedores de almacenamiento 106 retirados temporalmente se pueden reposicionar en la columna de almacenamiento 105 original. Sin embargo, los contenedores de almacenamiento 106 retirados pueden reubicarse alternativamente en otras columnas de almacenamiento 105.

Cuando se va a almacenar un contenedor de almacenamiento 106 en una de las columnas 105, se instruye a uno de los vehículos de manipulación de contenedores 201 para que recoja el contenedor de almacenamiento 106 del puerto 120' de la columna de puerto 120 que transfiere contenedores de almacenamiento desde un acceso o una estación de transferencia y lo transporte a una ubicación por encima de la columna de almacenamiento 105 donde se va a almacenar. Después de que se hayan retirado todos los contenedores de almacenamiento posicionados en o por encima de la posición objetivo dentro de la pila de columnas de almacenamiento 107, el vehículo de manipulación de contenedores 201 posiciona el contenedor de almacenamiento 106 en la posición deseada. Los contenedores de almacenamiento 106 retirados pueden luego bajarse nuevamente a la columna de almacenamiento 105 o reubicarse en otras columnas de almacenamiento.

Las ubicaciones de cada contenedor de almacenamiento 106 dentro de la estructura de armazón 100 y las ubicaciones y movimientos de cada vehículo de manipulación de contenedores 201 que opera en el sistema de almacenamiento y recuperación son monitoreadas y controladas continuamente por un sistema de control 500, así como una referencia al contenido de cada contenedor de almacenamiento 106, de modo que un contenedor de almacenamiento 106 deseado puede entregarse en la ubicación deseada y en el momento deseado sin que los vehículos de manipulación de contenedores 201 colisionen entre sí.

Un ejemplo de un sistema de control típico 500 se muestra en la figura 2. El sistema de control 500 está adaptado para transmitir instrucciones de operación y movimiento a un controlador de vehículo 230 situado en cada vehículo de manipulación de contenedores 201 para controlar todos los movimientos y operaciones en el sistema de almacenamiento y recuperación 1. El sistema de control 500 instruye a cada vehículo 201 para que almacene o recupere contenedores de almacenamiento 106. La posición actual de cada vehículo 201 se comunica desde un vehículo 201 al sistema de control 500, permitiéndole así controlar los movimientos de todos los vehículos 201 en el sistema de rieles 108 de una manera óptima sin que los vehículos 150 hagan cola o colisionen.

En el ejemplo mostrado, el sistema de control 500 comprende un controlador maestro 220, una base de datos 210, un planificador de encaminamiento 200 y un transmisor/receptor 225 para comunicar instrucciones a cada vehículo de manipulación de contenedores 201.

La base de datos realiza un seguimiento de la ubicación de los contenedores de almacenamiento 106, así como qué contenedor de almacenamiento 106 se debe manipular en cualquier momento, es decir, qué contenedor de almacenamiento 106 se debe recuperar o almacenar en la cuadricula de almacenamiento 104. El planificador de encaminamiento 200 está adaptado para encontrar rutas óptimas para los vehículos de manipulación de contenedores 201.

El controlador maestro 220 está adaptado para coordinar información de la base de datos 210 y del planificador de encaminamiento y para generar instrucciones operativas para cada vehículo de manipulación de contenedores 201, por ejemplo, qué contenedor de almacenamiento manipular y qué ruta en el sistema de rieles 108 seguir de acuerdo con la entrada procedente del planificador de encaminamiento 200.

El sistema de control 500 se comunica con un ordenador central donde se transmiten órdenes y tareas al sistema de control 500.

Un sistema automatizado de almacenamiento y recuperación 1 normalmente funciona con una pluralidad de vehículos de manipulación de contenedores 201 que transfieren contenedores de almacenamiento de una ubicación a otra. Un sistema de almacenamiento y recuperación más grande puede estar equipado con varios cientos de vehículos de manipulación de contenedores 201, donde a cada uno se le asigna una tarea mediante la recepción de instrucciones transmitidas desde el sistema de control 500. Una tarea puede ser, por ejemplo, obtener un contenedor de almacenamiento específico 106 desde una columna de almacenamiento 105 donde se encuentra, seguir una ruta recorriendo una distancia establecida en direcciones establecidas, entregar un contenedor de almacenamiento 106 en el puerto 119', etc.

El sistema de control 500 instruye a cada vehículo de manipulación de contenedores 201 para que realice una tarea y siga una ruta específica desde una ubicación actual hasta un destino objetivo. La meta general es encontrar la mejor ruta para cada vehículo de manipulación de contenedores 201 y las rutas que no entren en conflicto entre sí. La mejor ruta suele ser la ruta más corta que no entre en conflicto con otras rutas en el mismo período de tiempo.

Los algoritmos de búsqueda de rutas de múltiples agentes (MAPF) son conocidos dentro de la técnica de la ciencia informática y se pueden utilizar para resolver el problema de encontrar rutas para múltiples agentes desde sus ubicaciones actuales hasta sus ubicaciones objetivo sin colisionar entre sí, mientras que al mismo tiempo se optimiza una función de costo, como la suma de las longitudes de las rutas de todos los agentes.

Para el sistema de almacenamiento y recuperación 1, un vehículo de manipulación de contenedores 201 representa un agente. Sin embargo, la mayoría de los algoritmos MAPF son algoritmos de una sola pasada que resuelven un escenario específico en el que los vehículos de manipulación de contenedores 201 finalizan sus tareas planificadas siguiendo una ruta establecida desde una posición actual hasta una posición final para realizar una tarea antes de crear nuevas rutas de acuerdo con nuevas tareas. Adaptar estos algoritmos de búsqueda de rutas de múltiples agentes a un entorno que cambia dinámicamente, donde los vehículos de manipulación de contenedores 201 pueden cambiar el tipo de tarea o el objetivo antes de finalizar una primera tarea asignada, o donde hay nuevos vehículos de manipulación de contenedores 201 activos que operan en el sistema de almacenamiento, no es trivial.

Al utilizar un algoritmo MAPF, los vehículos de manipulación de contenedores 201 pueden encaminarse simultáneamente, pero como el algoritmo MAPF tiene un tiempo de ejecución considerable, los vehículos de manipulación de contenedores 201 deben esperar mientras se generan nuevas rutas.

En el artículo "Cooperative pathfinding", de David Silver, 2005, (www.aaai.org), se utiliza una ventana deslizante que define un área restringida para el encaminamiento con el fin de encontrar rutas que no colisionen dentro del área en entornos de tiempo real. Sin embargo, la búsqueda cooperativa de posibles rutas está limitada a una profundidad fija especificada por la ventana actual. Cada agente busca una ruta parcial hacia su destino y luego comienza a seguirla. A intervalos regulares, por ejemplo cuando un agente está a la mitad de su ruta parcial, la ventana se desplaza hacia adelante y se calcula una nueva ruta parcial. Esto significa que la búsqueda cooperativa sólo considera los agentes dentro de la ventana deslizante, es decir, se ignoran otros agentes fuera de la ventana que define el área restringida. Para encontrar las direcciones de los agentes hacia los destinos, se realiza una búsqueda abstracta en profundidad.

BNAYA ZAHY y colaboradores: "Conflict-Oriented Windowed Hierarchical Cooperative A", 2014 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), IEEE, 31 de mayo de 2014, páginas 3743-3748 describe, de acuerdo con su resumen, un enfoque general para el algoritmo base WHCA* que es ortogonal a todas las demás extensiones existentes. La mejora del WHCA* se logra mediante la introducción del principio Orientado al Conflicto (CO) para centrar la coordinación de los agentes en torno a los conflictos. Además, se proporciona un mecanismo de priorización orientado a conflictos que elige inteligentemente qué agente debe actuar a continuación.

El documento WO2019238670A1 describe, de acuerdo con su resumen, un método de funcionamiento de un sistema de almacenamiento y recuperación automatizado, en donde el método comprende: - detectar con la unidad de control central si el acceso de un primer vehículo de manipulación de contenedores a una celda objetivo, que es una de la pluralidad de celdas de la cuadrícula, está bloqueado por un segundo vehículo de manipulación de contenedores, - transmitir una señal de datos desde la unidad de control central a la unidad de control de vehículo del primer vehículo de manipulación de contenedores ordenando al primer vehículo de manipulación de contenedores que se mueva hacia la celda objetivo cuando el segundo vehículo de manipulación de contenedores esté más allá de dicha distancia predeterminada. El documento también se refiere a un sistema automatizado de almacenamiento y recuperación que comprende vehículos de manipulación de contenedores que comprenden una unidad de control central configurada para realizar el método mencionado anteriormente.

El documento WO2015185628A2 describe, de acuerdo con su resumen, sistemas, métodos y conjuntos de instrucciones codificadas ejecutables por máquina para controlar el movimiento de dispositivos de transporte y/u operaciones realizadas en varias estaciones de trabajo. En particular, el documento proporciona métodos, sistemas y medios legibles por ordenador para controlar el movimiento de dispositivos de transporte configurados para el manejo total y/o parcialmente automatizado de mercancías y/o el control de operaciones realizadas en varias estaciones de trabajo.

La presente invención presenta un método de encaminamiento donde se encuentran rutas completas desde las ubicaciones actuales de los vehículos de manejo de contenedores hasta los destinos pero donde solo una primera parte de cada ruta es bloqueada en un período de tiempo establecido. Este método proporciona una ruta eficiente en términos de tiempo y donde el reencaminamiento se puede realizar sin detener los vehículos de manipulación de contenedores.

SUMARIO DE LA INVENCIÓN

El propósito de la invención es proporcionar una forma mejorada de encaminar y reencaminar vehículos de manipulación de contenedores a medida que realizan sus operaciones cuando circulan por un sistema de rieles de un sistema de almacenamiento y recuperación. Un nuevo método, sistema y programa informático ofrecen más alternativas de ruta para todos los vehículos de manipulación de contenedores que las que ofrecían los sistemas de encaminamiento anteriores.

Esto se logra encaminando y reencaminando los vehículos de manipulación de contenedores con la mayor frecuencia posible durante su recorrido desde sus ubicaciones actuales hasta los destinos objetivo y para ello se consideran todas las rutas de todos los vehículos de manipulación de contenedores desde las ubicaciones actuales hasta las tareas en las ubicaciones de destino.

De acuerdo con el método inventivo, las rutas de los vehículos de manipulación de contenedores se calculan sobre la marcha a medida que los vehículos de manipulación de contenedores se mueven hacia sus destinos. Los vehículos de manipulación de contenedores se pueden reencaminar de manera eficiente para seguir nuevas rutas para adaptarse a los cambios en la situación del tráfico, y se pueden crear nuevas rutas para los vehículos de manipulación de contenedores recientemente activos.

El nuevo método requiere menos tiempo para encontrar nuevas rutas para todos los vehículos de manipulación de contenedores sin detenerlos y proporciona más alternativas de ruta para todos los vehículos de manipulación de contenedores. De acuerdo con este método, se utiliza un MAPF para encontrar rutas para todos los vehículos de manipulación de contenedores hasta sus destinos finales, pero donde solo se bloquea una primera parte de cada ruta durante un intervalo de tiempo establecido, a diferencia de la técnica anterior, donde se bloquea la ruta completa o donde solo se evalúan las rutas para los vehículos dentro de un área restringida definida por una ventana deslizante, como se describe en el artículo mencionado anteriormente de David Silver.

El nuevo método proporciona más alternativas de ruta a medida que los vehículos de manipulación de contenedores se mueven a lo largo de sus rutas asignadas, ya que la parte de cada ruta que ha sido cubierta se libera para nuevas rutas, así como la parte de una ruta asignada que aún no ha sido bloqueada.

El método inventivo proporciona un sistema fluido y en constante cambio, y el MAPF no sólo lo permite, sino que también permite acortar los tiempos de recorrido en comparación con los algoritmos de planificación anteriores porque los caminos están bloqueados durante menos tiempo.

La invención está definida por un método para encaminar y reencaminar vehículos de manipulación de contenedores que manipulan contenedores de almacenamiento en un sistema automatizado de almacenamiento y recuperación que comprende una estructura de armazón que forma una estructura de cuadrícula de almacenamiento tridimensional para almacenar los contenedores de almacenamiento en columnas de almacenamiento, incluyendo la estructura de armazón un sistema de rieles basado en cuadrícula dispuesto por encima de las columnas de almacenamiento, proporcionando el sistema de rieles rutas disponibles para los vehículos de manipulación de contenedores que manipulan y transfieren los contenedores de almacenamiento hacia y desde las columnas de almacenamiento, y en donde cada vehículo de manipulación de contenedores comprende un primer conjunto de ruedas configurado para mover el vehículo a lo largo de una primera dirección lateral (X) del sistema de rieles basado en cuadrícula y un segundo conjunto de ruedas configurado para mover el vehículo a lo largo de una segunda dirección lateral (Y) del sistema de rieles basado en cuadrícula, siendo la segunda dirección (Y) perpendicular a la primera dirección (X), estando controlados los movimientos de los vehículos de manipulación de contenedores por un sistema de control que determina qué tareas deben realizar los vehículos de manipulación de contenedores especificados, las ubicaciones de destino para realizar las tareas y qué rutas deben recorrer los vehículos de manipulación de contenedores en el sistema de rieles.

El método comprende las siguientes etapas realizadas por el sistema de control:

a. ejecutar en el sistema de control un algoritmo de búsqueda de rutas de múltiples agentes, MAPF, para establecer y asignar rutas en el sistema de rieles para los vehículos de manipulación de contenedores desde sus ubicaciones actuales hasta las tareas asignadas en las ubicaciones de destino;

b. determinar la distancia que pueden recorrer los vehículos de manipulación de contenedores en una primera parte de las rutas asignadas dentro de un intervalo de tiempo establecido, siendo la primera parte más corta que las rutas asignadas a los destinos;

c. bloquear los primeros tramos de las rutas asignadas que pueden recorrer los vehículos de manipulación de contenedores dentro del intervalo de tiempo establecido;

d. instruir a los vehículos de manipulación de contenedores para que se desplacen desde sus ubicaciones actuales hasta una ubicación final en las rutas bloqueadas asignadas;

e. repetir las etapas a) a d).

De acuerdo con una realización del método, un límite superior del intervalo de tiempo establecido en la etapa b) puede corresponder a un tiempo de ejecución que el sistema de control utiliza para ejecutar el algoritmo MAPF e instruir a los vehículos de manipulación de contenedores para que se muevan de acuerdo con rutas establecidas. La distancia que recorre un vehículo de manipulación de contenedores en el sistema de rieles de acuerdo con una ruta asignada dentro de este intervalo de tiempo será entonces la parte de la ruta completa establecida por el MAPF que está bloqueada.

De acuerdo con una realización del método, un límite superior del intervalo de tiempo establecido en la etapa b) puede corresponder al tiempo transcurrido para que todos los vehículos de manipulación de contenedores se muevan desde las posiciones actuales a las posiciones en el sistema de rieles ubicadas por encima de las columnas de almacenamiento más cercanas donde pueden cambiar de dirección.

De acuerdo con una realización del método, la duración del intervalo de tiempo establecido en la etapa b) puede establecerse de acuerdo con el tamaño del sistema automatizado de almacenamiento y/o recuperación y el número de vehículos de manipulación de contenedores que se incluirán en el algoritmo MAPF.

De acuerdo con la invención, el método incluye ampliar la parte bloqueada de la ruta asignada para un vehículo de manipulación de contenedores al que se le haya dado una prioridad.

De acuerdo con una realización del método, el método puede incluir extender la parte bloqueada de la ruta asignada para un vehículo de manipulación de contenedores que no esté respondiendo a las instrucciones.

De acuerdo con una realización del método, la parte bloqueada de las rutas asignadas puede extenderse a lo largo de la ruta establecida por el algoritmo MAPf desde la ubicación actual del vehículo de manipulación de contenedores hasta la tarea en la ubicación de destino.

De acuerdo con la invención, las rutas bloqueadas se excluyen de la consideración de rutas disponibles durante la ejecución del algoritmo MAPF.

De acuerdo con una realización del método, la distancia entre cada ruta establecida por el algoritmo MAPF se puede adaptar al tipo de vehículo de manipulación de contenedores que recorre las rutas asignadas.

De acuerdo con una realización del método, se pueden controlar los movimientos de los vehículos de manipulación de contenedores para evitar un posible problema de colas en los lugares de destino.

De acuerdo con una realización del método, los vehículos de manipulación de contenedores pueden ser redirigidos si se prevé un problema de colas en los lugares de destino.

De acuerdo con una realización del método, los vehículos de manipulación de contenedores pueden ser redirigidos a posiciones o rutas donde no haya vehículos de manipulación de contenedores presentes o hacia donde no se dirijan.

De acuerdo con una realización del método, los movimientos de los vehículos de manipulación de contenedores se pueden controlar de acuerdo con la carga actual que transportan y el estado de los vehículos de manipulación de contenedores.

La invención se define además por un sistema de control para controlar el encaminamiento y reencaminamiento de vehículos de manipulación de contenedores que manipulan contenedores de almacenamiento en un sistema automatizado de almacenamiento y recuperación que comprende una estructura de armazón que forma una estructura de cuadrícula de almacenamiento tridimensional para almacenar los contenedores de almacenamiento en columnas de almacenamiento, incluyendo la estructura de armazón un sistema de rieles basado en cuadrícula que está dispuesto por encima de las columnas de almacenamiento y proporciona rutas disponibles para los vehículos de manipulación de contenedores que manipulan y transfieren los contenedores de almacenamiento hacia y desde las columnas de almacenamiento, y en donde cada vehículo de manipulación de contenedores comprende un primer conjunto de ruedas configurado para mover el vehículo a lo largo de una primera dirección lateral (X) del sistema de rieles basado en cuadrícula y un segundo conjunto de ruedas configurado para mover el vehículo a lo largo de una segunda dirección lateral (Y) del sistema de rieles basado en cuadrícula, siendo la segunda dirección (Y) perpendicular a la primera dirección (X). Los movimientos de los vehículos de manipulación de contenedores están controlados por el sistema de control que determina qué tareas deben realizar los vehículos de manipulación de contenedores específicos, las ubicaciones de destino para realizar las tareas y qué rutas deben recorrer los vehículos de manipulación de contenedores en el sistema de rieles.

El sistema de control comprende un planificador de encaminamiento para encontrar rutas óptimas para los vehículos de manipulación de contenedores, una base de datos para realizar un seguimiento de los contenedores de almacenamiento, un controlador maestro conectado a un transmisor/receptor, donde el sistema de control está adaptado para ejecutar el método descrito anteriormente y para comunicar instrucciones de control a cada vehículo de manipulación de contenedores.

La invención se define además mediante un producto de programa informático que, cuando es ejecutado por un procesador en un sistema de control de un sistema automatizado de almacenamiento y recuperación, realiza el método descrito anteriormente para el encaminamiento y reencaminamiento eficientes de vehículos de manipulación de contenedores que manipulan contenedores de almacenamiento en un sistema automatizado de almacenamiento y recuperación.

BREVE DESCRIPCIÓN DE LOS DIBUJOS

Se adjuntan los siguientes dibujos para facilitar la comprensión de la invención. Los dibujos muestran realizaciones de la invención, que ahora se describirán a modo de ejemplo solo, donde:

La figura 1 es una vista en perspectiva de una estructura de armazón de un sistema automatizado de almacenamiento y recuperación de la técnica anterior.

La figura 2 muestra un ejemplo de un sistema de control para controlar vehículos de manipulación de contenedores que operan en un sistema automatizado de almacenamiento y recuperación.

La figura 3 es un diagrama de flujo que ilustra las diferentes etapas del método para el encaminamiento y reencaminamiento eficientes de vehículos de manipulación de contenedores de un sistema automatizado de almacenamiento y recuperación.

La figura 4 ilustra un ejemplo de encaminamiento simple de acuerdo con el encaminamiento anterior y el nuevo.

Referencias

1 - Sistema automatizado de almacenamiento y recuperación

100 - Estructura de armazón

102 - Miembros verticales de la estructura de armazón

103 - Miembros horizontales de la estructura de armazón

104 - Estructura de cuadrícula de almacenamiento

105 - Columna de almacenamiento

106 - Contenedor de almacenamiento

106' - Posición particular del contenedor de almacenamiento 107 - Pila

108 - Sistema de rieles

110 - Rieles paralelos en la primera dirección (X)

110a - Primer riel en la primera dirección (X)

110b - Segundo riel en la primera dirección (X)

111 - Rieles paralelos en la segunda dirección (Y)

111a - Primer riel de la segunda dirección (Y)

111b - Segundo riel de la segunda dirección (Y)

112 - Abertura de acceso

119 - primera columna de puerto

119' - primer puerto

120 - segunda columna de puerto

120' - segundo puerto

200 - Planificador de encaminamiento

201 - Vehículo de manipulación de contenedores

210 - Base de datos

220 - Controlador maestro

225 - Transmisor/Receptor

230 - Controlador de vehículo

X - Primera dirección

Y - Segunda dirección

Z - Tercera dirección

500 - Sistema de control

DESCRIPCIÓN DETALLADA DE LA INVENCIÓN

En la siguiente descripción se explicará la invención con más detalle con referencia a los dibujos adjuntos. Sin embargo, debe entenderse que los dibujos no pretenden limitar la invención a la materia objeto representada en los dibujos.

En la sección de antecedentes anterior se describió, con referencia a la figura 1, un sistema automatizado de almacenamiento y recuperación 1, típico de la técnica anterior, con una estructura de armazón 100.

La estructura de armazón 100 puede ser de cualquier tamaño, y se entiende que puede ser considerablemente más ancha y/o más larga y/o más profunda que la divulgada en la figura 1. Por ejemplo, la estructura de armazón 100 puede tener una extensión horizontal de más de 700x700 columnas de almacenamiento 105 y una profundidad de almacenamiento para almacenar más de doce contenedores de almacenamiento 106 apilados, y donde los contenedores de almacenamiento 106 son manipulados por cientos de vehículos de manipulación de contenedores 201 que circulan por el sistema de rieles 108.

Además, la cuadrícula de almacenamiento 104 puede ser considerablemente más profunda que la mostrada en la figura 1, que muestra pilas de ocho contenedores de almacenamiento 106. Por ejemplo, la cuadrícula de almacenamiento 104 puede estar diseñada para contener doce contenedores de almacenamiento apilados 106.

Los vehículos de manipulación de contenedores 201 pueden ser de cualquier tipo conocido en la técnica, por ejemplo, cualquiera de los vehículos automatizados de manipulación de contenedores descritos en los documentos WO2014/090684 A1, NO317366 o WO2015/193278A1.

El sistema de rieles 108 dispuesto a lo largo de la parte superior de la estructura del armazón 100 permite que los vehículos de manipulación de contenedores 201 se muevan horizontalmente entre las columnas de almacenamiento 105 y los puertos con los que interactúan, es decir, los puertos en los que reciben instrucciones de entregar o recuperar un contenedor de almacenamiento 106.

El sistema automatizado de almacenamiento y recuperación 1 comprende una estructura de armazón 100 que forma una estructura de cuadrícula de almacenamiento tridimensional 104 con un sistema de rieles 108 basado en cuadrícula para almacenar los contenedores de almacenamiento 106 en columnas de almacenamiento 105, estando dispuesto el sistema de rieles 108 basado en cuadrícula por encima de las columnas de almacenamiento 105 y proporcionando el sistema de rieles 108 las rutas disponibles para los vehículos de manipulación de contenedores 201 que manipulan y transfieren los contenedores de almacenamiento 106 hacia y desde las columnas de almacenamiento 105, y en donde cada vehículo de manipulación de contenedores 201 comprende un primer conjunto de ruedas configurado para mover el vehículo a lo largo de una primera dirección lateral (X) del sistema de rieles basado en cuadrícula y un segundo conjunto de ruedas configurado para mover el vehículo a lo largo de una segunda dirección lateral (Y) del sistema de rieles 108 basado en cuadrícula, siendo la segunda dirección (Y) perpendicular a la primera dirección (X), los movimientos de los vehículos de manipulación de contenedores están controlados por un sistema de control 500, que determina qué tareas deben realizar los vehículos de manipulación de contenedores 201 específicos, las ubicaciones de destino para realizar las tareas y las rutas que deben recorrer los vehículos de manipulación de contenedores 201 en el sistema de rieles 108.

La figura 2 muestra un ejemplo de un sistema de control 500 para controlar los vehículos de manipulación de contenedores 201 de acuerdo con una realización de la invención. En este ejemplo, el sistema de control 500 comprende un controlador maestro 220, una base de datos 210 que se utiliza para realizar un seguimiento de los contenedores de almacenamiento 106, un planificador de encaminamiento 200 utilizado para encontrar rutas óptimas para los vehículos de manipulación de contenedores 201 y un transmisor/receptor 225 para comunicar instrucciones a cada vehículo de manipulación de contenedores 201. La figura muestra que el planificador de encaminamiento 200 está conectado a la base de datos 210. Sin embargo, este puede no ser el caso, ya que el planificador de encaminamiento 200 puede recibir toda la información necesaria desde el controlador maestro 220.

El sistema de control 500 normalmente se comunica con un ordenador central donde se transmiten órdenes y tareas al sistema de control 500. El sistema de control 500 se comunica además con los controladores de vehículo 230 situados en cada vehículo de manipulación de contenedores 201 y controla el flujo de tráfico de los vehículos de manipulación de contenedores 201 de acuerdo con la información proporcionada por el planificador de encaminamiento 200. La comunicación se realiza preferiblemente de forma inalámbrica, por ejemplo mediante señales de radio o señales luminosas.

La figura 3 es un diagrama de flujo que ilustra las diferentes etapas del método 400 para el encaminamiento y reencaminamiento eficientes de vehículos de manipulación de contenedores 201 de un sistema automatizado de almacenamiento y recuperación 1.

La primera etapa 410 del método es ejecutar un algoritmo de búsqueda de rutas de múltiples agentes, MAPF, en el sistema de control 500 para establecer y asignar rutas en el sistema de rieles 108 para los vehículos de manipulación de contenedores 201 desde sus ubicaciones actuales hasta las tareas asignadas en las ubicaciones de destino.

A modo de ejemplo, una tarea puede ser, por ejemplo, recoger un contenedor de almacenamiento 106 específico y llevarlo a una columna de puerto ubicada en otra ubicación. Cuando varios vehículos de manipulación de contenedores 201 reciben diferentes tareas y ubicaciones de destino, es vital que las rutas que siguen en el sistema de rieles sean únicas para cada vehículo de manipulación de contenedores 201, evitando así colisiones.

Como se mencionó en la introducción, el MAPF se utiliza para encontrar rutas utilizadas para controlar el flujo de tráfico de muchos agentes simultáneamente sin que colisionen. En el presente caso, con el sistema automatizado de almacenamiento y recuperación 1, los agentes son los vehículos de manipulación de contenedores 201.

Los diferentes módulos del sistema de control 500 se pueden configurar como una unidad de control central que ejecuta y controla todas las diferentes etapas del método descrito en el presente documento, o como unidades separadas que están conectadas entre sí para formar el sistema de control 500. Con módulos separados, como se muestra a modo de ejemplo en la figura 2, el módulo denominado planificador de encaminamiento 200 será el que ejecute el MAPF para encontrar rutas factibles para los vehículos de manipulación de contenedores 201 desde sus ubicaciones actuales hasta sus destinos y para bloquear una primera parte de las rutas que no se pueden cambiar. Las rutas resultantes encontradas para los vehículos de manipulación de contenedores 201 se comunican al controlador maestro 220 que, a través del transmisor/receptor 225, controlará cada vehículo de manipulación de contenedores de acuerdo con las rutas establecidas.

El MAPF se puede utilizar para encontrar rutas para todos los vehículos de manipulación de contenedores 201 que operen en un sistema de rieles basado en una cuadrícula 108, o se puede utilizar para un grupo seleccionado de vehículos de manipulación de contenedores 201.

Para sistemas automatizados de almacenamiento y recuperación 1 más grandes, por ejemplo operados por cientos de vehículos de manipulación de contenedores 201, uno o más vehículos de manipulación de contenedores 201 pueden dedicarse a realizar tareas específicas y operar en áreas asignadas donde siguen rutas preestablecidas en el sistema de rieles 108.

Otro ejemplo es cuando un primer grupo de vehículos de manipulación de contenedores 201 se controla de acuerdo con un MAPF en un área del sistema de rieles 108, mientras que un segundo o más grupos de vehículos de manipulación de contenedores 201 se controlan de acuerdo con otro MAPF en otra área del sistema de rieles 108. Se pueden ejecutar diferentes algoritmos MAPF en paralelo por diferentes sistemas informáticos para acelerar la ejecución.

Ejemplos de vehículos de manipulación de contenedores 201 que realizan tareas dedicadas específicas son, por ejemplo, vehículos de excavación que preparan un contenedor de almacenamiento 106 específico, para su posterior manipulación por otros vehículos de manipulación de contenedores 201, retirando primero otros contenedores de almacenamiento 106 apilados encima del contenedor de almacenamiento 106 específico almacenado en una columna de almacenamiento 105. Los vehículos de manipulación de contenedores 201 que realizan tareas dedicadas específicas pueden tener patrones de movimiento y velocidades diferentes en comparación con otros vehículos de manipulación de contenedores 201. Por lo tanto, se pueden controlar por separado o se pueden realizar ajustes en las decisiones de encaminamiento para tener en cuenta estas diferencias.

Las rutas para los vehículos de manipulación de contenedores 201 se establecen y asignan después de llevar a cabo la primera etapa 410 del método, es decir, de ejecutar un algoritmo MAPF. Estas rutas se ejecutan desde la ubicación actual de los vehículos de manipulación de contenedores 201 hasta las tareas asignadas en las ubicaciones de destino.

La siguiente etapa 420 del método es determinar lo lejos pueden recorrer los vehículos de manipulación de contenedores 201 en una primera parte de las rutas asignadas dentro de un intervalo de tiempo establecido. La duración del intervalo de tiempo establecido se puede configurar de acuerdo con el tamaño del sistema automatizado de almacenamiento y recuperación 1 y la cantidad de vehículos de manipulación de contenedores 201 que se incluirán en el algoritmo MAPF.

De acuerdo con una realización, el intervalo de tiempo establecido es un intervalo de tiempo que corresponde al tiempo que un vehículo de manipulación de contenedores 201 utiliza para moverse desde su posición actual a una posición en el sistema de rieles 108 por encima de la columna de almacenamiento 105 contigua más cercana. Si un vehículo de manipulación de contenedores 201 acaba de sobrepasar una posición por encima de una columna de almacenamiento 105, no podrá cambiar de dirección hasta que llegue a la siguiente columna de almacenamiento contigua más cercana. El intervalo de tiempo será entonces el tiempo que utiliza el vehículo de manipulación de contenedores 201 para desplazarse hasta la columna de almacenamiento 105 más cercana donde puede cambiar de dirección si es necesario.

De acuerdo con otra realización, el intervalo de tiempo establecido corresponde al tiempo de ejecución que utiliza el sistema de control 500 para ejecutar el algoritmo MAPF, es decir, para establecer las rutas e instruir a los vehículos de manipulación de contenedores 201 para que se desplacen a lo largo de las rutas establecidas. Esto proporcionará una forma óptima de encaminamiento, ya que es posible que el algoritmo MAPF ya haya establecido nuevas rutas posibles cuando los vehículos de manipulación de contenedores 201 lleguen al final de las rutas bloqueadas. Por lo tanto, los vehículos de manipulación de contenedores 201 no tienen que detenerse al final de una ruta bloqueada para recibir nuevas instrucciones de recorrido, sino que pueden continuar y seguir la primera ruta asignada o ser reencaminados a una nueva ruta sin detenerse.

La siguiente etapa 430 del método es bloquear las primeras partes de las rutas asignadas que los vehículos de manipulación de contenedores 201 pueden recorrer dentro de dicho intervalo de tiempo establecido. Esto significa que esta parte de la ruta no se puede cambiar, mientras que el resto de las rutas asignadas establecidas por el MAPF se pueden cambiar a nuevas rutas comenzando desde las ubicaciones finales de las rutas bloqueadas.

La siguiente etapa 440 es instruir a los vehículos de manipulación de contenedores 201 para que se muevan desde sus ubicaciones actuales a las ubicaciones finales en las rutas bloqueadas asignadas.

Las etapas 410 a 440 se repiten para cada vehículo de manipulación de contenedores 201 hasta que hayan completado las tareas asignadas. Cada vez que se repite el método, puede verse como una iteración, donde cada iteración permite reencaminar los vehículos de manipulación de contenedores 210 desde las rutas establecidas por el MAPF en una iteración anterior. De acuerdo con este método, los vehículos de manipulación de contenedores 201 pueden cambiar fácilmente el tipo de tarea o de objetivo antes de finalizar una primera tarea asignada, o se pueden agregar nuevos vehículos de manipulación de contenedores 201 activos para operar en el sistema de almacenamiento.

De acuerdo con la invención, una ruta bloqueada se extiende si se le da prioridad a un vehículo de manipulación de contenedores 201. Un ejemplo de esto es cuando un puerto señala que está listo para recibir un contenedor de almacenamiento 106 del vehículo de manipulación de contenedores 201. En este caso, la ruta completa determinada por el MAPF para el vehículo de manipulación de contenedores 201, que va desde su posición actual hasta el puerto, se bloquea y no se puede cambiar hasta que se complete la tarea asignada, por ejemplo, entregar un contenedor de almacenamiento al puerto.

De acuerdo con otra realización de la invención, una ruta bloqueada también se extiende si un vehículo de manipulación de contenedores 201 no responde a las instrucciones del sistema de control 500. Esto puede deberse a un vehículo de manipulación de contenedores 201 defectuoso. Es posible que se haya detenido en algún lugar a lo largo de su ruta bloqueada o que no responda a las instrucciones, como las instrucciones de reencaminamiento al final de una ruta bloqueada. Si es así, puede continuar el recorrido hasta algún lugar a lo largo de su ruta asignada, es decir, aquella parte de la ruta asignada que no está bloqueada. Al bloquear la ruta completa establecida por el MAPF, otros vehículos que manipulen contenedores evitarán colisionar con ella.

Al ampliar las rutas bloqueadas para incluir las rutas completas establecidas por el algoritmo MAPF, es decir, desde las ubicaciones actuales de los vehículos de manipulación de contenedores 201 hasta las tareas en las ubicaciones de destino, se evitan posibles conflictos con otros vehículos de manipulación de contenedores 201. Esto es favorable cuando, por ejemplo, se le da prioridad a un vehículo de manipulación de contenedores 201 o cuando un puerto señala que está listo para interactuar con un vehículo de manipulación de contenedores 201 asignado.

De acuerdo con la invención, las rutas bloqueadas se excluyen de la ejecución en el algoritmo MAPF. Para los vehículos de manipulación de contenedores 201 que funcionan normalmente sin prioridad, esto significa que su ubicación actual se utiliza como entrada para el algoritmo MAPF, es decir, las ubicaciones actuales proporcionan un conjunto de ubicaciones finales para las rutas bloqueadas. Para los vehículos de manipulación de contenedores 201 con prioridad o los vehículos de manipulación de contenedores 201 defectuosos, la ruta completa establecida hasta la tarea asignada en las ubicaciones de destino se excluye de la ejecución posterior en el algoritmo MAPF. La determinación de qué vehículos de manipulación de contenedores tendrán prioridad puede basarse en varios factores. Algunas tareas afectan al rendimiento más que otras. Un vehículo de manipulación de contenedores 201 asignado para entregar un contenedor de almacenamiento 106 en un puerto normalmente tiene prioridad en comparación con un vehículo de manipulación de contenedores 201 asignado para entregar un contenedor de almacenamiento 106 a una columna de almacenamiento 105. Normalmente, las rutas óptimas se crean primero para los vehículos de manipulación de contenedores 201 priorizados. Existen diferentes algoritmos de encaminamiento para priorizar rutas y determinar rutas óptimas. Se basan en funciones de coste con un conjunto de diferentes parámetros de entrada como el tiempo y la distancia para llegar a un destino, la prioridad de la tarea asignada, el tiempo de espera previsto en un puerto, etc.

Como se mencionó, el algoritmo MAPF se utiliza para establecer y asignar rutas en el sistema de rieles 108 para los vehículos de manipulación de contenedores 201 desde sus ubicaciones actuales hasta tareas en ubicaciones de destino. Las entradas al algoritmo MAPF son el diseño del sistema de rieles 108, los vehículos de manipulación de contenedores 201 en funcionamiento y la ubicación actual y la ubicación de destino de cada vehículo de manipulación de contenedores 201. De acuerdo con una realización del método, una entrada adicional al algoritmo MAPF es el espacio libre requerido entre cada ruta establecida por el algoritmo MAPF, por ejemplo, para proporcionar suficiente espacio libre, con un margen, para evitar colisiones. El espacio libre requerido se adapta al tipo de vehículo de manipulación de contenedores 201 utilizado para una tarea, así como a los tipos de rieles utilizados en la ruta hacia las tareas en los lugares de destino.

Una configuración de riel de doble vía permite que dos vehículos de manipulación de contenedores pasen uno junto al otro sobre rieles en dos columnas de almacenamiento 105 adyacentes. Las configuraciones de riel de vía única no permiten la etapa de que pasen vehículos de manipulación de contenedores 201 y pueden requerir un espacio de paso libre, entre dos vehículos de manipulación de contenedores 201 que pasen, correspondiente al menos a la huella de una columna de almacenamiento, si no es posible sacar del camino el vehículo de manipulación de contenedores que esté obstruyendo.

De acuerdo con una realización del método, los movimientos de los vehículos de manipulación de contenedores 201 se controlan adicionalmente para evitar posibles problemas de colas en los lugares de destino. Esto se puede hacer de diferentes maneras. Si, por ejemplo, se prevé que varios vehículos de manipulación de contenedores 201 llegarán al mismo puerto aproximadamente al mismo tiempo, se pueden clasificar y se pueden reducir las velocidades de avance de los vehículos de manipulación de contenedores 201 de menor rango o se pueden detener en un lugar donde no estorben hasta que un vehículo de manipulación de contenedores 201 de primer rango haya terminado su tarea en el puerto. Otra forma de evitar un problema de cola previsto es, por ejemplo, reencaminar los vehículos de manipulación de contenedores para que finalicen las tareas asignadas en otros lugares de destino, por ejemplo entregar un contenedor de almacenamiento 106 en otro puerto.

Hay diferentes vehículos de manipulación de contenedores que tienen diferentes especificaciones, como aceleración, velocidad y carga máxima. Una entrada adicional al algoritmo MAPF puede ser proporcionar detalles del tipo de vehículos de manipulación de contenedores 201 asignados para realizar una tarea, así como la carga actual en el vehículo de manipulación de contenedores 201 en función del peso de un contenedor de almacenamiento 106 transportado y el estado del vehículo de manipulación de contenedores 201, por ejemplo, batería baja, piezas desgastadas, agarre de las ruedas, etc. Dicha entrada adicional puede afectar a la forma en que se controlan los movimientos del vehículo de manipulación de contenedores 201 y si es necesario aumentar las distancias libres entre los vehículos.

La figura 4 ilustra un ejemplo simple de cómo se establecían rutas de acuerdo con el método de encaminamiento antiguo y cómo se establecen rutas de acuerdo con el método de encaminamiento mejorado descrito anteriormente.

R1 y R2 indican las ubicaciones actuales de los vehículos de manipulación de contenedores 1 y 2. D1 y D2 indican las ubicaciones de destino de los vehículos de manipulación de contenedores 1 y 2.

En este ejemplo, el robot 1 en R1 recibe una tarea justo antes de que el robot 2 en R2 reciba una tarea. De acuerdo con los sistemas de encaminamiento anteriores, primero se creará y bloqueará una ruta que vaya desde la ubicación actual R1 del robot 1 hasta su destino D1. A continuación, se creará una ruta para el robot 2, y esta se hace de tal manera que no entre en conflicto con la ruta bloqueada establecida del robot 1. Como se ve en la figura 4, la ruta del robot 2 no es óptima en términos de distancia recorrida, ya que necesita evitar el espacio D1 de la cuadrícula y posiblemente cualquier otro espacio de la cuadrícula bloqueado en la ruta asignada de R1 a D1.

De acuerdo con el método de encaminamiento mejorado divulgado en el presente documento, solo se bloquea una primera parte de las rutas establecidas para los vehículos de manipulación de contenedores, mientras que la última parte de la ruta establecida es una ruta planificada que se puede cambiar. Esto significa que cuando los vehículos de manipulación de contenedores llegan al final de las rutas bloqueadas y se ejecuta nuevamente el algoritmo MAPF, pueden ser reencaminados para seguir una nueva ruta desde las posiciones de inicio actuales en el final de las rutas bloqueadas.

Por lo tanto, la última parte de la ruta del robot 1 no se bloqueará, asumiendo que el robot 1 aún no ha llegado al final de la primera parte bloqueada, cuando el algoritmo MAPF establece una ruta para el robot 2, lo que da como resultado rutas óptimas para ambos vehículos de manipulación de contenedores.

Esta nueva forma de encaminamiento es a la vez flexible y eficiente y considera todas las rutas de todos los vehículos de manipulación de contenedores 201 hacia sus lugares de destino asignados en múltiples etapas mientras un determinado vehículo de manipulación de contenedores se dirige a lo largo de una ruta asignada.

La invención está definida además por un sistema de control 500 para controlar el encaminamiento y reencaminamiento eficientes de los vehículos de manipulación de contenedores 201 que manipulan contenedores de almacenamiento 106 en un sistema automatizado de almacenamiento y recuperación 1 como el descrito anteriormente con referencia a la figura 1.

El sistema de control 500 se ha descrito anteriormente con referencia a la figura 2. Además, comprende un procesador dispuesto para ejecutar un programa informático que, cuando se ejecuta, realiza el método descrito anteriormente, con referencia a la figura 3, lo que permite el encaminamiento y reencaminamiento eficientes de los vehículos de manipulación de contenedores 201 que manipulan contenedores de almacenamiento 106 en un sistema automatizado de almacenamiento y recuperación 1. El programa informático podría ejecutarse en un procesador del planificador de encaminamiento 200.

Claims (13)

REIVINDICACIONES

1. Un método para encaminar y reencaminar vehículos de manipulación de contenedores (201) que manipulan contenedores de almacenamiento (106) en un sistema automatizado de almacenamiento y recuperación que comprende una estructura de armazón (100) que forma una estructura de cuadrícula de almacenamiento tridimensional (104) para almacenar los contenedores de almacenamiento (106) en columnas de almacenamiento (105), incluyendo la estructura de armazón un sistema de rieles basado en cuadrícula (108) dispuesto por encima de las columnas de almacenamiento (105), con el sistema de rieles (108) proporcionando rutas disponibles para los vehículos de manipulación de contenedores (201) que manipulan y transfieren los contenedores de almacenamiento (106) hacia y desde las columnas de almacenamiento (105), y en donde cada vehículo de manipulación de contenedores (201) comprende un primer conjunto de ruedas configurado para mover el vehículo a lo largo de una primera dirección lateral (X) del sistema de rieles basado en cuadrícula y un segundo conjunto de ruedas configurado para mover el vehículo a lo largo de una segunda dirección lateral (Y) del sistema de rieles basado en cuadrícula (108), siendo la segunda dirección (Y) perpendicular a la primera dirección (X), estando controlados los movimientos de los vehículos de manipulación de contenedores por un sistema de control (500) que determina qué tareas deben realizar los vehículos de manipulación de contenedores (201) especificados, las ubicaciones de destino para realizar las tareas y qué rutas deben recorrer los vehículos de manipulación de contenedores (201) en el sistema de rieles (108), el método comprende las siguientes etapas realizadas por el sistema de control (500):

a. ejecutar (410) un algoritmo de búsqueda de rutas de múltiples agentes, MAPF, en el sistema de control (500) para establecer y asignar rutas en el sistema de rieles (108) para todos los vehículos de manipulación de contenedores (201) desde sus ubicaciones actuales hasta las tareas asignadas en las ubicaciones de destino, b. determinar (420) la distancia que pueden recorrer los vehículos de manipulación de contenedores (201), siendo esta una primera parte, en las rutas asignadas dentro de un intervalo de tiempo establecido, siendo la primera parte más corta que las rutas asignadas a los destinos,

c. bloquear (430) las primeras partes de las rutas asignadas que los vehículos de manipulación de contenedores (201) pueden recorrer dentro del intervalo de tiempo establecido, donde las primeras partes bloqueadas de las rutas no se pueden cambiar y se excluyen de la consideración de las rutas disponibles mientras se ejecuta el algoritmo m Ap F,

d. extender las primeras partes bloqueadas de la ruta asignada para un vehículo de manipulación de contenedores (201) al que se le da prioridad,

e. instruir (440) a los vehículos de manipulación de contenedores (201) para que se desplacen desde sus ubicaciones actuales a una ubicación final en las primeras partes bloqueadas de las rutas asignadas, f. repetir las etapas a) a f).

2. El método de acuerdo con la reivindicación 1, donde el intervalo de tiempo establecido en la etapa b) corresponde a un tiempo de ejecución que el sistema de control (500) utiliza para ejecutar el algoritmo MAPF e instruir a los vehículos de manipulación de contenedores (201) para que se muevan de acuerdo con rutas establecidas.

3. El método de acuerdo con la reivindicación 1 o 2, donde el intervalo de tiempo establecido en la etapa b) es el tiempo transcurrido para que todos los vehículos de manipulación de contenedores (201) se muevan desde las posiciones actuales a las posiciones en el sistema de rieles (108) ubicadas por encima de las columnas de almacenamiento (105) más cercanas donde pueden cambiar de dirección.

4. El método de acuerdo con cualquiera de las reivindicaciones anteriores, donde la duración del intervalo de tiempo establecido en la etapa b) se establece en función del tamaño del sistema automatizado de almacenamiento y/o recuperación y del número de vehículos de manipulación de contenedores (201) a incluir en el algoritmo MAPF.

5. El método de acuerdo con cualquiera de las reivindicaciones anteriores, en donde el método incluye extender la parte bloqueada de la ruta asignada para un vehículo de manipulación de contenedores (201) que no esté respondiendo a las instrucciones.

6. El método de acuerdo con la reivindicación 5, donde se extiende la parte bloqueada de la ruta asignada a lo largo de la ruta establecida por el algoritmo MAPF desde la ubicación actual del vehículo de manipulación de contenedores (201) hasta la tarea en la ubicación de destino.

7. El método de acuerdo con cualquiera de las reivindicaciones anteriores, donde la separación entre rutas establecida por el algoritmo MAPF está adaptada al tipo de vehículo de manipulación de contenedores (201) que recorre las rutas asignadas.

8. El método de acuerdo con cualquiera de las reivindicaciones anteriores, donde se controlan los movimientos de los vehículos de manipulación de contenedores (201) para evitar un posible problema de colas en las ubicaciones de destino.

9. El método de acuerdo con la reivindicación 8, donde los vehículos de manipulación de contenedores (201) son redirigidos si se prevé un problema de colas en los lugares de destino.

10. El método de acuerdo con la reivindicación 9, donde los vehículos de manipulación de contenedores (201) son redirigidos a posiciones o rutas donde no estén presentes vehículos de manipulación de contenedores (201) o hacia las que no estén encaminados.

11. El método de acuerdo con cualquiera de las reivindicaciones anteriores, donde los movimientos de los vehículos de manipulación de contenedores (201) se controlan en función del tipo de los vehículos de manipulación de contenedores (201), la carga actual transportada y el estado de los vehículos de manipulación de contenedores (201).

12. Un sistema de control (500) sistema para controlar el encaminamiento y reencaminamiento eficientes de vehículos de manipulación de contenedores (201) que manipulan contenedores de almacenamiento (106) en un sistema automatizado de almacenamiento y recuperación que comprende una estructura de armazón (100) que forma una estructura de cuadrícula de almacenamiento tridimensional (104) para almacenar los contenedores de almacenamiento (106) en columnas de almacenamiento (105), incluyendo la estructura de armazón (100) un sistema de rieles basado en cuadrícula (108) que está dispuesto por encima de las columnas de almacenamiento (105) y proporcionando el sistema de rieles (108) rutas disponibles para los vehículos de manipulación de contenedores (201) que manipulan y transfieren los contenedores de almacenamiento (106) hacia y desde las columnas de almacenamiento (105), y en donde cada vehículo de manipulación de contenedores (201) comprende un primer conjunto de ruedas configurado para mover el vehículo a lo largo de una primera dirección lateral (X) del sistema de rieles basado en cuadrícula y un segundo conjunto de ruedas configurado para mover el vehículo a lo largo de una segunda dirección lateral (Y) del sistema de rieles basado en cuadrícula (108), siendo la segunda dirección (Y) perpendicular a la primera dirección (X), estando controlados los movimientos de los vehículos de manipulación de contenedores por el sistema de control (500) que determina qué tareas deben realizar los vehículos de manipulación de contenedores (201) específicos, las ubicaciones de destino para realizar las tareas y qué rutas deben recorrer los vehículos de manipulación de contenedores (201) en el sistema de rieles (108), donde

el sistema de control (500) comprende un planificador de encaminamiento (200) para encontrar rutas óptimas para los vehículos de manipulación de contenedores (201), una base de datos (210) para realizar un seguimiento de los contenedores de almacenamiento (106), un controlador maestro (220) conectado a un transmisor/receptor (225), donde el sistema de control (500) está adaptado para ejecutar el método de acuerdo con las reivindicaciones 1 a 11 y comunicar instrucciones de control a cada vehículo de manipulación de contenedores (201).

13. Un producto de programa informático que, cuando es ejecutado por un procesador de un sistema de control (500) de un sistema automatizado de almacenamiento y recuperación (1), realiza el método de acuerdo con las reivindicaciones 1 a 11 para el encaminamiento y reencaminamiento eficientes de vehículos de manipulación de contenedores (201) que manipulan contenedores de almacenamiento (106) en un sistema automatizado de almacenamiento y recuperación.