Systems and methods for flexible route planning

• US 10,371,537 B1
• Filed: 11/29/2017
• Issued: 08/06/2019
• Est. Priority Date: 11/29/2017
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Wilczynski, Peter, Glidden, Reese
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US15/826,446
• Time in Patent Office: 615 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3605 Destination input or retrieval

Abstract

Systems, methods, and non-transitory computer readable media are provided for flexible route planning. Locations for a planned movement may be obtained. The locations may include at least a starting location and an ending location. A route for the planned movement may be determined. The route may include at least the starting location and the ending location. A composite cost of using the route may be determined. The composite cost may include at least a temporal cost component and a non-temporal cost component. An interface through which the composite cost is accessible may be provided.

Claims

1. A system comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the system to perform;

obtaining locations for a planned movement of multiple vehicles, the locations including at least a first starting location associated with a first vehicle of the multiple vehicles, a second starting location associated with a second vehicle of the multiple vehicles, and an ending location associated with the first and second vehicles of the multiple vehicles;

determining a route for the planned movement of the multiple vehicles, the route including at least the first and second starting locations and the ending location;

determining a composite cost of using the route, the composite cost including at least a temporal cost component and a non-temporal cost component; and

providing an interface through which the composite cost is accessible.

2. The system of claim 1, wherein the locations further include one or more intermediate locations.

3. The system of claim 1, wherein the temporal cost component is determined based on a temporal route graph and the non-temporal cost component is determined based on a two-dimensional non-temporal cost map.

4. The system of claim 1, wherein the temporal cost component reflects an expected time duration to use the route and the non-temporal cost component reflects a measure of a characteristic of an environment through which the route travels.

5. The system of claim 4, wherein the characteristic includes at least one of:

a geographic characteristic, a preference characteristic, a difficulty characteristic, or a risk characteristic.

6. The system of claim 1, wherein the route includes multiple modes of motion along the route.

7. The system of claim 1, wherein the interface enables creation of a new path for the route based on a change to an environment through which the route travels.

8. A method implemented by a computing system including one or more processors and storage media storing machine-readable instructions, wherein the method is performed using the one or more processors, the method comprising:

obtaining locations for a planned movement of multiple vehicles, the locations including at least a first starting location associated with a first vehicle of the multiple vehicles, a second starting location associated with a second vehicle of the multiple vehicles, and an ending location associated with the first and second vehicles of the multiple vehicles;

determining a route for the planned movement of the multiple vehicles, the route including at least the first and second starting locations and the ending location;

determining a composite cost of using the route, the composite cost including at least a temporal cost component and a non-temporal cost component; and

providing an interface through which the composite cost is accessible.

9. The method of claim 8, wherein the locations further include one or more intermediate locations.

10. The method of claim 8, wherein the temporal cost component is determined based on a temporal route graph and the non-temporal cost component is determined based on a two-dimensional non-temporal cost map.

11. The method of claim 8, wherein the temporal cost component reflects an expected time duration to use the route and the non-temporal cost component reflects a measure of a characteristic of an environment through which the route travels.

12. The method of claim 11, wherein the characteristic includes at least one of:

a geographic characteristic, a preference characteristic, a difficulty characteristic, or a risk characteristic.

13. The method of claim 8, wherein the route includes multiple modes of motion along the route.

14. The method of claim 8, wherein the interface enables creation of a new path for the route based on a change to an environment through which the route travels.

15. A non-transitory computer readable medium comprising instructions that, when executed, cause one or more processors to perform:

obtaining locations for a planned movement of multiple vehicles, the locations including at least a first starting location associated with a first vehicle of the multiple vehicles, a second starting location associated with a second vehicle of the multiple vehicles, and an ending location associated with the first and second vehicles of the multiple vehicles;

determining a route for the planned movement of the multiple vehicles, the route including at least the first and second starting locations and the ending location;

determining a composite cost of using the route, the composite cost including at least a temporal cost component and a non-temporal cost component; and

providing an interface through which the composite cost is accessible.

16. The non-transitory computer readable medium of claim 15, wherein the locations further include one or more intermediate locations.

17. The non-transitory computer readable medium of claim 15, wherein the temporal cost component is determined based on a temporal route graph and the non-temporal cost component is determined based on a two-dimensional non-temporal cost map.

18. The non-transitory computer readable medium of claim 15, wherein the temporal cost component reflects an expected time duration to use the route and the non-temporal cost component reflects a measure of a characteristic of an environment through which the route travels.

19. The non-transitory computer readable medium of claim 18, wherein the characteristic includes at least one of:

a geographic characteristic, a preference characteristic, a difficulty characteristic, or a risk characteristic.

20. The non-transitory computer readable medium of claim 15, wherein the interface enables creation of a new path for the route based on a change to an environment through which the route travels.