ROUTING OF CONTAINER HANDLING VEHICLES OPERATING AN AUTOMATED STORAGE SYSTEM

Abstract

A method, control system and computer program for 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 (X) of the grid-based rail system and a second set of wheels configured to move the vehicle along a second lateral direction (Y) of the grid-based rail system, the second direction (Y) being perpendicular to the first direction (X), the movements of the container handling vehicles being controlled by a 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. The method comprises the following steps performed by the control system when executing the computer program: running a multi-agent pathfinding algorithm, MAPF, 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; 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; locking the first parts of the assigned routes that the container handling vehicles can travel within the set time interval; instructing the container handling vehicles to move from their current locations to an end location on the assigned locked routes; repeating steps above.

Claims

1. A method for routing of container handling vehicles in an automated storage and retrieval system comprising a framework structure, the movements of the container handling vehicles being controlled by a control system, the method comprising the following steps performed by the control system: a. running a pathfinding algorithm for establishing and assigning routes 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; d. instructing the container handling vehicles to move from their current locations to an end location on the assigned locked routes; e. repeating steps a) to d).

2. The method according to claim 1, wherein an upper limit of the set time interval in step b) corresponds to an execution time the control system uses for executing the pathfinding algorithm and instructing the container handling vehicles to move according to established routes.

3. The method according to claim 1, wherein an upper limit of the set time interval in step b) is the elapsed time for all container handling vehicles to move from current positions to positions on a grid-based rail system located above nearest storage columns of the framework structure where they can change directions.

4. The method according to claim 1, wherein the duration of the set time interval in step b) is set according to the size of the automated storage and retrieval system and the number of container handling vehicles to be included in the pathfinding algorithm.

5. The method according to claim 1, wherein the method includes extending the locked part of the assigned route for a container handling vehicle which is given priority.

6. The method according to claim 5, wherein a container handling vehicle is given priority if its assigned task is to deliver a storage container to a port column of the automated storage and retrieval system.

7. The method according to claim 5, where the locked part of the assigned route is extended along the route established by the pathfinding algorithm from the current location of the container handling vehicle to a task at the destination location.

8. The method according to claim 1, wherein the method includes extending the locked part of the assigned route for a container handling vehicle which is not responding to instructions.

9. The method according to claim 1, wherein locked routes are excluded from consideration of available routes during running the pathfinding algorithm.

10. The method according to claim 1, wherein the clearance between each route established by the pathfinding algorithm is adapted to one or more of: a type of container handling vehicle travelling the assigned routes; and a type of rails of the automated storage and retrieval system on the assigned routes.

11. The method according to claim 1, wherein the movements of the container handling vehicles are controlled to avoid a possible queueing problem at the destination locations.

12. The method according to claim 11, wherein if two or more of the container handling vehicles are scheduled to arrive at a same port at about a same time, the method comprises one or more of: reducing a driving speed of one of the two or more container handling vehicles; and stopping one of the two or more container handling vehicles.

13. The method according to claim 11, wherein container handling vehicles are redirected if a queueing problem is foreseen at the destination locations.

14. The method according to claim 13, wherein container handling vehicles are redirected to positions or routes where container handling vehicles are not present or routed towards.

15. The method according to claim 1, wherein the movements of the container handling vehicles are controlled according to type of container handling vehicles, current load being carried and condition of the container handling vehicles.

16. The method according to claim 1, wherein the control system runs the pathfinding algorithm to establish and assign routes for the container handling vehicles in a first area of the automated storage and retrieval system, and wherein the control system runs a further pathfinding algorithm to establish and assign routes for container handling vehicles in a second area of the automated storage and retrieval system.

17. The method according to claim 16, wherein the control system runs the pathfinding algorithm and the further pathfinding algorithm in parallel.

18. The method according to claim 1, wherein inputs to the pathfinding algorithm include a layout of a rail system on which the container handling vehicles travel, the current locations of the container handling vehicles, and the destination locations of the container handling vehicles.

