[go: up one dir, main page]

WO2024251392A1 - Method, system and computer program product for determining non-conflicting routes for container handling vehicles - Google Patents

Method, system and computer program product for determining non-conflicting routes for container handling vehicles Download PDF

Info

Publication number
WO2024251392A1
WO2024251392A1 PCT/EP2024/051343 EP2024051343W WO2024251392A1 WO 2024251392 A1 WO2024251392 A1 WO 2024251392A1 EP 2024051343 W EP2024051343 W EP 2024051343W WO 2024251392 A1 WO2024251392 A1 WO 2024251392A1
Authority
WO
WIPO (PCT)
Prior art keywords
grid
container handling
route
routes
zones
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
PCT/EP2024/051343
Other languages
French (fr)
Inventor
Øystein MYRMO
Vegard SYRE-AAKER
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Autostore Technology AS
Original Assignee
Autostore Technology AS
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Autostore Technology AS filed Critical Autostore Technology AS
Publication of WO2024251392A1 publication Critical patent/WO2024251392A1/en
Anticipated expiration legal-status Critical
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/20—Control system inputs
    • G05D1/24—Arrangements for determining position or orientation
    • G05D1/246—Arrangements for determining position or orientation using environment maps, e.g. simultaneous localisation and mapping [SLAM]
    • G05D1/2464—Arrangements for determining position or orientation using environment maps, e.g. simultaneous localisation and mapping [SLAM] using an occupancy grid
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B65—CONVEYING; PACKING; STORING; HANDLING THIN OR FILAMENTARY MATERIAL
    • B65G—TRANSPORT OR STORAGE DEVICES, e.g. CONVEYORS FOR LOADING OR TIPPING, SHOP CONVEYOR SYSTEMS OR PNEUMATIC TUBE CONVEYORS
    • B65G1/00—Storing articles, individually or in orderly arrangement, in warehouses or magazines
    • B65G1/02—Storage devices
    • B65G1/04—Storage devices mechanical
    • B65G1/0464—Storage devices mechanical with access from above
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/60—Intended control result
    • G05D1/69—Coordinated control of the position or course of two or more vehicles
    • G05D1/693—Coordinated control of the position or course of two or more vehicles for avoiding collisions between vehicles
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/60—Intended control result
    • G05D1/69—Coordinated control of the position or course of two or more vehicles
    • G05D1/698—Control allocation
    • G05D1/6987—Control allocation by centralised control off-board any of the vehicles
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D2105/00—Specific applications of the controlled vehicles
    • G05D2105/20—Specific applications of the controlled vehicles for transportation
    • G05D2105/28—Specific applications of the controlled vehicles for transportation of freight
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D2107/00—Specific environments of the controlled vehicles
    • G05D2107/70—Industrial sites, e.g. warehouses or factories
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D2109/00—Types of controlled vehicles
    • G05D2109/10—Land vehicles
    • G05D2109/14—Land vehicles moving on a grid

