# US 11,441,913 B2 · Autonomous vehicle waypoint routing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,441,913 B2 - Document ID: US11441913B2 - Status: Granted - Kind: B2 - Application number: 16/173,633 - Filed: 2018-10-29 - Published: 2020-02-20 - Granted: 2022-09-13 - Earliest claimed: 2018-08-20 - Assignees: Uatc, LLC - Applicants: Uatc, LLC - Inventors: Bryan John Nagy; Xiaodong Zhang; Brett Bavar; Misna Sameer - Web page: https://patentgrep.com/patent/US11441913B2 ## CPC - G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)} - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)} - G05D 1/0221: {involving a learning process} - 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 Various examples are directed to systems and methods for navigating an autonomous vehicle. Trip plan data may describe a plurality of candidate vehicle start points, a plurality of candidate waypoints, and a plurality of candidate vehicle end points. A plurality of candidate routes may be determined between an algorithm start point and an algorithm end point. Each candidate route of the plurality of candidate routes may include at least one of the plurality of candidate waypoints and at least one of the plurality of candidate vehicle end points. A best rate may be determined using the plurality of candidate routes. The best route may include a first candidate vehicle start point, a first candidate waypoint, and a first candidate vehicle end point. The autonomous vehicle may be controlled along the best route from the first candidate vehicle start point towards the first candidate vehicle end point. ## Claims ### Claim 1 An autonomous vehicle system comprising: at least one processor; and a storage device storing instructions that, when executed by the at least one processor, causes the at least one processor to perform operations comprising: accessing trip plan data describing a plurality of candidate vehicle start points, a plurality of candidate waypoints, and a plurality of candidate vehicle end points; determining a plurality of candidate routes between an algorithm start point and an algorithm end point, wherein each candidate route of the plurality of candidate routes includes at least one of the plurality of candidate waypoints and at least one of the plurality of candidate vehicle end points, the determining of the plurality of candidate routes comprising: determining a first candidate route of the plurality of candidate routes; storing state data generated from the determining of the first candidate route; and generating a second candidate route of the plurality of candidate routes using the state data; selecting a route from the plurality of candidate routes, the selected route including a first candidate vehicle start point, a first candidate waypoint, and a first candidate vehicle end point; and controlling an autonomous vehicle along the selected route from the first candidate vehicle start point towards the first candidate vehicle end point. ### Claim 2 (depends on 1) The system of claim 1, wherein the first candidate vehicle start point is a current location of the autonomous vehicle. ### Claim 3 (depends on 1) The system of claim 1, wherein determining the selected route comprises determining a selected route between a second stage algorithm start point and a second stage algorithm end point. ### Claim 4 (depends on 1) The system of claim 1, wherein the storage device further stores instructions that, when executed by the at least one processor, causes the at least one processor to perform operations comprising, before determining the selected route, modifying weightings for a plurality of route component costs associated with points prior to the plurality of candidate vehicle start points. ### Claim 5 (depends on 1) The system of claim 1, wherein the first candidate vehicle start point corresponds to a first geographic location and wherein the algorithm start point is non-geographic. ### Claim 6 (depends on 1) The system of claim 1, wherein the storage device further stores instructions that, when executed by the at least one processor, causes the at least one processor to perform operations comprising: accessing a first route component cost between the first candidate vehicle start point and a second point, wherein the first route component cost is based at least in part on an estimated driving time between the first candidate vehicle start point and the second point; and accessing a second route component cost between the algorithm start point and the first candidate vehicle start point, wherein second route component cost is based at least in part on a cost to move an autonomous vehicle payload to the first candidate vehicle start point, and wherein the determining of the plurality of candidate routes is based at least in part on the first route component cost and the second route component cost. ### Claim 7 (depends on 1) The system of claim 1, wherein determining the selected route comprises determining a selected route between a second stage algorithm start point and a second stage algorithm end point, wherein the selected route between the second stage algorithm start point and the second stage algorithm end point comprises a first waypoint of the plurality of candidate waypoints. ### Claim 8 (depends on 7) The system of claim 7, wherein the selecting of the selected route further comprises substituting a portion of the selected route between the second stage algorithm start point and the second stage algorithm end point into a first candidate route of the plurality of candidate routes. ### Claim 9 A method of navigating an autonomous vehicle, comprising: accessing trip plan data describing a plurality of candidate vehicle start points, a plurality of candidate waypoints, and a plurality of candidate vehicle end points; determining a plurality of candidate routes between an algorithm start point and an algorithm end point, wherein each candidate route of the plurality of candidate routes includes at least one of the plurality of candidate waypoints and at least one of the plurality of candidate vehicle end points, the determining of the plurality of candidate routes comprising: determining a first candidate route of the plurality of candidate routes; storing state data generated from the determining of the first candidate route; and generating a second candidate route of the plurality of candidate routes using the state data; selecting a route from the plurality of candidate routes, the selected route including a first candidate vehicle start point, a first candidate waypoint, and a first candidate vehicle end point; and controlling the autonomous vehicle along the selected route from the first candidate vehicle start point towards the first candidate vehicle end point. ### Claim 10 (depends on 9) The method of claim 9, wherein the first candidate vehicle start point is a current location of the autonomous vehicle. ### Claim 11 (depends on 9) The method of claim 9, wherein determining the selected route comprises determining a selected route between a second stage algorithm start point and a second stage algorithm end point. ### Claim 12 (depends on 9) The method of claim 9, further comprising, before determining the selected route, modifying weightings for a plurality of route component costs associated with points prior to the plurality of candidate vehicle start points. ### Claim 13 (depends on 9) The method of claim 9, wherein the first candidate vehicle start point corresponds to a first geographic location and wherein the algorithm start point is non-geographic. ### Claim 14 (depends on 9) The method of claim 9, further comprising: accessing a first route component cost between the first candidate vehicle start point and a second point, wherein the first route component cost is based at least in part on an estimated driving time between the first candidate vehicle start point and the second point; and accessing a second route component cost between the algorithm start point and the first candidate vehicle start point, wherein second route component cost is based at least in part on a cost to move an autonomous vehicle payload to the first candidate vehicle start point, and wherein the determining of the plurality of candidate routes is based at least in part on the first route component cost and the second route component cost. ### Claim 15 (depends on 9) The method of claim 9, wherein determining the selected route comprises determining a selected route between a second stage algorithm start point and a second stage algorithm end point, wherein selected route between the second stage algorithm start point and the second stage algorithm end point comprises a first waypoint of the plurality of candidate waypoints. ### Claim 16 (depends on 15) The method of claim 15, wherein determining the selected route further comprises substituting a portion of the selected route between the second stage algorithm start point and the second stage algorithm end point into a first candidate route of the plurality of candidate routes. ### Claim 17 A method of navigating an autonomous vehicle, comprising: accessing trip plan data describing a directed route comprising a plurality of route components; selecting a route to an algorithm end point, wherein the selected route proceeds from a first route component of the plurality of route components to the algorithm end point; controlling the autonomous vehicle along the selected route towards the first route component; and controlling the autonomous vehicle along the directed route from the first route component. ### Claim 18 (depends on 17) The method of claim 17, wherein determining the selected route to the algorithm end point comprises determining the selected route from an algorithm start point to the algorithm end point.