19. A control system for controlling efficient routing and rerouting of container handling vehicles in an automated storage and retrieval system comprising a framework structure, the movements of the container handling vehicles being controlled by the control system, wherein the control system (500) is adapted for executing the method according to claim 1 and communicating control instructions to each container handling vehicle.

20. A computer program product that when executed by a processor in a control system of an automated storage and retrieval system performs the method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0061] The following drawings are appended to facilitate the understanding of the invention. The drawings show embodiments of the invention, which will now be described by way of example only, where:

[0062] FIG. 1 is a perspective view of a framework structure of a prior art automated storage and retrieval system.

[0063] FIG. 2 shows an example of a control system for controlling container handling vehicles operating on an automated storage and retrieval system.

[0064] FIG. 3 is a flowchart illustrating the different steps of the method for efficient routing and rerouting of container handling vehicles of an automated storage and retrieval system.

[0065] FIG. 4 illustrates a simple routing example according to previous and new routing.

REFERENCES

[0066] 1Automated storage and retrieval system [0067] 100Framework structure [0068] 102Upright members of framework structure [0069] 103Horizontal members of framework structure [0070] 104Storage grid structure [0071] 105Storage column [0072] 106Storage container [0073] 106Particular position of storage container [0074] 107Stack [0075] 108Rail system [0076] 110Parallel rails in first direction (X) [0077] 110aFirst rail in first direction (X) [0078] 110bSecond rail in first direction (X) [0079] 111Parallel rail in second direction (Y) [0080] 111aFirst rail of second direction (Y) [0081] 111bSecond rail of second direction (Y) [0082] 112Access opening [0083] 119first Port column [0084] 119first Port [0085] 120second Port column [0086] 120second Port [0087] 200Routing planner [0088] 201Container handling vehicle [0089] 210Database [0090] 220Master controller [0091] 225Transmitter/Receiver [0092] 230Vehicle controller [0093] XFirst direction [0094] YSecond direction [0095] ZThird direction [0096] 500Control system

DETAILED DESCRIPTION OF THE INVENTION

[0097] In the following description, the invention will be explained in more detail with reference to the appended drawings. It should be understood, however, that the drawings are not intended to limit the invention to the subject-matter depicted in the drawings.

[0098] A typical prior art automated storage and retrieval system 1 with a framework structure 100 was described in the background section above with reference to FIG. 1.

[0099] The framework structure 100 can be of any size, and it is understood that it can be considerably wider and/or longer and/or deeper than the one disclosed in FIG. 1. For example, the framework structure 100 may have a horizontal extent of more than 700700 storage columns 105 and a storage depth for storing more than twelve stacked storage containers 106, and where storage containers 106 are handled by hundreds of container handling vehicles 201 running on the rail system 108.

[0100] Also, the storage grid 104 can be considerably deeper than disclosed in FIG. 1, showing stacks of eight storage containers 106. For example, the storage grid 104 may be designed to hold twelve stacked storage containers 106.

[0101] The container handling vehicles 201 can be of any type known in the art, e.g. any one of the automated container handling vehicles disclosed in WO2014/090684 A1, in NO317366 or in WO2015/193278A1.

[0102] The rail system 108 arranged across the top of the framework structure 100 allows the container handling vehicles 201 to move horizontally between storage columns 105 and ports that they are interacting with, i.e. ports they are instructed to deliver or retrieve a storage container 106 to and from.

[0103] The automated storage and retrieval system 1 comprises a framework structure 100 forming a three-dimensional storage grid structure 104 with a grid-based rail system 108 for storing the storage containers 106 in storage columns 105, the grid-based rail system 108 being arranged above the storage columns 105 with the rail system 108 providing available routes for the container handling vehicles 201 handling and transferring the storage containers 106 to and from the storage columns 105, and wherein each container handling vehicle 201 comprises a first set of wheels configured to move the vehicle along a first lateral direction (X) of the grid-based rail system and a second set of wheels configured to move the vehicle along a second lateral direction (Y) of the grid-based rail system 108, the second direction (Y) being perpendicular to the first direction (X), the movements of the container handling vehicles are controlled by a control system 500, that determines which tasks to be done by specified container handling vehicles 201, destination locations for performing the tasks and which routes the container handling vehicles 201 are to travel on the rail system 108.

