Route guidance system

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.

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.