System and method for managing mobile drive units

• US 8,068,978 B2
• Filed: 01/17/2011
• Issued: 11/29/2011
• Est. Priority Date: 06/19/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Kiva Systems, Inc (Amazon.com, Inc.)
• Inventors: D'Andrea, Raffaello, Barbehenn, Michael T., Hoffman, Andrew E., Mountz, Michael C., Wurman, Peter R.
• Primary Examiner(s): Beaulieu; Yonel
• Application Number:
  US13/007,936
• Publication Number:
  US 20110112758A1
• Time in Patent Office: 316 Days
• Field of Search: 701200-202, 701/209, 340/988
• US Class Current: 701/201
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means

Abstract

A method for moving a mobile drive unit within a workspace includes receiving a path. The path includes at least an initial segment and one or more additional segments. The initial segment includes a portion of the path adjacent to the first point; and at least one of the additional segments includes a portion of the path adjacent to the second point. The method further includes storing the path, reserving the initial segment of the path, and moving away from the first point along the initial segment. After initiating movement along the initial segment, the method includes reserving each of the additional segments of the path and moving toward the second point along each of the additional segments while that segment is reserved.

Claims

1. A system for transporting inventory items, comprising:

a route planning module operable to transmit a route response to a mobile drive unit, wherein the route response defines a path between a first point and a second point;

a segment reservation module operable to;

receive a reservation request from a mobile drive unit, the reservation request identifying a requested segment to be reserved;

in response to receiving the reservation request, decide whether to reserve at least the requested segment for the requesting mobile drive unit; and

transmit a reservation response to the reservation requesting mobile drive unit,

wherein the reservation response indicates whether the requested segment has been reserved; and

a mobile drive unit operable to;

receive the route response defining the path, wherein;

the path comprises an initial segment and one or more additional segments;

the initial segment includes a portion of the path adjacent to the first point; and

at least one of the additional segments includes a portion of the path adjacent to the second point;

store the path;

reserve the initial segment of the path;

move away from the first point along the initial segment;

after initiating movement along the initial segment, reserve each of the one or more additional segments of the path;

move toward the second point along each segment while that segment is reserved.

2. The system of claim 1, wherein the one or more additional segments comprise a plurality of additional segments;

and wherein the mobile drive unit is further operable to reserve each of the additional segments while traversing the path.

3. The system of claim 2, wherein one of the additional segments comprises a second segment, and the mobile drive unit is further operable to reserve the second segment by reserving the second segment while moving along the initial segment.

4. The system of claim 3, wherein the mobile drive unit is operable to reserve the second segment while moving along the initial segment by reserving the second segment after completing a predetermined portion of the first segment.

5. The system of claim 3, wherein the mobile drive unit is operable to reserve the second segment while moving away from the first point along the initial segment by:

determining that less than a predetermined minimum threshold of the initial segment remains to be completed; and

in response to determining that less than the predetermined minimum threshold remains to be completed, reserving the second segment.

6. The system of claim 1, wherein the mobile drive unit is operable to reserve one of the first segment and the additional segments by:

transmitting a reservation request identifying a requested segment to a management module;

receiving a reservation response indicating the requested segment has been reserved for the mobile drive unit; and

moving along the requested segment in response to receiving the reservation response indicating that the requested segment has been reserved for the mobile drive unit.

7. The system of claim 6, wherein the mobile drive unit is operable to transmit a reservation request by transmitting the reservation request and delaying movement along the requested segment until receiving a reservation response indicating that the requested segment has been reserved for the mobile drive unit.

8. The system of claim 6, wherein the mobile drive unit is operable to transmit a reservation request by:

transmitting a reservation request identifying a requested segment;

receiving a reservation response indicating that the request segment has not been reserved for the mobile drive unit;

waiting a predetermined amount of time without moving along the requested segment;

transmitting a second reservation request identifying the requested segment;

receiving a reservation response indicating that the requested segment has been reserved for the mobile drive unit; and

moving along the requested segment in response to receiving the reservation request indicating that the requested segment has been reserved for the mobile drive unit.

9. The system of claim 6, wherein the mobile drive unit is operable to transmit a reservation request by:

transmitting one or more reservation requests identifying a requested segment;

receiving, in response to each reservation request, a reservation response indicating that the requested segment has not been reserved for the mobile drive unit; and

in response to receiving a predetermined number of reservation responses indicating that the requested segment has not been reserved for the mobile drive unit requesting a second path to the second point.

10. The system of claim 9, wherein the second path comprises a path between a current location of the mobile drive unit and the second point.

11. The system of claim 6, wherein the mobile drive unit is operable to transmit a reservation request by:

transmitting a reservation request identifying a requested segment;

