Systems and methods for controlling order fulfillment using spatial batching

Patent metadata

Field	Value
Publication number	US-11760574-B2
Application number	US-202117193059-A
Country	US
Kind code	B2
Filing date	Mar 5, 2021
Priority date	Mar 5, 2021
Publication date	Sep 19, 2023
Grant date	Sep 19, 2023

Abstract

An order fulfillment system controller receives orders for different objects, generates a number of batched tasks that is less than the number of received orders, and determines a set of the orders with a total distance between them that is greater than a total distance between other sets of the orders. The controller allocates a different order from the set of order to a different batched task, and allocates each unallocated order to a selected batched task based on the distance between objects of the unallocated order and objects previously allocated to the selected batched task being less than the distance between objects of the unallocated order and objects previously allocated to other batched tasks. The controller controls different agents according to the allocation of different subsets of orders to different batched tasks.

First claim

What is claimed is:

1. A method comprising:
receiving, at a controller comprising one or more processors, a plurality of orders for different objects that are stored at various storage locations in a site;
generating, by operation of the one or more processors, a particular number of batched tasks, wherein the particular number of batched tasks is less than a number of orders in the plurality of orders;
determining, by operation of the one or more processors, a distance between objects of a particular set of orders from the plurality of orders that is greater than a distance between objects of different sets of orders from the plurality of orders, wherein each of the particular set of orders and the different sets of orders comprises a number of orders that is equal to the particular number of batched tasks;
allocating, by operation of the one or more processors, a different order from the particular set of orders to a different batched task of the particular number of batched tasks;
selecting, by operation of the one or more processors, an unallocated order from the plurality of orders, wherein the unallocated order is not within the particular set of orders;
allocating, by operation of the one or more processors, the unallocated order from to a selected batched task of the particular number of batched tasks,
wherein the unallocated order is allocated to the selected batched task based on a distance between two or more objects of the unallocated order and each object from a particular order of the particular set of orders that is previously allocated to the selected batched task,
wherein the distance between the two or more objects and each object from the particular order is less than a distance between the two or more objects and each object from other orders of the particular set of orders previously allocated to other batched tasks of the particular number of batched tasks,
wherein said allocating the unallocated order further comprises allocating the two or more objects to the selected batched task without splitting the two or more objects between different batched tasks; and

controlling, with the controller, operations of a first agent in the site according to objects from two or more orders that are allocated to a first batched task of the particular number of batched tasks, and operations of a different second agent in the site according to objects from two or more orders that are allocated to a second batched task of the particular number of batched tasks.

2. The method of claim 1 further comprising:
computing a distance between each object of the plurality of orders and every other object of the plurality of orders.

3. The method of claim 2 , wherein computing the distance further comprises:
receiving a mapping that identifies a storage location of each object from the plurality of orders in the site;
quantizing the mapping to precomputed regions; and
determining a distance between a pair of objects based on the precomputed regions separating the pair of objects.

4. The method of claim 1 ,
wherein receiving the plurality of orders comprises receiving the different objects of the plurality of orders in a first sequence; and
wherein controlling the operations of the first agent and the second agent comprises retrieving the different objects of the plurality of orders according to a second sequence that is different than the first sequence and that is defined as part of each batched task.

5. The method of claim 1 further comprising:
modifying a sequence of orders allocated to a particular batched task of the particular number of batched tasks by changing a first sequence with which unallocated orders of the plurality of orders are selected to a second sequence.

6. The method of claim 1 further comprising:
generating a data structure that stores a distance between each pair of the different objects from the plurality of orders; and
wherein allocating the unallocated order further comprises retrieving the distance between a first object of the two or more objects from the unallocated order and a second object from the particular set of orders allocated to the particular number of batched tasks by indexing the data structure with a first identifier of the first object and a second identifier of the second object.

7. The method of claim 1 ,
wherein allocating the unallocated order further comprises selecting unallocated orders from the plurality of orders in a first sequence and producing a first set of batched tasks based on said selecting of the unallocated orders in the first sequence;
the method further comprising:
selecting the unallocated orders from the plurality of orders in a second sequence that is different than the first sequence;
producing a second set of batched tasks that comprises different combinations of the unallocated orders than the first set of batched tasks;
comparing a total distance resulting from the first set of batched tasks and a total distance resulting from the second set of batched tasks; and
wherein controlling the first agent and the second agent comprises controlling the first agent and the second agent according to the first set of batched tasks in response to the total distance resulting from the first set of batched tasks being less than the total distance resulting from the second set of batched tasks, and controlling the first agent and the second agent according to the second set of batched tasks in response to the total distance resulting from the first set of batched tasks being greater than the total distance resulting from the second set of batched tasks.

8. The method of claim 1 wherein controlling the operations of the first agent and the second agent comprises:
retrieving objects for a first set of the plurality of orders with the first agent under control of the controller, and retrieving objects for a different second set of the plurality of orders with the second agent under control of the controller.

9. The method of claim 1 further comprising:
computing a distance between objects of two or more orders that are allocated to a particular batched task; and
defining a modified retrieval sequence for the objects of the two or more orders that minimizes a total distance between the objects of the two or more orders based on said computing of the distance between the objects of the two or more orders.

10. The method of claim 1 further comprising:
monitoring a state of the first agent and the second agent;
wherein said controlling comprises controlling the first agent according to two or more orders allocated to the first batched task based on the state of the first agent and the state of the second agent identifying the first agent to be closer to an object of the first batched task than the second agent.

11. The method of claim 1 , wherein said controlling comprises:
retrieving objects for a first set of the plurality of orders allocated to the first batched task with the first agent under control of the controller while simultaneously retrieving objects for a different second set of the plurality of orders allocated to the second batched task with the second agent under control of the controller.

12. The method of claim 1 further comprising:
determining a number of available agents from a plurality of agents operating in the site; and
wherein said generating comprises generating the particular number of batched tasks based on the number of available agents.

13. The method of claim 1 further comprising:
determining a total number of objects that each agent retrieves during a single tour through the site; and
wherein said generating comprises genera

Assignees

• Invia Robotics Inc

Inventors

• Voorhies Randolph Charles
• Parks Ii Daniel Frank
• Elazary Lior

Classifications

• B65G1/1371 Primary

  with data records · CPC title

• B65G1/1378 Primary

  the orders being assembled on fixed commissioning areas remote from the storage areas · CPC title

• B65G2203/0233

  Position of the article · CPC title

• B65G2209/02

  Batch order forming, e.g. several batches simultaneously · CPC title

• B65G1/0492

  with cars adapted to travel in storage aisles · CPC title