# US 2018/0321675 A1 · Roadmap Segmentation for Robotic Device Coordination > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0321675 A1 - Document ID: US20180321675A1 - Status: Published application - Kind: A1 - Application number: 16/025,231 - Filed: 2018-07-02 - Published: 2018-11-08 - Earliest claimed: 2016-08-08 - Assignees: X Development LLC - Applicants: X Development LLC - Inventors: Jared Russell; Geoffrey Lalonde - Web page: https://patentgrep.com/patent/US20180321675A1 ## CPC - G08G 1/166: {for active traffic, e.g. moving vehicles, pedestrians, bikes} - B60W 30/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 - G01C 21/206: {specially adapted for indoor navigation} - G01C 21/3819: {Road shape data, e.g. outline of a route} - G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles} - G05D 1/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - 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)} - G05D 1/0293: {Convoy travelling} - G08G 1/207: {with respect to certain areas, e.g. forbidden or allowed areas with possible alerting when inside or outside boundaries} - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) - B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES ## 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. ## Claims ### Claim 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; 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 follow a preceding robotic device using at least one sensor on the robotic device when the robotic device is in an edge non-interaction region, and wherein the instructions cause the robotic device to request permission before entering an edge interaction region. ### Claim 2 (depends on 1) The method of claim 1, wherein the traversal regions of the two robotic devices correspond to footprints of the two robotic devices. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) The method of claim 1, further comprising providing a minimum following distance to the robotic device for travel within each edge non-interaction region. ### Claim 6 (depends on 1) The method of claim 1, further comprising providing a maximum velocity to the robotic device for travel within each edge interaction region. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 9) 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. ### Claim 11 (depends on 9) The method of claim 9, wherein the robotic device is associated with a convoy of mobile robotic devices, the method further comprising causing the robotic device to: 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. ### Claim 12 (depends on 1) 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. ### Claim 13 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; 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 follow a preceding robotic device using at least one sensor on the robotic device when the robotic device is in an edge non-interaction region, and wherein the instructions cause the robotic device to request permission before entering an edge interaction region. ### Claim 14 (depends on 13) The computing device of claim 13, 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. ### Claim 15 (depends on 14) The computing device of claim 14, wherein the user interface enables setting of a maximum velocity for robots within the plurality of edge interaction regions. ### Claim 16 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 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; 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 follow a preceding robotic device using at least one sensor on the robotic device when the robotic device is in an edge non-interaction region, and wherein the instructions cause the robotic device to request permission before entering an edge interaction region. ### Claim 17 (depends on 16) The non-transitory computer readable medium of claim 16, wherein the traversal regions of the two robotic devices correspond to footprints of the two robotic devices. ### Claim 18 (depends on 16) The non-transitory computer readable medium of claim 16, the functions further comprising: receiving the roadmap; and 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. ### Claim 19 (depends on 16) The non-transitory computer readable medium of claim 16, 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. ### Claim 20 (depends on 16) The non-transitory computer readable medium of claim 16, wherein the functions further comprise providing a minimum following distance to the robotic device for travel within each edge non-interaction region.