[0104] FIG. 2 shows an example of a control system 500 for controlling the container handling vehicles 201 according to an embodiment of the invention. In this example, the control system 500 comprises a master controller 220, a database 210 that is used for keeping track of the storage containers 106, a routing planner 200 used for finding optimal routes for the container handling vehicles 201 and a transmitter/receiver 225 for communicating instructions to each container handling vehicle 201. The figure shows that the routing planner 200 is connected to the database 210. This may however not be the case as the routing planner 200 may receive all necessary information from the master controller 220.

[0105] The control system 500 typically communicates with a central computer where orders and tasks are transmitted to the control system 500. The control system 500 further communicates with vehicle controllers 230 in each container handling vehicle 201 and controls traffic flow of the container handling vehicles 201 according to input from the routing planner 200. The communication is preferably performed wirelessly, e.g. via radio signals, light signals.

[0106] FIG. 3 is a flowchart illustrating the different steps of the method 400 for efficient routing and rerouting of container handling vehicles 201 of an automated storage and retrieval system 1.

[0107] The first step 410 of the method is running a multi-agent pathfinding algorithm, MAPF, in the control system 500 for establishing and assigning routes on the rail system 108 for the container handling vehicles 201 from their current locations to assigned tasks at destination locations.

[0108] As an example, a task may for instance be to pick up a specified storage container 106 and bring it to a port column located at another location. When several container handling vehicles 201 receive different tasks and destination locations it is vital that the routes they are following on the rail system are unique for each container handling vehicle 201 thereby avoiding collisions.

[0109] As mentioned in the introduction, MAPF is used for finding routes used for controlling traffic flow of many agents simultaneously without colliding. In the present case, with the automated storage and retrieval system 1, the agents are the container handling vehicles 201.

[0110] The different modules of the control system 500 can be configured as one central control unit executing and controlling all the different steps of the method described herein, or as separate units which are connected to each other to make the control system 500. With separate modules, as shown as an example in FIG. 2, the module named routing planner 200 will be the one running the MAPF for finding feasible routes for the container handling vehicles 201 from their current locations to their destinations and for locking a first part of the routes that cannot be changed. The resulting routes found for the container handling vehicles 201 are communicated to the master controller 220 which will, via the transmitter/receiver 225, control each container handling vehicle according to established routes.

[0111] The MAPF can be used for finding routes for all container handling vehicles 201 operating on a grid-based rail system 108 or it can be used for a selected group of container handling vehicles 201.

[0112] For larger automated storage and retrieval systems 1, e.g. operated by hundreds of container handling vehicles 201, one or more container handling vehicles 201 can be dedicated to performing specific tasks and operating in allocated areas where they follow preset routes on the rail system 108.

[0113] Another example is where a first group of container handling vehicles 201 are controlled according to one MAPF in one area of the rail-system 108, while a second or further group of container handling vehicle 201 are controlled according to another MAPF in another area of the rail-system 108. Different MAPF algorithms can be executed in parallel by different computer systems to speed up execution.

[0114] Examples of container handling vehicles 201 performing specific dedicated tasks are for instance digging vehicles preparing a specific storage container 106 for further handling by other container handling vehicles 201 by first removing other storage containers 106 stacked above the specific storage container 106 stored in a storage column 105.

[0115] Container handling vehicles 201 performing specific dedicated tasks may have different moving patterns and speeds compared to other container handling vehicles 201. These can therefore be separately controlled, or adjustments can be made in the routing decisions to take account of these differences.

[0116] Routes for the container handling vehicles 201 are established and assigned after executing the first step 410 of the method, i.e. running a MAPF algorithm. These routes are running from the current location of the container handling vehicles 201 to allocated tasks at destination locations.

[0117] The next step 420 of the method is determining how far the container handling vehicles 201 can travel on a first part of the assigned routes within a set time interval. The duration of the set time interval can be set according to the size of the automated storage and retrieval system 1 and the number of container handling vehicles 201 to be included in the MAPF algorithm.

