# US 11,307,590 B2 · Systems and methods for overlap-aware ranking of navigation avoidance areas for autonomous vehicles > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,307,590 B2 - Document ID: US11307590B2 - Status: Granted - Kind: B2 - Application number: 16/457,986 - Filed: 2019-06-29 - Published: 2020-12-31 - Granted: 2022-04-19 - Earliest claimed: 2019-06-29 - Assignees: GM Cruise Holdings LLC - Applicants: GM Cruise Holdings LLC - Inventors: Alexander John Bowe; Lucio Otavio Marchioro Rech - Web page: https://patentgrep.com/patent/US11307590B2 ## CPC - G05D 1/0214: {in accordance with safety or protection criteria, e.g. avoiding hazardous areas (monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13)} - G01C 21/3461: {Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries} - G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G05D 1/228: Command input arrangements located on-board unmanned vehicles - G05D 1/246: using environment maps, e.g. simultaneous localisation and mapping [SLAM] - G05D 1/617: Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards (arrangements for controlling the position or course of two or more vehicles for avoiding collisions therebetween G05D1/693; arrangements for reacting to or preventing system or operator failure G05D1/80) - G06F 16/24578: {using ranking} - G06F 16/29: Geographical information databases - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G08G 1/015: with provision for distinguishing between two or more types of vehicles, e.g. between motor-cars and cycles - G08G 1/096827: {where the route is computed onboard} - G08G 1/207: {with respect to certain areas, e.g. forbidden or allowed areas with possible alerting when inside or outside boundaries} - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - 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) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - 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}) ## Abstract A computing system that analyzes the network effects of avoidance areas on autonomous vehicle routing is described herein. The computing system includes a data store that comprises a set of avoidance areas through which the autonomous vehicle is prohibited from being routed. A grouping system identifies groups of avoidance areas. A graph construction system constructs a graph representation of the avoidance area groups. A ranking algorithm is evaluated over the graph representation to generate a ranking of the avoidance area groups by relative impact on routing metrics for routes through an operational area of the autonomous vehicle. A mapping vehicle can be dispatched to resolve avoidance areas in avoidance area groups indicating in the ranking as having a greater impact on routing metrics than other avoidance area groups. ## Claims ### Claim 1 A computing system, comprising: a data store, the data store comprising a set of avoidance areas, wherein an avoidance area specifies a geographic area through which autonomous vehicles are prohibited from being routed; at least one processor; and memory that stores computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts comprising: receiving data indicative of a plurality of avoidance area groups, each of the avoidance area groups comprising at least one avoidance area in the set of avoidance areas, wherein a first avoidance area group in the avoidance area groups shares at least one avoidance area with a second avoidance area group in the avoidance area groups; constructing a graph representation of the plurality of avoidance area groups, the graph comprising: vertices, wherein each vertex is representative of a different avoidance area group in the avoidance area groups; and edges, each edge in the edges connecting two respective vertices in the vertices, each of the edges being assigned a respective weight, the weight of an edge in the edges being based upon a number of avoidance areas shared between the avoidance area groups represented by the vertices connected by the edge; generating a ranking of the avoidance area groups based upon the graph representation, the ranking indicative of relative impacts of the avoidance area groups on routing metrics for a set of routes through an operational area of an autonomous vehicle; and issuing a dispatch instruction to an autonomous vehicle (AV) based upon the ranking of the avoidance area groups, the dispatch instruction configured to cause the AV to navigate to an avoidance area and to perform a mapping operation in the avoidance area, wherein the avoidance area is included in an avoidance area group in the plurality of avoidance area groups. ### Claim 2 (depends on 1) The computing system of claim 1, the acts further comprising: generating the plurality of avoidance area groups based upon the set of avoidance areas. ### Claim 3 (depends on 2) The computing system of claim 2, wherein the generating the plurality of avoidance area groups is based upon the set of routes through the operational area or a second set of routes through the operational area. ### Claim 4 (depends on 2) The computing system of claim 2, wherein the generating the plurality of avoidance area groups is based upon distances between the avoidance areas. ### Claim 5 (depends on 1) The computing system of claim 1, each of the vertices being assigned a respective weight, wherein a first weight assigned to a first vertex that is representative of a first avoidance area group is based upon impact scores of the first avoidance area group with respect to the set of routes through the operational area. ### Claim 6 (depends on 5) The computing system of claim 5, the acts further comprising computing a first impact score in the impact scores based upon a difference between a routing metric for a first route that passes through the first avoidance area group and the routing metric for a second route that does not pass through the first avoidance area group, the first route being included in the set of routes. ### Claim 7 (depends on 5) The computing system of claim 5, wherein the first weight is a mean of the impact scores. ### Claim 8 (depends on 1) The computing system of claim 1, wherein the edges are undirected edges, the weights of the edges being the number of shared avoidance areas between the avoidance area groups represented by the vertices connected by the edges. ### Claim 9 (depends on 1) The computing system of claim 1, wherein the edges are directed edges, a first weight assigned to a first edge in the edges being based upon the number of avoidance areas in one of the vertices connected by the first edge the number of avoidance areas shared by the avoidance area groups represented by the vertices connected by the first edge. ### Claim 10 (depends on 9) The computing system of claim 9, the first weight being the number of avoidance areas shared by the avoidance area groups represented by the vertices connected by the first edge divided by the number of avoidance areas in one of the vertices connected by the first edge. ### Claim 11 (depends on 1) The computing system of claim 1, wherein generating the ranking of the avoidance area groups comprises computing, for each of the vertices, a rank value. ### Claim 12 (depends on 11) The computing system of claim 11, wherein the computing the rank value for each of the vertices is based upon the weights assigned to the edges and weights assigned to the vertices. ### Claim 13 (depends on 1) The computing system of claim 1, wherein generating the ranking of the avoidance area groups comprises executing a PageRank algorithm over the graph to determine a PageRank value for each of the vertices. ### Claim 14 A method for generating a prioritized order for resolution of avoidance areas in an operational area of an autonomous vehicle, the method comprising: identifying a plurality of avoidance area groups based upon a set of avoidance areas, the avoidance areas specifying geographic areas through which autonomous vehicles are prohibited from being routed, each of the avoidance area groups comprising at least one avoidance area in the set of avoidance areas, wherein a first avoidance area group in the avoidance area groups shares at least one avoidance area with a second avoidance area group in the avoidance area groups, wherein the avoidance area groups are identified based upon distances between the avoidance areas; constructing a graph representation of the plurality of avoidance area groups, the graph comprising: vertices, wherein each vertex is representative of a different avoidance area group in the avoidance area groups; and edges, each edge in the edges connecting two respective vertices in the vertices; and generating a ranking of the avoidance area groups based upon the graph representation, the ranking indicative of relative impacts of the avoidance area groups on routing metrics for a set of routes through an operational area of an autonomous vehicle; and issuing a dispatch instruction to an autonomous vehicle (AV) based upon the ranking of the avoidance area groups, the dispatch instruction configured to cause the AV to navigate to an avoidance area and to perform a mapping operation in the avoidance area, wherein the avoidance area is included in an avoidance area group in the plurality of avoidance area groups. ### Claim 15 (depends on 14) The method of claim 14, wherein generating the ranking of the avoidance area groups comprises computing a PageRank score for each of the avoidance area groups based upon the graph representation, wherein the ranking of the avoidance areas is based upon the PageRank scores. ### Claim 16 (depends on 14) The method of claim 14, wherein the plurality of avoidance area groups are identified based further upon the set of routes through the operational area or a second set of routes through the operational area. ### Claim 17 (depends on 14) The method of claim 14, each of the edges being assigned a respective weight, the weight of an edge in the edges being based upon a number of avoidance areas shared between the avoidance area groups represented by the vertices connected by the edge. ### Claim 18 A computer-readable storage medium having computer-executable instructions stored thereon, wherein the computer-executable instructions, when executed by a processor, cause the processor to perform acts comprising: receiving a set of avoidance areas, wherein the avoidance areas identify geographic areas through which autonomous vehicles are prohibited from being routed identifying a plurality of avoidance area groups based upon a set of routes through an operational area of an autonomous vehicle, each of the avoidance area groups comprising at least one avoidance area in the set of avoidance areas, wherein a first avoidance area group in the avoidance area groups shares at least one avoidance area with a second avoidance area group in the avoidance area groups; constructing a graph representation of the plurality of avoidance area groups, the graph comprising: vertices, wherein each vertex is representative of a different avoidance area group in the avoidance area groups; and edges, each edge in the edges connecting two respective vertices in the vertices, each of the edges being assigned a respective weight, the weight of an edge in the edges being based upon a number of avoidance areas shared between the avoidance area groups represented by the vertices connected by the edge; generating a ranking of the avoidance area groups based upon the graph representation, the ranking indicative of relative impacts of the avoidance area groups on routing metrics for a set of routes through an operational area of an autonomous vehicle; and issuing a dispatching instruction to an autonomous vehicle based upon the ranking of the avoidance area groups, the dispatching instruction configured to cause the autonomous vehicle to navigate to an avoidance area and perform a mapping operation with respect to the avoidance area. ### Claim 19 (depends on 18) The computer-readable storage medium of claim 18, wherein the generating the ranking of the avoidance area groups comprises executing a PageRank algorithm over the graph representation of the avoidance area groups. ### Claim 20 (depends on 18) The computer-readable storage medium of claim 18, wherein the avoidance area groups are identified based upon distances between the avoidance areas.