Techniques for contention resolution for mobile drive units

• US 10,209,711 B1
• Filed: 09/28/2016
• Issued: 02/19/2019
• Est. Priority Date: 09/28/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brazeau, Jeremiah David
• Primary Examiner(s): Shaawat, Mussa A
• Assistant Examiner(s): Kerrigan, Michael V
• Application Number:
  US15/279,264
• Time in Patent Office: 874 Days
• Field of Search: None
• CPC Class Codes: B65G 1/10 with relatively movable racks to facilitate insertion or removal of articles cabinets with means for moving compartments up and down A47B51/00; cabinet system, e.g. consisting of cabinets arranged in a row with means to open or close passages between adjacent cabinets A47B53/02
• CPC Class Codes: B65G 1/1373 for fulfilling orders in warehouses
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0221 involving a learning process
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Systems and methods are provided herein for providing contention resolutions for components (e.g., mobile drive units, personnel devices) of an inventory system. For example, a method may comprise determining a task to be performed by a mobile drive unit within a storage facility. The MDU may be provided a set of commands related to the task. Conflict information may be received from the MDU that indicates an obstacle related to the set of commands and the task. An alternate set of commands may be generated for the MDU based at least in part on the conflict information and a computer-generated model. In at least one embodiment, the computer-generated model may be trained based at least in part on historical conflict information and conflict resolution information specific to tasks performed within the storage facility. The alternate set of commands related to the task may be provided to the MDU.

Claims

1. An inventory system, comprising:

a plurality of mobile drive units located within a storage facility and individually configured to move items within the storage facility;

one or more data networks;

one or more processors; and

one or more memories storing computer-readable instructions that, upon execution by the one or more processors, cause the inventory system to at least;

determine a location of an item to be moved within the storage facility from a first location to a second location;

identify a mobile drive unit of the plurality of mobile drive units based at least in part on respective locations of the plurality of mobile drive units, the first location, and the second location;

generate a set of commands for incrementally moving the item from first location to the second location;

provide, over the one or more data networks, the set of commands to the mobile drive unit, wherein providing the set of commands to the mobile drive unit causes the mobile drive unit to execute at least one of the set of commands;

receive, from the mobile drive unit over the one or more data networks, information related to an obstacle encountered by the mobile drive unit in the course of incrementally executing the set of commands, the obstacle inhibiting the mobile drive unit from moving the item from the first location to the second location according to the set of commands;

in response to receiving the information related to the obstacle, obtain a model for determining an action from a set of actions, the model having been generated utilizing historical data associated with the plurality of mobile drive units and at least one machine learning technique, the historical data indicating encounters by the plurality of mobile drive units with past obstacles and one or more actions taken in response to the encounters;

determine an action of the one or more actions based at least in part on the information related to the obstacle and the model;

generate an alternate set of commands for incrementally executing the determined action;

provide, over the one or more data networks, the alternate set of commands for incrementally executing the determined action to the mobile drive unit, wherein providing the alternate set of commands to the mobile drive unit causes the mobile drive unit to execute at least one of the alternate set of commands;

obtain conflict resolution information based at least in part on monitoring the plurality of mobile drive units for a period of time after providing the alternate set of commands, wherein the conflict resolution information comprises a time measurement corresponding to task performance by at least one mobile drive unit of the plurality of mobile drive units; and

modify the model based at least in part on the conflict resolution information.

2. The inventory system of claim 1, wherein the obstacle comprises at least one of another mobile drive unit, a stationary object, or a malfunction of the mobile drive unit.

3. The inventory system of claim 1, wherein execution of the computer-readable instructions further causes the inventory system to:

reserve, to the mobile drive unit, a first path within the storage facility for moving the item from the first location to the second location, the first path associated with the set of commands;

in response to generating the alternate set of commands, enable the first path to be reserved by another mobile drive unit of the plurality of mobile drive units; and

reserve, to the mobile drive unit, a second path within the storage facility for moving the item from a location associated with the obstacle to the second location, the second path associated with the alternate set of commands.

4. The inventory system of claim 1, wherein the information related to the obstacle is collected by one or more sensors of the mobile drive unit.

5. A computer-implemented method, comprising:

determining a task to be performed by a mobile drive unit of a plurality of mobile drive units within a storage facility;

providing, to the mobile drive unit, a set of commands related to the task, wherein providing the set of commands causes the mobile drive unit to execute at least one of the set of commands;

receiving conflict information from at least one mobile drive unit of the plurality of mobile drive units, the conflict information indicating an obstacle related to the set of commands and the task;

generating an alternate set of commands for the mobile drive unit, the alternate set of commands being generated based at least in part on the conflict information and a computer-generated model, the computer-generated model being trained based at least in part on historical conflict information specific to tasks performed within the storage facility and at least one machine learning algorithm;

providing the alternate set of commands related to the task to the mobile drive unit, wherein providing the alternate set of commands causes the mobile drive unit to execute at least one of the alternate set of commands;