Definitions

  • the present invention relates to an automated storage and retrieval system for storage and retrieval of containers, in particular to a method, system and computer program product for determining a non-conflicting route among routes of other container handling vehicles operating on a rail system of the automated storage and retrieval system.
  • Fig. 1 discloses a prior art automated storage and retrieval system 10 with a framework structure 100 and Figs. 2, 3 and 4 disclose three different prior art container handling vehicles 201,301,401 suitable for operating on such a system 10.
  • the framework structure 100 comprises upright members 102 and a storage volume comprising storage columns 105 arranged in rows between the upright members 102.
  • storage columns 105 storage containers 106, also known as bins, are stacked one on top of one another to form stacks 107.
  • the members 102 may typically be made of metal, e.g. extruded aluminum profiles.
  • the framework structure 100 of the automated storage and retrieval system 10 comprises a rail system 108 arranged across the top of framework structure 100, on which rail system 108 a plurality of container handling vehicles 201,301,401 maybe operated to raise storage containers 106 from, and lower storage containers 106 into, the storage columns 105, and also to transport the storage containers 106 above the storage columns 105.
  • the rail system 108 comprises a first set of parallel rails no arranged to guide movement of the container handling vehicles 201,301,401 in a first direction X across the top of the frame structure 100, and a second set of parallel rails 111 arranged perpendicular to the first set of rails no to guide movement of the container handling vehicles 201,301,401 in a second direction Y which is perpendicular to the first direction X.
  • Containers 106 stored in the columns 105 are accessed by the container handling vehicles 201,301,401 through access openings 112 in the rail system 108.
  • the container handling vehicles 201,301,401 can move laterally above the storage columns 105, i.e. in a plane which is parallel to the horizontal X-Y plane.
  • the upright members 102 of the framework structure 100 may be used to guide the storage containers during raising of the containers out from and lowering of the containers into the columns 105.
  • the stacks 107 of containers 106 are typically self-supporting.
  • Each prior art container handling vehicle 201,301,401 comprises a vehicle body 201a, 301a, 401a and first and second sets of wheels 201b, 201c, 301b, 301c, 401b, 401c which enable the lateral movement of the container handling vehicles 201,301,401 in the X direction and in the Y direction, respectively.
  • first and second sets of wheels 201b, 201c, 301b, 301c, 401b, 401c which enable the lateral movement of the container handling vehicles 201,301,401 in the X direction and in the Y direction, respectively.
  • the first set of wheels 201b, 301b, 401b is arranged to engage with two adjacent rails of the first set no of rails
  • the second set of wheels 201c, 301c, 401c is arranged to engage with two adjacent rails of the second set 111 of rails.
  • At least one of the sets of wheels 201b, 201c, 301b, 301c, 401b, 401c can be lifted and lowered, so that the first set of wheels 201b, 301b, 401b and/or the second set of wheels 201c, 301c, 401c can be engaged with the respective set of rails no, 111 at any one time.
  • Each prior art container handling vehicle 201,301,401 also comprises a lifting device for vertical transportation of storage containers 106, e.g. raising a storage container 106 from, and lowering a storage container 106 into, a storage column 105.
  • the lifting device comprises one or more gripping / engaging devices which are adapted to engage a storage container 106, and which gripping / engaging devices can be lowered from the vehicle 201,301,401 so that the position of the gripping / engaging devices with respect to the vehicle 201,301,401 can be adjusted in a third direction Z which is orthogonal the first direction X and the second direction Y.
  • Parts of the gripping device of the container handling vehicles 301,401 are shown in Figs. 3 and 4 indicated with reference number 304,404.
  • the gripping device of the container handling device 201 is located within the vehicle body 201a in Fig. 2 and is thus not shown.
  • each storage column 105 can be identified by its X and Y coordinates.
  • the storage volume of the framework structure 100 has often been referred to as a grid 104, where the possible storage positions within this grid are referred to as storage grid cells.
  • Each storage column may be identified by a position in an X- and T-direction, while each storage grid cell may be identified by a container number in the X-, Y- and Z-direction.
  • Each prior art container handling vehicle 201,301,401 comprises a storage compartment or space for receiving and stowing a storage container 106 when transporting the storage container 106 across the rail system 108.
  • the storage space may comprise a cavity arranged internally within the vehicle body 201a, 401a as shown in Figs. 2 and 4 and as described in e.g. WO2O15/193278A1 and W02019/206487A1, the contents of which are incorporated herein by reference.
  • FIG. 3 shows an alternative configuration of a container handling vehicle 301 with a cantilever construction.
  • a container handling vehicle 301 with a cantilever construction.
  • Such a vehicle is described in detail in e.g. NO317366, the contents of which are also incorporated herein by reference.
  • the cavity container handling vehicle 201 shown in Fig. 2 may have a footprint that covers an area with dimensions in the X and Y directions which is generally equal to the lateral extent of a storage column 105, e.g. as is described in WO2O15/193278A1, the contents of which are incorporated herein by reference.
  • the term ‘lateral’ used herein may mean ‘horizontal’.
  • the cavity container handling vehicles 401 may have a footprint which is larger than the lateral area defined by a storage column 105 as shown in Fig. 1 and 4, e.g. as is disclosed in W02014/090684A1 or W02019/206487A1.
  • the rail system 108 typically comprises rails with grooves in which the wheels of the vehicles run.
  • the rails may comprise upwardly protruding elements, where the wheels of the vehicles comprise flanges to prevent derailing. These grooves and upwardly protruding elements are collectively known as tracks.
  • Each rail may comprise one track, or each rail 110,111 may comprise two parallel tracks.
  • each rail in one direction e.g. an X direction
  • each rail in the other, perpendicular direction e.g. a Y direction
  • Each rail 110,111 may also comprise two track members that are fastened together, each track member providing one of a pair of tracks provided by each rail.
  • W02018/146304A1 illustrates a typical configuration of rail system 108 comprising rails and parallel tracks in both X and Y directions.
  • columns 105 are storage columns 105, i.e. columns 105 where storage containers 106 are stored in stacks 107. However, some columns 105 may have other purposes.
  • columns 119 and 120 are such special-purpose columns used by the container handling vehicles 201,301,401 to drop off and/or pick up storage containers 106 so that they can be transported to an access station (not shown) where the storage containers 106 can be accessed from outside of the framework structure 100 or transferred out of or into the framework structure 100.
  • such a location is normally referred to as a ‘port’ and the column in which the port is located maybe referred to as a ‘port column’ 119,120.
  • the transportation to the access station maybe in any direction, that is horizontal, tilted and/or vertical.
  • the storage containers 106 maybe placed in a random or dedicated column 105 within the framework structure 100, then picked up by any container handling vehicle and transported to a port column 119,120 for further transportation to an access station.
  • the transportation from the port to the access station may require movement along various directions, by means such as delivery vehicles, trolleys, or other transportation lines.
  • tilted means transportation of storage containers 106 having a general transportation orientation somewhere between horizontal and vertical.
  • the first port column 119 may for example be a dedicated drop-off port column where the container handling vehicles 201,301,401 can drop off storage containers 106 to be transported to an access or a transfer station
  • the second port column 120 may be a dedicated pick-up port column where the container handling vehicles 201,301,401 can pick up storage containers 106 that have been transported from an access or a transfer station.
  • the access station may typically be a picking or a stocking station where product items are removed from or positioned into the storage containers 106.
  • the storage containers 106 are normally not removed from the automated storage and retrieval system 10 but are returned into the framework structure 100 again once accessed.
  • a port can also be used for transferring storage containers to another storage facility (e.g. to another framework structure or to another automated storage and retrieval system), to a transport vehicle (e.g. a train or a lorry), or to a production facility.
  • a conveyor system comprising conveyors is normally employed to transport the storage containers between the port columns 119,120 and the access station.
  • the conveyor system may comprise a lift device with a vertical component for transporting the storage containers 106 vertically between the port column 119,120 and the access station.
  • the conveyor system may be arranged to transfer storage containers 106 between different framework structures, e.g. as is described in W02014/075937A1, the contents of which are incorporated herein by reference.
  • a storage container 106 stored in one of the columns 105 disclosed in Fig. 1 is to be accessed, one of the container handling vehicles 201,301,401 is instructed to retrieve the target storage container 106 from its position and transport it to the drop-off port column 119.
  • This operation involves moving the container handling vehicle 201,301,401 to a location above the storage column 105 in which the target storage container 106 is positioned, retrieving the storage container 106 from the storage column 105 using the container handling vehicle’s 201,301,401 lifting device (not shown), and transporting the storage container 106 to the drop-off port column 119. If the target storage container 106 is located deep within a stack 107, i.e.
  • the operation also involves temporarily moving the abovepositioned storage containers prior to lifting the target storage container 106 from the storage column 105.
  • This step which is sometimes referred to as “digging” within the art, may be performed with the same container handling vehicle that is subsequently used for transporting the target storage container to the drop-off port column 119, or with one or a plurality of other cooperating container handling vehicles.
  • the automated storage and retrieval system 1 may have container handling vehicles 201,301,401 specifically dedicated to the task of temporarily removing storage containers 106 from a storage column 105. Once the target storage container 106 has been removed from the storage column 105, the temporarily removed storage containers 106 can be repositioned into the original storage column 105. However, the removed storage containers 106 may alternatively be relocated to other storage columns 105.
  • one of the container handling vehicles 201,301,401 is instructed to pick up the storage container 106 from the pick-up port column 120 and transport it to a location above the storage column 105 where it is to be stored.
  • the container handling vehicle 201,301,401 positions the storage container 106 at the desired position. The removed storage containers 106 may then be lowered back into the storage column 105 or relocated to other storage columns 105.
  • the automated storage and retrieval system 10 For monitoring and controlling the automated storage and retrieval system 10, e.g. monitoring and controlling the location of respective storage containers 106 within the framework structure 100, the content of each storage container 106, and the movement of the container handling vehicles 201,301,401 so that a desired storage container 106 can be delivered to the desired location at the desired time without the container handling vehicles 201,301,401 colliding with each other, the automated storage and retrieval system 10 comprises a control system 121 which typically is computerized and which typically comprises a database for keeping track of the storage containers 106.
  • Jobs are assigned to container handling vehicles 201,301,401 for handling and transporting storage containers 106 from one location to another when operating on the rail system 108.
  • a simple way of doing this is to use the Manhattan distance/time as an estimation.
  • Manhattan distance One drawback of using Manhattan distance is that the geometry of the grid is not considered, so that in some cases the estimation can be very inaccurate, for example across a gap in the grid with no rails or permanently blocked cells.
  • the A* search algorithm is often used for conflictbased search and to generate routes for multiple agents such as container handling vehicles 201,301,401. Finding routes can be costly CPU wise when having many agents to move and/or a large grid for available for movements. While routing several agents, conflicting routes are marked as they occur. Conflicts are resolved by re-routing agents that did not get a route to their destination.
  • ZoneRouter a method for determining possible routes of a container handling vehicle 201,301,401.
  • Conflict -based search is first performed by using ZoneRouter to find possible routes for agents from starting positions to ending positions.
  • the method is very fast in most cases, while also being accurate in all cases.
  • the rail system 108 arranged across the top of framework structure 100 is transformed to a simpler 2D-representation by describing it as a finite set of rectangular vertical and horizontal zones. These zones and their overlaps can then be used to quickly query for optimal routes and durations.
  • the output routes from ZoneRouter and durations can be used to improve assignments and estimate times as well as to provide useful input to the actual route calculation.
  • the ZoneRouter does not however take any other container handling vehicles or their movement into account (e.g., a second, third, fourth, etc., container handling vehicle).
  • the present invention is a development of ZoneRouter and provides a solution for generating routes for several container handling vehicles having conflicting routes generated by ZoneRouter.
  • the invention is defined by a method of determining a route for a container handling vehicle, where the route is a route among a route of at least one other container handling vehicle, operating on a grid system e.g. a rail system of an automatic grid-based storage and retrieval system comprising a framework structure including the rail system, the rail system comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction which is perpendicular to the first direction, the rail system defining a plurality of grid positions each being identifiable by a first coordinate in the first direction and a second coordinate in the second direction.
  • a grid system e.g. a rail system of an automatic grid-based storage and retrieval system comprising a framework structure including the rail system, the rail system comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction which is perpendicular to the first direction, the rail system defining a plurality of grid positions each
  • the method comprising using a control system communicating with a vehicle controller in each container handling vehicle: creating a model of the rail system, comprising the steps of: representing the rail system as a finite set of non-overlapping rectangular first zones of grid positions, each first zone latitudinally extending in the first direction, and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction, wherein the zones are positioned around grid positions that are not accessible by the container handling vehicle; determining overlap information, wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones; and determining grid position zone information by, for each grid position, determining in which of the finite set of first zones and/or the finite set of second zones the grid position is located, wherein the control system receives requests for routes for each of at least two container handling vehicles to move from respective first grid positions to respective second grid positions, the control system
  • the routes of the container handling vehicles are ranked and prioritized according to the number of possible routes, where routes of container handling vehicles having least possible routes are ranked first while routes of container handling vehicles having most possible routes are ranked and prioritized last, and selecting routes for the container handling vehicle according to ranking.
  • Cost functions may also be included to determine both non-conflicting routes and fastest routes to destinations. If for instance a container handling vehicle has five possible routes to a destination where two of the routes have low cost, while another container handling vehicle has three possible routes to a destination, all routes having same cost, a conflicting low cost route of the container handling vehicle having more possible routes may be selected.
  • routes having lowest cost are prioritized and selected.
  • a route having lowest cost is the fastest route for a container handling vehicle from its current position to a destination, e.g. a movement along a straight line will have lower cost that a movement where direction has to be changed one or more times to reach a destination.
  • the method may comprise, using the set of first zones, the set of second zones and the overlap information to generate a zone graph comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
  • the method may comprise, determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph.
  • the graph traversal and path search algorithm may in one embodiment be an A* algorithm.
  • representing the rail system as the set of first zones and the set of second zones may comprise: defining the grid positions that are not accessible by the container handling vehicle as blocked cells and grid cells accessible for the container handling vehicle as open cells, determining a first set of non-overlapping rectangular regions of grid positions, each first region latitudinally extending in the first direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining a second set of non-overlapping rectangular regions of grid positions, each second region longitudinally extending in the second direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining the finite set of first zones by removing any region of the first set of regions that falls completely within a region of the second set of regions; and determining the finite set of second zones by removing any region of the second set of regions that falls completely within a region of the first set regions.
  • the step of determining the first set of regions may comprise determining continuous sections of open cells extending in the first direction that are uninterrupted by a blocked cell, each continuous section having a start position having a first coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells latitudinally extending in the first direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same first coordinate and the same length, or a single vertical continuous section
  • the step of determining the second set of regions comprises determining continuous sections of open cells extending in the second direction that are uninterrupted by a blocked cell, each continuous section having a start position having a second coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells longitudinally extending in the second direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same second coordinate and the same length, or a single horizontal continuous section.
  • defining grid positions that are not accessible by the container handling vehicle may comprise determining one or more grid positions that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle, and identifying the one or more grid positions as being not accessible by the container handling vehicle.
  • the method may comprise: receiving a request for a route for a plurality of container handling vehicles from a plurality of first grid position to a second grid position; determining the fastest route for each of the plurality of container handling vehicles from the plurality of first grid position to the second grid position using the model of the rail system, and determining based on the fastest route for each of the plurality container handling vehicles an optimal container handling vehicle of the plurality container handling vehicles for moving to the second grid position, and instructing the optimal container handling vehicle to move to the second grid position.
  • the method may comprise: using timing information of the container handling vehicles following routes to determine if crossings of the routes at potentially conflicting grid positions, are non-conflicting.
  • the invention concerns a system of determining a route for a container handling vehicle, where the route is a route among routes of other container handling vehicles, all operating on a rail system of an automatic grid-based storage and retrieval system comprising a framework structure including the rail system, the rail system comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction which is perpendicular to the first direction, the rail system defining a plurality of grid positions each being identifiable by a first coordinate in the first direction and a second coordinate in the second direction; a control system configured to communicate with a vehicle controller in the container handling vehicle, wherein the control system is configured to: create a model of the rail system, by: representing the rail system as a finite set of non-overlapping rectangular first zones of grid positions, each first zone longitudinally extending in the first direction, and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction, wherein
  • the system may be configured to determine, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate nor the same second coordinate.
  • the system may be configured to determine, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones.
  • the system may be configured to use the set of first zones, the set of second zones and the overlap information to generate a zone graph comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
  • the system may be configured to determine, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph.
  • the graph traversal and path search algorithm may in one embodiment be an A* algorithm.
  • representing the rail system as the set of first zones and the set of second zones may comprise: defining the grid positions that are not accessible by the container handling vehicle as blocked cells and grid cells accessible for the container handling vehicle as open cells, determining a first set of non-overlapping rectangular regions of grid positions, each first region latitudinally extending in the first direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining a second set of non-overlapping rectangular regions of grid positions, each second region longitudinally extending in the second direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining the finite set of first zones by removing any region of the first set of regions that falls completely within a region of the second set of regions, and determining the finite set of second zones by removing any region of the second set of regions that falls completely within a region of the first set regions.
  • determining the first set of regions may comprise determining continuous sections of open cells extending in the first direction that are uninterrupted by a blocked cell, each continuous section having a start position having a first coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells latitudinally extending in the first direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same first coordinate and the same length, or a single vertical continuous section, and the step of determining the second set of regions comprises determining continuous sections of open cells extending in the second direction that are uninterrupted by a blocked cell, each continuous section having a start position having a second coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells longitudinally extending in the second direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same second coordinate and the same length, or a single horizontal continuous section.
  • defining grid positions that are not accessible by the container handling vehicle may comprise determining one or more grid positions that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle, and identifying the one or more grid positions as being not accessible by the container handling vehicle.
  • the system may be configured to receive a request for a route for a plurality of container handling vehicles from a plurality of first grid position to a second grid position, determine the fastest route for each of the plurality of container handling vehicles from the plurality of first grid position to the second grid position using the model of the rail system, determine based on the fastest route for each of the plurality container handling vehicles an optimal container handling vehicle of the plurality container handling vehicles for moving to the second grid position, and instruct the optimal container handling vehicle to move to the second grid position.
  • the invention is directed to computer program product for a control system in the system of the second aspect, wherein the computer program product comprising instructions that when performed on the control system performs the method according to the first aspect.
  • aspects of the invention provide a system, method, and computer program product for determining non-conflicting routes for container handling vehicles operating on a rail system of an automatic grid-based storage and retrieval system.
  • the method comprises creating a model of the rail system representing the rail system as a finite set of non-overlapping rectangular first zones in a first direction, and a finite set of non-overlapping rectangular second zones in a second direction, wherein the zones are positioned around grid positions that are not accessible by the container handling vehicle, determining overlap information indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones, determining grid position zone information by, for each grid position determining in which of the finite set of first zones and/or the finite set of second zones the grid position is located, receiving a request for a route for each of at least two container handling vehicles to move from respective first grid positions to respective second grid positions, prioritizing and selecting routes for each container handling vehicle, where a
  • Fig. 1 is a perspective view of a framework structure of a prior art automated storage and retrieval system.
  • FIG. 2 is a perspective view of a prior art container handling vehicle having an internally arranged cavity for carrying storage containers therein.
  • FIG. 3 is a perspective view of a prior art container handling vehicle having a cantilever for carrying storage containers underneath.
  • FIG. 4 is a perspective view, seen from below, of a prior art container handling vehicle having an internally arranged cavity for carrying storage containers therein.
  • Fig. 5 is a schematic top view of an exemplary rail system and blocked cells.
  • Fig. 6 is a schematic illustration of a method according to an embodiment of the present invention.
  • Figs. 7 is a schematic illustration of a method according to an embodiment of the present invention.
  • FIGs. 8 is a schematic illustration of a method according to an embodiment of the present invention.
  • FIG. 9 is a schematic illustration of a method according to an embodiment of the present invention.
  • FIG. 10 is a schematic illustration of a method according to an embodiment of the present invention.
  • FIG. 11 is a schematic illustration of a shortest route according to an embodiment of the present invention.
  • Fig. 12 is a schematic illustration of a shortest route according to an embodiment of the present invention.
  • Fig. 13 is a schematic illustration of a shortest route according to an embodiment of the present invention.
  • Fig. 14 is a schematic illustration of a shortest route according to an embodiment of the present invention.
  • Fig. 15 is a flowchart of a method according to an embodiment of the present invention.
  • Fig. 16 is a schematic illustration of a zone graph according to an embodiment of the present invention.
  • FIG. 17 is a schematic illustration of a shortest route according to an embodiment of the present invention.
  • Fig. 18 is a schematic illustration of a shortest route according to an embodiment of the present invention.
  • Fig. 19 is a schematic illustration of conflicting routes for several container handling vehicles.
  • a method (1500) is provide of determining a route for a container handling vehicle (201,301,401). The method comprises receiving requests for routes (1505) for each of at least two container handling vehicles
  • the method determines a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions.
  • the method prioritizes and selects routes (1512) for each container handling vehicle
  • a container handling vehicle (201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes.
  • the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401).
  • the framework structure 100 of the automated storage and retrieval system 10 is constructed in a similar manner to the prior art framework structure 100 described above in connection with Fig. 1. That is, the framework structure 100 comprises several upright members 102, and comprises a first, upper rail system 108 extending in the X direction and Y direction. Examples of container handling vehicles 201,301,401 running on the rail system 108 are illustrated in Figs. 2-4.
  • the framework structure 100 further comprises storage compartments in the form of storage columns 105 provided between the members 102 wherein storage containers 106 are stackable in stacks 107 within the storage columns 105.
  • the framework structure 100 can be of any size. It is understood that the framework structure can be considerably wider and/or longer and/or deeper than disclosed in Fig. 1. For example, the framework structure 100 may have a horizontal extent of more than 700x700 columns and a storage depth of more than twelve containers. [oo8o] As described in the background section above the present invention is a further development of the Autostore’s ZoneRouter method used for determining possible routes on the rail system for a container handling vehicle operating on an automated storage and retrieval system. To fully understand the present invention, the ZoneRouter method will therefore first be described by referring to one embodiment of an automated storage and retrieval system having a storage cells, rail system, and blocked cell as illustrated in Figs. 5 - 18.
  • Fig. 5 is a schematic top view of an exemplary rail system 500.
  • the rail system 500 comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction Y which is perpendicular to the first direction X.
  • the rail system 500 defines a plurality of grid positions (Xi,Yj) each being identifiable by a first coordinate Xi in the first direction X and a second coordinate Yj in the second direction Y.
  • the illustrated grid positions (Xi,Yj) are for simplicity square, however, in typical implementations such as the rail system 108 of Fig. 1, the grid positions (Xi,Yj) or cells, are rectangular. For rectangular cells, the time to drive over a cell is different in the x- and the y-direction.
  • the rail system is an example of a grid system.
  • Grid positions (Xi,Yj) that are permanently inaccessible for a container handling vehicle 201,301,401 are referred to as permanently blocked cells 501.
  • the permanently blocked cells 501 are grid positions that are not physically accessible for the container handling vehicles due to the physical layout of a warehouse, such as a wall, a pillar, a low ceiling or other reasons physical reasons for missing cells.
  • grid positions (Xi,Yj) that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle 201,301,401 operating on the rail system 500, such that the grid position is not physically accessible for the container handling vehicle 201,301,401.
  • One such grid position 601 is illustrated in Figs. 6 - 14, 17 and 18.
  • Fig. 15 illustrates a flowchart of a method 1500 of determining a route for a container handling vehicle 201,301,401 operating on the rail system 500 illustrated in Fig. 5.
  • the method comprises, using a control system communicating with a vehicle controller in the container handling vehicle 201,301,401, creating a model 1501 of the rail system 500, receiving a request for a route 1505 for at least two container handling vehicle 201,301,401 from a first grid position to a second grid position, and determining a route or a set of routes 1506 for the at least two container handling vehicles 201,301,401 from the first grid position to the second grid position using the model of the rails system 500.
  • a slack number means that there are 4 possible routes, all leading to the same destination.
  • the slack number i.e. number of possible routes, is used for selecting routes 1512 for each container handling vehicle 201,301,401 to avoid conflicts between routes.
  • a route for a container handling vehicle 201,301,401 having a low slack number is selected over a conflicting route of container handling vehicle 201,301,401 having a higher slack number. In this case, conflicting routes are excluded from the possible routes of the container handling vehicle 201,301,401 having the higher slack number.
  • One or more routes for a container handling vehicle 201,301,401 having a slack number of for instance 8 will be excluded from available routes and prioritized for a container handling vehicle 201,301,401 having a lower slack number, if the routes are in conflict.
  • creating the model 1501 of the rail system 500 comprises the step of representing the rail system 500 as a finite set of non-overlapping rectangular first zones 1502 of grid positions A, B, C, D, E, F, G, H, I, J, K, L, each first zone latitudinally extending in the first direction X, and a finite set of non-overlapping rectangular second zones of grid positions 1, 2, 3, 4, 5, 6, 7, 8, 9, each second zone longitudinally extending in the second direction Y, wherein the zones are positioned around grid positions 501, 601 that are not accessible by the container handling vehicle 201,301,401.
  • overlap information is determined, wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L and a zone of the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • zone 1 overlaps zone A, C, D, E and F
  • zone 2 overlaps zone L
  • zone 3 overlaps zone A, C, D, E, F, I and L, and so on.
  • This information may be stored in an array and it is not modified once created.
  • grid position zone information is determined by, for each grid position (Xi,Yj), determining in which of the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L and/or the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9 the grid position (Xi,Yj) is located.
  • the grid position information may be stored in a matrix or similar structure and is not modified once created.
  • Fig. 10 illustrates the zones that all the grid positions belong to.
  • a grid position belongs to minimum one zone and maximum two zones. This allows for a sparse saving of data and fast lookup by grid position.
  • the step of representing the rail system 500 as the set of first zones A, B, C, D, E, F, G, H, I, J, K, L and the set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9 comprises the step 1507 of defining the grid positions (Xi,Yj) that are not accessible by the container handling vehicle 201,301,401 as blocked cells 501, 601 and grid cells accessible for the container handling vehicle 201,301,401 as open cells 502.
  • Blocked cells 501, 601 maybe permanently blocked cells 501 or maybe grid positions 601 that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle 201,301,401 operating on the rail system 500 such that the container handling vehicle 201,301,401 cannot pass in at least one direction.
  • continuous open cells denote the largest extent of side-by-side open cells in each direction.
  • step 1510 determining the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L by removing any region 708, 710, 711 of the first set of regions that falls completely within a region of the second set of regions 717, 723, 726, and determining the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9 by removing any region 718, 724, 727 of the second set of regions that falls completely within a region of the first set regions 707,
  • Regions that fall completely withing another region are redundant. Removing these redundant regions is important for several reasons such as to make any A* route search efficient, and that moving from one zone to another zone implies making a turn.
  • the step of determining the first set of regions 1508 comprises, illustrated in Fig. 6 B, determining continuous sections of open cells 502 extending in the first direction X that are uninterrupted by a blocked cell 501, 601, each continuous section having a start position having a first coordinate Xi and a length defined by the number of open cells 502 uninterrupted by a blocked cell 501, 601, and as illustrated by Fig. 7B, the largest possible rectangle of continuous open cells 502 latitudinally extending in the first direction X uninterrupted by a blocked cell 501, 601 comprises either a number of adjacent continuous sections having a start position with the same first coordinate Xi and the same length, or a single vertical continuous section.
  • the step of determining the second set of regions 1509 comprises, illustrated in Fig. 6 A, determining continuous sections of open cells 502 extending in the second direction Y that are uninterrupted by a blocked cell 501, 601, each continuous section having a start position having a second coordinate Yj and a length defined by the number of open cells 502 uninterrupted by a blocked cell 501, 601, and as illustrated by Fig. 7 A, the largest possible rectangle of continuous open cells 502 longitudinally extending in the second direction Y uninterrupted by a blocked cell 501, 601 comprises either a number of adjacent continuous sections having a start position with the same second coordinate Yi and the same length, or a single horizontal continuous section.
  • the method comprises using the set of first zones, the set of second zones and the overlap information to generate a zone graph 1511 comprising nodes and edges, wherein the nodes represent the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L and the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9, and the edges represent the overlap information.
  • Fig. 16 is an exemplary schematic illustration of a zone graph 1600 of the zones and edges of the rail system 500 above the dashed line ai-a2 shown in Fig. 9. The circles represent the zones A, C, D, E, F, I, L, 1, 2, 3, 4, 5 and the interconnecting lines the edges.
  • the stippled edges extending from zones D and F illustrates overlap to zones below the dashed line ai-a2 in Fig. 9.
  • a request for a route 1505 for the container handling vehicle 201,301,401 from a first grid position to a second grid position comprises the first grid position, i.e. the start position of the container handling vehicle 201,301,401, and the second grid position, i.e. the end position of the container handling vehicle 201,301,401.
  • the request may also comprise information about the container handling vehicle 201,301,401 such as robot type, current direction of movement, and orientation of the container handling vehicle 201,301,401 on the rail system 500, and information about the rail system 500, such as cell sizes to calculate movement times.
  • the request for the route is for the optimal route from the first grid position to the second grid position, e.g. the fastest route.
  • the request is for minimum cost.
  • the request is the same as for a route, but instead of returning a route, the request returns the cost/duration of the optimal route.
  • the method of the present invention distinctly handles three main cases: straight routes, Manhattan routes and routes through more than two zones.
  • the fastest route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj). This guarantees that there is no blockage between the start and end positions. If only considering that the first grid position and the second grid position share either the same first coordinate (Xi) or the same second coordinate (Yj), there is no guarantee that the container handling vehicle can follow the route, for example if going from zone L to zone K as illustrated in Fig. 9 B.
  • Fig. 11 illustrates a straight line route between point A and B within the same zone 7.
  • the fastest route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj).
  • Fig. 12 illustrates the two possibilities from A to B within zone C for a non-moving container handling vehicle.
  • the fastest route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones, such as illustrated in Fig. 13. In this case it is first verified that the first grid position and the second grid positions are not in the same zone.
  • the third case it is determined using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones. That is, the route is passing through more than two zones.
  • the fastest route between the first grid position and the second grid position is determined using a graph traversal and path search algorithm on the zone graph 1600. Any suitable graph traversal and path search algorithm known to the skilled person may be used.
  • a preferred graph traversal and path search algorithm is an A* algorithm. As illustrated in Fig. 14, a turn is created when moving to the first available cell inside the next zone, such that long route segments are created at the end of the route. This allows easy determination of the optimal route. This is due to the acceleration/deceleration of the container handling vehicles.
  • the determination considers the overlapping zones, calculates the time of going into the first available cell in the first overlapping zone from the first grid position. From the first available cell in the first overlapping zone, this is repeated for the first available cell in the second overlapping zone and so on to determine the route.
  • the last part of the route indicated by dashed lines, is treated separately because the container handling vehicle has required direction into the final zone.
  • the second to last segment is therefore extended one cell in this case before turning to match the second grid position in the correct way.
  • the determination of the fastest route from the first grid position to the second grid position is determined as if the container handling vehicle is alone on the rail system 500. That is, other container handling vehicles on the rail system and other temporary blockages such as top bins, are not considered.
  • the control system 121 is in communication with a plurality of container handling vehicles 201,301,401, and has knowledge of their current positions, paths, and other temporary blockages. The control system 121 may therefore find that the determined fastest route is inaccessible because other container handling vehicles are standing on the route or because of other temporary blockages, and parts of the optimal route can be modified to take this into account.
  • a slack number means that there are 4 possible routes, all leading to the same destination.
  • the first route segment is set to go into the next zone 7, that is not turn at the first available cell. There are then four possibilities since the next zone 7 has height 4, which means that the segment has a slack of 4, giving 4 permutations of the route from the first grid position to the second grid position. While the first slack choice, i.e. turning at the first available cell, is the optimal one, the other routes will not be far off.
  • the second route segment has a slack of 3, since the next zone E has a width of 3, providing three extra route permutations on top of the existing four from the first segment.
  • the route from the first grid position to the second grid position then has 12 permutations that the control system 121 can iterate through fast to determine the most optimal of them, in view of other container handling vehicles and temporary blockages on the rail system 500.
  • the determination of the fastest route between grid positions may be performed for a plurality of container handling vehicles, e.g. to determine which of a plurality of container handling vehicles that is the optimal container handling vehicle to perform a task, or to determine which of a plurality of tasks to be performed first.
  • a task such as picking up storage container, is to be completed at the second grid position.
  • a request may be received for a route for a plurality of container handling vehicles 201,301,401 from a plurality of first grid position to the second grid position. Then the fastest route for each of the plurality of container handling vehicles 201,301,401 from the plurality of first grid position to the second grid position maybe determined using the model of the rail system 500.
  • an optimal container handling vehicle of the plurality container handling vehicles 201,301,401 for moving to the second grid position maybe determined, and the optimal container handling vehicle is instructed to move to the second grid position to perform the task.
  • the ZoneRouter method described above, with reference to Figs. 5- 18, does not consider any other container handling vehicles having conflicting routes via the same overlapping zones or their movement when following routes.
  • the present invention is a further development of the described ZoneRouter and provides a method for solving conflicting routes for several container handling vehicles 201,301,401 being generated by the ZoneRouter.
  • the routes generated by the ZoneRouter have the added concept of slack, meaning that a route for one container handling vehicle is in practice a set of routes, where the slack number of a container handling vehicle represents the number of possible routes from a starting position to a destination.
  • the present invention uses slack numbers of several container handling vehicles 201,301,401 to determine non-conflicting routes for container handling vehicles 201,301,401 having routes via overlapping zones as their possible routes.
  • the slack number is used to determine routes that should be selected to avoid conflict. Based on the slack number, possible route conflicts are resolved by prioritizing and keeping routes for container handling vehicles 201,301,401 having a lower slack number and selecting a non-conflicting route for a container handling vehicle 201,301,401 having a higher slack number.
  • Fig. 19 illustrates an example of possible routes for three different container handling vehicles in an example grid.
  • Route A has 12 possibilities, i.e. a slack of 12, because it has 4 possible routes in the horizontal zone and 3 possible routes in the vertical zone.
  • Route B has a slack of 1, meaning that it only has one optimal route, as has route C. In this case it is identified that route A and B, and route A and C have a conflict.
  • the slack of a route A indicates that it is globally better to take one of the centre routes in the Y-direction and allow route B and C to have their optimal route.
  • time can be considered to avoid conflicts between agents such as container handling vehicles 201, 301, 401.
  • agents such as container handling vehicles 201, 301, 401.
  • route B is given priority, since route A can be routed differently, there is still a conflict with route B when route A goes in the X-direction through route B. Since the timing information of the routes for the agents is known or can be calculated, we know that there will be no conflict in the X-direction since an agent for route B has already passed crossing rails when an agent for route A moves in the X- direction.
  • An advantage of the present solution is that generating routes is fast and requires less load on CPU or GPU.
  • a route set for each agent is fully parallelizable and can be run in a multithreaded fashion, either on a CPU or on a GPU.
  • the rail system (108, 500) as a finite set of nonoverlapping rectangular first zones (1502) of grid positions, each first zone latitudinally extending in the first direction (X), and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction (Y), wherein the zones are positioned around grid positions (501, 601) that are not accessible by the container handling vehicle (201,301,401);
  • the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones;
  • control system receives requests for routes (1505) for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions, the control system:
  • each container handling vehicle (201,301,401) controls each container handling vehicle (201,301,401) to follow the selected routes.
  • any of clauses 1 - 3 comprising, determining, using the grid position zone information, that the route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj).
  • the method of any of clauses 1 - 4 comprising, determining, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj).
  • the method of any of clauses 1 - 5, comprising, determining, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones.
  • the method of clause 1, comprising, using the set of first zones, the set of second zones and the overlap information to generate a zone graph (1511) comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
  • the method of clause 7, comprising, determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph.
  • the method of any of clauses 1 - 9, wherein representing the rail system (108, 500) as the set of first zones and the set of second zones comprises:
  • the step of determining the first set of regions (1508) comprises determining continuous sections of open grid cells (502) extending in the first direction (X) that are uninterrupted by a blocked grid cell (501, 601), each continuous section having a start position having a first coordinate (Xi) and a length defined by the number of open grid cells (502) uninterrupted by a blocked grid cell (501, 601); wherein the largest possible rectangle of continuous open grid cells (502) latitudinally extending in the first direction (X) uninterrupted by a blocked grid cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same first coordinate (Xi) and the same length, or a single vertical continuous section; and the step of determining the second set of regions (1509) comprises determining continuous sections of open grid cells (
  • a rail system (108, 500) of an automatic grid-based storage and retrieval system (10) comprising a framework structure (100) including the rail system (108, 500), the rail system (108, 500) comprising a first set of parallel rails (110) in a first direction (X), and a second set of parallel rails (111) arranged in a second direction (Y) which is perpendicular to the first direction (X), the rail system (108, 500) defining a plurality of grid positions ((Xi,Yj)) each being identifiable by a first coordinate (Xi) in the first direction (X) and a second coordinate (Yj) in the second direction (Y); a control system (121) configured to communicate with a vehicle controller in the container handling vehicle (201,301,401), wherein the control system (121) is configured to:
  • the rail system (108, 500) as a finite set of non-overlapping rectangular first zones of grid positions, each first zone longitudinally extending in the first direction (X), and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction (Y), wherein the zones are positioned around grid positions (501, 601) that are not accessible by the container handling vehicle (201,301,401);
  • the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones;
  • control system upon receiving a request for routes for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions, the control system is configured to:
  • the control system (121) is configured to rank and prioritize the routes of the container handling vehicles (201,301,401) according to the number of possible routes, where routes of container handling vehicles (201,301,401) having least possible routes are ranked first while routes of container handling vehicles (201,301,401) having most possible routes are ranked and prioritized last, and where routes for the container handling vehicle (201,301,401) according to ranking are selected.
  • the control system (121) is configured to prioritize and select routes having lowest cost. .
  • the system of any of clauses 15 - 19, configured to determining, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones.
  • the system of any of clauses 15 - 20, configured using the set of first zones, the set of second zones and the overlap information to generate a zone graph (1511) comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information. .
  • the system of clause 21, configured to determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph.
  • the system of any of clauses 15 - 23, wherein representing the rail system (108, 500) as the set of first zones and the set of second zones comprises:
  • the step of determining the first set of regions (1508) comprises determining continuous sections of open cells (502) extending in the first direction (X) that are uninterrupted by a blocked cell (501, 601), each continuous section having a start position having a first coordinate (Xi) and a length defined by the number of open cells (502) uninterrupted by a blocked cell (501, 601); wherein the largest possible rectangle of continuous open cells (502) longitudinally extending in the first direction (X) uninterrupted by a blocked cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same first coordinate (Xi) and the same length, or a single vertical continuous section; and the step of determining the second set of regions (1509) comprises determining continuous sections of open cells (502) extending in the second direction (Y)

Landscapes

  • Engineering & Computer Science (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Mechanical Engineering (AREA)
  • Warehouses Or Storage Devices (AREA)

Abstract

A method for determining a route for a container handling vehicle (201,301,401), where the route is a route among a route of at least one other container handling vehicle (201,301,401) in an automatic grid-based storage and retrieval system (10) comprising a grid system having a first direction (X) and a second direction (Y) which is perpendicular to the first direction (X), the grid system defining a plurality of grid positions ((Xi,Yj)) each being identifiable by a first coordinate (Xi) in the first direction (X) and a second coordinate (Yj) in the second direction (Y), the method for use by a control system (121) communicating with a vehicle controller in each container handling vehicle (201,301,401). The method comprises: receiving requests for routes (1505) for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions; determining a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions; prioritizing and selecting routes (1512) for each container handling vehicle (201,301,401), where a container handling vehicle (201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes, where for the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401); and controlling each container handling vehicle (201,301,401) to follow the selected routes.

Description

METHOD, SYSTEM AND COMPUTER PROGRAM PRODUCT FOR DETERMINING NON-CONFLICTING ROUTES FOR CONTAINER HANDLING VEHICLES
FIELD OF THE INVENTION
[001] The present invention relates to an automated storage and retrieval system for storage and retrieval of containers, in particular to a method, system and computer program product for determining a non-conflicting route among routes of other container handling vehicles operating on a rail system of the automated storage and retrieval system.
BACKGROUND AND PRIOR ART
[002] Fig. 1 discloses a prior art automated storage and retrieval system 10 with a framework structure 100 and Figs. 2, 3 and 4 disclose three different prior art container handling vehicles 201,301,401 suitable for operating on such a system 10.
[003] The framework structure 100 comprises upright members 102 and a storage volume comprising storage columns 105 arranged in rows between the upright members 102. In these storage columns 105 storage containers 106, also known as bins, are stacked one on top of one another to form stacks 107. The members 102 may typically be made of metal, e.g. extruded aluminum profiles.
[004] The framework structure 100 of the automated storage and retrieval system 10 comprises a rail system 108 arranged across the top of framework structure 100, on which rail system 108 a plurality of container handling vehicles 201,301,401 maybe operated to raise storage containers 106 from, and lower storage containers 106 into, the storage columns 105, and also to transport the storage containers 106 above the storage columns 105. The rail system 108 comprises a first set of parallel rails no arranged to guide movement of the container handling vehicles 201,301,401 in a first direction X across the top of the frame structure 100, and a second set of parallel rails 111 arranged perpendicular to the first set of rails no to guide movement of the container handling vehicles 201,301,401 in a second direction Y which is perpendicular to the first direction X. Containers 106 stored in the columns 105 are accessed by the container handling vehicles 201,301,401 through access openings 112 in the rail system 108. The container handling vehicles 201,301,401 can move laterally above the storage columns 105, i.e. in a plane which is parallel to the horizontal X-Y plane. [005] The upright members 102 of the framework structure 100 may be used to guide the storage containers during raising of the containers out from and lowering of the containers into the columns 105. The stacks 107 of containers 106 are typically self-supporting.
[006] Each prior art container handling vehicle 201,301,401 comprises a vehicle body 201a, 301a, 401a and first and second sets of wheels 201b, 201c, 301b, 301c, 401b, 401c which enable the lateral movement of the container handling vehicles 201,301,401 in the X direction and in the Y direction, respectively. In Figs. 2, 3 and 4 two wheels in each set are fully visible. The first set of wheels 201b, 301b, 401b is arranged to engage with two adjacent rails of the first set no of rails, and the second set of wheels 201c, 301c, 401c is arranged to engage with two adjacent rails of the second set 111 of rails. At least one of the sets of wheels 201b, 201c, 301b, 301c, 401b, 401c can be lifted and lowered, so that the first set of wheels 201b, 301b, 401b and/or the second set of wheels 201c, 301c, 401c can be engaged with the respective set of rails no, 111 at any one time.
[007] Each prior art container handling vehicle 201,301,401 also comprises a lifting device for vertical transportation of storage containers 106, e.g. raising a storage container 106 from, and lowering a storage container 106 into, a storage column 105. The lifting device comprises one or more gripping / engaging devices which are adapted to engage a storage container 106, and which gripping / engaging devices can be lowered from the vehicle 201,301,401 so that the position of the gripping / engaging devices with respect to the vehicle 201,301,401 can be adjusted in a third direction Z which is orthogonal the first direction X and the second direction Y. Parts of the gripping device of the container handling vehicles 301,401 are shown in Figs. 3 and 4 indicated with reference number 304,404. The gripping device of the container handling device 201 is located within the vehicle body 201a in Fig. 2 and is thus not shown.
[008] Conventionally, and also for the purpose of this application, Z=i identifies the uppermost layer available for storage containers below the rails 110,111, i.e. the layer immediately below the rail system 108, =2 the second layer below the rail system 108, =3 the third layer etc. In the exemplary prior art disclosed in Fig. 1, =8 identifies the lowermost, bottom layer of storage containers. Similarly, X=i...n and Y=i...n identifies the position of each storage column 105 in the horizontal plane. Consequently, as an example, and using the Cartesian coordinate system X, Y, Z indicated in Fig. 1, the storage container identified as 106’ in Fig. 1 can be said to occupy storage position X=17, Y=i, Z=6. The container handling vehicles 201,301,401 can be said to travel in layer Z=o, and each storage column 105 can be identified by its X and Y coordinates. Thus, the storage containers shown in Fig. 1 extending above the rail system 108 are also said to be arranged in layer Z=o.
[009] The storage volume of the framework structure 100 has often been referred to as a grid 104, where the possible storage positions within this grid are referred to as storage grid cells. Each storage column may be identified by a position in an X- and T-direction, while each storage grid cell may be identified by a container number in the X-, Y- and Z-direction.
[0010] Each prior art container handling vehicle 201,301,401 comprises a storage compartment or space for receiving and stowing a storage container 106 when transporting the storage container 106 across the rail system 108. The storage space may comprise a cavity arranged internally within the vehicle body 201a, 401a as shown in Figs. 2 and 4 and as described in e.g. WO2O15/193278A1 and W02019/206487A1, the contents of which are incorporated herein by reference.
[0011] Fig. 3 shows an alternative configuration of a container handling vehicle 301 with a cantilever construction. Such a vehicle is described in detail in e.g. NO317366, the contents of which are also incorporated herein by reference.
[0012] The cavity container handling vehicle 201 shown in Fig. 2 may have a footprint that covers an area with dimensions in the X and Y directions which is generally equal to the lateral extent of a storage column 105, e.g. as is described in WO2O15/193278A1, the contents of which are incorporated herein by reference. The term ‘lateral’ used herein may mean ‘horizontal’.
[0013] Alternatively, the cavity container handling vehicles 401 may have a footprint which is larger than the lateral area defined by a storage column 105 as shown in Fig. 1 and 4, e.g. as is disclosed in W02014/090684A1 or W02019/206487A1.
[0014] The rail system 108 typically comprises rails with grooves in which the wheels of the vehicles run. Alternatively, the rails may comprise upwardly protruding elements, where the wheels of the vehicles comprise flanges to prevent derailing. These grooves and upwardly protruding elements are collectively known as tracks. Each rail may comprise one track, or each rail 110,111 may comprise two parallel tracks. In other rail systems 108, each rail in one direction (e.g. an X direction) may comprise one track and each rail in the other, perpendicular direction (e.g. a Y direction) may comprise two tracks. Each rail 110,111 may also comprise two track members that are fastened together, each track member providing one of a pair of tracks provided by each rail.
[0015] W02018/146304A1, the contents of which are incorporated herein by reference, illustrates a typical configuration of rail system 108 comprising rails and parallel tracks in both X and Y directions.
[0016] In the framework structure 100, most of the columns 105 are storage columns 105, i.e. columns 105 where storage containers 106 are stored in stacks 107. However, some columns 105 may have other purposes. In Fig. 1, columns 119 and 120 are such special-purpose columns used by the container handling vehicles 201,301,401 to drop off and/or pick up storage containers 106 so that they can be transported to an access station (not shown) where the storage containers 106 can be accessed from outside of the framework structure 100 or transferred out of or into the framework structure 100. Within the art, such a location is normally referred to as a ‘port’ and the column in which the port is located maybe referred to as a ‘port column’ 119,120. The transportation to the access station maybe in any direction, that is horizontal, tilted and/or vertical. For example, the storage containers 106 maybe placed in a random or dedicated column 105 within the framework structure 100, then picked up by any container handling vehicle and transported to a port column 119,120 for further transportation to an access station. The transportation from the port to the access station may require movement along various directions, by means such as delivery vehicles, trolleys, or other transportation lines. Note that the term ‘tilted’ means transportation of storage containers 106 having a general transportation orientation somewhere between horizontal and vertical.
[0017] In Fig. 1, the first port column 119 may for example be a dedicated drop-off port column where the container handling vehicles 201,301,401 can drop off storage containers 106 to be transported to an access or a transfer station, and the second port column 120 may be a dedicated pick-up port column where the container handling vehicles 201,301,401 can pick up storage containers 106 that have been transported from an access or a transfer station.
[0018] The access station may typically be a picking or a stocking station where product items are removed from or positioned into the storage containers 106. In a picking or a stocking station, the storage containers 106 are normally not removed from the automated storage and retrieval system 10 but are returned into the framework structure 100 again once accessed. A port can also be used for transferring storage containers to another storage facility (e.g. to another framework structure or to another automated storage and retrieval system), to a transport vehicle (e.g. a train or a lorry), or to a production facility.
[0019] A conveyor system comprising conveyors is normally employed to transport the storage containers between the port columns 119,120 and the access station.
[0020] If the port columns 119,120 and the access station are located at different levels, the conveyor system may comprise a lift device with a vertical component for transporting the storage containers 106 vertically between the port column 119,120 and the access station.
[0021] The conveyor system may be arranged to transfer storage containers 106 between different framework structures, e.g. as is described in W02014/075937A1, the contents of which are incorporated herein by reference.
[0022] When a storage container 106 stored in one of the columns 105 disclosed in Fig. 1 is to be accessed, one of the container handling vehicles 201,301,401 is instructed to retrieve the target storage container 106 from its position and transport it to the drop-off port column 119. This operation involves moving the container handling vehicle 201,301,401 to a location above the storage column 105 in which the target storage container 106 is positioned, retrieving the storage container 106 from the storage column 105 using the container handling vehicle’s 201,301,401 lifting device (not shown), and transporting the storage container 106 to the drop-off port column 119. If the target storage container 106 is located deep within a stack 107, i.e. with one or a plurality of other storage containers 106 positioned above the target storage container 106, the operation also involves temporarily moving the abovepositioned storage containers prior to lifting the target storage container 106 from the storage column 105. This step, which is sometimes referred to as “digging” within the art, may be performed with the same container handling vehicle that is subsequently used for transporting the target storage container to the drop-off port column 119, or with one or a plurality of other cooperating container handling vehicles. Alternatively, or in addition, the automated storage and retrieval system 1 may have container handling vehicles 201,301,401 specifically dedicated to the task of temporarily removing storage containers 106 from a storage column 105. Once the target storage container 106 has been removed from the storage column 105, the temporarily removed storage containers 106 can be repositioned into the original storage column 105. However, the removed storage containers 106 may alternatively be relocated to other storage columns 105.
[0023] When a storage container 106 is to be stored in one of the columns 105, one of the container handling vehicles 201,301,401 is instructed to pick up the storage container 106 from the pick-up port column 120 and transport it to a location above the storage column 105 where it is to be stored. After any storage containers 106 positioned at or above the target position within the stack 107 have been removed, the container handling vehicle 201,301,401 positions the storage container 106 at the desired position. The removed storage containers 106 may then be lowered back into the storage column 105 or relocated to other storage columns 105.
[0024] For monitoring and controlling the automated storage and retrieval system 10, e.g. monitoring and controlling the location of respective storage containers 106 within the framework structure 100, the content of each storage container 106, and the movement of the container handling vehicles 201,301,401 so that a desired storage container 106 can be delivered to the desired location at the desired time without the container handling vehicles 201,301,401 colliding with each other, the automated storage and retrieval system 10 comprises a control system 121 which typically is computerized and which typically comprises a database for keeping track of the storage containers 106.
[0025] Jobs are assigned to container handling vehicles 201,301,401 for handling and transporting storage containers 106 from one location to another when operating on the rail system 108. When estimating durations to assign jobs it is important to have good estimations to execute or assign the jobs in the optimal order. A simple way of doing this is to use the Manhattan distance/time as an estimation. One drawback of using Manhattan distance is that the geometry of the grid is not considered, so that in some cases the estimation can be very inaccurate, for example across a gap in the grid with no rails or permanently blocked cells.
[0026] The A* search algorithm, or a variant of A*, is often used for conflictbased search and to generate routes for multiple agents such as container handling vehicles 201,301,401. Finding routes can be costly CPU wise when having many agents to move and/or a large grid for available for movements. While routing several agents, conflicting routes are marked as they occur. Conflicts are resolved by re-routing agents that did not get a route to their destination.
[0027] Performing a full A* routing algorithm for all container handling vehicles 201,301,401 for all tasks to be performed is in general too time consuming for real time computer processing, especially for large grids.
[0028] To solve this, AutoStore has previously developed a method, known as the ZoneRouter, for determining possible routes of a container handling vehicle 201,301,401. Conflict -based search is first performed by using ZoneRouter to find possible routes for agents from starting positions to ending positions. The method is very fast in most cases, while also being accurate in all cases. The rail system 108 arranged across the top of framework structure 100 is transformed to a simpler 2D-representation by describing it as a finite set of rectangular vertical and horizontal zones. These zones and their overlaps can then be used to quickly query for optimal routes and durations. The output routes from ZoneRouter and durations can be used to improve assignments and estimate times as well as to provide useful input to the actual route calculation.
[0029] The ZoneRouter does not however take any other container handling vehicles or their movement into account (e.g., a second, third, fourth, etc., container handling vehicle). The present invention is a development of ZoneRouter and provides a solution for generating routes for several container handling vehicles having conflicting routes generated by ZoneRouter.
SUMMARY OF THE INVENTION
[0030] This summary is provided to introduce in simplified form a selection of concepts that are further described herein. The summary is not intended to identify key or essential features of the invention.
[0031] The present invention is set forth and characterized in the independent claims, while the dependent claims describe other characteristics of the invention. The present invention is also set forth and characterized in the independent cluses, while the dependent clauses describe other characteristics of the invention.
[0032] More specifically, the invention is defined by a method of determining a route for a container handling vehicle, where the route is a route among a route of at least one other container handling vehicle, operating on a grid system e.g. a rail system of an automatic grid-based storage and retrieval system comprising a framework structure including the rail system, the rail system comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction which is perpendicular to the first direction, the rail system defining a plurality of grid positions each being identifiable by a first coordinate in the first direction and a second coordinate in the second direction.
[0033] The method comprising using a control system communicating with a vehicle controller in each container handling vehicle: creating a model of the rail system, comprising the steps of: representing the rail system as a finite set of non-overlapping rectangular first zones of grid positions, each first zone latitudinally extending in the first direction, and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction, wherein the zones are positioned around grid positions that are not accessible by the container handling vehicle; determining overlap information, wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones; and determining grid position zone information by, for each grid position, determining in which of the finite set of first zones and/or the finite set of second zones the grid position is located, wherein the control system receives requests for routes for each of at least two container handling vehicles to move from respective first grid positions to respective second grid positions, the control system: determining a route or a number of possible routes for the at least two container handling vehicles, from the respective first grid positions to the respective second grid positions, using the model of the rail system, prioritizing and selecting routes for each container handling vehicle, where a container handling vehicle having a lower number of possible routes is selected over a conflicting route of a container handling vehicle having a higher number of possible routes to avoid conflicts between routes, where for_the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle; and controlling each container handling vehicle to follow the selected routes. [0034] Conflicting routes are routes for container handling vehicles having one or more overlapping zones.
[0035] According to one embodiment of the invention, wherein for three or more container handling vehicles that may have conflicting routes, the routes of the container handling vehicles are ranked and prioritized according to the number of possible routes, where routes of container handling vehicles having least possible routes are ranked first while routes of container handling vehicles having most possible routes are ranked and prioritized last, and selecting routes for the container handling vehicle according to ranking. Cost functions may also be included to determine both non-conflicting routes and fastest routes to destinations. If for instance a container handling vehicle has five possible routes to a destination where two of the routes have low cost, while another container handling vehicle has three possible routes to a destination, all routes having same cost, a conflicting low cost route of the container handling vehicle having more possible routes may be selected.
[0036] According to another embodiment, wherein for at least two container handling vehicles having at least two possible routes each, routes having lowest cost are prioritized and selected. A route having lowest cost is the fastest route for a container handling vehicle from its current position to a destination, e.g. a movement along a straight line will have lower cost that a movement where direction has to be changed one or more times to reach a destination.
[0037] In one embodiment, the method may comprise, using the set of first zones, the set of second zones and the overlap information to generate a zone graph comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
[0038] In one embodiment, the method may comprise, determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph. The graph traversal and path search algorithm may in one embodiment be an A* algorithm.
[0039] In one embodiment, representing the rail system as the set of first zones and the set of second zones may comprise: defining the grid positions that are not accessible by the container handling vehicle as blocked cells and grid cells accessible for the container handling vehicle as open cells, determining a first set of non-overlapping rectangular regions of grid positions, each first region latitudinally extending in the first direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining a second set of non-overlapping rectangular regions of grid positions, each second region longitudinally extending in the second direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining the finite set of first zones by removing any region of the first set of regions that falls completely within a region of the second set of regions; and determining the finite set of second zones by removing any region of the second set of regions that falls completely within a region of the first set regions.
[0040] In one embodiment, the step of determining the first set of regions may comprise determining continuous sections of open cells extending in the first direction that are uninterrupted by a blocked cell, each continuous section having a start position having a first coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells latitudinally extending in the first direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same first coordinate and the same length, or a single vertical continuous section, and the step of determining the second set of regions comprises determining continuous sections of open cells extending in the second direction that are uninterrupted by a blocked cell, each continuous section having a start position having a second coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells longitudinally extending in the second direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same second coordinate and the same length, or a single horizontal continuous section.
[0041] In one embodiment, defining grid positions that are not accessible by the container handling vehicle may comprise determining one or more grid positions that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle, and identifying the one or more grid positions as being not accessible by the container handling vehicle.
[0042] In one embodiment, the method may comprise: receiving a request for a route for a plurality of container handling vehicles from a plurality of first grid position to a second grid position; determining the fastest route for each of the plurality of container handling vehicles from the plurality of first grid position to the second grid position using the model of the rail system, and determining based on the fastest route for each of the plurality container handling vehicles an optimal container handling vehicle of the plurality container handling vehicles for moving to the second grid position, and instructing the optimal container handling vehicle to move to the second grid position.
[0043] In one embodiment, the method may comprise: using timing information of the container handling vehicles following routes to determine if crossings of the routes at potentially conflicting grid positions, are non-conflicting.
[0044] In a second aspect, the invention concerns a system of determining a route for a container handling vehicle, where the route is a route among routes of other container handling vehicles, all operating on a rail system of an automatic grid-based storage and retrieval system comprising a framework structure including the rail system, the rail system comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction which is perpendicular to the first direction, the rail system defining a plurality of grid positions each being identifiable by a first coordinate in the first direction and a second coordinate in the second direction; a control system configured to communicate with a vehicle controller in the container handling vehicle, wherein the control system is configured to: create a model of the rail system, by: representing the rail system as a finite set of non-overlapping rectangular first zones of grid positions, each first zone longitudinally extending in the first direction, and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction, wherein the zones are positioned around grid positions that are not accessible by the container handling vehicle; determining overlap information, wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones; and determining grid position zone information by, for each grid position, determining in which of the finite set of first zones and/or the finite set of second zones the grid position is located; wherein upon receiving a request for routes for each of at least two container handling vehicles to move from respective first grid positions to respective second grid positions, the control system is configured to: determine a route or a number of possible routes for the at least two container handling vehicles, from the respective first grid positions to the respective second grid positions, using the model of the rail system, prioritize and select routes for each container handling vehicle, where a container handling vehicle having a lower number of possible routes is selected over a conflicting route of a container handling vehicle having a higher number of possible routes to avoid conflicts between routes, where for the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from possible routes, and an alternative route is selected for that container handling vehicle; and control each container handling vehicle to follow the selected routes.
[0045] In one embodiment, the system may be configured to determine, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate nor the same second coordinate.
[0046] In one embodiment, the system may be configured to determine, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones.
[0047] In one embodiment, the system may be configured to use the set of first zones, the set of second zones and the overlap information to generate a zone graph comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
[0048] In one embodiment, the system may be configured to determine, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph. The graph traversal and path search algorithm may in one embodiment be an A* algorithm.
[0049] In one embodiment, representing the rail system as the set of first zones and the set of second zones may comprise: defining the grid positions that are not accessible by the container handling vehicle as blocked cells and grid cells accessible for the container handling vehicle as open cells, determining a first set of non-overlapping rectangular regions of grid positions, each first region latitudinally extending in the first direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining a second set of non-overlapping rectangular regions of grid positions, each second region longitudinally extending in the second direction and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell, determining the finite set of first zones by removing any region of the first set of regions that falls completely within a region of the second set of regions, and determining the finite set of second zones by removing any region of the second set of regions that falls completely within a region of the first set regions.
[0050] In one embodiment, determining the first set of regions may comprise determining continuous sections of open cells extending in the first direction that are uninterrupted by a blocked cell, each continuous section having a start position having a first coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells latitudinally extending in the first direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same first coordinate and the same length, or a single vertical continuous section, and the step of determining the second set of regions comprises determining continuous sections of open cells extending in the second direction that are uninterrupted by a blocked cell, each continuous section having a start position having a second coordinate and a length defined by the number of open cells uninterrupted by a blocked cell, wherein the largest possible rectangle of continuous open cells longitudinally extending in the second direction uninterrupted by a blocked cell comprises either a number of adjacent continuous sections having a start position with the same second coordinate and the same length, or a single horizontal continuous section.
[0051] In one embodiment, defining grid positions that are not accessible by the container handling vehicle may comprise determining one or more grid positions that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle, and identifying the one or more grid positions as being not accessible by the container handling vehicle.
[0052] In one embodiment, the system may be configured to receive a request for a route for a plurality of container handling vehicles from a plurality of first grid position to a second grid position, determine the fastest route for each of the plurality of container handling vehicles from the plurality of first grid position to the second grid position using the model of the rail system, determine based on the fastest route for each of the plurality container handling vehicles an optimal container handling vehicle of the plurality container handling vehicles for moving to the second grid position, and instruct the optimal container handling vehicle to move to the second grid position.
[0053] In a third aspect the invention is directed to computer program product for a control system in the system of the second aspect, wherein the computer program product comprising instructions that when performed on the control system performs the method according to the first aspect.
[0054] Aspects of the invention provide a system, method, and computer program product for determining non-conflicting routes for container handling vehicles operating on a rail system of an automatic grid-based storage and retrieval system. The method comprises creating a model of the rail system representing the rail system as a finite set of non-overlapping rectangular first zones in a first direction, and a finite set of non-overlapping rectangular second zones in a second direction, wherein the zones are positioned around grid positions that are not accessible by the container handling vehicle, determining overlap information indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones, determining grid position zone information by, for each grid position determining in which of the finite set of first zones and/or the finite set of second zones the grid position is located, receiving a request for a route for each of at least two container handling vehicles to move from respective first grid positions to respective second grid positions, prioritizing and selecting routes for each container handling vehicle, where a container handling vehicle having a lower number of possible routes is selected over a conflicting route of a container handling vehicle having a higher number of possible routes to avoid conflicts between routes.
BRIEF DESCRIPTION OF THE DRAWINGS
[0055] 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:
[0056] Fig. 1 is a perspective view of a framework structure of a prior art automated storage and retrieval system.
[0057] Fig. 2 is a perspective view of a prior art container handling vehicle having an internally arranged cavity for carrying storage containers therein.
[0058] Fig. 3 is a perspective view of a prior art container handling vehicle having a cantilever for carrying storage containers underneath.
[0059] Fig. 4 is a perspective view, seen from below, of a prior art container handling vehicle having an internally arranged cavity for carrying storage containers therein.
[0060] Fig. 5 is a schematic top view of an exemplary rail system and blocked cells.
[0061] Fig. 6 is a schematic illustration of a method according to an embodiment of the present invention. [0062] Figs. 7 is a schematic illustration of a method according to an embodiment of the present invention.
[0063] Figs. 8 is a schematic illustration of a method according to an embodiment of the present invention.
[0064] Fig. 9 is a schematic illustration of a method according to an embodiment of the present invention.
[0065] Fig. 10 is a schematic illustration of a method according to an embodiment of the present invention.
[0066] Fig. 11 is a schematic illustration of a shortest route according to an embodiment of the present invention.
[0067] Fig. 12 is a schematic illustration of a shortest route according to an embodiment of the present invention.
[0068] Fig. 13 is a schematic illustration of a shortest route according to an embodiment of the present invention.
[0069] Fig. 14 is a schematic illustration of a shortest route according to an embodiment of the present invention.
[0070] Fig. 15 is a flowchart of a method according to an embodiment of the present invention.
[0071] Fig. 16 is a schematic illustration of a zone graph according to an embodiment of the present invention.
[0072] Fig. 17 is a schematic illustration of a shortest route according to an embodiment of the present invention.
[0073] Fig. 18 is a schematic illustration of a shortest route according to an embodiment of the present invention.
[0074] Fig. 19 is a schematic illustration of conflicting routes for several container handling vehicles.
DETAILED DESCRIPTION
[0075] In overview, a method (1500) is provide of determining a route for a container handling vehicle (201,301,401). The method comprises receiving requests for routes (1505) for each of at least two container handling vehicles
(201.301.401) to move from respective first grid positions to respective second grid positions. The method determines a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions. The method prioritizes and selects routes (1512) for each container handling vehicle
(201.301.401). A container handling vehicle (201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes. For the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401). Each container handling vehicle
(201.301.401) is controlled to follow the selected routes.
[0076] In the following, embodiments of the invention will be discussed 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.
[0077] The framework structure 100 of the automated storage and retrieval system 10 is constructed in a similar manner to the prior art framework structure 100 described above in connection with Fig. 1. That is, the framework structure 100 comprises several upright members 102, and comprises a first, upper rail system 108 extending in the X direction and Y direction. Examples of container handling vehicles 201,301,401 running on the rail system 108 are illustrated in Figs. 2-4.
[0078] The framework structure 100 further comprises storage compartments in the form of storage columns 105 provided between the members 102 wherein storage containers 106 are stackable in stacks 107 within the storage columns 105.
[0079] The framework structure 100 can be of any size. It is understood that the framework structure can be considerably wider and/or longer and/or deeper than disclosed in Fig. 1. For example, the framework structure 100 may have a horizontal extent of more than 700x700 columns and a storage depth of more than twelve containers. [oo8o] As described in the background section above the present invention is a further development of the Autostore’s ZoneRouter method used for determining possible routes on the rail system for a container handling vehicle operating on an automated storage and retrieval system. To fully understand the present invention, the ZoneRouter method will therefore first be described by referring to one embodiment of an automated storage and retrieval system having a storage cells, rail system, and blocked cell as illustrated in Figs. 5 - 18.
[0081] Fig. 5 is a schematic top view of an exemplary rail system 500. The rail system 500 comprising a first set of parallel rails in a first direction, and a second set of parallel rails arranged in a second direction Y which is perpendicular to the first direction X. The rail system 500 defines a plurality of grid positions (Xi,Yj) each being identifiable by a first coordinate Xi in the first direction X and a second coordinate Yj in the second direction Y. Fig. 5 illustrates one exemplary grid position (Xi,Yj), where Xi=4 and Yj=2. The illustrated grid positions (Xi,Yj) are for simplicity square, however, in typical implementations such as the rail system 108 of Fig. 1, the grid positions (Xi,Yj) or cells, are rectangular. For rectangular cells, the time to drive over a cell is different in the x- and the y-direction. The rail system is an example of a grid system.
[0082] Grid positions (Xi,Yj) that are permanently inaccessible for a container handling vehicle 201,301,401 are referred to as permanently blocked cells 501. The permanently blocked cells 501 are grid positions that are not physically accessible for the container handling vehicles due to the physical layout of a warehouse, such as a wall, a pillar, a low ceiling or other reasons physical reasons for missing cells. In addition to the permanently blocked cells there maybe grid positions (Xi,Yj) that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle 201,301,401 operating on the rail system 500, such that the grid position is not physically accessible for the container handling vehicle 201,301,401. One such grid position 601 is illustrated in Figs. 6 - 14, 17 and 18.
[0083] Fig. 15 illustrates a flowchart of a method 1500 of determining a route for a container handling vehicle 201,301,401 operating on the rail system 500 illustrated in Fig. 5. The method comprises, using a control system communicating with a vehicle controller in the container handling vehicle 201,301,401, creating a model 1501 of the rail system 500, receiving a request for a route 1505 for at least two container handling vehicle 201,301,401 from a first grid position to a second grid position, and determining a route or a set of routes 1506 for the at least two container handling vehicles 201,301,401 from the first grid position to the second grid position using the model of the rails system 500.
[0084] The number of possible routes on the rail system 108 for a container handling vehicle when driving from a start position to a destination is described with a slack number. A slack of 4 means that there are 4 possible routes, all leading to the same destination.
[0085] The slack number, i.e. number of possible routes, is used for selecting routes 1512 for each container handling vehicle 201,301,401 to avoid conflicts between routes. A route for a container handling vehicle 201,301,401 having a low slack number is selected over a conflicting route of container handling vehicle 201,301,401 having a higher slack number. In this case, conflicting routes are excluded from the possible routes of the container handling vehicle 201,301,401 having the higher slack number. One or more routes for a container handling vehicle 201,301,401 having a slack number of for instance 8 will be excluded from available routes and prioritized for a container handling vehicle 201,301,401 having a lower slack number, if the routes are in conflict.
[0086] With additional reference to Fig. 9, creating the model 1501 of the rail system 500 comprises the step of representing the rail system 500 as a finite set of non-overlapping rectangular first zones 1502 of grid positions A, B, C, D, E, F, G, H, I, J, K, L, each first zone latitudinally extending in the first direction X, and a finite set of non-overlapping rectangular second zones of grid positions 1, 2, 3, 4, 5, 6, 7, 8, 9, each second zone longitudinally extending in the second direction Y, wherein the zones are positioned around grid positions 501, 601 that are not accessible by the container handling vehicle 201,301,401.
[0087] In a following step 1503, overlap information is determined, wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L and a zone of the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9. For example, using the information from Fig. 9 it is clear that zone 1 overlaps zone A, C, D, E and F, zone 2 overlaps zone L, zone 3 overlaps zone A, C, D, E, F, I and L, and so on. This information may be stored in an array and it is not modified once created. [oo88] In the next step 1504, grid position zone information is determined by, for each grid position (Xi,Yj), determining in which of the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L and/or the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9 the grid position (Xi,Yj) is located. The grid position information may be stored in a matrix or similar structure and is not modified once created. Fig. 10 illustrates the zones that all the grid positions belong to. A grid position belongs to minimum one zone and maximum two zones. This allows for a sparse saving of data and fast lookup by grid position.
[0089] The steps of receiving and determining the route for the container handling vehicle 201,301,401 from a first grid position to a second grid position using the model of the rail system 500 is described with reference to Figs. 11 - 14 and 17.
[0090] Now with reference to Figs. 15, in one embodiment, the step of representing the rail system 500 as the set of first zones A, B, C, D, E, F, G, H, I, J, K, L and the set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9 comprises the step 1507 of defining the grid positions (Xi,Yj) that are not accessible by the container handling vehicle 201,301,401 as blocked cells 501, 601 and grid cells accessible for the container handling vehicle 201,301,401 as open cells 502. Blocked cells 501, 601 maybe permanently blocked cells 501 or maybe grid positions 601 that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle 201,301,401 operating on the rail system 500 such that the container handling vehicle 201,301,401 cannot pass in at least one direction.
[0091] Then in a following step, illustrated in Fig. 7, determining a first set of non-overlapping rectangular regions 1508 of grid positions 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, each first region latitudinally extending in the first direction X and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell 501, 601, and determining a second set of non-overlapping rectangular regions 1509 of grid positions 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, each second region longitudinally extending in the second direction Y and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell 501, 601. The term continuous open cells denote the largest extent of side-by-side open cells in each direction.
[0092] Then in a following step 1510, illustrated in Fig. 8, determining the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L by removing any region 708, 710, 711 of the first set of regions that falls completely within a region of the second set of regions 717, 723, 726, and determining the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9 by removing any region 718, 724, 727 of the second set of regions that falls completely within a region of the first set regions 707,
709, 715-
[0093] Regions that fall completely withing another region are redundant. Removing these redundant regions is important for several reasons such as to make any A* route search efficient, and that moving from one zone to another zone implies making a turn.
[0094] Now with reference to Fig. 15, in one embodiment, the step of determining the first set of regions 1508 comprises, illustrated in Fig. 6 B, determining continuous sections of open cells 502 extending in the first direction X that are uninterrupted by a blocked cell 501, 601, each continuous section having a start position having a first coordinate Xi and a length defined by the number of open cells 502 uninterrupted by a blocked cell 501, 601, and as illustrated by Fig. 7B, the largest possible rectangle of continuous open cells 502 latitudinally extending in the first direction X uninterrupted by a blocked cell 501, 601 comprises either a number of adjacent continuous sections having a start position with the same first coordinate Xi and the same length, or a single vertical continuous section. Similarly, the step of determining the second set of regions 1509 comprises, illustrated in Fig. 6 A, determining continuous sections of open cells 502 extending in the second direction Y that are uninterrupted by a blocked cell 501, 601, each continuous section having a start position having a second coordinate Yj and a length defined by the number of open cells 502 uninterrupted by a blocked cell 501, 601, and as illustrated by Fig. 7 A, the largest possible rectangle of continuous open cells 502 longitudinally extending in the second direction Y uninterrupted by a blocked cell 501, 601 comprises either a number of adjacent continuous sections having a start position with the same second coordinate Yi and the same length, or a single horizontal continuous section.
[0095] In one embodiment, the method comprises using the set of first zones, the set of second zones and the overlap information to generate a zone graph 1511 comprising nodes and edges, wherein the nodes represent the finite set of first zones A, B, C, D, E, F, G, H, I, J, K, L and the finite set of second zones 1, 2, 3, 4, 5, 6, 7, 8, 9, and the edges represent the overlap information. [0096] Fig. 16 is an exemplary schematic illustration of a zone graph 1600 of the zones and edges of the rail system 500 above the dashed line ai-a2 shown in Fig. 9. The circles represent the zones A, C, D, E, F, I, L, 1, 2, 3, 4, 5 and the interconnecting lines the edges. The stippled edges extending from zones D and F illustrates overlap to zones below the dashed line ai-a2 in Fig. 9.
[0097] A request for a route 1505 for the container handling vehicle 201,301,401 from a first grid position to a second grid position comprises the first grid position, i.e. the start position of the container handling vehicle 201,301,401, and the second grid position, i.e. the end position of the container handling vehicle 201,301,401. The request may also comprise information about the container handling vehicle 201,301,401 such as robot type, current direction of movement, and orientation of the container handling vehicle 201,301,401 on the rail system 500, and information about the rail system 500, such as cell sizes to calculate movement times. The request for the route is for the optimal route from the first grid position to the second grid position, e.g. the fastest route. Alternatively, instead of requesting a route, the request is for minimum cost. The request is the same as for a route, but instead of returning a route, the request returns the cost/duration of the optimal route.
[0098] When determining the fastest route, the method of the present invention distinctly handles three main cases: straight routes, Manhattan routes and routes through more than two zones.
[0099] Using the grid position zone information it may be determined that the fastest route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj). This guarantees that there is no blockage between the start and end positions. If only considering that the first grid position and the second grid position share either the same first coordinate (Xi) or the same second coordinate (Yj), there is no guarantee that the container handling vehicle can follow the route, for example if going from zone L to zone K as illustrated in Fig. 9 B. Fig. 11 illustrates a straight line route between point A and B within the same zone 7.
[00100] Using the grid position zone information it may be determined that the fastest route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj). For Manhattan routes inside a single zone there are two equally optimal routes to choose from. Fig. 12 illustrates the two possibilities from A to B within zone C for a non-moving container handling vehicle.
[00101] If in either of the single zone routes cases discussed above, the container handling vehicle is moving and is currently driving past the second grid position or driving away from the second grid position, additional two turns are required to get to the second grid position, unless currently driving across the target position which requires the container handling vehicle to stop and drive straight back.
[00102] Using the grid position zone information and the overlap information it may be determined that the fastest route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones, such as illustrated in Fig. 13. In this case it is first verified that the first grid position and the second grid positions are not in the same zone.
[00103] In the third case, it is determined using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones. That is, the route is passing through more than two zones. In this case the fastest route between the first grid position and the second grid position is determined using a graph traversal and path search algorithm on the zone graph 1600. Any suitable graph traversal and path search algorithm known to the skilled person may be used. A preferred graph traversal and path search algorithm is an A* algorithm. As illustrated in Fig. 14, a turn is created when moving to the first available cell inside the next zone, such that long route segments are created at the end of the route. This allows easy determination of the optimal route. This is due to the acceleration/deceleration of the container handling vehicles. Long route segments provide for less acceleration/deceleration which is more optimal. In particular, the determination considers the overlapping zones, calculates the time of going into the first available cell in the first overlapping zone from the first grid position. From the first available cell in the first overlapping zone, this is repeated for the first available cell in the second overlapping zone and so on to determine the route. The last part of the route, indicated by dashed lines, is treated separately because the container handling vehicle has required direction into the final zone. The second to last segment is therefore extended one cell in this case before turning to match the second grid position in the correct way.
[00104] The determination of the fastest route from the first grid position to the second grid position is determined as if the container handling vehicle is alone on the rail system 500. That is, other container handling vehicles on the rail system and other temporary blockages such as top bins, are not considered. The control system 121 is in communication with a plurality of container handling vehicles 201,301,401, and has knowledge of their current positions, paths, and other temporary blockages. The control system 121 may therefore find that the determined fastest route is inaccessible because other container handling vehicles are standing on the route or because of other temporary blockages, and parts of the optimal route can be modified to take this into account.
[00105] The number of possible routes on the rail system 108 for a container handling vehicle when driving from a start position to a destination is described with a slack number. A slack of 4 means that there are 4 possible routes, all leading to the same destination.
[00106] Illustrated in Fig. 17 the first route segment is set to go into the next zone 7, that is not turn at the first available cell. There are then four possibilities since the next zone 7 has height 4, which means that the segment has a slack of 4, giving 4 permutations of the route from the first grid position to the second grid position. While the first slack choice, i.e. turning at the first available cell, is the optimal one, the other routes will not be far off. Illustrated in Fig. 18, the second route segment has a slack of 3, since the next zone E has a width of 3, providing three extra route permutations on top of the existing four from the first segment. The route from the first grid position to the second grid position then has 12 permutations that the control system 121 can iterate through fast to determine the most optimal of them, in view of other container handling vehicles and temporary blockages on the rail system 500.
[00107] The determination of the fastest route between grid positions may be performed for a plurality of container handling vehicles, e.g. to determine which of a plurality of container handling vehicles that is the optimal container handling vehicle to perform a task, or to determine which of a plurality of tasks to be performed first. In one example a task, such as picking up storage container, is to be completed at the second grid position. In one embodiment of the method a request may be received for a route for a plurality of container handling vehicles 201,301,401 from a plurality of first grid position to the second grid position. Then the fastest route for each of the plurality of container handling vehicles 201,301,401 from the plurality of first grid position to the second grid position maybe determined using the model of the rail system 500. Based on the fastest route for each of the plurality container handling vehicles 201,301,401 an optimal container handling vehicle of the plurality container handling vehicles 201,301,401 for moving to the second grid position maybe determined, and the optimal container handling vehicle is instructed to move to the second grid position to perform the task.
[00108] The ZoneRouter method described above, with reference to Figs. 5- 18, does not consider any other container handling vehicles having conflicting routes via the same overlapping zones or their movement when following routes. The present invention is a further development of the described ZoneRouter and provides a method for solving conflicting routes for several container handling vehicles 201,301,401 being generated by the ZoneRouter.
[00109] As mentioned, the routes generated by the ZoneRouter have the added concept of slack, meaning that a route for one container handling vehicle is in practice a set of routes, where the slack number of a container handling vehicle represents the number of possible routes from a starting position to a destination.
[00110] The present invention uses slack numbers of several container handling vehicles 201,301,401 to determine non-conflicting routes for container handling vehicles 201,301,401 having routes via overlapping zones as their possible routes.
[00111] Instead of selecting which of conflicting routes should be re-routed, the slack number is used to determine routes that should be selected to avoid conflict. Based on the slack number, possible route conflicts are resolved by prioritizing and keeping routes for container handling vehicles 201,301,401 having a lower slack number and selecting a non-conflicting route for a container handling vehicle 201,301,401 having a higher slack number.
[00112] Fig. 19 illustrates an example of possible routes for three different container handling vehicles in an example grid. Route A has 12 possibilities, i.e. a slack of 12, because it has 4 possible routes in the horizontal zone and 3 possible routes in the vertical zone. Route B has a slack of 1, meaning that it only has one optimal route, as has route C. In this case it is identified that route A and B, and route A and C have a conflict. Instead of selecting which of the routes should be re-routed, the slack of a route A indicates that it is globally better to take one of the centre routes in the Y-direction and allow route B and C to have their optimal route.
[00113] Further, time can be considered to avoid conflicts between agents such as container handling vehicles 201, 301, 401. For example, if route B is given priority, since route A can be routed differently, there is still a conflict with route B when route A goes in the X-direction through route B. Since the timing information of the routes for the agents is known or can be calculated, we know that there will be no conflict in the X-direction since an agent for route B has already passed crossing rails when an agent for route A moves in the X- direction.
[00114] If some agents cannot be routed, e.g. if two routes are equal but opposite in direction, it is possible to fall back to regular A* routing and conflict resolution based on other priorities.
[00115] An advantage of the present solution is that generating routes is fast and requires less load on CPU or GPU. A route set for each agent is fully parallelizable and can be run in a multithreaded fashion, either on a CPU or on a GPU.
[00116] List of reference numbers: Prior art (Figs. 1-4):
Figure imgf000029_0001
(Figs. 5 - 19)
Figure imgf000030_0001
CLAUSES
[00117] Aspects and features of the present invention are defined in the following numbered clauses.
1. A method (1500) of determining a route for a container handling vehicle (201,301,401), where the route is a route among a route of at least one other container handling vehicle (201,301,401), operating on a rail system (108, 500) of an automatic grid-based storage and retrieval system (10) comprising a framework structure (100) including the rail system (108, 500), the rail system (108, 500) comprising a first set of parallel rails (no) in a first direction (X), and a second set of parallel rails (111) arranged in a second direction (Y) which is perpendicular to the first direction (X), the rail system (108, 500) defining a plurality of grid positions ((Xi,Yj)) each being identifiable by a first coordinate (Xi) in the first direction (X) and a second coordinate (Yj) in the second direction (Y), the method comprising using a control system (121) communicating with a vehicle controller in each container handling vehicle (201,301,401):
- creating a model (1501) of the rail system (108, 500), comprising the steps of:
- representing the rail system (108, 500) as a finite set of nonoverlapping rectangular first zones (1502) of grid positions, each first zone latitudinally extending in the first direction (X), and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction (Y), wherein the zones are positioned around grid positions (501, 601) that are not accessible by the container handling vehicle (201,301,401);
- determining overlap information (1503), wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones;
- determining grid position zone information (1504) by, for each grid position ((Xi,Yj)), determining in which of the finite set of first zones and/or the finite set of second zones the grid position ((Xi,Yj)) is located,
- wherein the control system receives requests for routes (1505) for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions, the control system:
- determining a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions, using the model (1501) of the rail system (108, 500),
- prioritizing and selecting routes (1512) for each container handling vehicle (201,301,401), where a container handling vehicle (201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes, where for the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401); and
- controlling each container handling vehicle (201,301,401) to follow the selected routes. The method according to clause 1, wherein for three or more container handling vehicles (201,301,401) that may have conflicting routes, the routes of the container handling vehicles (201,301,401) are ranked and prioritized according to the number of possible routes, where routes of container handling vehicles (201,301,401) having least possible routes are ranked first while routes of container handling vehicles (201,301,401) having most possible routes are ranked and prioritized last, and selecting routes for the container handling vehicle (201,301,401) according to ranking. The method according to clause 1, wherein for at least two container handling vehicles (201,301,401) having at least two possible routes each, routes having lowest cost are prioritized and selected. The method of any of clauses 1 - 3, comprising, determining, using the grid position zone information, that the route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj). The method of any of clauses 1 - 4, comprising, determining, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj). The method of any of clauses 1 - 5, comprising, determining, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones. The method of clause 1, comprising, using the set of first zones, the set of second zones and the overlap information to generate a zone graph (1511) comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information. The method of clause 7, comprising, determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph. The method of clause 8, wherein the graph traversal and path search algorithm is an A* algorithm. The method of any of clauses 1 - 9, wherein representing the rail system (108, 500) as the set of first zones and the set of second zones comprises:
- defining the grid positions that are not accessible (1507) by the container handling vehicle (201,301,401) as blocked grid cells (501, 601) and grid cells accessible for the container handling vehicle (201,301,401) as open grid cells (502);
- determining a first set of non-overlapping rectangular regions (1508) of grid positions (701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715), each first region latitudinally extending in the first direction (X) and defining the largest possible rectangle of continuous open grid cells uninterrupted by at least one blocked grid cell (501, 601);
- determining a second set of non-overlapping rectangular regions (1509) of grid positions (716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727), each second region longitudinally extending in the second direction (Y) and defining the largest possible rectangle of continuous open grid cells uninterrupted by at least one blocked grid cell (501, 601);
- determining the finite set of first zones by removing (1510) any region (708, 710, 711) of the first set of regions that falls completely within a region of the second set of regions (717, 723, 726); and
- determining the finite set of second zones by removing (1510) any region (718, 724, 727) of the second set of regions that falls completely within a region of the first set regions (707, 709, 715). The method of clause 10, wherein the step of determining the first set of regions (1508) comprises determining continuous sections of open grid cells (502) extending in the first direction (X) that are uninterrupted by a blocked grid cell (501, 601), each continuous section having a start position having a first coordinate (Xi) and a length defined by the number of open grid cells (502) uninterrupted by a blocked grid cell (501, 601); wherein the largest possible rectangle of continuous open grid cells (502) latitudinally extending in the first direction (X) uninterrupted by a blocked grid cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same first coordinate (Xi) and the same length, or a single vertical continuous section; and the step of determining the second set of regions (1509) comprises determining continuous sections of open grid cells (502) extending in the second direction (Y) that are uninterrupted by a blocked grid cell (501, 601), each continuous section having a start position having a second coordinate (Yj) and a length defined by the number of open grid cells (502) uninterrupted by a blocked grid cell (501, 601); wherein the largest possible rectangle of continuous open grid cells (502) longitudinally extending in the second direction (Y) uninterrupted by a blocked grid cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same second coordinate (Yi) and the same length, or a single horizontal continuous section. The method of any of clauses 1 - 11, wherein defining grid positions that are not accessible by the container handling vehicle (201,301,401) comprises:
- determining one or more grid positions ((Xi,Yj)) that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle (201,301,401); and
- identifying the one or more grid positions (601) as being not accessible by the container handling vehicle (201,301,401). The method of any of clauses 1 - 12, wherein the method comprises:
- receiving a request for a route for a plurality of container handling vehicles (201,301,401) from a plurality of first grid position to a second grid position;
- determining the fastest route for each of the plurality of container handling vehicles (201,301,401) from the plurality of first grid position to the second grid position using the model of the rail system (108, 500);
- determining based on the fastest route for each of the plurality container handling vehicles (201,301,401) an optimal container handling vehicle of the plurality container handling vehicles
(201,301,401) for moving to the second grid position; and
- instructing the optimal container handling vehicle to move to the second grid position.
14. The method of any of clauses 1 - 13, wherein the method comprises:
- using timing information of the container handling vehicles
(201,301,401) following routes to determine if crossings of the routes at potentially conflicting grid positions ((Xi,Yj)), are non-conflicting.
15. A system of determining a route for a container handling vehicle
(201,301,401), where the route is a route among routes of other container handling vehicles (201,301,401), all operating on a rail system (108, 500) of an automatic grid-based storage and retrieval system (10) comprising a framework structure (100) including the rail system (108, 500), the rail system (108, 500) comprising a first set of parallel rails (110) in a first direction (X), and a second set of parallel rails (111) arranged in a second direction (Y) which is perpendicular to the first direction (X), the rail system (108, 500) defining a plurality of grid positions ((Xi,Yj)) each being identifiable by a first coordinate (Xi) in the first direction (X) and a second coordinate (Yj) in the second direction (Y); a control system (121) configured to communicate with a vehicle controller in the container handling vehicle (201,301,401), wherein the control system (121) is configured to:
- create a model of the rail system (108, 500), comprising the steps of:
- representing the rail system (108, 500) as a finite set of non-overlapping rectangular first zones of grid positions, each first zone longitudinally extending in the first direction (X), and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction (Y), wherein the zones are positioned around grid positions (501, 601) that are not accessible by the container handling vehicle (201,301,401);
- determining overlap information, wherein the overlap information is indicative of one or more regions of the rail system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones; and
- determining grid position zone information by, for each grid position ((Xi,Yj)), determining in which of the finite set of first zones and/or the finite set of second zones the grid position ((Xi,Yj)) is located;
- wherein upon receiving a request for routes for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions, the control system is configured to:
- determine a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions, using the model (1501) of the rail system (108, 500),
- prioritizing and selecting routes (1512) for each container handling vehicle (201,301,401), where a container handling vehicle (201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes, where for the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401); and
- control each container handling vehicle (201,301,401) to follow the selected routes.
16. The system according to clause 15, wherein for three or more container handling vehicles (201,301,401) that may have conflicting routes, the control system (121) is configured to rank and prioritize the routes of the container handling vehicles (201,301,401) according to the number of possible routes, where routes of container handling vehicles (201,301,401) having least possible routes are ranked first while routes of container handling vehicles (201,301,401) having most possible routes are ranked and prioritized last, and where routes for the container handling vehicle (201,301,401) according to ranking are selected. - The system according to clause 15, wherein for at least two container handling vehicles (201,301,401) having at least two possible routes each, the control system (121) is configured to prioritize and select routes having lowest cost. . The system of any of clauses 15 - 17, configured to determining, using the grid position zone information, that the route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj). . The system of any of clauses 15 - 18, configured to determining, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj). . The system of any of clauses 15 - 19, configured to determining, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones. . The system of any of clauses 15 - 20, configured using the set of first zones, the set of second zones and the overlap information to generate a zone graph (1511) comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information. . The system of clause 21, configured to determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph. The system of clause 22, wherein the graph traversal and path search algorithm is an A* algorithm. The system of any of clauses 15 - 23, wherein representing the rail system (108, 500) as the set of first zones and the set of second zones comprises:
- defining the grid positions that are not accessible (1507) by the container handling vehicle (201,301,401) as blocked grid cells (501, 601) and grid cells accessible for the container handling vehicle (201,301,401) as open cells (502);
- determining a first set of non-overlapping rectangular regions (1508) of grid positions (701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715), each first region longitudinally extending in the first direction (X) and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell (501, 601);
- determining a second set of non-overlapping rectangular regions (1509) of grid positions (716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727), each second region longitudinally extending in the second direction (Y) and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell (501, 601);
- determining the finite set of first zones by removing (1510) any region (708, 710, 711) of the first set of regions that falls completely within a region of the second set of regions (717, 723, 726); and
- determining the finite set of second zones by removing (1510) any region (718, 724, 727) of the second set of regions that falls completely within a region of the first set regions (707, 709, 715). The system of clause 24, wherein the step of determining the first set of regions (1508) comprises determining continuous sections of open cells (502) extending in the first direction (X) that are uninterrupted by a blocked cell (501, 601), each continuous section having a start position having a first coordinate (Xi) and a length defined by the number of open cells (502) uninterrupted by a blocked cell (501, 601); wherein the largest possible rectangle of continuous open cells (502) longitudinally extending in the first direction (X) uninterrupted by a blocked cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same first coordinate (Xi) and the same length, or a single vertical continuous section; and the step of determining the second set of regions (1509) comprises determining continuous sections of open cells (502) extending in the second direction (Y) that are uninterrupted by a blocked cell (501, 601), each continuous section having a start position having a second coordinate (Yj) and a length defined by the number of open cells (502) uninterrupted by a blocked cell (501, 601); wherein the largest possible rectangle of continuous open cells (502) longitudinally extending in the second direction (Y) uninterrupted by a blocked cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same second coordinate (Yi) and the same length, or a single horizontal continuous section. The system of any of clauses 15 - 25, wherein defining grid positions that are not accessible by the container handling vehicle (201,301,401) comprises:
- determining one or more grid positions ((Xi,Yj)) that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle (201,301,401); and
- identifying the one or more grid positions (601) as being not accessible by the container handling vehicle (201,301,401). The system of any of clauses 15 - 26, configured to:
- receiving a request for a route for a plurality of container handling vehicles (201,301,401) from a plurality of first grid position to a second grid position; - determining the fastest route for each of the plurality of container handling vehicles (201,301,401) from the plurality of first grid position to the second grid position using the model of the rail system (108, 500);
- determining based on the fastest route for each of the plurality container handling vehicles (201,301,401) an optimal container handling vehicle of the plurality container handling vehicles (201,301,401) for moving to the second grid position; and
- instructing the optimal container handling vehicle to move to the second grid position. A computer program product for a control system (121) in the system of clauses 15, wherein the computer program product comprising instructions that when performed on the control system (121) performs the method according to clauses 1 - 14.

