Coordination of mobile drive units

• US 10,126,747 B1
• Filed: 09/29/2015
• Issued: 11/13/2018
• Est. Priority Date: 09/29/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Svec, Petr, Bell, Matthew Paul, Barbehenn, Michael T.
• Primary Examiner(s): Ismail, Mahmoud S
• Application Number:
  US14/869,265
• Time in Patent Office: 1,141 Days
• Field of Search: 701301, 701117, 700255, 41433113
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05B 19/4189 characterised by the transport system
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

In one example, an intersection of a first path and a second path may be determined. The first path may be associated with a first mobile drive unit and the second path may be associated with a second mobile drive unit. A plurality of velocity sets may be determined based on the intersection. A velocity set may be selected from the plurality of velocity sets. The velocity set may include velocity values that correspond to the first mobile drive unit and the second mobile drive unit. The selected velocity set may be provided to at least one of the first mobile drive unit or the second mobile drive unit.

Claims

1. A computer-implemented method, comprising:

accessing a first path of a first mobile drive unit within a workspace, the first mobile drive unit having a first initial location along the first path;

accessing a second path of a second mobile drive unit within the workspace, the second mobile drive unit having a second initial location along the second path;

determining an intersection point of the first path and the second path within the workspace;

determining a set of potential yield rules applicable to the first mobile drive unit and the second mobile drive unit, each potential yield rule indicating that, prior to arriving at the intersection point, (a) the first mobile drive unit yield, (b) the second mobile drive unit yield, (c) the first mobile drive unit and the second mobile drive unit yield, or (d) neither the first mobile drive unit nor the second mobile drive unit yield;

determining, based at least in part on the set of potential yield rules, a first plurality of velocity sets, each velocity set comprising at least a first velocity value corresponding to the first mobile drive unit and a second velocity value corresponding to the second mobile drive unit, wherein movement in accordance with any velocity set from the first plurality of velocity sets causes the first mobile drive unit and the second mobile drive unit to avoid a potential collision event at the intersection point;

determining, based at least in part on a second intersection, a second plurality of velocity sets corresponding to the first mobile drive unit and the second mobile drive unit;

searching a space of discrete event states at which velocities are applied at discrete event states to find sequences of discrete event states, with each sequence of discrete event states forming a corresponding sequence of velocity sets, each sequence of velocity sets comprising at least one velocity set from the first plurality of velocity sets and at least one velocity set from the second plurality of velocity sets;

evaluating each sequence of velocity sets at corresponding sequences of discrete event states using a scoring metric;

selecting, based at least in part on evaluating each sequence, a particular sequence of velocity sets; and

controlling the first mobile drive unit and the second mobile drive unit by instructing the first mobile drive unit and the second mobile drive unit to move in accordance with the particular sequence of velocity sets.

2. The computer-implemented method of claim 1, further comprising:

after determining the set of potential yield rules, eliminating one or more potential yield rules from the set of potential yield rules that would require both the first mobile drive unit and the second mobile drive unit to yield to each other;

determining, based on the set of potential yield rules, a plurality of candidate velocity sets, each candidate set of the plurality of candidate velocity sets including at least one velocity value corresponding to the first mobile drive unit or the second mobile drive unit; and

eliminating, from the plurality of candidate velocity sets, one or more candidate velocity sets that, if selected, would lead to the potential collision event at the intersection point between the first mobile drive unit and the second mobile drive unit.

3. The computer-implemented method of claim 1, wherein determining the intersection point of the first path and the second path is further based at least in part on the first initial location, a first initial orientation of the first mobile drive unit, a maximum speed for the first mobile drive unit, the second initial location, a second initial orientation of the second mobile drive unit, and a maximum speed for the second mobile drive unit.

4. The computer-implemented method of claim 1, wherein the scoring metric comprises one or more of a time of arrival metric, an energy expenditure metric, a component wear metric, a stability metric, a jerk metric, or an acceleration metric.

