Method and system for electronically determining dynamic traffic information
First Claim
1. A method of determining a path traveled by a vehicle in a road network having a plurality of road segments connected into a plurality of paths, the method comprising:
- obtaining a current location measurement for the vehicle, wherein said current location measurement has an accuracy range;
determining the road segments located within said accuracy range of said current location measurement to form a set of current possible positions for the vehicle;
retrieving a set of stored possible paths for the vehicle;
generating a new set of possible paths based on said set of current possible positions and said set of stored possible paths; and
storing said new set of possible paths as said set of stored possible paths, wherein said generating a new set of possible paths includes;
extending each stored possible path to each current possible position to form a set of extended paths;
storing each extended path that includes a current possible position that can be reached from the stored possible path in said extended path; and
removing each extended path that includes a current possible position that cannot be reached from the stored possible path in said extended path.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of and system for determining a path traveled by a vehicle in a road network having a plurality of road segments connected into a plurality of paths that includes obtaining a current location measurement having an accuracy range, determining the road segments located within this accuracy range of the current location measurement to form a set of current possible positions for the vehicle, retrieving a set of stored possible paths for the vehicle, generating a new set of possible paths based on the set of current possible positions and the set of stored possible paths, and storing the new set of possible paths as the set of stored possible paths.
-
Citations
56 Claims
-
1. A method of determining a path traveled by a vehicle in a road network having a plurality of road segments connected into a plurality of paths, the method comprising:
-
obtaining a current location measurement for the vehicle, wherein said current location measurement has an accuracy range;
determining the road segments located within said accuracy range of said current location measurement to form a set of current possible positions for the vehicle;
retrieving a set of stored possible paths for the vehicle;
generating a new set of possible paths based on said set of current possible positions and said set of stored possible paths; and
storing said new set of possible paths as said set of stored possible paths, wherein said generating a new set of possible paths includes;
extending each stored possible path to each current possible position to form a set of extended paths;
storing each extended path that includes a current possible position that can be reached from the stored possible path in said extended path; and
removing each extended path that includes a current possible position that cannot be reached from the stored possible path in said extended path. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
wherein said storing includes storing each extended path that exists in the road network, and wherein said removing includes removing each extended path that does not exist in the road network. -
3. The method of claim 1,
wherein said set of current possible positions includes a first current possible position and a second current possible position; -
wherein said set of stored possible paths includes a first stored possible path and a second stored possible path; and
wherein said extending includes;
adding said first current possible position to said first stored possible path to form a first extended path, adding said second current possible position to said first stored possible path to form a second extended path, adding said first current possible position to said second stored possible path to form a third extended path, and adding said second current possible position to said second stored possible path to form a fourth extended path.
-
-
4. The method of claim 3, wherein said storing includes:
-
storing said first extended path if said first current possible position can be reached from said first stored possible path;
storing said second extended path if said second current possible position can be reached from said first stored possible path;
storing said third extended path if said first current possible position can be reached from said second stored possible path; and
storing said fourth extended path if said second current possible position can be reached from said second stored possible path.
-
-
5. The method of claim 4, wherein said removing includes:
-
removing said first extended path if said first current possible position cannot be reached from said first stored possible path;
removing said second extended path if said second current possible position cannot be reached from said first stored possible path;
removing said third extended path if said first current possible position cannot be reached from said second stored possible path; and
removing said fourth extended path if said second current possible position cannot be reached from said second stored possible path.
-
-
6. The method of claim 1, further comprising filtering said current location measurement.
-
7. The method of claim 6,
wherein said set of stored possible paths includes a stored possible path having a previous current location measurement, wherein said previous current location measurement includes a first timestamp; -
wherein said current location measurement includes a second timestamp; and
wherein said filtering includes;
eliminating said current location measurement if the difference between said first timestamp and said second timestamp is less than a minimum travel time, storing said current location measurement if the difference between said first timestamp and said second timestamp is greater than said minimum travel time.
-
-
8. The method of claim 6, wherein said filtering includes eliminating said current location measurement if it is obtained from a non-vehicle source.
-
9. The method of claim 1, further comprising:
-
storing a sub-path that is common to all paths in said new set of possible paths, wherein said sub-path includes a common road segment;
removing road segments from each path in said new set of possible paths that precede said common road segment to form a set of shortened paths;
storing said set of shortened paths as said new set of possible paths; and
storing said sub-path in a road segment database.
-
-
10. The method of claim 1, wherein said generating a new set of possible paths includes:
-
extending each stored possible path to each current possible position to form a set of extended paths;
storing each extended path having an available travel time that is greater than a minimum travel time; and
removing each extended path having an available travel time that is less than said minimum travel time.
-
-
11. The method of claim 10,
wherein said set of stored possible paths includes a stored possible path having a previous current location measurement, wherein said previous current location measurement includes a first timestamp; -
wherein said current location measurement includes a second timestamp; and
wherein said available travel time is the difference between said first timestamp and said second timestamp.
-
-
12. The method of claim 1, wherein said obtaining includes obtaining a location measurement from a probe.
-
13. The method of claim 12, wherein said probe is a GPS receiver.
-
14. The method of claim 12, wherein said probe is a cellular phone.
-
-
15. A method of determining a path traveled by a vehicle in a road network having a plurality of road segments connected into a plurality of paths, the method comprising:
-
obtaining a current location measurement for the vehicle, wherein said current location measurement has an accuracy range;
determining the road segments located within said accuracy range of said current location measurement to form a set of current possible positions for the vehicle;
retrieving a set of stored possible paths for the vehicle;
generating a new set of possible paths based on said set of current possible positions and said set of stored possible paths;
storing said new set of possible paths as said set of stored possible paths;
detecting when said set of stored possible paths includes a sub-path having a common road segment that is common to all paths in said set of stored possible paths; and
storing said sub-path. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38)
calculating a travel time for said common road segment; and
storing said travel time in a road segment database, wherein said road segment database includes travel times from multiple vehicles.
-
-
17. The method of claim 16, further comprising:
-
calculating an average travel time for said common road segment using travel times from said road segment database; and
storing said average travel time in a traffic information database.
-
-
18. The method of claim 17, further comprising:
-
receiving a request for an expected current trip time for said common road segment; and
delivering a response based on said average travel time.
-
-
19. The method of claim 18, wherein said response is formatted.
-
20. The method of claim 18, wherein said response is provided to an external distribution channel.
-
21. The method of claim 17, further comprising:
-
storing said average travel time in a historical database, wherein said historical database includes travel times from multiple vehicles at various times;
receiving a request for an expected historical trip time for said common road segment; and
delivering a response based on travel times in said historical database.
-
-
22. The method of claim 17, further comprising:
-
receiving a request for an expected current arrival time for said common road segment; and
delivering a response based on said average travel time.
-
-
23. The method of claim 17, further comprising:
-
storing said average travel time in a historical database, wherein said historical database includes travel times from multiple vehicles at various times;
receiving a request for an expected historical arrival time for said common road segment; and
delivering a response based on travel times in said historical database.
-
-
24. The method of claim 17, wherein said traffic information database is further configured to store average travel times for a plurality of road segments in the road network.
-
25. The method of claim 24, further comprising:
-
receiving a request for an expected current trip time along a route; and
delivering a response based on said average travel times in said traffic information database.
-
-
26. The method of claim 24, further comprising:
-
receiving a request for an expected current arrival time along a route; and
delivering a response based on said average travel times in said traffic information database.
-
-
27. The method of claim 24, further comprising:
-
receiving a request for an unexpected delay on a route; and
delivering a response based on said average travel times in said traffic information database.
-
-
28. The method of claim 17, further comprising:
-
storing said average travel time in a historical database, wherein said historical database includes travel times from multiple vehicles at various times, wherein said historical database is configured to store travel times for a plurality of road segments in the road network;
receiving a request for an expected historical trip time along a route; and
delivering a response based on said travel times in said historical database.
-
-
29. The method of claim 17, further comprising:
-
storing said average travel time in a historical database, wherein said historical database includes travel times from multiple vehicles at various times, wherein said historical database is configured to store travel times for a plurality of road segments in the road network;
receiving a request for an expected historical arrival time along a route; and
delivering a response based on said travel times in said historical database.
-
-
30. The method of claim 16, further comprising:
-
calculating a median travel time for said common road segment using travel times from said road segment database; and
storing said median travel time in a traffic information database.
-
-
31. The method of claim 16, further comprising:
-
generating a distribution of travel times for said common road segment using travel times from said road segment database; and
storing said distribution in a traffic information database.
-
-
32. The method of claim 16, further comprising:
-
calculating a delay for said common road segment using travel times from said road segment database; and
storing said delay in a traffic information database.
-
-
33. The method of claim 32, further comprising:
-
receiving a request for an unexpected delay on said common road segment; and
delivering a response based on said delay in said traffic information database.
-
-
34. The method of claim 15, further comprising:
-
calculating a speed for said common road segment; and
storing said speed in a road segment database, wherein said road segment database includes speeds from multiple vehicles.
-
-
35. The method of claim 34, further comprising:
-
calculating an average speed for said common road segment using speeds from said road segment database; and
storing said average speed in a traffic information database.
-
-
36. The method of claim 34, further comprising:
-
calculating a median speed for said common road segment using speeds from said road segment database; and
storing said median speed in a traffic information database.
-
-
37. The method of claim 34, further comprising:
-
generating a distribution of speeds for said common road segment using speeds from said road segment database; and
storing said distribution in a traffic information database.
-
-
38. The method of claim 37, further comprising:
-
identifying a first peak in said distribution;
identifying a second peak in said distribution;
associating said first peak with a first lane in the road network; and
associating said second peak with a second lane in the road network.
-
-
39. A system for determining a path traveled by a vehicle along road segments in a road network, the system comprising:
-
a processor configured to;
receive a current location measurement for the vehicle, determine the road segments located within an accuracy range of said current location measurement to form a set of current possible positions for said vehicle, and generate a new set of possible paths based on said set of current possible positions and a set of stored possible paths for the vehicle; and
a database configured to;
store said set of stored possible paths for the vehicle, store said new set of possible paths as said set of stored possible paths, and store a sub-path that is common to all paths in said set of stored possible paths, wherein said sub-path includes a common road segment. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56)
wherein said processor is further configured to calculate a travel time for said common road segment; wherein said database is further configured to store said travel time; and
wherein said database is further configured to store travel times for said common road segment from multiple vehicles.
-
-
42. The system of claim 41,
wherein said processor is further configured to calculate a speed for said common road segment; -
wherein said database is further configured to store said speed; and
wherein said database is further configured to store speeds for said common road segment from multiple vehicles.
-
-
43. The system of claim 42,
wherein said processor is further configured to generate an overall calculation for said common road segment using travel times or speeds from said database; - and
wherein said processor is further configured to generate overall calculations using said travel times or speeds from said database for a plurality of road segments in the road network.
- and
-
44. The system of claim 43, wherein said overall calculation is an average travel time.
-
45. The system of claim 43, wherein said overall calculation is a median travel time.
-
46. The system of claim 43, wherein said overall calculation is a distribution of travel times.
-
47. The system of claim 43, wherein said overall calculation is a delay.
-
48. The system of claim 47,
wherein said processor is configured to receive a request for an unexpected delay on a route; - and
wherein said processor is configured to deliver a response based on said overall calculations.
- and
-
49. The system of claim 43,
wherein said processor is configured to receive a request for an expected current trip time for a shortest path connecting a first location point to a second location point; - and
wherein said processor is configured to deliver a response based on said overall calculations.
- and
-
50. The system of claim 43,
wherein said processor is configured to receive a request for an expected historical trip time for a shortest path connecting a first location point to a second location point; - and
wherein said processor is configured to deliver a response based on said overall calculations.
- and
-
51. The system of claim 43,
wherein said processor is configured to receive a request for an expected current arrival time for a shortest path connecting a first location point to a second location point; - and
wherein said processor is configured to deliver a response based on said overall calculations.
- and
-
52. The system of claim 43,
wherein said database is further configured to store overall calculations corresponding to various times for a plurality of road segments; -
wherein said processor is configured to receive a request for an expected historical arrival time for a shortest path connecting a first location point to a second location point; and
wherein said processor is configured to deliver a response based on said overall calculations.
-
-
53. The system of claim 43,
wherein said processor is configured to receive a request for an expected current trip time along a route; - and
wherein said processor is configured to deliver a response based on said overall calculations.
- and
-
54. The system of claim 43,
wherein said database is further configured to store overall calculations corresponding to various times for a plurality of road segments; -
wherein said processor is configured to receive a request for an expected historical trip time along a route; and
wherein said processor is configured to deliver a response based on said overall calculations.
-
-
55. The system of claim 43,
wherein said processor is configured to receive a request for an expected current arrival time along a route; - and
wherein said processor is configured to deliver a response based on said overall calculations.
- and
-
56. The system of claim 43,
wherein said database is further configured to store overall calculations corresponding to various times for a plurality of road segments; -
wherein said processor is configured to receive a request for an expected historical arrival time along a route; and
wherein said processor is configured to deliver a response based on said overall calculations.
-
Specification