WO2024256038A1 - Path planning for determining routes for container handling vehicles - Google Patents

Path planning for determining routes for container handling vehicles Download PDF

Info

Publication number
WO2024256038A1
WO2024256038A1 PCT/EP2024/051330 EP2024051330W WO2024256038A1 WO 2024256038 A1 WO2024256038 A1 WO 2024256038A1 EP 2024051330 W EP2024051330 W EP 2024051330W WO 2024256038 A1 WO2024256038 A1 WO 2024256038A1
Authority
WO
WIPO (PCT)
Prior art keywords
grid
target area
container handling
cell
handling vehicle
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/051330
Other languages
French (fr)
Inventor
Vegard SYRE-AAKER
Torgeir LILLESKOG
Øystein MYRMO
Torgeir Woldstad SKOGEN
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
Priority to KR1020267000995A priority Critical patent/KR20260025371A/en
Priority to AU2024303605A priority patent/AU2024303605A1/en
Priority to CN202480039733.8A priority patent/CN121311840A/en
Publication of WO2024256038A1 publication Critical patent/WO2024256038A1/en
Anticipated expiration legal-status Critical
Pending legal-status Critical Current

Links

Classifications

    • 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/137—Storage devices mechanical with arrangements or automatic control means for selecting which articles are to be removed
    • B65G1/1373—Storage devices mechanical with arrangements or automatic control means for selecting which articles are to be removed for fulfilling orders in warehouses
    • B65G1/1378—Storage devices mechanical with arrangements or automatic control means for selecting which articles are to be removed for fulfilling orders in warehouses the orders being assembled on fixed commissioning areas remote from the storage areas
    • 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/644—Optimisation of travel parameters, e.g. of energy consumption, journey time or distance
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/20—Instruments for performing navigational calculations
    • G01C21/206—Instruments for performing navigational calculations specially adapted for indoor navigation
    • 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
    • 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
    • B65G2201/00—Indexing codes relating to handling devices, e.g. conveyors, characterised by the type of product or load being conveyed or handled
    • B65G2201/02—Articles
    • B65G2201/0235—Containers
    • 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 storage containers, and in particular to a method, system and computer program product for planning and handling moving of a container handling vehicle operating on a grid system of the automated storage and retrieval system for preparing the container handling vehicle to handle a storage container.
  • 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 exact destination or stop position of the vehicle body of the container handling vehicle 201, 301, 401 depends on the footprint of container handling vehicle 201, 301, 401 that is controlled.
  • the specific position of the grid cell will be the stop position of the vehicle body 201a.
  • the stop position of the vehicle body 30ia- will be any grid cell next to and overlapping with the specific grid cell such that the cantilever part that is handling a storage container 106 is directly above the specific grid cell.
  • 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.
  • 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. [0026] 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 receiving an instruction to perform a job, a container handling vehicle 201,301,401 typically moves and follows a path from its current location to a destination for delivering or retrieving a storage container 106.
  • Path planning is a central part of software controlling the container handling vehicles to perform jobs.
  • a path planning algorithm finding paths for robots is the well-known A* search algorithm, finding a path for a robot to a destination.
  • robots will have well-defined destinations. However, in some cases it is not important that a robot moves to a defined destination such as a specific grid cell, but rather to a specific area or towards a target grid cell. The reason for this may for instance be to position the robot close to an area on the grid where a job soon is expected to be requested.
  • An example of a case where a specific destination may not be defined is if a target destination is currently occupied but will be available at an unknown time in the future. Another example is if a robot currently does not have any valid job, such as handling a storage container 106. In this case, it would be smart to move the robot to an area where it is expected that a job will occur in near future. It may also be smart to distribute robots on the rail system 108 to have short distance to expected jobs. In both cases, it is not necessary to move the robot to an exact position.
  • the present solution describes a method of determining a route and moving a container handling vehicle along the route to a target area of a grid system such as the grid rail system 108.
  • the invention is defined by a method of determining a route for a container handling vehicle to a target area of a grid system, the grid system is arranged at least partially across a framework structure of an automated storage and retrieval system, a plurality of container handling vehicles are operable on the grid system to retrieve storage containers from, and deliver storage containers into storage columns arranged in rows between upright members of the framework structure, and to move the storage containers to and from one or more grid cells on the grid system corresponding to storage columns.
  • the grid system may be a grid rail system.
  • a central control system which is in communication with a local controller of each container handling vehicle: determining the target area to be two or more connected grid cells, setting a task of moving a container handling vehicle to the target area, selecting a container handling vehicle to be moved to the target area, searching for and determining an optimal route for the selected container handling vehicle to the target area, instructing the selected container handling vehicle to move along the determined route to the target area.
  • Connected grid cells are grid cells adjacent to each other, meaning that that the grid system arranged across the top of the framework structure run continuously from one grid cell to another.
  • the route determined is towards a target grid cell that is enclosed by the target area.
  • the target area may for instance comprise grid cells within defined rectangles This target area may further be restricted to comprise grid cells from which move time from the grid cells within the rectangles to the target grid cell within the rectangle is less than a set time value.
  • the determined target area comprises grid cells within a set radius.
  • the determined target area of grid cells comprises grid cells within a set rectangle.
  • the set radius defines a Manhattan distance from the container handling vehicle to the target grid cell.
  • the grid cells of the target area comprise a list of preselected grid cells fully enclosing the target grid cell.
  • the determined target area of grid cells comprises grid cells from which move time from the grid cells to the target grid cell is less than a set time value, e.g. less that 4s.
  • the determined target area of grid cells comprises grid cells within a first set radius and a second larger set radius.
  • the determined target area of grid cells comprises grid cells within a first set rectangle and a second larger set rectangle.
  • the target area of grid cells which is associated with the target grid cell further comprises grid cells from which move time or Manhattan distance from the grid cells to a target grid cell is less than a set time value
  • the invention concerns a system of determining a route for a container handling vehicle to a target area of a grid system
  • the grid system is arranged at least partially across a framework structure of an automated storage and retrieval system
  • a plurality of container handling vehicles are operable on the grid system to retrieve storage containers from, and deliver storage containers into storage columns arranged in rows between upright members of the framework structure, and to move the storage containers to and from one or more grid cells on the grid system corresponding to storage columns
  • a central control system configured to communicate with a local controller of each container handling vehicle, wherein the central control system is configured to: determine the target area to be two or more connected grid cells, set a task of moving a container handling vehicle to the target area, select a container handling vehicle to be moved to the target area, search for and determine an optimal route for the selected container handling vehicle to the target area, instruct the selected container handling vehicle to move along the determined route to the target area.
  • the system is configured to determine the route towards a target grid
  • the system is configured to for determine the target area grid cells within a set radius.
  • the system is configured to determine the target area as grid cells within a set rectangle.
  • the system is configured to set the radius by defining a Manhattan distance from the container handling vehicle to a target grid cell.
  • the system is configured to determine the target area of grid cells which is associated with the target grid cell to comprise grid cells from which move time or Manhattan distance from the grid cells to the target grid cell is less than a set time value.
  • the invention is directed to computer program product for a central control system in the system of the second aspect, wherein the computer program product comprises instructions that when performed on the central control system performs the method according to the first aspect.
  • 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 illustration of a target area within a predefined radius of a target grid cell X.
  • Fig. 6 is a schematic illustration of a target area providing a set move time to a target grid cell X.
  • Fig. 7a is a first schematic illustration of a target area defined by the location of grid cells surrounding a target grid cell X.
  • Fig. 7b is a second schematic illustration of a target area defined by the location of grid cells surrounding a target grid cell X.
  • Fig. 8 is a schematic illustration of a target area comprising predefined grid cells enclosing a target grid cell X.
  • Fig. 9 is a schematic illustration of a target area comprising predefined grid cells surrounding a target grid cell X within a first and second predefined radius of the target grid cell X.
  • FIG. 10 is a flowchart of a method according to the present invention for determining a route for a container handling vehicle to a target area of a grid system.
  • a method of determining a route for a container handling vehicle to a target area of a grid system or grid rail system comprises determining the target area to be two or more connected grid cells, setting a task of moving a container handling vehicle to the target area, selecting a container handling vehicle to be moved to the target area, searching for and determining an optimal route for the selected container handling vehicle to the target area, instructing the selected container handling vehicle to move along the determined route to the target area.
  • 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.
  • the present solution describes a method of determining a route and moving a container handling vehicle along the route to a target area of a grid rail system 108 without having defined target grid cell.
  • the algorithm will terminate when a target grid cell is reached.
  • the path planning algorithm may terminate whenever a container handling vehicle reaches a target area. When within the target area, the container handling vehicle may stop and wait for further instruction or continue to a target grid cell within the target area.
  • FIG. 5 - 9 The figures illustrate a top view of different automated storage and retrieval systems 1 comprising grid cells.
  • Grid rail systems 108 are arranged across framework structures 100 of the different automated storage and retrieval systems 1.
  • Each grid cell has unique coordinates.
  • a target grid X is used for illustrative purposes. The solution will however also function by only defining a set of grid cells within a target area as defined in the independent claims.
  • Fig. 5 is a schematic illustration of a target area within a predefined set radius of a target grid cell marked with an X.
  • the grid cells marked with 2 and 3 indicate ports for transferring storage containers 106.
  • the set target area of grid cells associated with the target grid cell X comprises grid cells fully within the set radius of the target grid cell X as well as enclosing the target grid cell X.
  • a container handling vehicle 201, 301, 401 receives a task from a central control system 121 which is in communication with a local controller of the container handling vehicle 201, 301, 401.
  • the task determined by the central control system 121 maybe to move along a route towards a target area of grid cells which is associated with the target grid cell X. In Fig. 5 this means any grid cell having a Manhattan distance of 2 from the target grid cell X at coordinates (36,27).
  • a route towards the target grid cell X is determined, e.g. by applying A* search algorithm.
  • the A* search algorithm is applied to the target grid cell X to determine a route from the location of the container handling vehicle to the target grid cell X.
  • the container handling vehicle then moves along the route.
  • position data of the container handling vehicle 201, 301, 401 is established, and the container handling vehicle 201, 301, 401 is instructed to stop and wait for further instructions or to continue to a target grid cell as planned once it is within the target area of grid cells.
  • the container handling vehicle 201, 301, 401 will then be in a good position to perform a task at the target grid cell when instructed to do so.
  • a route is determined towards another grid cell in the target area, other than the target cell X.
  • the target area is determined as above. Once the target area has been determined, an algorithm is used to determine a route to a grid cell in the target area.
  • the route is determined as follows.
  • the system determines which grid cell, of the plurality of grid cells in the target area, is closest to the selected container handling vehicle. Once the closest cell is determined, the A* algorithm is used to determine the first cell on the route. This is done by determining the best first cell on a route towards the identified closest cell. This is done by considering each of the available cells. Once the first cell on the route (the first route cell) is determined, the system then finds the closest cell in the target area to the first route cell. That is, the system determines which grid cell, of the plurality of grid cells in the target area, is closest to the first route cell. This is the updated closest cell. Once the updated closest cell is determined, the A* algorithm is used to determine the next cell on the route.
  • the process is then repeated from the second route cell: the closest cell in the target area to the second route cell is determined (updated closest cell), and an algorithm is used to find the best next cell on the route to reach the updated closest cell. This process is repeated until it is determined that the closest cell in the target area to the n th route cell is the n th route cell, indicating that the route has reached the grid area.
  • route cell For each cell on the route (‘route cell’), the system calculates an updated closest cell in the target area, and determines the next route cell by determining next cell on a route towards the updated closest cell. The process repeats for each route cell until the route reaches the target area.
  • Fig. 6 is a schematic illustration of another embodiment showing a target area providing a set move time to a target grid cell X.
  • the target area comprises grid cells providing least move time to a target grid cell X. This is like Manhattan distance, except that the radius would be the time around the target grid cell X. This option would minimize/ define the time from the outer radius to the target grid cell X.
  • the figure shows the least move time with radius of ⁇ 4 seconds from the target grid cell X.
  • Fig. 7a is a first schematic illustration of a target area defined by the location of grid cells surrounding a target grid cell X.
  • the target may be a port which in this example is located at coordinates (34, 21).
  • Using the location of grid cells surrounding a target grid cell X may be used if the grid layout is complex.
  • Fig. 7b is an example of this, showing a second schematic illustration of a target area defined by the location of grid cells comprising a target grid cell X.
  • the target grid cell X is close to an edge.
  • a distance radius or move time radius, as illustrated in fig. 5 and 6, could accept destinations on the other side of the blocked cells which is not feasible.
  • Ta address this problem, a combination of least move time radius and Manhattan distance, ref. figs. 5 and 6, and grid cells at defined locations, ref. figs. 7a and 7b, is another.
  • a target area would need to be both within the radius and at one of grid cells at defined locations to be valid.
  • the grid cells that are covered by both the radius and grid cells at defined location of should fully surround the target.
  • the radius defines how close to a target grid cell the A* search algorithm should terminate, and the grid cells at defined locations defines oddities on the grid and grid cells that should be avoided.
  • FIG. 8 is a schematic illustration of a target area comprising predefined grid cells enclosing a target grid cell X.
  • any of the predefined grid cells will be the target area where a container handling vehicle 201, 301, 401 will stop or respond to further instructions from the central control system 121 for performing a job at target grid cell X.
  • FIG. 9 is a schematic illustration of a target area comprising predefined grid cells surrounding target grid cell X within a first predefined radius and second larger predefined radius of the target grid cell X.
  • This embodiment addresses scenarios where a container handling vehicle 201, 301, 401 must move from a current stop position leaving the target area within the first predefined radius, for instance to let another container handling vehicle 201, 301, 401 pass. In most cases this would be unproblematic, as the container handling vehicle 201, 301, 401 would be close enough to a target grid cell.
  • the solution is to define a second larger radius from the target grid cell X which is used as a hysteresis. If the robot is located within the second radius at the start of a path planning algorithm, the path planning algorithm can still use the target grid cell as a destination without moving the robot into the first radius.
  • a container handling vehicle 201, 301, 401 For controlling a container handling vehicle 201, 301, 401, different commands are transmitted from the central control system 121 such as PUT, GET and MOVE.
  • PUT For placing a storage container 106 in a dedicated drop-off port column, for instance a port, the PUT command is used.
  • GET command For retrieving a storage container 106 from a pick-up column, the GET command is used.
  • the MOVE command is used for moving a container handling vehicle 201,301,401 to a target grid cell.
  • the different embodiments of the method described above may be used in a scenario where a container handling vehicle 201,301,401 received a PUT or GET command but cannot reach a target within a time limit. The command can then be converted to a MOVE command, i.e. move to a target area.
  • the container handling vehicle 201,301,401 will then be close to a drop-off or pick-up column where a job is soon expected to
  • a target grid cell may not necessarily be one specific grid cell.
  • the target grid cell is any grid cell within a set target area that is closest to current position of the selected container handling vehicle. This will then be the target grid cell for the A* search algorithm.
  • FIG. 10 is a flowchart of a method according to the present invention of determining a route 500 for a container handling vehicle 201, 301, 401 to a target area of a grid rail system 108 comprising grid cells.
  • Steps 510, 520, 530 shown in the figure can be performed in any order.
  • the first step of the method is to set determine a target area 510 comprising two or more grid cells.
  • the grid cells within a target area may for instance be a set of twelve grid cell enclosing a target grid cell.
  • the next step 520 is setting a task of a robot to move to the target area.
  • the target area may typically comprise grid cells enclosing a port where a storage container 106 is placed or retrieved.
  • the destination for a search algorithm may be any grid cell within the target area that currently is closest to the position of the container handling vehicle 201, 301, 401, or it maybe a specific target grid cell within the target area, e.g. a port.
  • the next step 530 is to select a container handling vehicle 201, 301, 401 to move to the target area.
  • step 540 an optimal route for the container handling vehicle 201, 301, 401 to the target area, or target grid cell within the target area, is searched for and determined.
  • the selected container handling vehicle 201, 301, 401 is instructed to move along the determined route 550 to the target area. Due to traffic of other container handling vehicles 201, 301, 401, the optimal route for the selected container handling vehicle 201, 301, 401 is typically changed several times before reaching a target area. [0095]
  • the present solution allows more flexible target destinations and routing to areas of the grid system having high activity and where for instance jobs are expected to be requested. By positioning container handling vehicles close to areas on the grid system where jobs are expected to be requested, fewer conflicts between routes for several container handling vehicles are expected, which in turn will give more optimal routes since the container handling vehicles need to travel less distance to do a job. Another advantage of the described solution is low computational overhead compared to the standard A* search algorithm.

