# US 12,222,210 B1 · Route guidance system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,210 B1 - Document ID: US12222210B1 - Status: Granted - Kind: B1 - Application number: 18/161,512 - Filed: 2023-01-30 - Granted: 2025-02-11 - Earliest claimed: 2018-09-24 - Assignees: Apple Inc. - Applicants: Srichand Pendyala; Marlene Wan; Craig M. Hiller; Lukas M. Marti; Josh Redding - Inventors: Srichand Pendyala; Marlene Wan; Craig M. Hiller; Lukas M. Marti; Josh Redding - Web page: https://patentgrep.com/patent/US12222210B1 ## CPC - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes} - 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) ## Abstract A method includes determining a routing graph based on a map, wherein the routing graph represents locations from the map; determining a routing horizon based on the routing graph, wherein the routing horizon defines a portion of the routing graph that is usable for routing; determining a cost-action structure that includes, for each location of the routing horizon, a cost-to-go value for travel from a respective location from the routing horizon to a destination, wherein the cost-to-go values implicitly describe an optimal route for travel from each of the respective locations from the routing horizon to the destination; receiving, from an autonomous agent, a request that specifies one of the locations from the routing horizon; and providing, to the autonomous agent, information from the cost-action structure based on the specified location from the routing horizon. ## Claims ### Claim 1 A method, comprising: determining a routing graph based on a map; determining a routing horizon based on the routing graph, wherein the routing horizon defines a portion of the routing graph that is usable for routing, and the routing horizon includes locations that are represented by the portion of the routing graph; determining, for each of the locations, an optimal route from the location to a destination using the routing graph and a graph search algorithm; determining, for each of the locations, a cost-to-go value for travel from the location to the destination using the optimal route from the location to the destination; storing the optimal route and the cost-to-go value for each of the locations in a cost-action structure; receiving, from an autonomous agent, a request for information from the cost-action structure, wherein the request from the autonomous agent is received subsequent to storing the optimal route and the cost-to-go value for each of the locations in the cost-action structure; and providing, to the autonomous agent, information from the cost-action structure in response to the request, wherein the information from the cost-action structure includes the cost-to-go value for a first one of the locations, the autonomous agent is configured to determine a control decision based on the cost-to-go value for the first one of the locations, and the autonomous agent is configured to move in accordance with the control decision. ### Claim 2 (depends on 1) The method of claim 1, wherein the request for information from the cost-action structure identifies a current location of the autonomous agent, and the information from the cost-action structure is provided based on the current location of the autonomous agent. ### Claim 3 (depends on 1) The method of claim 1, wherein the request for information from the cost-action structure identifies the first one of the locations. ### Claim 4 (depends on 3) The method of claim 3, wherein the request for information from the cost-action structure identifies a second one of the locations, the information from the cost-action structure includes the cost-to-go value for the second one of the locations, and the autonomous agent is configured to determine the control decision further based on the cost-to-go value for the second one of the locations. ### Claim 5 (depends on 1) The method of claim 1, wherein the request for information from the cost-action structure identifies a proposed action, and the first one of the locations is associated with the proposed action. ### Claim 6 (depends on 1) The method of claim 1, wherein the information from the cost-action structure that is provided to the autonomous agent in response to the request further includes the optimal route from the first one of the locations to the destination. ### Claim 7 (depends on 1) The method of claim 1, wherein the cost-to-go value for each of the locations and the optimal route for each of the locations are not dependent on a current location of the autonomous agent. ### Claim 8 A non-transitory computer-readable storage device including program instructions executable by one or more processors that, when executed, cause the one or more processors to perform operations, the operations comprising: determining a routing graph based on a map; determining a routing horizon based on the routing graph, wherein the routing horizon defines a portion of the routing graph that is usable for routing, and the routing horizon includes locations that are represented by the portion of the routing graph; determining, for each of the locations, an optimal route from the location to a destination using the routing graph and a graph search algorithm; determining, for each of the locations, a cost-to-go value for travel from the location to the destination using the optimal route from the location to the destination; storing the optimal route and the cost-to-go value for each of the locations in a cost-action structure; receiving, from an autonomous agent, a request for information from the cost-action structure, wherein the request from the autonomous agent is received subsequent to storing the optimal route and the cost-to-go value for each of the locations in the cost-action structure; and providing, to the autonomous agent, information from the cost-action structure in response to the request, wherein the information from the cost-action structure includes the cost-to-go value for a first one of the locations, the autonomous agent is configured to determine a control decision based on the cost-to-go value for the first one of the locations, and the autonomous agent is configured to move in accordance with the control decision. ### Claim 9 (depends on 8) The non-transitory computer-readable storage device of claim 8, wherein the request for information from the cost-action structure identifies a current location of the autonomous agent, and the information from the cost-action structure is provided based on the current location of the autonomous agent. ### Claim 10 (depends on 8) The non-transitory computer-readable storage device of claim 8, wherein the request for information from the cost-action structure identifies the first one of the locations. ### Claim 11 (depends on 10) The non-transitory computer-readable storage device of claim 10, wherein the request for information from the cost-action structure identifies a second one of the locations, the information from the cost-action structure includes the cost-to-go value for the second one of the locations, and the autonomous agent is configured to determine the control decision further based on the cost-to-go value for the second one of the locations. ### Claim 12 (depends on 8) The non-transitory computer-readable storage device of claim 8, wherein the request for information from the cost-action structure identifies a proposed action, and the first one of the locations is associated with the proposed action. ### Claim 13 (depends on 8) The non-transitory computer-readable storage device of claim 8, wherein the information from the cost-action structure that is provided to the autonomous agent in response to the request further includes the optimal route from the first one of the locations to the destination. ### Claim 14 (depends on 8) The non-transitory computer-readable storage device of claim 8, wherein the cost-to-go value for each of the locations and the optimal route for each of the locations are not dependent on a current location of the autonomous agent. ### Claim 15 A system, comprising: one or more memory devices; and one or more processors configured to execute instructions stored in the one or more memory devices to: determine a routing graph based on a map; determine a routing horizon based on the routing graph, wherein the routing horizon defines a portion of the routing graph that is usable for routing, and the routing horizon includes locations that are represented by the portion of the routing graph; determine, for each of the locations, an optimal route from the location to a destination using the routing graph and a graph search algorithm; determine, for each of the locations, a cost-to-go value for travel from the location to the destination using the optimal route from the location to the destination; store the optimal route and the cost-to-go value for each of the locations in a cost-action structure; receive, from an autonomous agent, a request for information from the cost-action structure, wherein the request from the autonomous agent is received subsequent to storing the optimal route and the cost-to-go value for each of the locations in the cost-action structure; and provide, to the autonomous agent, information from the cost-action structure in response to the request, wherein the information from the cost-action structure includes the cost-to-go value for a first one of the locations, the autonomous agent is configured to determine a control decision based on the cost-to-go value for the first one of the locations, and the autonomous agent is configured to move in accordance with the control decision. ### Claim 16 (depends on 15) The system of claim 15, wherein the request for information from the cost-action structure identifies a current location of the autonomous agent, and the information from the cost-action structure is provided based on the current location of the autonomous agent. ### Claim 17 (depends on 15) The system of claim 15, wherein the request for information from the cost-action structure identifies the first one of the locations. ### Claim 18 (depends on 17) The system of claim 17, wherein the request for information from the cost-action structure identifies a second one of the locations, the information from the cost-action structure includes the cost-to-go value for the second one of the locations, and the autonomous agent is configured to determine the control decision further based on the cost-to-go value for the second one of the locations. ### Claim 19 (depends on 15) The system of claim 15, wherein the request for information from the cost-action structure identifies a proposed action, and the first one of the locations is associated with the proposed action. ### Claim 20 (depends on 15) The system of claim 15, wherein the information from the cost-action structure that is provided to the autonomous agent in response to the request further includes the optimal route from the first one of the locations to the destination. ### Claim 21 (depends on 15) The system of claim 15, wherein the cost-to-go value for each of the locations and the optimal route for each of the locations are not dependent on a current location of the autonomous agent.