SYSTEM AND METHOD FOR COORDINATING MOVEMENT OF MOBILE DRIVE UNITS

• US 20080051985A1
• Filed: 06/19/2006
• Published: 02/28/2008
• 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.
• Granted Patent: US 7,920,962 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G05B 19/41895 using automatic guided vehicles [AGV] control of position or course of AGV's G05D1/00
• CPC Class Codes: G05B 2219/31003 Supervise route, reserve route and allocate route to vehicle, avoid collision
• CPC Class Codes: G05B 2219/45056 Handling cases, boxes
• 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/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127
• CPC Class Codes: G05D 1/0297 by controlling means in a control room
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/60 Electric or hybrid propulsion means for production processes

Abstract

A method for moving one or more mobile drive units within a workspace includes receiving, from a first mobile drive unit, a reservation request requesting use of a first path segment to move in a first direction. The method further includes determining that a second mobile drive unit is currently located on the first path segment and determining whether the second mobile drive unit is moving in the first direction. Additionally, the method includes transmitting a reservation response indicating that the reservation request is denied, in response to determining that the second mobile drive unit is not moving in the first direction. The method also includes transmitting a reservation response indicating that the reservation request is granted, in response to determining that the second mobile drive unit is moving in the first direction.

Claims

1. A method for moving one or more mobile drive units within a workspace, comprising:

receiving, from a first mobile drive unit, a reservation request requesting use of a first path segment to move in a first direction;

determining that a second mobile drive unit is currently located on the first path segment;

determining whether the second mobile drive unit is moving in the first direction;

in response to determining that the second mobile drive unit is not moving in the first direction, transmitting a reservation response indicating that the reservation request is denied; and

in response to determining that the second mobile drive unit is moving in the first direction, transmitting a reservation response indicating that the reservation request is granted.

2. The method of claim 1, further comprising:

receiving the reservation response at the first mobile drive unit;

in response to receiving the reservation response, determining whether the reservation request was granted; and

in response to determining that the reservation request was granted, moving the first mobile drive unit across the first path segment in the first direction.

3. The method of claim 2, further comprising:

in response to determining that the reservation request was denied;

waiting a predetermined amount of time; and

after waiting the predetermined amount of time, transmitting a second reservation request from the first mobile drive unit requesting use of the first path segment to move in the first direction.

4. The method of claim 1, wherein the reservation request comprises a current reservation request and wherein determining whether the second mobile drive unit is currently located on the first path segment comprises:

prior to receiving the current reservation request from the first mobile drive unit, receiving a previous reservation request from the second mobile drive unit requesting use of the first path segment to travel in a reserved direction;

storing the previous reservation request; and

determining whether the second mobile drive unit is moving in the first direction based on the stored previous reservation request.

5. The method of claim 1, wherein transmitting the reservation response indicating that the reservation request is granted comprises:

determining whether the first path segment extends farther than a second path segment currently reserved by the second mobile drive unit;

in response to determining that the first path segment extends farther than the second path segment, transmitting a reservation response indicating that the reservation request is denied; and

in response to determining that the first path segment does not extend farther than the second path segment, transmitting a reservation response indicating that the reservation request is granted.

6. The method of claim 1, wherein transmitting the reservation response indicating that the reservation request is granted, comprises:

determining whether the first path segment extends farther than a second path segment currently reserved by the second mobile drive unit;

in response to determining that the first path segment does not extend farther than the second path segment, transmitting a reservation response indicating that the reservation request is granted; and

in response to determining that the first path segment extends farther than the second path segment, transmitting a reservation response indicating that a reservation has been granted on a portion of the first path segment, wherein the portion is less than an entirety of the first path segment.

7. The method of claim 1, wherein the first path segment comprises one or more cells of a grid-based workspace.

8. A method for moving one or more mobile drive units within a workspace, comprising:

receiving, at a first mobile drive unit, a command to move in a first direction;

initiating, in a first mobile drive unit, movement in the first direction along a path segment;

detecting an object located on the path segment in the first direction from the first mobile drive unit;

determining whether the object comprises a second mobile drive unit moving in the first direction;

in response to determining that the object comprises a second mobile drive unit, continuing movement in the first direction; and

in response to determining that the object does not comprise a second mobile drive unit moving in the first direction, terminating movement in the first direction.

9. The method of claim 8, wherein determining that the object comprises a second mobile drive unit moving in the first direction comprises determining whether the first mobile drive unit detects a drive identification signal transmitted by a second mobile drive unit, the drive identification signal indicating that the second mobile drive unit is a mobile drive unit moving in the first direction.