Claims

1. A method (1500) of determining a route for a container handling vehicle (201,301,401), where the route is a route among a route of at least one other container handling vehicle (201,301,401) in an automatic gridbased storage and retrieval system (10) comprising a grid system having a first direction (X) and a second direction (Y) which is perpendicular to the first direction (X), the grid system defining a plurality of grid positions ((Xi,Yj)) each being identifiable by a first coordinate (Xi) in the first direction (X) and a second coordinate (Yj) in the second direction (Y), the method for use by a control system (121) communicating with a vehicle controller in each container handling vehicle (201,301,401), the method comprising:
- receiving requests for routes (1505) for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions;
- determining a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions;
- prioritizing and selecting routes (1512) for each container handling vehicle (201,301,401), where a container handling vehicle (201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes, where for the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401); and
- controlling each container handling vehicle (201,301,401) to follow the selected routes.
2. The method according to claim 1, wherein a model (1501) of the grid system is created representing the grid system as a finite set of nonoverlapping rectangular first zones (1502) of grid positions, each first zone latitudinally extending in the first direction (X), and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction (Y), wherein the zones are positioned around grid positions (501, 601) that are not accessible by the container handling vehicle (201,301,401); wherein overlap information (1503) is determined, wherein the overlap information is indicative of one or more regions of the grid system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones; wherein grid position zone information (1504) is determined by, for each grid position ((Xi,Yj)), determining in which of the finite set of first zones and/or the finite set of second zones the grid position ((Xi,Yj)) is located; wherein the model is used to determine the route or number of possible routes (1506) for the at least two container handling vehicles
(201.301.401), from the respective first grid positions to the respective second grid positions.
3. The method according to claim 1 or claim 2, wherein the grid system is a rail system (108,500) on which the container handling vehicles operate, wherein the rail system (108,500) comprise a first set of parallel rails (no) arranged in the first direction (X) and a second set of parallel rails (111) arranged in the second direction (Y), and wherein the automatic grid-based storage and retrieval system (10) comprises a framework structure (100) including the rail system (108, 500).
4. The method according to any preceding claim, wherein for three or more container handling vehicles (201,301,401) that may have conflicting routes, the routes of the container handling vehicles (201,301,401) are ranked and prioritized according to the number of possible routes, where routes of container handling vehicles (201,301,401) having least possible routes are ranked first while routes of container handling vehicles
(201.301.401) having most possible routes are ranked and prioritized last, and selecting routes for the container handling vehicle (201,301,401) according to ranking.
5. The method according to any of claims 1 - 3, wherein for at least two container handling vehicles (201,301,401) having at least two possible routes each, routes having lowest cost are prioritized and selected.
6. The method of any of claims 1 - 5, comprising, determining, using the grid position zone information, that the route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj).
7. The method of any of claims 1 - 6, comprising, determining, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj).
8. The method of any of claims 1 - 7, comprising, determining, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones.
9. The method of any of the preceding claims, comprising, using the set of first zones, the set of second zones and the overlap information to generate a zone graph (1511) comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
10. The method of claim 9, comprising, determining, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determining the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph.
11. The method of claim 10, wherein the graph traversal and path search algorithm is an A* algorithm.
12. The method of any of claims 1 - 11, wherein representing the rail system (108, 500) as the set of first zones and the set of second zones comprises: defining the grid positions that are not accessible (1507) by the container handling vehicle (201,301,401) as blocked grid cells (501, 601) and grid cells accessible for the container handling vehicle (201,301,401) as open grid cells (502); determining a first set of non-overlapping rectangular regions (1508) of grid positions (701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715), each first region latitudinally extending in the first direction (X) and defining the largest possible rectangle of continuous open grid cells uninterrupted by at least one blocked grid cell (501, 601); determining a second set of non-overlapping rectangular regions (1509) of grid positions (716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727), each second region longitudinally extending in the second direction (Y) and defining the largest possible rectangle of continuous open grid cells uninterrupted by at least one blocked grid cell (501, 601); determining the finite set of first zones by removing (1510) any region (708, 710, 711) of the first set of regions that falls completely within a region of the second set of regions (717, 723, 726); and determining the finite set of second zones by removing (1510) any region (718, 724, 727) of the second set of regions that falls completely within a region of the first set regions (707, 709, 715).
13. The method of claim 12, wherein the step of determining the first set of regions (1508) comprises determining continuous sections of open grid cells (502) extending in the first direction (X) that are uninterrupted by a blocked grid cell (501, 601), each continuous section having a start position having a first coordinate (Xi) and a length defined by the number of open grid cells (502) uninterrupted by a blocked grid cell (501, 601); wherein the largest possible rectangle of continuous open grid cells (502) latitudinally extending in the first direction (X) uninterrupted by a blocked grid cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same first coordinate (Xi) and the same length, or a single vertical continuous section; and the step of determining the second set of regions (1509) comprises determining continuous sections of open grid cells (502) extending in the second direction (Y) that are uninterrupted by a blocked grid cell (501, 601), each continuous section having a start position having a second coordinate (Yj) and a length defined by the number of open grid cells (502) uninterrupted by a blocked grid cell (501, 601); wherein the largest possible rectangle of continuous open grid cells (502) longitudinally extending in the second direction (Y) uninterrupted by a blocked grid cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same second coordinate (Yi) and the same length, or a single horizontal continuous section.
14. The method of any of claims 1 - 13, wherein defining grid positions that are not accessible by the container handling vehicle (201,301,401) comprises: determining one or more grid positions ((Xi,Yj)) that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle (201,301,401); and identifying the one or more grid positions (601) as being not accessible by the container handling vehicle (201,301,401).
15. The method of any of claims 1 - 14, wherein the method comprises: receiving a request for a route for a plurality of container handling vehicles (201,301,401) from a plurality of first grid position to a second grid position; determining the fastest route for each of the plurality of container handling vehicles (201,301,401) from the plurality of first grid position to the second grid position using the model of the rail system (108, 500); determining based on the fastest route for each of the plurality container handling vehicles (201,301,401) an optimal container handling vehicle of the plurality container handling vehicles (201,301,401) for moving to the second grid position; and instructing the optimal container handling vehicle to move to the second grid position.
16. The method of any of claims 1 - 16, wherein the method comprises: using timing information of the container handling vehicles
(201,301,401) following routes to determine if crossings of the routes at potentially conflicting grid positions ((Xi,Yj)), are non-conflicting.
17. A system of determining a route for a container handling vehicle
(201,301,401), where the route is a route among routes of other container handling vehicles (20i,30i,40i)in an automatic grid-based storage and retrieval system (10) comprising a grid system having a first direction (X) and a second direction (Y) which is perpendicular to the first direction (X), the grid system) defining a plurality of grid positions ((Xi,Yj)) each being identifiable by a first coordinate (Xi) in the first direction (X) and a second coordinate (Yj) in the second direction (Y); a control system (121) configured to communicate with a vehicle controller in the container handling vehicles (201,301,401), wherein the control system (121) is configured to: receive a request for routes for each of at least two container handling vehicles (201,301,401) to move from respective first grid positions to respective second grid positions; determine a route or a number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions; prioritizing and selecting routes (1512) for each container handling vehicle (201,301,401), where a container handling vehicle
(201,301,401) having a lower number of possible routes is selected over a conflicting route of a container handling vehicle (201,301,401) having a higher number of possible routes to avoid conflicts between routes, where for the container handling vehicle having the higher number of possible routes and the conflicting route, the conflicting route is excluded from the possible routes, and an alternative route is selected for that container handling vehicle (201,301,401); and control each container handling vehicle (201,301,401) to follow the selected routes.
18. The system of claim 17, wherein the control system (121) is configured to create a model of the grid system by: representing the grid system as a finite set of non-overlapping rectangular first zones of grid positions, each first zone longitudinally extending in the first direction (X), and a finite set of non-overlapping rectangular second zones of grid positions, each second zone longitudinally extending in the second direction (Y), wherein the zones are positioned around grid positions (501, 601) that are not accessible by the container handling vehicle (201,301,401); determining overlap information, wherein the overlap information is indicative of one or more regions of the grid system in which there is an overlap between a zone of the finite set of first zones and a zone of the finite set of second zones; and determining grid position zone information by, for each grid position ((Xi,Yj)), determining in which of the finite set of first zones and/or the finite set of second zones the grid position ((Xi,Yj)) is located; wherein the control system is configured to use the model to determine the route or number of possible routes (1506) for the at least two container handling vehicles (201,301,401), from the respective first grid positions to the respective second grid positions.
19. The system of claim 17 or claim 18, wherein the grid system is a rail system (108,500) on which the container handling vehicles operate, wherein the rail system (108,500) comprise a first set of parallel rails (110) arranged in the first direction (X) and a second set of parallel rails (111) arranged in the second direction (Y), and wherein the automatic grid-based storage and retrieval system (10) comprises a framework structure (100) including the rail system (108, 500).
20. The system according to any of claims 17 to 19, wherein for three or more container handling vehicles (201,301,401) that may have conflicting routes, wherein the control system (121) is a configured to rank and prioritize the routes of the container handling vehicles (201,301,401) according to the number of possible routes, where routes of container handling vehicles (201,301,401) having least possible routes are ranked first while routes of container handling vehicles (201,301,401) having most possible routes are ranked and prioritized last, and where routes for the container handling vehicle (201,301,401) according to ranking are selected.
21. The system according to any of claims 17 to 20, wherein for at least two container handling vehicles (201,301,401) having at least two possible routes each, the control system (121) is configured to prioritize and select routes having lowest cost.
22. The system of any of claims 17 to 21, wherein the system is configured to determine, using the grid position zone information, that the route is a straight line between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share either the same first coordinate (Xi) or the same second coordinate (Yj).
23. The system of any of claims 17 - 22, wherein the system is configured to determine, using the grid position zone information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in the same zone and share neither the same first coordinate (Xi) nor the same second coordinate (Yj).
24. The system of any of claims 17 - 23, wherein the system, is configured to determine, using the grid position zone information and the overlap information, that the route is a single-turn Manhattan route between the first grid position and the second grid position when the first grid position and the second grid position are in different and overlapping zones.
25. The system of any of claims 17 - 24, wherein the system is configured to use the set of first zones, the set of second zones and the overlap information to generate a zone graph (1511) comprising nodes and edges, wherein the nodes represent the finite set of first zones and the finite set of second zones, and the edges represent the overlap information.
26. The system of claim 25, wherein the system is configured to determine, using the grid position zone information and the overlap information, that the first grid position and the second grid position are not in the same zone and not in overlapping zones, and determine the route between the first grid position and the second grid position using a graph traversal and path search algorithm on the zone graph.
27. The system of claim 26, wherein the graph traversal and path search algorithm is an A* algorithm.
28. The system of any of claims 17 - 27, wherein the system is configured to represent the rail system (108, 500) as the set of first zones and the set of second zones by: defining the grid positions that are not accessible (1507) by the container handling vehicle (201,301,401) as blocked grid cells (501, 601) and grid cells accessible for the container handling vehicle (201,301,401) as open cells (502); determining a first set of non-overlapping rectangular regions (1508) of grid positions (701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715), each first region longitudinally extending in the first direction (X) and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell (501, 601); determining a second set of non-overlapping rectangular regions (1509) of grid positions (716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727), each second region longitudinally extending in the second direction (Y) and defining the largest possible rectangle of continuous open cells uninterrupted by at least one blocked cell (501, 601); determining the finite set of first zones by removing (1510) any region (708, 710, 711) of the first set of regions that falls completely within a region of the second set of regions (717, 723, 726); and determining the finite set of second zones by removing (1510) any region (718, 724, 727) of the second set of regions that falls completely within a region of the first set regions (707, 709, 715).
29. The system of claim 28, wherein the determining the first set of regions (1508) comprises determining continuous sections of open cells (502) extending in the first direction (X) that are uninterrupted by a blocked cell (501, 601), each continuous section having a start position having a first coordinate (Xi) and a length defined by the number of open cells (502) uninterrupted by a blocked cell (501, 601); wherein the largest possible rectangle of continuous open cells (502) longitudinally extending in the first direction (X) uninterrupted by a blocked cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same first coordinate (Xi) and the same length, or a single vertical continuous section; and the determining the second set of regions (1509) comprises determining continuous sections of open cells (502) extending in the second direction (Y) that are uninterrupted by a blocked cell (501, 601), each continuous section having a start position having a second coordinate (Yj) and a length defined by the number of open cells (502) uninterrupted by a blocked cell (501, 601); wherein the largest possible rectangle of continuous open cells (502) longitudinally extending in the second direction (Y) uninterrupted by a blocked cell (501, 601) comprises either a number of adjacent continuous sections having a start position with the same second coordinate (Yi) and the same length, or a single horizontal continuous section.
30. The system of any of claims 17 - 29, wherein the defining grid positions that are not accessible by the container handling vehicle (201,301,401) comprises: determining one or more grid positions ((Xi,Yj)) that have at least one physical dimension that is smaller than at least one physical dimension of the container handling vehicle (201,301,401); and identifying the one or more grid positions (601) as being not accessible by the container handling vehicle (201,301,401).
31. The system of any of claims 17 - 30, wherein the system is configured to: receive a request for a route for a plurality of container handling vehicles (201,301,401) from a plurality of first grid position to a second grid position; determine the fastest route for each of the plurality of container handling vehicles (201,301,401) from the plurality of first grid position to the second grid position using the model of the rail system (108, 500); determine based on the fastest route for each of the plurality container handling vehicles (201,301,401) an optimal container handling vehicle of the plurality container handling vehicles (201,301,401) for moving to the second grid position; and instruct the optimal container handling vehicle to move to the second grid position.
32. A computer program product for a control system (121) in the system of claims 17, wherein the computer program product comprising instructions that when performed on the control system (121) performs the method according to claims 1 - 17.
PCT/EP2024/051343 2023-06-08 2024-01-22 Method, system and computer program product for determining non-conflicting routes for container handling vehicles Pending WO2024251392A1 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
NO20230663 2023-06-08
NO20230663 2023-06-08