waiting a predetermined amount of time for a reservation request indicating that the requested segment has been reserved for the mobile drive unit;

determining whether the predetermined amount of time has expired; and

in response to determining the predetermined amount of time has expired, requesting a second path to the second point.

12. The system of claim 11, wherein the second path comprises a path between a current location of the mobile drive unit and the second point.

13. The system of claim 1, wherein the mobile drive unit is operable to wirelessly transmit a reservation request to the segment reservation module, and wherein the segment reservation module is operable to receive a reservation request by receiving a reservation request transmitted wirelessly to the route planning module.

14. The system of claim 1, wherein the first point comprises a current location of an inventory pod and wherein the second point comprises a destination for the inventory pod, and wherein the mobile drive unit is operable to move along the first segment by:

docking with the inventory pod; and

moving the inventory pod along the first segment after docking with the inventory pod.

15. The system of claim 1, wherein the mobile drive unit is operable to move along a final segment of the one or more additional segments by:

moving the inventory pod along the final segment to the second point;

undocking from the inventory pod substantially near to the second point; and

moving away from the inventory pod.

16. The system of claim 1, wherein the segment reservation module is further operable to determine a modified segment to reserve based on the requested segment and an error margin;

and wherein deciding to reserve at least the requested segment comprises determining whether to reserve the modified segment for the requesting mobile drive unit.

17. The system of claim 16, wherein the segment reservation module is operable to determine a modified segment that comprises the requested segment and a cell adjacent to the requested segment.

18. The system of claim 1, wherein the mobile drive unit comprises a first mobile drive unit, and wherein the segment reservation module is further operable to:

determine a reservation type requested for at least a first portion of the requested segment;

in response to determining that a rotation reservation is requested for the first portion of the requested segment;

grant a rotation reservation request received from a second mobile drive requesting a reservation of the first portion to allow the second mobile drive unit to rotate an inventory holder in an area adjacent to the first portion; and

deny any other type of reservation requests for the first portion while the first mobile drive unit has the first portion reserved.

19. The system of claim 1, wherein the mobile drive unit is further operable to release the reservation of the initial segment after moving across the initial segment.

20. The system of claim 1, wherein the mobile drive unit is further operable to release a portion of the initial segment after moving across the portion, wherein the portion is less than an entirety of the initial segment.

21. The system of claim 1, wherein the segment reservation module is further operable to:

determine a state of the mobile drive unit; and

decide whether to release the reservation of the initial segment based on the state of the mobile drive unit.

22. A route planning module operable to:

receive a route request from a mobile drive unit;

in response to receiving the route request, generate a path between a first point and a second point, wherein;

the path comprises an initial segment and one or more additional segments;

the initial segment includes a portion of the path adjacent to the first point; and

at least one of the additional segments includes a portion of the path adjacent to the second point;

store the path;

transmit a route response defining the initial segment to the mobile drive unit;

receive one or more subsequent requests from the mobile drive unit; and

in response to each of the one or more subsequent requests from the mobile drive unit, transmit an additional route response defining an additional segment of the path.

23. A system for moving inventory items, comprising:

a route planning module operable to;

generate a first path between a first point and a second point, wherein the first path comprises a plurality of segments;

transmit, to a mobile drive unit, information specifying an initial segment of the first path; and

a mobile drive unit operable to;

receive the information specifying the initial segment of the first path;

reserve the initial segment of the first path;

move away from the first point along the initial segment of the first path;

after initiating movement along the initial segment of the first path, request a next segment; and

wherein the route planning module is further operable to;

in response to the mobile drive unit requesting the next segment, decide whether to generate a new path for the mobile drive unit;

in response to deciding not to generate a new path, transmit a second segment of the first path; and

in response to deciding to generate a new path;

generate a second path between a current location of the mobile drive unit and the second point; and

transmit information identifying a first segment of the second path to the mobile drive unit.

24. The system of claim 23, wherein the route planning module is operable to store the first path.

25. The system of claim 24, wherein the route planning module, in response to deciding to generate a new path, is further operable to generate a second path based on an algorithm that uses the stored first path as an input.

26. The system of claim 23, wherein:

the route planning module is further operable to transmit information to the mobile drive unit that specifies the initial segment of the first path by transmitting information to the mobile drive unit that specifies an entirety of the first path;

the mobile drive unit is operable to request the next segment by transmitting a route request to the route planning module, wherein the route request specifies at least a remainder of the first path; and

the route planning module, in response to deciding to generate a new path, is further operable to generate a second path based on an algorithm that uses at least the remainder of the first path as an input.

27. The system of claim 23, wherein route planning module is further operable to:

detect a change in a state of an inventory system associated with the mobile drive unit; and

decide whether to generate a new path for the mobile drive unit based on the detected change.

