Systems and methods for distance and congestion-aware resource deployment

• US 9,361,793 B2
• Filed: 06/11/2014
• Issued: 06/07/2016
• Est. Priority Date: 10/24/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Curtis, Spike, Janatpour, Dustin, Bailey, Drew
• Primary Examiner(s): Buttram, Todd
• Application Number:
  US14/302,279
• Publication Number:
  US 20150120176A1
• Time in Patent Office: 727 Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 50/26 Government or public services business processes related to the transportation industry G06Q50/40
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G08G 1/00 Traffic control systems for road vehicles arrangement of road signs or traffic signals E01F9/00 ; automatic vehicle control B62D
• CPC Class Codes: G08G 1/205 Indicating the location of the monitored vehicles as destination, e.g. accidents, stolen, rental

Abstract

Computer-implemented systems and methods are disclosed for distance and congestion-aware resource deployment. In some embodiments, a method is provided to estimate a vehicle deployment region. The method includes constructing a graph data structure using at least in part a single invocation of a form of Dijkstra'"'"'s algorithm. The method additionally includes partitioning an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of the vehicle. The method also includes selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location, and wherein each selected geographical location was determined, using the graph data structure, to be reachable from the vehicle location within a specified maximum cost. The method further includes forming a polygon representing a vehicle deployment region from the selected geographical locations.

Claims

1. A method for estimating a vehicle deployment region, the method comprising the following operations performed by one or more processors:

partitioning an angular space centered on a vehicle location into a plurality of angular space regions;

selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, each selected geographical location being reachable from the vehicle location within a specified maximum cost;

forming a polygon representing a region from the selected geographical locations, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location; and

presenting information concerning the region to a user.

2. The method of claim 1, wherein each geographical location is determined using a graph data structure.

3. The method of claim 2, wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.

4. The method of claim 3, wherein the graph data structure reflects restrictions imposed by local traffic rules.

5. The method of claim 4, wherein the graph data structure is constructed using a truncated form of Dijkstra'"'"'s algorithm.

6. The method of claim 5, wherein an origin node within the plurality of nodes represents a street intersection nearest to the current or potential location of a vehicle.

7. The method of claim 6, wherein edges connect the nodes in the graph data structure and represent street segments.

8. The method of claim 7, further comprising:

assigning traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.

9. The method of claim 8, wherein the traversal cost of an edge is based at least in part on the time it would take to traverse a street segment corresponding to the edge.

10. The method of claim 8, wherein the street-level data includes real-time traffic data.

11. The method of claim 8, wherein the street-level data includes information representing a current average traffic speed for each street segment.

12. The method of claim 1, wherein presenting information concerning the estimated vehicle deployment region comprises:

displaying the polygon by overlaying it on a map at the vehicle'"'"'s current or potential deployment location.

13. A system for estimating a vehicle deployment region, the system comprising:

a memory device that stores a set of instructions; and

at least one processor that executes the set of instructions to perform the following operations;

partition an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of a vehicle;

select, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, each selected geographical location being reachable from the vehicle location within a specified maximum cost;

form a polygon representing a vehicle deployment region from the selected geographical locations, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location; and

present, based on the polygon, information concerning the estimated vehicle deployment region to a user.

14. The system of claim 13, wherein each geographical location is determined using a data graph structure.

15. The system of claim 14, wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.

16. The system of claim 15, wherein the graph data structure reflects restrictions imposed by local traffic rules.

17. The system of claim 16, wherein the graph data structure is constructed using a truncated form of Dijkstra'"'"'s algorithm.

18. The system of claim 17, wherein edges connect the nodes in the graph data structure and represent street segments.

19. The system of claim 18, wherein the set of instructions further cause the at least one processor to:

assign traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.

20. The system of claim 19, wherein the traversal cost of an edge is based at least in part on the time it would take to traverse a street segment corresponding to the edge.

21. The system of claim 20, wherein the street-level data includes information representing a current average traffic speed for each street segment.

22. The system of claim 13, wherein the set of instructions further cause the at least one processor to:

display the polygon by overlaying it on a map at the vehicle'"'"'s current or potential vehicle deployment location.

23. A non-transitory computer-readable medium storing a set of instructions that are executable by one or more processors to cause the one or more processors to perform a method for estimating a vehicle deployment region, the method comprising:

partitioning an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of a vehicle;

selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, each selected geographical location being reachable from the vehicle location within a specified maximum cost;

forming a polygon representing a vehicle deployment region from the selected geographical locations, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location; and

presenting, based on the polygon, information concerning the estimated vehicle deployment region to a user.

24. The computer-readable medium of claim 23, wherein each geographical location is determined using a graph data structure.

25. The computer-readable medium of claim 24, wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.

26. The computer-readable medium of claim 25, wherein the graph data structure reflects restrictions imposed by local traffic rules.

27. The computer-readable medium of claim 26, wherein the graph data structure is constructed using a truncated form of Dijkstra'"'"'s algorithm.

28. The computer-readable medium of claim 27, wherein an origin node within the plurality of nodes represents a street intersection nearest to the current or potential location of a vehicle.

29. The computer-readable medium of claim 28, wherein edges connect the nodes in the graph data structure and represent street segments.

30. The computer-readable medium of claim 29, wherein the instructions further cause the one or more processors to assign traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.

31. The computer-readable medium of claim 30, wherein the traversal cost of an edge is based at least in part on the time it would take to traverse a street segment corresponding to the edge.

32. The computer-readable medium of claim 30, wherein the street-level data includes real-time traffic data.

33. The computer-readable medium of claim 30, wherein the street-level data includes information representing a current average traffic speed for each street segment.

34. The computer-readable medium of claim 30, wherein presenting information concerning the estimated vehicle deployment region comprises:

displaying the polygon by overlaying it on a map at the vehicle'"'"'s current or potential deployment location.