Publications (1)

Publication Number Publication Date
WO2024251392A1 true WO2024251392A1 (en) 2024-12-12

Family

ID=93795106

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2024/051343 Pending WO2024251392A1 (en) 2023-06-08 2024-01-22 Method, system and computer program product for determining non-conflicting routes for container handling vehicles

Country Status (1)

Country Link
WO (1) WO2024251392A1 (en)

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
NO317366B1 (en) 1999-07-01 2004-10-18 Autostore As Storage system with remote controlled wagons with two wheelsets and lifting device for operation on rails arranged in cross over columns of storage units separated by vertical profile posts
WO2014075937A1 (en) 2012-11-13 2014-05-22 Jakob Hatteland Logistics As Storage system
WO2014090684A1 (en) 2012-12-10 2014-06-19 Jakob Hatteland Logistics As Robot for transporting storage bins
WO2015193278A1 (en) 2014-06-19 2015-12-23 Jakob Hatteland Logistics As Robot for transporting storage bins
WO2018146304A1 (en) 2017-02-13 2018-08-16 Autostore Technology AS Rail arrangement for a storage system
WO2019206487A1 (en) 2018-04-25 2019-10-31 Autostore Technology AS Container handling vehicle with first and second sections and lifting device motor in second section
WO2023186802A1 (en) * 2022-03-30 2023-10-05 Autostore Technology AS Method, system and computer program product for determining a route for a container handling vehicle
US11866260B2 (en) * 2020-08-26 2024-01-09 Autostore Technology AS Routing of container handling vehicles operating an automated storage system

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
NO317366B1 (en) 1999-07-01 2004-10-18 Autostore As Storage system with remote controlled wagons with two wheelsets and lifting device for operation on rails arranged in cross over columns of storage units separated by vertical profile posts
WO2014075937A1 (en) 2012-11-13 2014-05-22 Jakob Hatteland Logistics As Storage system
WO2014090684A1 (en) 2012-12-10 2014-06-19 Jakob Hatteland Logistics As Robot for transporting storage bins
WO2015193278A1 (en) 2014-06-19 2015-12-23 Jakob Hatteland Logistics As Robot for transporting storage bins
WO2018146304A1 (en) 2017-02-13 2018-08-16 Autostore Technology AS Rail arrangement for a storage system
WO2019206487A1 (en) 2018-04-25 2019-10-31 Autostore Technology AS Container handling vehicle with first and second sections and lifting device motor in second section
US11866260B2 (en) * 2020-08-26 2024-01-09 Autostore Technology AS Routing of container handling vehicles operating an automated storage system
WO2023186802A1 (en) * 2022-03-30 2023-10-05 Autostore Technology AS Method, system and computer program product for determining a route for a container handling vehicle