28. The system of claim 27, wherein the route planning module is operable to detect a change in the state of the inventory system by detecting a change in a traffic level associated with the inventory system.

29. The system of claim 27, wherein the route planning module is operable to detect a change in the state of the inventory system by receiving information indicating a location of an obstacle in a workspace associated with the inventory system.

30. The system of claim 29, wherein the mobile drive unit is further operable to:

receive the information specifying the initial segment of the first path;

reserve the initial segment of the first path;

move away from the first point along the initial segment of the first path; and

after initiating movement of the mobile drive unit along the initial segment of the first path, request a next segment from the route planning module.

31. The system of claim 23, wherein the mobile drive unit is operable to reserve the initial segment of the first path by transmitting a reservation request identifying the initial segment to a segment reservation module, and further comprising:

the segment reservation module operable to;

receive the reservation request from the mobile drive unit;

in response to receiving the reservation request, decide whether to reserve at least the requested segment for the requesting mobile drive unit; and

transmit a reservation response to the reservation requesting mobile drive unit, wherein the reservation response indicates whether the requested segment has been reserved.

32. A method for moving inventory items, comprising:

generating a first path between a first point and a second point, wherein the first path comprises a plurality of segments;

transmitting information to a mobile drive unit that specifies an initial segment of the first path;

receiving a request for a next segment from the mobile drive unit;

in response to receiving the request for the next segment, deciding whether to generate a new path for the mobile drive unit;

in response to deciding not to generate a new path, transmitting a second segment of the first path; and

in response to deciding to generate a new path;

generating a second path between a current location of the mobile drive unit and the second point; and

transmitting information identifying a first segment of the second path to the mobile drive unit.

33. The method of claim 32, further comprising storing the first path.

34. The method of claim 33, wherein, generating a second path comprises generating a second path based on an algorithm that uses the stored first path as an input.

35. The method of claim 32, wherein:

transmitting information to the mobile drive unit that specifies the initial segment of the first path comprises transmitting information to the mobile drive unit that specifies an entirety of the first path;

receiving a request for a next segment comprises receiving a request that specifies at least a remainder of the first path; and

generating the second path comprises generating the second path based on an algorithm that uses at least the remainder of the first path as an input.

36. The method of claim 32, further comprising:

detecting a change in a state of an inventory system associated with the mobile drive unit; and

deciding whether to generate a new path for the mobile drive unit based on the detected change.

37. The method of claim 36, wherein detecting a change in the state of the inventory system comprises detecting a change in a traffic level associated with the inventory system.

38. The method of claim 36, wherein detecting a change in the state of the inventory system comprises receiving information indicating a location of an obstacle in a workspace associated with the inventory system.

39. The method of claim 38, further comprising:

receiving the information specifying the initial segment of the first path at the mobile drive unit;

reserving the initial segment of the first path;

moving the mobile drive unit away from the first point along the initial segment of the first path; and

after initiating movement of the mobile drive unit along the initial segment of the first path, requesting a next segment from the route planning module.

40. The method of claim 32, wherein reserving the initial segment of the first path comprises transmitting a reservation request from the mobile drive unit to a segment reservation module wherein the reservation request identifies the initial segment, and further comprising:

receiving, at the segment reservation module, the reservation request;

in response to receiving the reservation request, deciding whether to reserve at least the requested segment for the requesting mobile drive unit; and

transmitting a reservation response from the segment reservation module to the reservation requesting mobile drive unit, wherein the reservation response indicates whether the requested segment has been reserved.

41. A route scheduling module operable to:

generate a first path between a first point and a second point, wherein the first path comprises a plurality of segments;

transmit information to a mobile drive unit that specifies an initial segment of the first path;

receive a request for a next segment from the mobile drive unit;

in response to receiving the request for the next segment, decide whether to generate a new path for the mobile drive unit;

in response to deciding not to generate a new path, transmit a second segment of the first path; and

in response to deciding to generate a new path;

generate a second path between a current location of the mobile drive unit and the second point; and

transmit information identifying a first segment of the second path to the mobile drive unit.

42. A system for moving inventory items, comprising:

means for generating a first path between a first point and a second point, wherein the first path comprises a plurality of segments;

means for transmitting information to a mobile drive unit that specifies an initial segment of the first path;

means for receiving a request for a next segment from the mobile drive unit;

means for deciding, in response to receiving the request for the next segment, whether to generate a new path for the mobile drive unit;

means for transmitting a second segment of the first path in response to deciding not to generate a new path;

means for generating a second path between a current location of the mobile drive unit and the second point in response to deciding to generate a new path; and

means for transmitting information identifying a first segment of the second path to the mobile drive unit in response to deciding to generate the new path.