5. The computer-implemented method of claim 4, wherein evaluating each sequence of velocity sets includes

generating, based at least in part on the scoring metric, one or more scores corresponding to each sequence of velocity sets.

6. A computer-implemented method, comprising:

determining a first intersection of a first path and a second path, the first path being associated with a first mobile drive unit, and the second path being associated with a second mobile drive unit;

determining, based at least in part on the first intersection, a first plurality of velocity sets corresponding to the first mobile drive unit and the second mobile drive unit, each velocity set of the first plurality of velocity sets comprising at least a first velocity value corresponding to the first mobile drive unit and a second velocity value corresponding to the second mobile drive unit, wherein movement in accordance with any velocity set from the first plurality of velocity sets causes the first mobile drive unit and the second mobile drive unit to avoid a potential collision event at the first intersection;

determining, based at least in part on a second intersection, a second plurality of velocity sets corresponding to the first mobile drive unit and the second mobile drive unit;

searching a space of discrete event states at which velocities are applied at discrete event states to find sequences of discrete event states, with each sequence of discrete event states forming a corresponding sequence of velocity sets, each sequence of velocity sets comprising at least one velocity set from the first plurality of velocity sets and at least one velocity set from the second plurality of velocity sets;

evaluating each sequence of velocity sets at corresponding sequences of discrete event states using a scoring metric;

selecting, based at least in part on evaluating each sequence, a particular sequence of velocity sets, the particular sequence of velocity sets comprising first particular velocity values corresponding to the first mobile drive unit and second particular velocity values corresponding to the second mobile drive unit; and

controlling at least one of the first mobile drive unit or the second mobile drive unit by instructing at least one of the first mobile drive unit or the second mobile drive unit to move in accordance with the particular sequence of velocity sets.

7. The computer-implemented method of claim 6, wherein the first intersection comprises a location within a workspace where the first mobile drive unit and the second mobile drive unit may collide unless at least one of the first mobile drive unit or the second mobile drive unit is instructed to move in accordance with the selected velocity set.

8. The computer-implemented method of claim 6, further comprising, prior to determining the first plurality of velocity sets, determining a set of potential yield rules applicable to the first mobile drive unit and the second mobile drive unit, at least one potential yield rule of the set of potential yield rules indicating that at least one of the first mobile drive unit or the second mobile drive unit adjusts its velocity prior to arriving at the intersection.

9. The computer-implemented method of claim 8, wherein determining the first plurality of velocity sets is further based at least in part on the set of potential yield rules.

10. The computer-implemented method of claim 6, wherein:

evaluating each the sequence of velocity sets includes;

generating, based at least in part on the scoring metric, one or more scores corresponding to each sequence of velocity sets; and

ranking the one or more scores relative to each other to create a ranked set of scores; and

selecting the particular sequence of velocity sets is based at least in part on the ranked set of scores, the velocity set.

11. The computer-implemented method of claim 6, wherein the first path is orthogonal with respect to the second path at the intersection, and wherein the intersection comprises a location of the potential collision event between a leading portion of the second mobile drive unit and a side portion of the first mobile drive unit, or between a leading portion of the first mobile drive unit and a side portion of the second mobile drive unit.

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

prior to determining the first plurality of velocity sets, determining, based at least in part on a set of potential yield rules, a plurality of candidate velocity sets, each set of the plurality of candidate velocity sets comprising at least one known velocity value corresponding to the first mobile drive unit or the second mobile drive unit; and

eliminating, from the plurality of candidate velocity sets, one or more candidate velocity sets that, if selected, would lead to the potential collision event at the intersection between the first mobile drive unit and the second mobile drive unit.

20. The computer-implemented method of claim 6, further comprising determining the second intersection comprises determining an intersection of the first path and the second path or an intersection of at least one of the first path or the second path and a different path.

13. A system, comprising:

a plurality of mobile drive units disposed within a workspace and in communication with a management module; and

the management module comprising a memory and a processor configured to;

access a plurality of drive paths corresponding to a set of the plurality of mobile drive units, the plurality of drive paths located within the workspace;

determine a plurality of initial positions corresponding to the set of the plurality of mobile drive units;

determine a first intersection of at least two of the plurality of drive paths;

determine, based at least in part on the first intersection, a first plurality of velocity sets, wherein each velocity set of the first plurality of velocity sets includes at least two velocity values with a first velocity value applicable to a first mobile drive unit of the set of the plurality of mobile drive units and a second velocity value applicable to a second mobile drive unit of the set of the plurality of mobile drive units, wherein moving in accordance with any velocity set of the first plurality of velocity sets causes the first mobile drive unit and the second mobile drive unit to avoid a first potential collision at the first intersection;

determine, based at least in part on a second intersection, a second plurality of velocity sets corresponding to the first mobile drive unit and the second mobile drive unit;

search a space of discrete event states at which velocities are applied at discrete event states to find sequences of discrete event states, with each sequence of discrete event states forming a corresponding sequence of velocity sets, each sequence of velocity sets comprising at least one velocity set from the first plurality of velocity sets and at least one velocity set from the second plurality of velocity sets;

evaluate each sequence of velocity sets at corresponding sequences of discrete event states using a scoring metric;

select based at least in part on evaluating each sequence, a particular sequence of velocity sets, the particular sequence of velocity sets comprising two or more velocity profiles corresponding to the first and second mobile drive units; and

control the first and second mobile drive units by providing the particular sequence of velocity sets to the first and second mobile drive units to move in accordance with the particular sequence of velocity sets.

14. The system of claim 13, wherein the management module is further configured to determine the second intersection by at least:

accessing the plurality of drive paths corresponding to the set of the plurality of mobile drive units; and

determining, based at least in part on the first plurality of velocity sets, a plurality of updated positions corresponding to the set of the plurality of mobile drive units, wherein moving in accordance with the particular sequence of velocity sets avoids a second potential collision of the first mobile drive unit or the second mobile drive unit with a different mobile drive unit at the second intersection.

15. The system of claim 13, wherein the scoring metric comprises one or more of a time of arrival metric, an energy expenditure metric, a component wear metric, a stability metric, a jerk metric, or an acceleration metric.

16. The system of claim 13, wherein the plurality of drive paths is represented by a plurality of geometric paths within the workspace and the plurality of initial positions is represented by a plurality of sets of geometric coordinates within the workspace, and wherein determining the first intersection of the plurality of drive paths comprises:

accessing maximum velocities corresponding to the set of the plurality of mobile drive units;

determining, based at least in part on the maximum velocities and the initial positions, projected positions represented by one or more other sets of geometric coordinates within the workspace, the projected positions corresponding to the set of the plurality of mobile drive units; and

identifying the first intersection as a location within the workspace where two or more of the projected positions at least partially overlap.

17. The system of claim 13, wherein determining the first plurality of velocity sets is further based at least in part on a safety measure, the safety measure providing for individual safety zones that surround individual mobile drive units of the set of the plurality of mobile drive units.

18. The system of claim 13, wherein the management module is further configured to:

after determining the first intersection, determine a set of potential yield rules indicating that at least one mobile drive unit of the set of the plurality of mobile drive units yields prior to the first intersection;

exclude, from the set of potential yield rules, one or more potential yield rules that would prevent two or more mobile drive units from progressing by yielding to each other prior to the intersection; and

exclude, from the one or more velocity sets, other velocity sets that, if selected, would lead to the first potential collision of the two or more mobile drive units at the first intersection.

19. The system of claim 13, wherein:

the plurality of mobile drive units is configured to detachably couple to and transport a plurality of inventory holders; and

the plurality of inventory holders is configured to receive inventory items.