obtaining new conflict resolution information based at least in part on monitoring the plurality of mobile drive units for a period of time after the mobile drive unit has commenced executing the at least one of the alternate set of commands, wherein the new conflict resolution information comprises a time measurement corresponding to task performance by at least one mobile drive unit of the plurality of mobile drive units; and

modifying the computer-generated model based at least in part on the new conflict resolution information.

6. The computer-implemented method of claim 5, wherein the conflict information is received from a different mobile drive unit than the mobile drive unit performing the task.

7. The computer-implemented method of claim 5, further comprising:

determining a first priority for the task;

in response to receiving the conflict information, identifying a second mobile drive unit related to the conflict information; and

determining a second priority for a second task assigned to the second mobile drive unit, wherein the alternate set of commands are generated based at least in part on the first priority and the second priority.

8. The computer-implemented method of claim 5, wherein the conflict information comprises at least two of a location of the obstacle, an identifier of the mobile drive unit, one or more locations of one or more mobile drive units of the plurality of mobile drive units within a threshold distance of the location of the obstacle, a number of parallel paths available to the mobile drive unit, an indication of an obstacle type associated with the obstacle, or a malfunction identifier of the mobile drive unit.

9. The computer-implemented method of claim 5, wherein the new conflict resolution information further comprises navigational information corresponding to the plurality of mobile drive units over a period of time.

10. The computer-implemented method of claim 5, further comprising:

determining a conflict resolution score for an action associated with the alternate set of commands, the conflict resolution score being determined utilizing the computer-generated model, wherein the computer-generated model scores the action based at least in part on the at least one time measurement associated with the new conflict resolution information,

wherein future actions are determined based at least in part on the new conflict resolution information and the conflict resolution score.

11. The computer-implemented method of claim 5, wherein at least one of the historical conflict information or the conflict resolution information is pre-generated utilizing a simulated model.

12. The computer-implemented method of claim 5, further comprising:

providing subsequent commands to at least one of the plurality of mobile drive units based at least in part on the modified model, wherein providing the subsequent commands to the at least one mobile drive unit causes the at least one mobile drive unit to execute at least one of the subsequent commands.

13. One or more computer-readable storage media comprising computer-readable instructions that, upon execution by one or more processors of a mobile drive unit, cause the mobile drive unit to perform operations comprising:

obtaining a set of commands corresponding to machine instructions that enable the mobile drive unit to perform a task within a storage facility;

executing the set of commands to effectuate performance of the task;

detecting an obstacle that conflicts with the performance of the task;

determining that the obstacle necessitates a new set of commands;

obtaining the new set of commands based at least in part on the obstacle and a computer-generated model, the computer-generated model being trained based at least in part on historical conflict information and conflict resolution information specific to tasks performed within the storage facility;

commencing execution of the new set of commands; and

providing conflict resolution information for a period of time after commencing the execution of the new set of commands, the conflict resolution information comprising a time measurement corresponding to task performance by the mobile drive unit, wherein providing the conflict resolution information causes the computer-generated model to be retrained based at least in part on the conflict resolution information.

14. The computer-readable medium of claim 13, wherein the operations further comprise:

determining a communication channel with which to communicate obstacle information;

broadcasting a communication request on the communication channel;

receiving a communication response from at least one other mobile drive unit within the storage facility; and

broadcasting, on the communication channel, the obstacle information.

15. The computer-readable medium of claim 14, wherein the communication request comprises a location of the obstacle, and wherein the communication response is received from at least one mobile drive unit that is located within a threshold distance of the obstacle.

16. The computer-readable medium of claim 13, wherein the operations further comprise:

tracking navigational information and sensor data associated with the mobile drive unit;

receiving a request for the navigation information and sensor data, the request being received from a remote system; and

transmitting the navigation information and sensor data to the remote system, wherein the new set of commands is further based at least in part on the navigational information and sensor data, and wherein the navigation information and sensor data are utilized by the remote system to generate one or more protocol sets for obstacle resolution.

17. The computer-readable medium of claim 13, wherein the operations further comprise:

obtaining a plurality of protocol sets, an individual protocol set being related to obstacle resolution, wherein the plurality of protocol sets are determined by a remote system based at least in part on historical information related to a plurality of mobile drive units operating in the storage facility and the at least one machine learning algorithm; and

determining a particular protocol set from the plurality of protocol sets based at least in part on the obstacle, wherein the new set of commands are generated according to the protocol set.

18. The computer-readable medium of claim 13, wherein the operations further comprise:

determining a priority associated with the task, wherein the new set of commands are generated according to the historical information associated with a plurality of mobile drive units when the priority is above a threshold amount, and wherein the new set of commands is calculated such that the set is unique with respect to the historical information when the priority is below a threshold amount.

19. The computer-readable medium of claim 13, wherein the set of commands and the new set of commands are based at least in part on other sets of commands associated with a plurality of mobile drive units within the storage facility.