Roadmap segmentation for robotic device coordination

Patent metadata

Field	Value
Publication number	US-11145206-B2
Application number	US-201816025231-A
Country	US
Kind code	B2
Filing date	Jul 2, 2018
Priority date	Aug 8, 2016
Publication date	Oct 12, 2021
Grant date	Oct 12, 2021

Abstract

Systems and methods related to roadmaps for mobile robotic devices are provided. A computing device can determine a roadmap that includes a first intersection associated with first and second edges. The computing device can determine an edge interaction region (EIR) surrounding the first intersection that includes portions of the first and second edges, where a traversal region on the first edge portion can overlap a traversal region on the second edge portion. The computing device can determine first and second sub-edges of the first edge; the first sub-edge within the EIR and the second sub-edge outside the EIR. The computing device can receive a request to determine a route, determine the route specifying travel along the first sub-edge with a first rule set and along the second sub-edge with a second rule set, and provide the route.

First claim

What is claimed is:

1. A method, comprising:
determining, for a roadmap comprising a plurality of edges, a plurality of edge interaction regions and a plurality of edge non-interaction regions, wherein the plurality of edge interaction regions comprise regions in which traversal regions of two robotic devices on respective edges of the plurality of edges overlap, and wherein the plurality of edge non-interaction regions comprises regions in which traversal regions of two robotic devices on respective edges of the plurality of edges do not interact;
determining, for a robotic device, a route along one or more edges from the plurality of edges of the roadmap; and
providing instructions to cause the robotic device to navigate along the route, wherein the instructions cause the robotic device to use at least one sensor on the robotic device to follow a preceding robotic device along the route when the robotic device is in an edge non-interaction region, wherein the instructions cause the robotic device to request permission before entering an edge interaction region, and wherein the instructions cause the robotic device to navigate along the route without transmitting location information of the robotic device to a controller external to the robotic device.

2. The method of claim 1 , wherein the traversal regions of the two robotic devices correspond to footprints of the two robotic devices.

3. The method of claim 1 , further comprising adding a plurality of intersections to the roadmap, wherein each added intersection corresponds to a point between an edge interaction region and an edge non-interaction region.

4. The method of claim 1 , wherein the instructions cause the robotic device to be controlled by single agent planning software in an edge non-interaction region and by multiple agent planning software before entering an edge interaction region.

5. The method of claim 1 , further comprising providing a minimum following distance to the robotic device for travel within each edge non-interaction region.

6. The method of claim 1 , further comprising providing a maximum velocity to the robotic device for travel within each edge interaction region.

7. The method of claim 1 , wherein the plurality of edges are directed edges, and wherein the route along the one or more edges is based on directions of the one or more edges.

8. The method of claim 1 , further comprising providing instructions to cause at least one other robotic device to follow the robotic device into one or more edge interaction regions as part of a convoy.

9. The method of claim 1 , further comprising determining, for each edge interaction region, a state comprising one of: an available state, an unavailable state, or a deactivating state.

10. The method of claim 9 , further comprising causing the robotic device to:
stop before entering an edge interaction region if the state of the edge interaction region comprises the unavailable state, and
proceed to enter the edge interaction region if the state of the edge interaction region comprises the available state.

11. The method of claim 1 , further comprising providing the roadmap for display on a user interface, wherein the user interface enables modification of the plurality of edge interaction regions.

12. The method of claim 1 , wherein the instructions further cause the robotic device to not use the at least one sensor on the robotic device to follow a preceding robotic device into the edge interaction region prior to receiving permission to enter the edge interaction region.

13. The method of claim 1 , wherein when the robotic device is in an edge interaction region, the instructions cause the robotic device to travel through the edge interaction region without using the at least one sensor on the robotic device to follow a preceding robotic device through the edge interaction region.

14. A method, comprising:
determining, for a roadmap comprising a plurality of edges, a plurality of edge interaction regions and a plurality of edge non-interaction regions, wherein the plurality of edge interaction regions comprise regions in which traversal regions of two robotic devices on respective edges of the plurality of edges overlap, and wherein the plurality of edge non-interaction regions comprises regions in which traversal regions of two robotic devices on respective edges of the plurality of edges do not interact;
determining, for each of the plurality of edge interaction regions, a state comprising one of:
an available state, an unavailable state, or a deactivating state;
determining, for a robotic device, a route along one or more edges from the plurality of edges of the roadmap, wherein the robotic device is associated with a convoy of mobile robotic devices; and
providing instructions to cause the robotic device to:
navigate along the route,
use at least one sensor on the robotic device to follow a preceding robotic device in the convoy of mobile robotic devices along the route when the robotic device is in an edge non-interaction region,
stop before reaching an edge interaction region if the state of the edge interaction region comprises the deactivating state and if robotic devices in the convoy are absent from the edge interaction region; and
proceed to enter the edge interaction region if the state of the edge interaction comprises the deactivating state and if one or more robotic devices of the convoy are present in the edge interaction region.

15. 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 perform functions comprising:
determining, for a roadmap comprising a plurality of edges, a plurality of edge interaction regions and a plurality of edge non-interaction regions, wherein the plurality of edge interaction regions comprise regions in which traversal regions of two robotic devices on respective edges of the plurality of edges overlap, and wherein the plurality of edge non-interaction regions comprises regions in which traversal regions of two robotic devices on respective edges of the plurality of edges do not interact;
determining, for a robotic device, a route along one or more edges from the plurality of edges of the roadmap; and
providing instructions to cause the robotic device to use at least one sensor on the robotic device to follow a preceding robotic device along the route when the robotic device is in an edge non-interaction region, wherein the instructions cause the robotic device to request permission before entering an edge interaction region, and wherein the instructions cause the robotic device to navigate along the route without transmitting location information of the robotic device to a controller external to the robotic device.

16. The computing device of claim 15 , further comprising a user interface, wherein the functions further comprise displaying the roadmap on the user interface, wherein the user interface enables modification of the plurality of edge interaction regions.

17. The computing device of claim 16 , wherein the user interface enables setting of a maximum velocity for robots within the plurality of edge interaction regions.

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 perform functions comprising:
determining, for a roadmap comprising a plurality of edges, a plurality of edge inte

Assignees

• Boston Dynamics Inc

Inventors

• Russell Jared
• Lalonde Geoffrey

Classifications

• G01C21/3819

  Road shape data, e.g. outline of a route · CPC title

• G01C21/3841

  Data obtained from two or more sources, e.g. probe vehicles · CPC title

• G01C21/206

  specially adapted for indoor navigation · CPC title

• B60W30/00

  Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units · CPC title

• G08G1/207

  with respect to certain areas, e.g. forbidden or allowed areas with possible alerting when inside or outside boundaries · CPC title