Roadmap Annotation for Deadlock-Free Multi-Agent Navigation
First Claim
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;
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 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; and
based on the first priority being higher than the second priority, altering the second route to prevent the second robot from blocking the first robot on the first lane.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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; 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 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; and based on the first priority being higher than the second priority, altering the second route to prevent the second robot from blocking the first robot on the first lane. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. 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; 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 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; and based on the first priority being higher than the second priority, alter the second route to prevent the second robot from blocking the first robot on the first lane. - View Dependent Claims (19)
-
-
20. 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; 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 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; and based on the first priority being higher than the second priority, alter the second route to prevent the second robot from blocking the first robot on the first lane.
-
Specification