Similar Documents

Publication Publication Date Title
US20250216861A1 (en) Method, system and computer program product for determining a route for a container handling vehicle
US12421051B2 (en) Method, system and computer program for controlling an automated storage and retrieval system during rebuilding its physical design
EP4254123B1 (en) A method and system for autonomous controlling of movements of container handling vehicles operating in an automated storage and retrieval system
US20230222431A1 (en) Multiposition search
EP4143107B1 (en) Optimal utilizing of operational capacity of container handling vehicles assigned to interact with same port for transferring storage containers to and from an automatic storage and retrieval system
WO2024251392A1 (en) Method, system and computer program product for determining non-conflicting routes for container handling vehicles
EP4589501A1 (en) Method and system for scheduling orders in an automated storage and retrieval system
WO2024256038A1 (en) Path planning for determining routes for container handling vehicles
US20250236458A1 (en) Dynamic tuning of dig-down
KR20250129703A (en) Method, system and computer program product for moving storage containers
WO2024047063A1 (en) System and method for rearranging containers in an automated storage and retrieval system
HK40101663B (en) A method and system for autonomous controlling of movements of container handling vehicles operating in an automated storage and retrieval system
HK40101663A (en) A method and system for autonomous controlling of movements of container handling vehicles operating in an automated storage and retrieval system

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 24701620

Country of ref document: EP

Kind code of ref document: A1