Routing of container handling vehicles operating an automated storage system

A control system for controlling routing and rerouting of container handling vehicles handling storage containers in an automated storage and retrieval system comprising a framework structure forming a three-dimensional storage grid structure for storing the storage containers in storage columns, the framework structure including a grid-based rail system being arranged above the storage columns with the rail system providing available routes for the container handling vehicles handling and transferring the storage containers to and from the storage columns, and wherein each container handling vehicle comprises a first set of wheels configured to move the vehicle along a first lateral direction of the grid-based rail system and a second set of wheels configured to move the vehicle along a second lateral direction of the grid-based rail system, the second direction being perpendicular to the first direction, the movements of the container handling vehicles being controlled by the control system that determines which tasks are to be done by specified container handling vehicles, destination locations for performing the tasks and which routes the container handling vehicles are to travel on the rail system, wherein

• the control system comprises a routing planner for finding optimal routes for the container handling vehicles, a database for keeping track of the storage containers, a master controller connected to a transmitter/receiver, wherein the control system is adapted for executing a method for routing and rerouting of container handling vehicles handling storage containers in an automated storage and retrieval system and communicating control instructions to each container handling vehicle, wherein the automated storage and retrieval system comprises a framework structure forming a three-dimensional storage grid structure for storing the storage containers in storage columns, the framework structure including a grid-based rail system arranged above the storage columns with the rail system providing available routes for the container handling vehicles handling and transferring the storage containers to and from the storage columns, and wherein each container handling vehicle comprises a first set of wheels configured to move the vehicle along a first lateral direction of the grid-based rail system and a second set of wheels configured to move the vehicle along a second lateral direction of the grid-based rail system, the second direction being perpendicular to the first direction, the movements of the container handling vehicles being controlled by a control system, wherein the control system determines which tasks are to be done by specified container handling vehicles, destination locations for performing the tasks, and which routes the container handling vehicles are to travel on the rail system,
• wherein the method comprises the control system performing:
• (a) running a multi-agent pathfinding algorithm, MAPF algorithm, in the control system for establishing and assigning routes on the rail system for the container handling vehicles from their current locations to assigned tasks at destination locations;
• (b) determining how far the container handling vehicles can travel on a first part of the assigned routes within a set time interval, the first part being shorter than the assigned routes to the destinations;
• (c) locking the first parts of the assigned routes that the container handling vehicles can travel within the set time interval, wherein the locked first parts of the routes cannot be changed and are excluded from consideration of available routes during running the MAPF algorithm;
• (d) extending the locked first parts of the assigned route for a container handling vehicle which is given priority;
• (e) instructing the container handling vehicles to move from their current locations to an end location on the assigned locked routes;
• and
• (f) repeating steps (a) to (f).

A computer program product that when executed by a processor in a control system of an automated storage and retrieval system performs a method for efficient routing and rerouting of container handling vehicles handling storage containers in an automated storage and retrieval system comprising a framework structure forming a three-dimensional storage grid structure for storing the storage containers in storage columns, the framework structure including a grid-based rail system arranged above the storage columns with the rail system providing available routes for the container handling vehicles handling and transferring the storage containers to and from the storage columns, and wherein each container handling vehicle comprises a first set of wheels configured to move the vehicle along a first lateral direction of the grid-based rail system and a second set of wheels configured to move the vehicle along a second lateral direction of the grid-based rail system, the second direction being perpendicular to the first direction, the movements of the container handling vehicles being controlled by a control system, wherein the control system determines which tasks are to be done by specified container handling vehicles, destination locations for performing the tasks, and which routes the container handling vehicles are to travel on the rail system,

• wherein the method comprises the control system performing:
• (a) running a multi-agent pathfinding algorithm, MAPF algorithm, in the control system for establishing and assigning routes on the rail system for the container handling vehicles from their current locations to assigned tasks at destination locations;
• (b) determining how far the container handling vehicles can travel on a first part of the assigned routes within a set time interval, the first part being shorter than the assigned routes to the destinations;
• (c) locking the first parts of the assigned routes that the container handling vehicles can travel within the set time interval, wherein the locked first parts of the routes cannot be changed and are excluded from consideration of available routes during running the MAPF algorithm;
• (d) extending the locked first parts of the assigned route for a container handling vehicle which is given priority;
• (e) instructing the container handling vehicles to move from their current locations to an end location on the assigned locked routes;
• (f) repeating steps (a) to (f).