Landscapes

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

Abstract

A method, system and computer program product of determining a route for a container handling vehicle (201, 301, 401) to a target area of a grid system such as a grid rail system (108). The method comprises determining the target area to be two or more connected grid cells (510), setting a task of moving a container handling vehicle to the target area (520), selecting a container handling vehicle to be moved to the target area (530), searching for and determining an optimal route for the selected container handling vehicle to the target area (540), instructing the selected container handling vehicle to move along the determined route to the target area (550).

Description

PATH PLANNING FOR DETERMINING 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 storage containers, and in particular to a method, system and computer program product for planning and handling moving of a container handling vehicle operating on a grid system of the automated storage and retrieval system for preparing the container handling vehicle to handle a storage container.
BACKGROUND
[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=i , 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] When a container handling vehicle 201, 301, 401 is requested to handle a storage container 106 at a specific grid cell, the exact destination or stop position of the vehicle body of the container handling vehicle 201, 301, 401 depends on the footprint of container handling vehicle 201, 301, 401 that is controlled. For a cavity container handling vehicle 201 shown in Fig. 2, the specific position of the grid cell will be the stop position of the vehicle body 201a. For a cantilever container handling vehicle 301 shown in figure 3, the stop position of the vehicle body 30ia-will be any grid cell next to and overlapping with the specific grid cell such that the cantilever part that is handling a storage container 106 is directly above the specific grid cell.
[0015] 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.
[0016] 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.
[0017] 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.
[0018] 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.
[0019] 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.
[0020] A conveyor system comprising conveyors is normally employed to transport the storage containers between the port columns 119,120 and the access station.
[0021] 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.
[0022] 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.
[0023] 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.
[0024] 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.
[0025] 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. [0026] 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 receiving an instruction to perform a job, a container handling vehicle 201,301,401 typically moves and follows a path from its current location to a destination for delivering or retrieving a storage container 106.
[0027] Path planning is a central part of software controlling the container handling vehicles to perform jobs. A path planning algorithm finding paths for robots, is the well-known A* search algorithm, finding a path for a robot to a destination.
[0028] In most situations, robots will have well-defined destinations. However, in some cases it is not important that a robot moves to a defined destination such as a specific grid cell, but rather to a specific area or towards a target grid cell. The reason for this may for instance be to position the robot close to an area on the grid where a job soon is expected to be requested.
[0029] An example of a case where a specific destination may not be defined is if a target destination is currently occupied but will be available at an unknown time in the future. Another example is if a robot currently does not have any valid job, such as handling a storage container 106. In this case, it would be smart to move the robot to an area where it is expected that a job will occur in near future. It may also be smart to distribute robots on the rail system 108 to have short distance to expected jobs. In both cases, it is not necessary to move the robot to an exact position.
[0030] The A* search algorithm and other similar algorithms do not address this since the algorithm works when a robot has a defined end goal, such as a defined target grid cell.
[0031] The present solution describes a method of determining a route and moving a container handling vehicle along the route to a target area of a grid system such as the grid rail system 108.
SUMMARY OF THE INVENTION
[0032] 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. [0033] The present invention is set forth and characterized in the independent claims, while the dependent claims describe other characteristics of the invention.
[0034] More specifically, and in a first aspect, the invention is defined by a method of determining a route for a container handling vehicle to a target area of a grid system, the grid system is arranged at least partially across a framework structure of an automated storage and retrieval system, a plurality of container handling vehicles are operable on the grid system to retrieve storage containers from, and deliver storage containers into storage columns arranged in rows between upright members of the framework structure, and to move the storage containers to and from one or more grid cells on the grid system corresponding to storage columns. The grid system may be a grid rail system.
[0035] The following steps are performed by a central control system which is in communication with a local controller of each container handling vehicle: determining the target area to be two or more connected grid cells, setting a task of moving a container handling vehicle to the target area, selecting a container handling vehicle to be moved to the target area, searching for and determining an optimal route for the selected container handling vehicle to the target area, instructing the selected container handling vehicle to move along the determined route to the target area.
[0036] Connected grid cells are grid cells adjacent to each other, meaning that that the grid system arranged across the top of the framework structure run continuously from one grid cell to another.
[0037] According to one embodiment of the invention, the route determined is towards a target grid cell that is enclosed by the target area. The target area may for instance comprise grid cells within defined rectangles This target area may further be restricted to comprise grid cells from which move time from the grid cells within the rectangles to the target grid cell within the rectangle is less than a set time value.
[0038] According to one embodiment of the invention, the determined target area comprises grid cells within a set radius.
[0039] According to another embodiment of the invention, the determined target area of grid cells comprises grid cells within a set rectangle. [0040] In one embodiment, the set radius defines a Manhattan distance from the container handling vehicle to the target grid cell.
[0041] In one embodiment, the grid cells of the target area comprise a list of preselected grid cells fully enclosing the target grid cell.
[0042] According to another embodiment of the invention, the determined target area of grid cells comprises grid cells from which move time from the grid cells to the target grid cell is less than a set time value, e.g. less that 4s.
[0043] According to one embodiment, the determined target area of grid cells comprises grid cells within a first set radius and a second larger set radius.
[0044] According to one embodiment, the determined target area of grid cells comprises grid cells within a first set rectangle and a second larger set rectangle.
[0045] According to one embodiment, the target area of grid cells which is associated with the target grid cell further comprises grid cells from which move time or Manhattan distance from the grid cells to a target grid cell is less than a set time value
[0046] In a second aspect, the invention concerns a system of determining a route for a container handling vehicle to a target area of a grid system, the grid system is arranged at least partially across a framework structure of an automated storage and retrieval system, a plurality of container handling vehicles are operable on the grid system to retrieve storage containers from, and deliver storage containers into storage columns arranged in rows between upright members of the framework structure, and to move the storage containers to and from one or more grid cells on the grid system corresponding to storage columns, a central control system configured to communicate with a local controller of each container handling vehicle, wherein the central control system is configured to: determine the target area to be two or more connected grid cells, set a task of moving a container handling vehicle to the target area, select a container handling vehicle to be moved to the target area, search for and determine an optimal route for the selected container handling vehicle to the target area, instruct the selected container handling vehicle to move along the determined route to the target area. [0047] According to one embodiment, the system is configured to determine the route towards a target grid cell that is enclosed by the target area.
[0048] According to one embodiment, the system is configured to for determine the target area grid cells within a set radius.
[0049] According to another embodiment, the system is configured to determine the target area as grid cells within a set rectangle.
[0050] In one embodiment, the system is configured to set the radius by defining a Manhattan distance from the container handling vehicle to a target grid cell.
[0051] According to one embodiment, the system is configured to determine the target area of grid cells which is associated with the target grid cell to comprise grid cells from which move time or Manhattan distance from the grid cells to the target grid cell is less than a set time value.
[0052] In a third aspect, the invention is directed to computer program product for a central control system in the system of the second aspect, wherein the computer program product comprises instructions that when performed on the central control system performs the method according to the first aspect.
BRIEF DESCRIPTION OF THE DRAWINGS
[0053] 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:
[0054] Fig. 1 is a perspective view of a framework structure of a prior art automated storage and retrieval system.
[0055] Fig. 2 is a perspective view of a prior art container handling vehicle having an internally arranged cavity for carrying storage containers therein.
[0056] Fig. 3 is a perspective view of a prior art container handling vehicle having a cantilever for carrying storage containers underneath.
[0057] 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. [0058] Fig. 5 is a schematic illustration of a target area within a predefined radius of a target grid cell X.
[0059] Fig. 6 is a schematic illustration of a target area providing a set move time to a target grid cell X.
[0060] Fig. 7a is a first schematic illustration of a target area defined by the location of grid cells surrounding a target grid cell X.
[0061] Fig. 7b is a second schematic illustration of a target area defined by the location of grid cells surrounding a target grid cell X.
[0062] Fig. 8 is a schematic illustration of a target area comprising predefined grid cells enclosing a target grid cell X.
[0063] Fig. 9 is a schematic illustration of a target area comprising predefined grid cells surrounding a target grid cell X within a first and second predefined radius of the target grid cell X.
[0064] Fig. 10 is a flowchart of a method according to the present invention for determining a route for a container handling vehicle to a target area of a grid system.
DETAILED DESCRIPTION
[0065] In overview, a method of determining a route for a container handling vehicle to a target area of a grid system or grid rail system is provided. The method comprises determining the target area to be two or more connected grid cells, setting a task of moving a container handling vehicle to the target area, selecting a container handling vehicle to be moved to the target area, searching for and determining an optimal route for the selected container handling vehicle to the target area, instructing the selected container handling vehicle to move along the determined route to the target area.
[0066] 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.
[0067] 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.
[0068] 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.
[0069] 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.
[0070] As described in the background section above the present solution describes a method of determining a route and moving a container handling vehicle along the route to a target area of a grid rail system 108 without having defined target grid cell.
[0071] As mentioned, in a typical path planning algorithm, such as A*, the algorithm will terminate when a target grid cell is reached. However, according to the method described herein, the path planning algorithm may terminate whenever a container handling vehicle reaches a target area. When within the target area, the container handling vehicle may stop and wait for further instruction or continue to a target grid cell within the target area.
[0072] The method will now be explained by referring to several embodiments as illustrated in Figs. 5 - 9. The figures illustrate a top view of different automated storage and retrieval systems 1 comprising grid cells. Grid rail systems 108 are arranged across framework structures 100 of the different automated storage and retrieval systems 1. Each grid cell has unique coordinates. In the figures, a target grid X is used for illustrative purposes. The solution will however also function by only defining a set of grid cells within a target area as defined in the independent claims.
[0073] Fig. 5 is a schematic illustration of a target area within a predefined set radius of a target grid cell marked with an X. The grid cells marked with 2 and 3 indicate ports for transferring storage containers 106. The set target area of grid cells associated with the target grid cell X comprises grid cells fully within the set radius of the target grid cell X as well as enclosing the target grid cell X. In the figure, the target area is set with a radius having an acceptance distance of 2, i.e. Manhattan distance. This means that a container handling vehicle will reach the target grid cell X having coordinates x=36 and y=27 from any direction by moving at most along 2 grid cells.
[0074] A container handling vehicle 201, 301, 401 receives a task from a central control system 121 which is in communication with a local controller of the container handling vehicle 201, 301, 401. The task determined by the central control system 121 maybe to move along a route towards a target area of grid cells which is associated with the target grid cell X. In Fig. 5 this means any grid cell having a Manhattan distance of 2 from the target grid cell X at coordinates (36,27).
[0075] A route towards the target grid cell X is determined, e.g. by applying A* search algorithm. In some implementations, the A* search algorithm is applied to the target grid cell X to determine a route from the location of the container handling vehicle to the target grid cell X. The container handling vehicle then moves along the route. When moving along the route, position data of the container handling vehicle 201, 301, 401 is established, and the container handling vehicle 201, 301, 401 is instructed to stop and wait for further instructions or to continue to a target grid cell as planned once it is within the target area of grid cells. The container handling vehicle 201, 301, 401 will then be in a good position to perform a task at the target grid cell when instructed to do so.
[0076] In other implementations, a route is determined towards another grid cell in the target area, other than the target cell X. In this implementation, the target area is determined as above. Once the target area has been determined, an algorithm is used to determine a route to a grid cell in the target area.
[0077] The route is determined as follows. The system determines which grid cell, of the plurality of grid cells in the target area, is closest to the selected container handling vehicle. Once the closest cell is determined, the A* algorithm is used to determine the first cell on the route. This is done by determining the best first cell on a route towards the identified closest cell. This is done by considering each of the available cells. Once the first cell on the route (the first route cell) is determined, the system then finds the closest cell in the target area to the first route cell. That is, the system determines which grid cell, of the plurality of grid cells in the target area, is closest to the first route cell. This is the updated closest cell. Once the updated closest cell is determined, the A* algorithm is used to determine the next cell on the route. This is done by determining the best next cell on a route towards the updated closest cell. This next cell is the second route cell. The process is then repeated from the second route cell: the closest cell in the target area to the second route cell is determined (updated closest cell), and an algorithm is used to find the best next cell on the route to reach the updated closest cell. This process is repeated until it is determined that the closest cell in the target area to the nth route cell is the nth route cell, indicating that the route has reached the grid area.
[0078] There is disclosed a method for determining a route to a grid cell in the target area. For each cell on the route (‘route cell’), the system calculates an updated closest cell in the target area, and determines the next route cell by determining next cell on a route towards the updated closest cell. The process repeats for each route cell until the route reaches the target area.
[0079] Fig. 6 is a schematic illustration of another embodiment showing a target area providing a set move time to a target grid cell X. In this embodiment, the target area comprises grid cells providing least move time to a target grid cell X. This is like Manhattan distance, except that the radius would be the time around the target grid cell X. This option would minimize/ define the time from the outer radius to the target grid cell X. The figure shows the least move time with radius of ~4 seconds from the target grid cell X.
[0080] Fig. 7a is a first schematic illustration of a target area defined by the location of grid cells surrounding a target grid cell X. The target may be a port which in this example is located at coordinates (34, 21).
[0081] Using the location of grid cells surrounding a target grid cell X may be used if the grid layout is complex. Fig. 7b is an example of this, showing a second schematic illustration of a target area defined by the location of grid cells comprising a target grid cell X. Here, the the target grid cell X is close to an edge. A distance radius or move time radius, as illustrated in fig. 5 and 6, could accept destinations on the other side of the blocked cells which is not feasible.
[0082] Ta address this problem, a combination of least move time radius and Manhattan distance, ref. figs. 5 and 6, and grid cells at defined locations, ref. figs. 7a and 7b, is another. In this scenario, a target area would need to be both within the radius and at one of grid cells at defined locations to be valid. The grid cells that are covered by both the radius and grid cells at defined location of should fully surround the target. In this embodiment, the radius defines how close to a target grid cell the A* search algorithm should terminate, and the grid cells at defined locations defines oddities on the grid and grid cells that should be avoided.
[0083] Fig. 8 is a schematic illustration of a target area comprising predefined grid cells enclosing a target grid cell X. In this embodiment, any of the predefined grid cells will be the target area where a container handling vehicle 201, 301, 401 will stop or respond to further instructions from the central control system 121 for performing a job at target grid cell X.
[0084] Fig. 9 is a schematic illustration of a target area comprising predefined grid cells surrounding target grid cell X within a first predefined radius and second larger predefined radius of the target grid cell X. This embodiment addresses scenarios where a container handling vehicle 201, 301, 401 must move from a current stop position leaving the target area within the first predefined radius, for instance to let another container handling vehicle 201, 301, 401 pass. In most cases this would be unproblematic, as the container handling vehicle 201, 301, 401 would be close enough to a target grid cell.
However, if it should propose a problem, the solution is to define a second larger radius from the target grid cell X which is used as a hysteresis. If the robot is located within the second radius at the start of a path planning algorithm, the path planning algorithm can still use the target grid cell as a destination without moving the robot into the first radius.
[0085] It is a prerequisite that the shape/grid cells/radius chosen to fully enclose or surround a target grid cell. If not, it would be possible for the A* search algorithm to find a path to the target without visiting any of the grid cells around.
[0086] For controlling a container handling vehicle 201, 301, 401, different commands are transmitted from the central control system 121 such as PUT, GET and MOVE. For placing a storage container 106 in a dedicated drop-off port column, for instance a port, the PUT command is used. For retrieving a storage container 106 from a pick-up column, the GET command is used. For moving a container handling vehicle 201,301,401 to a target grid cell, the MOVE command is used. [0087] The different embodiments of the method described above may be used in a scenario where a container handling vehicle 201,301,401 received a PUT or GET command but cannot reach a target within a time limit. The command can then be converted to a MOVE command, i.e. move to a target area. The container handling vehicle 201,301,401 will then be close to a drop-off or pick-up column where a job is soon expected to be requested.
[0088] A target grid cell may not necessarily be one specific grid cell. According to one embodiment, the target grid cell is any grid cell within a set target area that is closest to current position of the selected container handling vehicle. This will then be the target grid cell for the A* search algorithm.
[0089] Fig. 10 is a flowchart of a method according to the present invention of determining a route 500 for a container handling vehicle 201, 301, 401 to a target area of a grid rail system 108 comprising grid cells.
[0090] Steps 510, 520, 530 shown in the figure can be performed in any order. Typically, the first step of the method is to set determine a target area 510 comprising two or more grid cells. The grid cells within a target area may for instance be a set of twelve grid cell enclosing a target grid cell.
[0091] The next step 520 is setting a task of a robot to move to the target area. The target area may typically comprise grid cells enclosing a port where a storage container 106 is placed or retrieved. The destination for a search algorithm may be any grid cell within the target area that currently is closest to the position of the container handling vehicle 201, 301, 401, or it maybe a specific target grid cell within the target area, e.g. a port.
[0092] The next step 530 is to select a container handling vehicle 201, 301, 401 to move to the target area.
[0093] In step 540, an optimal route for the container handling vehicle 201, 301, 401 to the target area, or target grid cell within the target area, is searched for and determined.
[0094] The selected container handling vehicle 201, 301, 401 is instructed to move along the determined route 550 to the target area. Due to traffic of other container handling vehicles 201, 301, 401, the optimal route for the selected container handling vehicle 201, 301, 401 is typically changed several times before reaching a target area. [0095] The present solution allows more flexible target destinations and routing to areas of the grid system having high activity and where for instance jobs are expected to be requested. By positioning container handling vehicles close to areas on the grid system where jobs are expected to be requested, fewer conflicts between routes for several container handling vehicles are expected, which in turn will give more optimal routes since the container handling vehicles need to travel less distance to do a job. Another advantage of the described solution is low computational overhead compared to the standard A* search algorithm.
LIST OF PRIOR ART REFERENCE NUMBERS (FIGS. 1-4);
Figure imgf000020_0001

