Roadmap annotation for deadlock-free multi-agent navigation

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.

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.