10. The method of claim 9, wherein:

the drive identification signal further indicates a state of the second mobile drive unit; and

continuing movement in the first direction comprises;

calculating a second speed based on the state of the second mobile drive unit; and

continuing movement in the first direction at the second speed.

11. The method of claim 10, wherein:

the drive identification signal indicates the state of the second mobile drive unit by indicating at least a current speed of the second mobile drive unit and a maximum deceleration rate associated with the second mobile drive unit; and

calculating a second speed based on the indicated state comprises calculating a second speed based on the current speed of the second mobile drive unit and the maximum deceleration rate associated with the second mobile drive unit.

12. The method of claim 11, wherein calculating a second speed based on the state of the second mobile drive unit comprises calculating a second speed based on the state of the second mobile drive unit and a maximum deceleration rate associated with the first mobile drive unit.

13. The method of claim 12, further comprising determining the maximum deceleration rate associated with the second mobile drive unit based on a docking state of the second mobile drive unit.

14. The method of claim 12, further comprising determining the maximum deceleration rate associated with the second mobile drive unit based on one or more properties of an inventory holder docked with the second mobile drive unit.

15. The method of claim 8, farther comprising:

transmitting in the first direction a second drive identification signal wherein the second drive identification signal indicates a first speed, wherein the first speed comprises a current speed of the first mobile drive unit;

calculating a second speed based on the first speed; and

moving the second mobile drive unit in the first direction at the second speed.

16. The method of claim 8, wherein the path segment comprises one or more cells of a grid-based workspace.

17. A system for transporting inventory items, comprising:

a plurality of mobile drive units;

a plurality of inventory holders; and

a management module operable to;

receive, from a first mobile drive unit, a reservation request requesting use of a first path segment to move in a first direction;

determine that a second mobile drive unit is currently located on the first path segment;

determine whether the second mobile drive unit is moving in the first direction;

in response to determining that the second mobile drive unit is not moving in the first direction, transmit a reservation response indicating that the reservation request is denied; and

in response to determining that the second mobile drive unit is moving in the first direction, transmit a reservation response indicating that the reservation request is granted.

18. The system of claim 17, wherein the first mobile drive unit is operable to:

receive the reservation response;

in response to receiving the reservation response, determine whether the reservation request was granted; and

in response to determining that the reservation request was granted, move across the first path segment in the first direction.

19. The system of claim 18, wherein the first mobile drive unit is operable to:

in response to determining that the reservation request was denied;

wait a predetermined amount of time; and

after waiting the predetermined amount of time, transmit a second reservation request requesting use of the first path segment to move in the first direction.

20. The system of claim 17, wherein the reservation request comprises a current reservation request, and wherein the management module is operable to determine whether the second mobile drive unit is currently located on the first path segment by:

prior to receiving the current reservation request from the first mobile drive unit, receiving a previous reservation request from the second mobile drive unit requesting use of the first path segment to travel in a reserved direction;

storing the previous reservation request; and

determining whether the second mobile drive unit is moving in the first direction based on the stored previous reservation request.

21. The system of claim 17, wherein the management module is operable to transmit the reservation response indicating that the reservation request is granted by:

determining whether the first path segment extends farther than a second path segment currently reserved by the second mobile drive unit;

in response to determining that the first path segment extends farther than the second path segment, transmitting a reservation response indicating that the reservation request is denied; and

in response to determining that the first path segment does not extend farther than the second path segment, transmitting a reservation response indicating that the reservation request is granted.

22. The system of claim 17, wherein the management module is operable to transmit the reservation response indicating that the reservation request is granted by:

determining whether the first path segment extends farther than a second path segment currently reserved by the second mobile drive unit;

in response to determining that the first path segment does not extend farther than the second path segment, transmitting a reservation response indicating that the reservation request is granted; and

in response to determining that the first path segment extends farther than the second path segment, transmitting a reservation response indicating that a reservation has been granted on a portion of the first path segment, wherein the portion is less than an entirety of the first path segment.

23. The system of claim 17, further comprising a grid-based workspace that includes a plurality of cells, and wherein the first path segment comprises one or more cells of the grid-based workspace.

24. A system for transporting inventory items, comprising:

a plurality of inventory holders; and

a plurality of mobile drive units, wherein at least a first mobile drive unit is operable to;

receive a command to move in a first direction;

initiate movement in a first direction along a path segment;

detect an object located on the path segment in the first direction from the first mobile drive unit;