Claims

1. A method of determining a route (500) for a container handling vehicle (201, 301, 401) to a target area of a grid system (108), the grid system (108) is arranged at least partially across a framework structure (100) of an automated storage and retrieval system (1), a plurality of container handling vehicles (201,301, 401) are operable on the grid system (108) to retrieve storage containers (106) from, and deliver storage containers (106) into storage columns (105) arranged in rows between upright members (102) of the framework structure (100), and to move the storage containers (106) to and from one or more grid cells on the grid system (108) corresponding to storage columns, wherein the following steps are performed by a central control system (121) which is in communication with a local controller of each container handling vehicle (201, 301, 401):
- determining the target area to be two or more connected grid cells (510),
- setting a task of moving a container handling vehicle (201, 301, 401) to the target area (520),
- selecting a container handling vehicle (201, 301, 401) to be moved to the target area (530),
- searching for and determining an optimal route for the selected container handling vehicle (201, 301, 401) to the target area (540),
- instructing the selected container handling vehicle (201, 301, 401) to move along the determined route to the target area (550).
2. The method of claim 1, wherein the grid system (108) is a grid rail system (108).
3. The method of claim 1 or claim 2, wherein the route determined is towards a target grid cell that is enclosed by the target area.
4. The method of claim 1 or claim 2, wherein determining an optimal route for the selected container handling vehicle to the target area comprises: calculating which grid cell, of the plurality of grid cells in the target area, is closest to the starting cell of the selected container handling vehicle; determining the next cell on the optimal route by determining the next cell on a route towards the identified closest cell; and for each subsequent cell on the optimal route: calculating an updated closest grid cell in the target area; and determining the next cell on the optimal route by determining the next cell on a route towards the updated closest cell.
5. The method of any preceding claim, wherein the determined target area of grid cells comprises grid cells within a set radius.
6. The method of any of claims 1 to 4, wherein the determined target area of grid cells comprises grid cells within a set rectangle.
7. The method of claim 5, wherein the set radius defines a Manhattan distance from the container handling vehicle (201, 301, 401) to a target grid cell.
8. The method of any preceding claim, wherein the grid cells comprise a list of preselected connected grid cells.
9. The method of claim 3, wherein the determined target area of grid cells comprises grid cells from which move time from the grid cells to the target grid cell is less than a set time value.
10. The method of claim 1, wherein the determined target area of grid cells comprises grid cells within a first set radius and a second larger set radius.
11. The method of claim 1, wherein the determined target area of grid cells comprises grid cells within a first set rectangle and a second larger set rectangle.
12. The method of claim 3, wherein the target area of grid cells further comprises grid cells from which move time or Manhattan distance from the grid cells to the target grid cell is less than a set time value.
13. A system of determining a route for a container handling vehicle (201, 301, 401) to a target area of a grid system (108), the rail system (108) is arranged at least partially across a framework structure (100) of an automated storage and retrieval system (i), a plurality of container handling vehicles (201,301, 401) are operable on the grid system (108) to retrieve storage containers (106) from, and deliver storage containers (106) into storage columns (105) arranged in rows between upright members (102) of the framework structure (100), and to move the storage containers (106) to and from one or more grid cells on the grid system (108) corresponding to storage columns, a central control system (121) configured to communicate with a local controller of each container handling vehicle (201, 301, 401), wherein the central control system (121) is configured to:
- determine the target area to be two or more connected grid cells (510),
- set a task of moving a container handling vehicle (201, 301, 401) to the target area (520),
- select a container handling vehicle (201, 301, 401) to be moved to the target area (530),
- search for and determine an optimal route for the selected container handling vehicle (201, 301, 401) to the target area (540),
- instruct the selected container handling vehicle (201, 301, 401) to move along the determined route to the target area (550).
14. The system of claim 13, wherein the grid system (108) is a grid rail system (108).
15. The system of claim 13 or claim 14, wherein the central control system (121) is configured to determine the route towards a target grid cell that is enclosed by the target area.
16. The system of claim 13 or claim 14, wherein the central control system (121) is configured to determine an optimal route for the selected container handling vehicle to the target area by: calculating which grid cell, of the plurality of grid cells in the target area, is closest to the starting cell of the selected container handling vehicle; determining the next cell on the optimal route by determining the next cell on a route towards the identified closest cell; and for each subsequent cell on the optimal route: calculating an updated closest grid cell in the target area; and determining the next cell on the optimal route by determining the next cell on a route towards the updated closest cell.
17. to determine the optimal route from the selected container handling vehicle towards the closest grid cell in the grid area.
18. The system of any of claims 13 to 16, wherein the central control system (121) is configured to determine the target as grid cells within a set radius.
19. The system of any of claims 13 to 16, wherein the central control system (121) is configured to determine the target area as grid cells within a set rectangle.
20. The system of claim 17, wherein the central control system (121) is configured to set the radius by defining a Manhattan distance from the container handling vehicle (201, 301, 401) to a target grid cell.
21. The system according of claim 15, wherein the central control system (121) is configured to determine the target area of grid cells which is associated with the target grid cell to be grid cells from which move time or Manhattan distance from the grid cells to the target grid cell is less than a set time value.
22. A computer program product for a central control system (121) of the system of any of claims 13 to 20, wherein the computer program product comprises instructions that when performed on the central control system (121) performs the method of any of claims 1 to 12.
PCT/EP2024/051330 2023-06-15 2024-01-22 Path planning for determining routes for container handling vehicles Pending WO2024256038A1 (en)

