Roadmap annotation for deadlock-free multi-agent navigation

• US 10,642,282 B2
• Filed: 04/12/2017
• Issued: 05/05/2020
• Est. Priority Date: 04/12/2017
• Status: Active Grant

• Current Assignee: Boston Dynamics, Inc. (SoftBank Group Corp.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Kichkaylo, Tatiana
• Primary Examiner(s): Rink, Ryan
• Application Number:
  US15/486,219
• Publication Number:
  US 20180299882A1
• Time in Patent Office: 1,119 Days
• Field of Search: None
• CPC Class Codes: G05B 19/418 Total factory control, i.e. centrally controlling a plurality of machines, e.g. direct or distributed numerical control [DNC], flexible manufacturing systems [FMS], integrated manufacturing systems [IMS] or computer integrated manufacturing [CIM]
• 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/32328 Dynamic scheduling, resource allocation, multi agent negotiation
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• 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: 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
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

Apparatus and methods related to routing robots are provided. A roadmap of an environment that includes first and second robots can be received. The roadmap can be annotated with unidirectional lanes connecting conflict regions, where each lane ends so to avoid blocking a conflict region. First and second routes for the respective uses of the first and second robots can be determined, where both the first and second routes include a first lane connected to a first conflict region. A first, higher priority and a second, lower priority can be assigned to the respective first and second robots. It can be determined that the second robot following the second route will block the first robot on the first lane. Based on the first priority being higher than the second priority, the computing device can alter the second route to prevent the second robot from blocking the first robot.

Claims

1. A method, comprising:

receiving, at a computing device, a roadmap of an existing environment that includes a first robot and a second robot;

annotating the roadmap with a plurality of lanes connecting a plurality of conflict regions using the computing device, wherein each lane is unidirectional and ends sufficiently distant from a conflict region to avoid blocking the conflict region, wherein the roadmap is annotated with a cycle of lanes such that the cycle contains a path between any pair of lanes of the cycle;

determining a first route through the environment along the roadmap for use by the first robot and a second route through the environment along the roadmap for use by the second robot, wherein both the first route and the second route include a first lane, and wherein the first lane connects to a first conflict region;

assigning a first priority to the first robot and a second priority to the second robot, wherein the first priority is initially higher than the second priority;

determining that the second robot following the second route will cause the second robot to block the first robot on the first lane before the first robot reaches the first conflict region;

based on the first priority being higher than the second priority, altering the second route by causing the second robot to travel through the cycle of lanes to prevent the second robot from blocking the first robot on the first lane, wherein causing the second robot to travel through the cycle of lanes comprises causing the second robot to return to the first lane with an increased priority from the second priority; and

resetting the first priority after the first robot completes the first route such that the second priority is higher than the first priority after the first robot completes the first route and before the second robot completes the second route.

2. The method of claim 1, wherein annotating the roadmap with the plurality of lanes comprises:

attempting to annotate the roadmap with a new lane using the computing device;

determining whether the new lane is unidirectional and ends sufficiently distant from a conflict region to avoid blocking the conflict region using the computing device; and

after determining that new lane is unidirectional and ends sufficiently distant from a conflict region to avoid blocking the conflict region, annotating the roadmap with the new lane.

3. The method of claim 2, wherein attempting to annotate the roadmap with the new lane comprises:

determining a location on the roadmap for the new lane using the computing device; and

attempting to annotate the location on the roadmap with the new lane using the computing device.

4. The method of claim 1, wherein annotating the roadmap with the plurality of lanes comprises:

selecting a first-paired lane and a second-paired lane from the one or more lanes;

determining whether a robot on the first-paired lane collides with a robot on the second-paired lane; and

after determining that a robot on the first-paired lane does collide with a robot on the second-paired lane, determining that the first-paired lane and/or the second-paired lane is not a lane.

5. The method of claim 1, wherein the first priority and the second priority are both based on a monotonically increasing function.

6. The method of claim 5, wherein the monotonically increasing function determines one or more of:

an amount of time taken by a robot while traveling on its route and a route-start value indicating a number of robots that have started on their routes since a robot started on the route.

7. The method of claim 1, wherein the first route comprises a sequence of lanes and corresponding wait times that lead the first robot from a starting location to a destination location.

8. The method of claim 1, further comprising:

determining a presence of an obstacle on the first route that blocks the first robot; and

after determining the presence of the obstacle on the first route that blocks the first robot;

generating a warning message indicating the presence of the obstacle, and

determining a new route for the first robot that avoids the obstacle.

9. The method of claim 1, wherein a third route of a third robot overlaps an overlapping portion of the route that has been reserved for the first robot, and wherein the method further comprises:

determining whether a third priority of the third robot is less than the first priority;

after determining that the third priority is less than the first priority, determining whether the third robot is at a position to traverse the overlapping portion before the first robot reaches the overlapping portion; and

after determining that the third robot is at the position to traverse the overlapping portion before the first robot reaches the overlapping portion, instructing the third robot to traverse the overlapping portion before the first robot reaches the overlapping portion.

10. The method of claim 1, wherein the first conflict region is reserved for exclusive use by the first robot and wherein altering the second route to prevent the second robot from blocking the first robot on the first lane comprises:

releasing a first reservation of the first conflict region for exclusive use by the first robot;

after releasing the first reservation of the first conflict region, obtaining a second reservation of the first conflict region for exclusive use by the second robot;

after obtaining the second reservation, instructing the second robot to leave the first edge and enter the first conflict region; and

after the second robot has traversed the first conflict region;

releasing the second reservation; and

obtaining a third reservation of the first conflict region for exclusive use by the first robot.

11. The method of claim 10, further comprising:

after the second robot has traversed the first conflict region, instructing the second robot to continue to a destination location via the second route.

12. The method of claim 1, wherein altering the second route for the second robot to avoid blocking the first lane comprises instructing the second robot to wait on a particular lane of the plurality of lanes.

13. The method of claim 1, wherein determining the first route through the environment comprises reserving a second conflict region along the first route for exclusive use by the first robot, and wherein the second conflict region lies between two or more lanes.

14. The method of claim 13, wherein the second conflict region comprises an intersection between two lanes.

15. The method of claim 13, wherein an unannotated portion of the roadmap is not annotated by the one or more lanes, and wherein the second conflict region comprises the unannotated portion of the roadmap.

16. A computing device, comprising:

one or more processors; and

data storage including at least computer-executable instructions stored thereon that, when executed by the one or more processors, cause the computing device to;

receive a roadmap of an existing environment that includes a first robot and a second robot;

annotate the roadmap with a plurality of lanes connecting a plurality of conflict regions, wherein each lane is unidirectional and ends sufficiently distant from a conflict region to avoid blocking the conflict region, wherein the roadmap is annotated with a cycle of lanes such that the cycle contains a path between any pair of lanes of the cycle;

determine a first route through the environment along the roadmap for use by the first robot and a second route through the environment along the roadmap for use by the second robot, wherein both the first route and the second route include a first lane, and wherein the first lane connects to a first conflict region;

assign a first priority to the first robot and a second priority to the second robot, wherein the first priority is initially higher than the second priority;

determine that the second robot following the second route will cause the second robot to block the first robot on the first lane before the first robot reaches the first conflict region;

based on the first priority being higher than the second priority, alter the second route to prevent the second robot by causing the second robot to travel through the cycle of lanes from blocking the first robot on the first lane, wherein causing the second robot to travel through the cycle of lanes comprises causing the second robot to return to the first lane with an increased priority from the second priority; and

reset the first priority after the first robot completes the first route such that the second priority is higher than the first priority after the first robot completes the first route and before the second robot completes the second route.

17. The computing device of claim 16, wherein the first conflict region is reserved for exclusive use by the first robot, and wherein altering the second route to prevent the second robot from blocking the first robot on the first lane comprises:

releasing a first reservation of the first conflict region for exclusive use by the first robot;

after releasing the first reservation of the first conflict region, obtaining a second reservation of the first conflict region for exclusive use by the second robot;

after obtaining the second reservation, instructing the second robot to leave the first edge and enter the first conflict region; and

after the second robot has traversed the first conflict region;

releasing the second reservation; and

obtaining a third reservation of the first conflict region for exclusive use by the first robot.

18. A non-transitory computer readable medium having stored thereon instructions, that when executed by one or more processors of a computing device, cause the computing device to:

receive a roadmap of an existing environment that includes a first robot and a second robot;

annotate the roadmap with a plurality of lanes connecting a plurality of conflict regions, wherein each lane is unidirectional and ends sufficiently distant from a conflict region to avoid blocking the conflict region, wherein the roadmap is annotated with a cycle of lanes such that the cycle contains a path between any pair of lanes of the cycle;

determine a first route through the environment along the roadmap for use by the first robot and a second route through the environment along the roadmap for use by the second robot, wherein both the first route and the second route include a first lane, and wherein the first lane connects to a first conflict region;

assign a first priority to the first robot and a second priority to the second robot, wherein the first priority is initially higher than the second priority;

determine that the second robot following the second route will cause the second robot to block the first robot on the first lane before the first robot reaches the first conflict region;

based on the first priority being higher than the second priority, alter the second route by causing the second robot to travel through the cycle of lanes to prevent the second robot from blocking the first robot on the first lane, wherein causing the second robot to travel through the cycle of lanes comprises causing the second robot to return to the first lane with an increased priority from the second priority; and

reset the first priority after the first robot completes the first route such that the second priority is higher than the first priority after the first robot completes the first route and before the second robot completes the second route.