determine whether the object comprises a second mobile drive unit moving in the first direction;

in response to determining that the object comprises a second mobile drive unit, continue movement in the first direction; and

in response to determining that the object does not comprise a second mobile drive unit moving in the first direction, terminate movement in the first direction.

25. The system of claim 24, wherein the first mobile drive unit is operable to determine that the object comprises a second mobile drive unit moving in the first direction by determining whether the first mobile drive unit detects a drive identification signal transmitted by a second mobile drive unit, the drive identification signal indicating that the second mobile drive unit is a mobile drive unit moving in the first direction.

26. The system of claim 25, wherein:

the drive identification signal further indicates a state of the second mobile drive unit; and

the first mobile drive unit is operable to continue movement in the first direction by;

calculating a second speed based on the state of the second mobile drive unit, and

continuing movement in the first direction at the second speed.

27. The system of claim 26, wherein the drive identification signal indicates the state of the second mobile drive unit by indicating at least a current speed of the second mobile drive unit and a maximum deceleration rate associated with the second mobile drive unit, and wherein the first mobile drive unit is operable to calculate a second speed based on the indicated state by calculating a second speed based on the current speed of the second mobile drive unit and the maximum deceleration rate associated with the second mobile drive unit.

28. The system of claim 27, wherein the first mobile drive unit is operable to calculate a second speed based on the state of the second mobile drive unit by calculating a second speed based on the state of the second mobile drive unit and a maximum deceleration rate associated with the first mobile drive unit.

29. The system of claim 28, wherein the second mobile drive unit is operable to determine the maximum deceleration rate associated with the second mobile drive unit based on a docking state of the second mobile drive unit.

30. The system of claim 28, wherein the second mobile drive unit is operable to determine the maximum deceleration rate associated with the second mobile drive unit based on one or more properties of an inventory holder docked with the second mobile drive unit.

31. The system of claim 24, wherein the first mobile drive unit is further operable to transmit in the first direction a second drive identification signal, wherein the second drive identification signal indicates a first speed and the first speed comprises a current speed of the first mobile drive unit, and wherein the second mobile drive unit is further operable to:

calculate a second speed based on the first speed;

move in the first direction at the second speed.

32. The system of claim 24, further comprising a grid-based workspace that includes a plurality of cells, and wherein the first path segment comprises one or more cells of the grid-based workspace.

33. A system for moving one or more mobile drive units within a workspace, comprising:

means for receiving, from a first mobile drive unit, a reservation request requesting use of a first path segment to move in a first direction;

means for determining that a second mobile drive unit is currently located on the first path segment;

means for determining whether the second mobile drive unit is moving in the first direction;

means for, responsive to the determining means determining that the second mobile drive unit is not moving in the first direction, transmitting a reservation response indicating that the reservation request is denied; and

means for, responsive to the determining means determining that the second mobile drive unit is moving in the first direction, transmitting a reservation response indicating that the reservation request is granted.

34. A system for moving one or more mobile drive units within a workspace, comprising:

means for receiving, at a first mobile drive unit, a command to move in a first direction;

means for initiating, in a first mobile drive unit, movement in the first direction along a path segment;

means for detecting an object located on the path segment in the first direction from the mobile drive unit;

means for determining whether the object comprises a second mobile drive unit moving in the first direction;

means for continuing movement in the first direction in response to determining that the object comprises a second mobile drive unit moving in the first direction; and

means for terminating movement in the first direction in response to determining that the object does not comprise a second mobile drive unit moving in the first direction.

35. An apparatus for managing mobile drive units, operable to:

receive, from a first mobile drive unit, a reservation request requesting use of a first path segment to move in a first direction;

determine that a second mobile drive unit is currently located on the first path segment;

determine whether the second mobile drive unit is moving in the first direction;

in response to determining that the second mobile drive unit is not moving in the first direction, transmit a reservation response indicating that the reservation request is denied; and

in response to determining that the second mobile drive unit is moving in the first direction, transmit a reservation response indicating that the reservation request is granted.

36. An apparatus for transporting inventory items, operable to:

receive a command to move in a first direction;

initiate movement in a first direction along a path segment;

detect an object located on the path segment in the first direction from the first mobile drive unit;

determine whether the object comprises a second mobile drive unit moving in the first direction;

in response to determining that the object comprises a second mobile drive unit, continue movement in the first direction; and

in response to determining that the object does not comprise a second mobile drive unit moving in the first direction, terminate movement in the first direction.