Priority Applications (3)

Application Number Priority Date Filing Date Title
KR1020267000995A KR20260025371A (en) 2023-06-15 2024-01-22 Route planning to determine routes for container handling carriers
AU2024303605A AU2024303605A1 (en) 2023-06-15 2024-01-22 Path planning for determining routes for container handling vehicles
CN202480039733.8A CN121311840A (en) 2023-06-15 2024-01-22 Path planning for determining the routes of container handling vehicles

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
NO20230693 2023-06-15
NO20230693 2023-06-15

Publications (1)

Publication Number Publication Date
WO2024256038A1 true WO2024256038A1 (en) 2024-12-19

Family

ID=93851378

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2024/051330 Pending WO2024256038A1 (en) 2023-06-15 2024-01-22 Path planning for determining routes for container handling vehicles

Country Status (4)

Country Link
KR (1) KR20260025371A (en)
CN (1) CN121311840A (en)
AU (1) AU2024303605A1 (en)
WO (1) WO2024256038A1 (en)

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
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

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
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

Also Published As

Publication number Publication date
KR20260025371A (en) 2026-02-24
CN121311840A (en) 2026-01-09
AU2024303605A1 (en) 2026-01-22

Similar Documents

Publication Publication Date Title
US20230021155A1 (en) Picking system, storage system comprising a picking system and method of picking
CN114402269A (en) Method and system for automatically controlling movement of container handling vehicles operating in an automated storage and retrieval system
US20250216861A1 (en) Method, system and computer program product for determining a route for a container handling vehicle
EP4284734A1 (en) Controlling storage locations of products stored in storage containers in an automated storage and retrieval system
EP4172892A1 (en) Multiposition search
US20250326582A1 (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
WO2024256038A1 (en) Path planning for determining routes for container handling vehicles
US12596985B2 (en) Multiposition search
EP4589501A1 (en) Method and system for scheduling orders in an automated storage and retrieval system
NO20221406A1 (en) Method, system and computer program product for moving a storage container
AU2024323504A1 (en) Charging container handling vehicles operating on an automated storage and retrieval system
WO2024251392A1 (en) Method, system and computer program product for determining non-conflicting routes for container handling vehicles
WO2025077992A1 (en) Method, system and computer readable storage medium of controlling movement of cantilever container handling vehicles
WO2024133494A1 (en) Robotic picking and conveyor system
WO2024245936A1 (en) Robotic picking and conveyor on top of grid
HK40064819A (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: 24701406

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: AU2024303605

Country of ref document: AU

ENP Entry into the national phase

Ref document number: 1020267000995

Country of ref document: KR

Free format text: ST27 STATUS EVENT CODE: A-0-1-A10-A15-NAP-PA0105 (AS PROVIDED BY THE NATIONAL OFFICE)

WWE Wipo information: entry into national phase

Ref document number: 1020267000995

Country of ref document: KR

WWE Wipo information: entry into national phase

Ref document number: 2024701406

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2024701406

Country of ref document: EP

Effective date: 20260115

ENP Entry into the national phase

Ref document number: 2024303605

Country of ref document: AU

Date of ref document: 20240122

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 2024701406

Country of ref document: EP

Effective date: 20260115

ENP Entry into the national phase

Ref document number: 2024701406

Country of ref document: EP

Effective date: 20260115

ENP Entry into the national phase

Ref document number: 2024701406

Country of ref document: EP

Effective date: 20260115

WWP Wipo information: published in national office

Ref document number: 1020267000995

Country of ref document: KR