[0118] According to one embodiment, the set time interval is a time interval corresponding to the time a container handling vehicle 201 uses to move from its current position to a position on the rail system 108 above a closest adjoining storage column 105. If a container handling vehicle 201 has just passed a position above a storage column 105 it will not be able to change direction until it reaches the next closest adjoining storage column. The time interval will then be the time the container handling vehicle 201 uses for moving to the nearest storage column 105 where it can change directions if necessary.

[0119] According to another embodiment, the set time interval corresponds to the execution time the control system 500 uses for running the MAPF algorithm, i.e. for establishing the routes, and instructing the container handling vehicles 201 to move along to established routes. This will provide an optimal way of routing since possible new routes may already have been established by the MAPF algorithm when the container handling vehicles 201 reach the end of the locked routes. The container handling vehicles 201 therefor do not have to stop at the end of a locked route for receiving new driving instructions but can continue and follow the first assigned route or be rerouted to a new route without stopping.

[0120] The next step 430 of the method is locking the first parts of the assigned routes that the container handling vehicles 201 can travel within said set time interval. This means that this part of the route cannot be changed, while the rest of the assigned routes established by the MAPF can be changed to new routes starting from end locations of the locked routes.

[0121] The next step 440 is instructing the container handling vehicles 201 to move from their current locations to end locations on the assigned locked routes.

[0122] Steps 410 to 440 are repeated for each container handling vehicle 201 until they have completed assigned tasks. Each time the method is repeated, it can be seen as an iteration, where each iteration enables rerouting of the container handling vehicles 201 from the routes established by the MAPF in a previous iteration.

[0123] According to this method, container handling vehicles 201 may easily change type of task or target before finishing a first assigned task, or new active container handling vehicles 201 can be added for operating on the storage system.

[0124] According to one embodiment of the invention, a locked route is extended if a container handling vehicle 201 is given priority. An example of this is when a port signals that it is ready to receive a storage container 106 from the container handling vehicle 201. In this case, the complete route determined by the MAPF for the container handling vehicle 201, running from its current position to the port, is locked and cannot be changed until the assigned task is completed, e.g. delivering a storage container to the port.

[0125] According to another embodiment of the invention, a locked route is also extended if a container handling vehicle 201 does not respond to instructions from the control system 500. This may be due to a faulty container handling vehicle 201. It may have stopped somewhere along its locked route or does not respond to instructions, such as rerouting instructions at the end of a locked route. If so, it may then continue to travel somewhere along its assigned route, i.e. that part of the assigned route that is not locked. By locking the complete route established by the MAPF, other container handling vehicles will avoid colliding with it.

[0126] By extending locked routes to include the complete routes established by the MAPF algorithm, i.e. from current locations of the container handling vehicles 201 to tasks at destination locations, possible conflicts with other container handling vehicles 201 are avoided. This is favorable when for instance a container handling vehicle 201 is given priority or when a port signals that it is ready to interact with an assigned container handling vehicle 201.

[0127] According to one embodiment of the method, locked routes are excluded from execution in the MAPF algorithm. For container handling vehicles 201 operating normally without priority this means that their current location is used as an input to the MAPF algorithm, i.e. the current locations provide one set of the end locations for the locked routes. For container handling vehicles 201 with priority, or faulty container handling vehicles 201, the complete established route to the assigned task at destination locations is excluded from further execution in the MAPF algorithm.

[0128] Determining which container handling vehicles that are given priority can be based on several factors. Some tasks impact performance more than other tasks. A container handling vehicle 201 assigned to deliver a storage container 106 in a port is normally prioritized compared to a container handling vehicle 201 assigned to deliver a storage container 106 to a storage column 105. Optimal routes are normally first created for prioritized container handling vehicles 201. There are different routing algorithms for route prioritizing and determining optimal routes. These are based on cost functions with a set of different input parameters such as time and distance to reach a destination, priority of the assigned task, expected waiting time at a port etc.

