# US 12,111,170 B1 · Model-based routing 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 12,111,170 B1 - Document ID: US12111170B1 - Status: Granted - Kind: B1 - Application number: 16/436,165 - Filed: 2019-06-10 - Granted: 2024-10-08 - Earliest claimed: 2019-06-10 - Assignees: Waymo LLC - Applicants: Waymo LLC - Inventors: Ajay Joshi; Joshua Herbach; Igor Tufanov; Xiang Gao; Dietmar Ebner - Web page: https://patentgrep.com/patent/US12111170B1 ## CPC - G01C 21/3492: {employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968)} - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - G05D 1/0061: {for transition from automatic pilot to manual pilot and vice versa} - G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)} - G05D 1/0217: {in accordance with energy consumption, time reduction or distance reduction criteria} - G08G 1/167: {Driving aids for lane monitoring, lane changing, e.g. blind spot detection} - 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 - 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 Aspects of the disclosure provide for the selection of a route for a vehicle having an autonomous driving mode. For instance, an initial location of the vehicle may be identified. This location may be used to determine a set of possible routes to a destination location. A cost for each route of the plurality is determined by inputting time of day information, map information, and details of that route into one or more models in order to determine whether the vehicle is likely to be stranded along that route and assessing the cost based at least in part on the determination of whether the vehicle is likely to be stranded along that route. One of the routes of the set of possible routes may be selected based on any determined costs. The vehicle may be controlled in the autonomous driving mode using the selected one. ## Claims ### Claim 1 A method of selecting a route for a vehicle having an autonomous driving mode, the method comprising: identifying, by one or more processors, an initial location; using, by the one or more processors, the initial location to determine a set of possible routes to a destination location; determining, by the one or more processors, a cost for each route of the set of possible routes by: inputting time of day information, map information, and details of the route into one or more models, determining, by the one or more models based on the inputting, a first binary indication of whether the vehicle is likely to become stranded along the route for at least a predetermined amount of time without progressing along the route, wherein the first binary indication has a value of 1 when the vehicle is likely to become stranded, and the first binary indication has a value of 0 when the vehicle is not likely to become stranded, and assessing the cost based at least in part on the first binary indication; selecting, by the one or more processors, one of the routes of the set of possible routes based on one or more of the determined costs; and controlling, by the one or more processors, the vehicle in the autonomous driving mode using the selected one of the routes. ### Claim 2 (depends on 1) The method of claim 1, wherein the time of day information indicates whether the vehicle is currently in a high traffic time or a low traffic time. ### Claim 3 (depends on 1) The method of claim 1, wherein the vehicle is likely to become stranded along the route for at least the predetermined amount of time without progressing along the route due to at least one of yielding to traffic or an occlusion, waiting for a passenger during pickup or drop off, or stopping for a traffic light. ### Claim 4 (depends on 1) The method of claim 1, wherein inputting the time of day information, the map information, and the details of the route into the one or more models provides an indication whether the vehicle is likely to disengage from the autonomous driving mode, such that a driver must take control of the vehicle, along the route. ### Claim 5 (depends on 4) The method of claim 4, wherein the one or more models provide a second binary indication of whether the vehicle is likely to disengage along the route, and assessing the cost is further based on the second binary indication. ### Claim 6 (depends on 1) The method of claim 1, wherein the details of the route include an estimated duration for a lane change and determining the cost of the route further includes inputting the estimated duration for the lane change into the one or more models in order to determine whether the vehicle is likely to successfully complete the lane change, and wherein assessing the cost is further based on the determination of whether the vehicle is likely to successfully complete the lane change. ### Claim 7 (depends on 6) The method of claim 6, wherein the one or more models provide a second binary indication of whether the vehicle is likely to successfully complete the lane change, and assessing the cost is further based on the second binary indication. ### Claim 8 (depends on 1) The method of claim 1, wherein the details of the route include a turn at an intersection and determining the cost of the route further includes inputting a location of the turn into the one or more models in order to determine whether the turn is likely to be unprotected, and wherein assessing the cost is further based on the determination of whether the turn is likely to be unprotected. ### Claim 9 (depends on 8) The method of claim 8, wherein the one or more models provide a second binary indication of whether the turn will be protected or unprotected, and assessing the cost is further based on the second binary indication. ### Claim 10 (depends on 1) The method of claim 1, wherein the first binary indication has a value of 1 when the vehicle is likely to become stranded, and the first binary indication has a value of 0 when the vehicle is not likely to become stranded. ### Claim 11 (depends on 1) The method of claim 1, wherein the assessed cost is greater when the first binary indication has a value of 1 than when the first binary indication has a value of 0. ### Claim 12 A system for selecting a route for a vehicle having an autonomous driving mode, the system comprising one or more processors configured to: identify a current location of the vehicle; use the current location of the vehicle to determine a set of possible routes to a destination location; determine a cost for each route of the set of possible routes by: inputting time of day information, map information, and details of the route into one or more models, determining, by the one or more models based on the inputting, a first binary indication of whether the vehicle is likely to become stranded along the route for at least a predetermined amount of time without progressing along the route, wherein the first binary indication has a value of 1 when the vehicle is likely to become stranded, and the first binary indication has a value of 0 when the vehicle is not likely to become stranded, and assessing the cost based at least in part on the first binary indication; select one of the routes of the set of possible routes based on one or more of the determined costs; and control the vehicle in the autonomous driving mode using the selected one of the routes. ### Claim 13 (depends on 12) The system of claim 12, wherein the first binary indication has a value of 1 when the vehicle is likely to become stranded and the first binary indication has a value of 0 when the vehicle is not likely to become stranded. ### Claim 14 (depends on 12) The system of claim 12, wherein the assessed cost is greater when the first binary indication has a value of 1 than when the first binary indication has a value of 0. ### Claim 15 (depends on 12) The system of claim 12, wherein the vehicle is likely to become stranded along the route for at least the predetermined amount of time without progressing along the route due to at least one of yielding to traffic or an occlusion, waiting for a passenger during pickup or drop off, or stopping for a traffic light. ### Claim 16 (depends on 12) The system of claim 12, wherein inputting the time of day information, the map information, and the details of the route into the one or more models provides an indication whether the vehicle is likely to disengage from the autonomous driving mode, such that a driver must take control of the vehicle, along the route. ### Claim 17 (depends on 16) The system of claim 16, wherein the one or more models provide a second binary indication of whether the vehicle is likely to disengage along the route, and the one or more processors are further configured to assess the cost further based on the second binary indication. ### Claim 18 (depends on 12) The system of claim 12, wherein the details of the route include an estimated duration for a lane change and the one or more processors are configured to determine the cost of the route by inputting the estimated duration into the one or more models in order to determine whether the vehicle is likely to successfully complete the lane change, and the one or more processors are configured to assess the cost further based on the determination of whether the vehicle is likely to successfully complete the lane change. ### Claim 19 (depends on 18) The system of claim 18, wherein the one or more models provide a second binary indication of whether the vehicle is likely to successfully complete the lane change, and the one or more processors are configured to assess the cost further based on the second binary indication. ### Claim 20 (depends on 12) The system of claim 12, wherein the details of the route include a turn at an intersection and the one or more processors are configured to determine the cost of the route by inputting a location of the turn into the one or more models in order to determine whether the turn is likely to be unprotected, and the one or more processors are configured to assess the cost further based on the determination of whether the turn is likely to be unprotected. ### Claim 21 (depends on 20) The system of claim 20, wherein the one or more models provide a second binary indication of whether the turn will be protected or unprotected, and the one or more processors are configured to assess the cost further based on the second binary indication. ### Claim 22 A vehicle having an autonomous driving mode, the vehicle comprising one or more processors configured to: identify a current location of the vehicle; use the current location of the vehicle to determine a set of possible routes to a destination location; determine a cost for each route of the set of possible routes by: inputting time of day information, map information, and details of the route into one or more models, determining, by the one or more models based on the inputting, a first binary indication of whether the vehicle is likely to become stranded along the route for at least a predetermined amount of time without progressing along the route, wherein the first binary indication has a value of 1 when the vehicle is likely to become stranded, and the first binary indication has a value of 0 when the vehicle is not likely to become stranded, and assessing the cost based at least in part on the first binary indication; select one of the routes of the set of possible routes based on one or more of the determined costs; and control the vehicle in the autonomous driving mode using the selected one of the routes.