[0129] As mentioned, the MAPF algorithm is used for establishing and assigning routes on the rail system 108 for the container handling vehicles 201 from their current locations to tasks at destination locations. Inputs to the MAPF algorithm are the layout of the rail system 108, operating container handling vehicles 201 and current location and destination location of each container handling vehicle 201.

[0130] According to one embodiment of the method, additional input to the MAPF algorithm are a clearance required between each route established by the MAPF algorithm for example, to provide sufficient clearance to avoid collisions with a margin. A required clearance is adapted to type of container handling vehicle 201 used for a task as well as types of rails used on the route to the tasks at destination locations.

[0131] A double-track rail configuration allows two container handling vehicles to pass each other on rails on two adjacent storage columns 105. Single-track rail configurations do not allow container handling vehicles 201 to pass and may require a passing clearance corresponding to at least the footprint of one storage column between two passing container handling vehicles 201 if it is not possible to move the obstructing container handling vehicle out of the way.

[0132] According to one embodiment of the method, movements of the container handling vehicles 201 are further controlled to avoid possible queueing problems at destination locations. This can be done in different ways. If for instance it is foreseen that several container handling vehicles 201 will arrive at the same port at about the same time, they can be ranked and driving speeds of lowest ranked container handling vehicles 201 can be reduced or they can be stopped at a location where they are out of the way until a first ranked container handling vehicle 201 has finished its task at the port. Another way of avoiding a foreseen queueing problem is for instance to redirect container handling vehicles to finish assigned tasks at other destination locations, e.g. to deliver a storage container 106 at another port.

[0133] There are different container handling vehicles having different specifications such as acceleration, speed, maximum load. Additional input to the MAPF algorithm may be to provide details of the type of container handling vehicles 201 assigned to perform a task as well as current load on the container handling vehicle 201 based on the weight of a transported storage container 106 and the condition of the container handling vehicle 201, e.g. low battery, worn parts, wheel grip etc. Such additional input can affect how movements of the container handling vehicle 201 are controlled and whether clearances between vehicles need to be increased.

[0134] FIG. 4 illustrates a simple example of how routes where established according to the old routing method and how routes are established according to the improved routing method described above.

[0135] R1 and R2 indicate current locations of container handling vehicles 1 and 2. D1 and D2 indicate destination locations for the container handling vehicle 1 and 2.

[0136] In this example, robot 1 at R1 receives a task just before robot 2 at R2 receives a task.

[0137] According to previous routing systems, a route running from the current location R1 of robot 1 to its destination D1 would be made and locked first. Next, a route for robot 2 would be made, and this is made such that it is not in conflicts with the established locked route of robot 1. As seen from FIG. 4, the route for robot 2 is not optimal in terms of distance travelled as it needs to avoid grid space D1 and possibly any other locked grid spaces on the assigned route from R1 to D1.

[0138] According to the improved routing method disclosed herein, only a first part of the routes established for the container handling vehicles are locked, while the last part of the established route is a planned routed that can be changed. This means that when the container handling vehicles reach the end of the locked routes, and the MAPF algorithm is run again, they can be rerouted to follow a new route from current starting positions at the end of the locked routes.

[0139] The last part of the route for robot 1 will therefore not be locked, assuming that robot 1 has not yet reached the end of the first locked part, when a route for robot 2 is established by the MAPF algorithm, resulting in optimal routes for both container handling vehicles.

[0140] This new way of routing is both flexible and efficient and considers all routes of all container handling vehicles 201 to their assigned destination locations at multiple stages while a given container handling vehicle is making its way along an assigned route.

[0141] The invention is further defined by a control system 500 for controlling efficient routing and rerouting of container handling vehicles 201 handling storage containers 106 in an automated storage and retrieval system 1 as the one described above with reference to FIG. 1.

[0142] The control system 500 is described above with reference to FIG. 2. It further comprises a processor arranged for running a computer program that when executed performs the method described above, with reference to FIG. 3, thereby enabling efficient routing and rerouting of container handling vehicles 201 handling storage containers 106 in an automated storage and retrieval system 1. The computer program might be running in a processor in the routing planner 200.