Method, System and Computer Program Product for Optimizing Route Planning Digital Maps

• US 20130179067A1
• Filed: 09/28/2011
• Published: 07/11/2013
• Est. Priority Date: 09/29/2010
• Status: Abandoned Application

• Current Assignee: University of Virginia Patent Foundation (University of Virginia)
• Original Assignee: University of Virginia Patent Foundation (University of Virginia)
• Inventors: Trowbridge, Matthew J., Cogill, Randy L.
• Application Number:
  US13/823,166
• Publication Number:
  US 20130179067A1
• Time in Patent Office: Days
• US Class Current: 701/410
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

A system for digital network map development and maintenance. The system provides for optimizing digital network maps that serve as the reference basis for location-based systems such as, but not limited to, route guidance, multi-modal transportation system monitoring, location-based consumer applications, and vehicle fleet administration. The system provides the ability to develop and maintain digital route maps derived at least in part from data on the routes that drivers or users actually travel to update a digital map. For a route defined between two or more points, costs may be assigned to each road segment. As such, given a collection of route preferences, an algorithm is provided that is capable of generating an optimized route planning digital map by finding and assigning a set of costs to road segments in a way that is consistent with these preferences.

Claims

1. A system for determining an optimum route planning digital map to be applied onto a first route planning digital map, said system comprising:

a) a memory component operative to store;

said first route planning digital map comprises a collection of nodes and arcs, wherein an arc is defined as a segment between a pair of nodes, and

preferred route data, said preferred route data comprises a collection of arcs representing a collection of routes that an entity finds preferable with respect to some unquantified criterion; and

b) a processor in communication with said memory component configured to;

assign arc costs to said arc, wherein said assigned arc cost is determined by synthesizing said preferred route data together with a distribution over baseline arc costs,

apply said assigned arc costs to said first route planning digital map to provide an optimized route planning digital map, and

perform at least one of;

storing said optimized route planning digital map for use;

or

communicating said optimized route planning digital map for use with an output device or other processor based system.

2. The system of claim 1, wherein said entity comprises at least one of:

individual, individuals, and specialized user.

3. The system of claim 1, wherein said arc costs comprises at least one penalty.

4. The system of claim 1, wherein said arc costs comprises at least one road segment avoidance.

5. The system of claim 1, wherein said arc costs comprises at least one of:

an event, an episode, and weather condition.

6. The system of claim 1, wherein said arc costs comprises at least one of:

travel time, safety, speed limit, congestion, distance, road width, road conditions, and terrain.

7. The system of claim 1, wherein said arc costs comprises at least one of:

travel time, safety, speed limit, congestion, road segment avoidance, road-absence activity, distance, penalties, road width, road conditions, weather, event, episode, and terrain.

8. The system of claim 1, wherein said arc costs comprises at least one road-absence activity.

9. The system of claim 1, wherein said synthesizing is performed by inferring arc costs using a probabilistic model.

10. The system of claim 9, wherein said probabilistic model is a Bayesian model.

11. The system of claim 9, wherein said inferred arc costs are chosen by deriving estimates from said probabilistic model.

12. The system of claim 10, wherein said inferred arc costs are chosen as maximum a-posteriori probability (MAP) estimates.

13. The system of claim 12, wherein said MAP estimates of said inferred arc costs are computed using sequential unconstrained minimization technique.

14. The system of claim 1, wherein said preferred route data is received from a source including at least one of:

manual communication entry, GPS communication, internet communication, or memory storage of preferred route data.

15. The system of claim 1, wherein said preferred route data is received from a source including at least one of:

triangulation system, accelerometer system, transponder system, radio frequency system, blue tooth communication system, RFID system, or gyro system.

16. The system of claim 1, wherein assigned arc costs are updated in real-time.

17. The system of claim 1, wherein said receiving at least part of said preferred route data is effected in real time.

18. The system of claim 17, wherein said assigned arc costs are updated in real time.

19. The system of claim 1, wherein said optimized route planning digital map to be utilized for at least one of:

commercial or personal transportation, parcel delivery, taxi or limousine service, military logistics and transportation, emergency medical services (EMS), disaster response, shipping logistics, and evacuation route planning.

20. The system of claim 1, wherein said optimized route planning digital map to be utilized for at least one of:

route guidance, multi-modal transportation system monitoring, location-based consumer applications, and vehicle fleet administration.

21. The system of claim 1, wherein said output device comprises at least one of the following:

monitor, printer, speaker, or display.

22. The system of claim 1, wherein said processor based system comprises at least one of:

computer, remote computer, networked computers, servers, PDAs, PCs, tracking module, workstation, microprocessor based appliance, and navigation system.

23. The system of claim 1, wherein said synthesizing comprises:

assigning prior distributions to said arc costs in said first route planning digital map.

24. The system of claim 23, wherein said synthesizing comprises:

assigning a distribution to error terms on said arcs in each route preference pair.

25. The system of claim 24, wherein said synthesizing comprises:

constructing likelihood functions characterizing the probability of observing each route preference.

26. The system of claim 25, wherein said synthesizing comprises:

combining prior distributions and likelihoods to determine updated arc costs.

27. A computer implemented method for determining an optimum route planning digital map, said method comprising:

providing for receiving a first route planning digital map data, said first route planning digital map data comprises a collection of nodes and arcs, wherein an arc is defined as a segment between a pair of nodes,

providing for receiving preferred route data, said preferred route data comprises a collection of arcs representing a collection of routes that an entity finds preferable with respect to some unquantified criterion;

providing for assigning arc costs to said arc, wherein said assigned arc cost is determined by synthesizing said preferred route data together with a distribution over baseline arc costs;

providing for applying said assigned arc costs to said first route planning digital map to provide an optimized route planning digital map; and

providing for communicating said optimized planning digital map for storage or output.

28. The method of claim 27, wherein said entity comprises at least one of:

individual, individuals, and specialized user.

29. The method of claim 27, wherein said arc costs comprises at least one penalty.

30. The method of claim 27, wherein said arc costs comprises at least one road segment avoidance.

31. The method of claim 27, wherein said arc costs comprises at least one of:

an event, an episode, and weather condition.

32. The method of claim 27, wherein said arc costs comprises at least one of:

travel time, safety, speed limit, congestion, distance, road width, road conditions, and terrain.

33. The method of claim 27, wherein said arc costs comprises at least one of:

travel time, safety, speed limit, congestion, road segment avoidance, road-absence activity, distance, penalties, road width, road conditions, weather, event, episode, and terrain.

34. The method of claim 27, wherein said arc costs comprises at least one road-absence activity.

35. The method of claim 27, wherein said synthesizing is performed by inferring arc costs using a probabilistic model.

36. The method of claim 35, wherein said probabilistic model is a Bayesian model.

37. The method of claim 35, wherein said inferred arc costs are chosen by deriving estimates from said probabilistic model.

38. The method of claim 36, wherein said inferred arc costs are chosen as maximum a-posteriori probability (MAP) estimates.

39. The method of claim 38, wherein said MAP estimates of said inferred arc costs are computed using sequential unconstrained minimization technique.

40. The method of claim 27, wherein said preferred route data is received from a source including at least one of:

manual communication entry, GPS communication, internet communication, or memory storage of preferred route data.

41. The method of claim 27, wherein said preferred route data is received from a source including at least one of:

triangulation system, accelerometer system, transponder system, radio frequency system, blue tooth communication system, RFID system, or gyro system.

42. The method of claim 27, wherein assigned arc costs are updated in real-time.

43. The method of claim 27, wherein said receiving at least part of said preferred route data is effected in real time.

44. The method of claim 43, wherein said assigned arc costs are updated in real time.

45. The method of claim 27, wherein said optimized route planning digital map to be utilized for at least one of:

commercial or personal transportation, parcel delivery, taxi or limousine service, military logistics and transportation, emergency medical services (EMS), disaster response, shipping logistics, and evacuation route planning.

46. The method of claim 27, wherein said optimized route planning digital map to be utilized for at least one of:

route guidance, multi-modal transportation system monitoring, location-based consumer applications, and vehicle fleet administration.

47. The method of claim 27, wherein said output device comprises at least one of the following:

monitor, printer, speaker, or display.

48. The method of claim 27, wherein said processor based system comprises at least one of:

computer, remote computer, networked computers, servers, PDAs, PCs, tracking module, workstation, microprocessor based appliance, and navigation system.

49. The method of claim 27, wherein said synthesizing comprises:

assigning prior distributions to said arc costs in said first route planning digital map.

50. The method of claim 49, wherein said synthesizing comprises:

assigning a distribution to error terms on said arcs in each route preference pair.

51. The method of claim 50, wherein said synthesizing comprises:

constructing likelihood functions characterizing the probability of observing each route preference.

52. The method of claim 51, wherein said synthesizing comprises:

combining prior distributions and likelihoods to determine updated arc costs.

59. The computer program product of claim 53, wherein said computer logic is configured to perform the steps included in any one of claims 28-52.

53. A computer program product comprising a non-transitory computer useable medium having a computer program logic for enabling a computer system for determining an optimum route planning digital map, said computer logic comprising:

receiving a first route planning digital map data, said first route planning digital map data comprises a collection of nodes and arcs, wherein an arc is defined as a segment between a pair of nodes,

receiving preferred route data, said preferred route data comprises a collection of arcs representing a collection of routes that an entity finds preferable with respect to some unquantified criterion;

assigning arc costs to said arc, wherein said assigned arc cost is determined by synthesizing said preferred route data together with a distribution over baseline arc costs;

applying said assigned arc costs to said first route planning digital map to provide an optimized route planning digital map; and

communicating said optimized planning digital map for storage or output.

54. A server computer system, said server computer system comprising:

a memory component operative to receive and store data representing an optimized route planning digital map; and

a processor in communication with said memory component configured to execute said optimized route planning digital map, wherein said optimized route planning digital map was produced by the following steps;

receiving a first route planning digital map data, said first route planning digital map data comprises a collection of nodes and arcs, wherein an arc is defined as a segment between a pair of nodes,

receiving preferred route data, said preferred route data comprises a collection of arcs representing a collection of routes that an entity finds preferable with respect to some unquantified criterion,

assigning arc costs to said arc, wherein said assigned arc cost is determined by synthesizing said preferred route data together with a distribution over baseline arc costs, and

applying said assigned arc costs to said first route planning digital map to generate said optimized route planning digital map.

55. The server computer system of claim 54, wherein said server computer system is a navigation system server.

56. A navigation system for use with a server computer system, said navigation system comprising:

a memory component operative to receive data from said server computer system, and store data representing an optimized route planning digital map; and

a processor in communication with said memory component configured to execute said optimized route planning digital map, wherein said optimized route planning digital map was produced by the following steps;

receiving a first route planning digital map data, said first route planning digital map data comprises a collection of nodes and arcs, wherein an arc is defined as a segment between a pair of nodes,

receiving preferred route data, said preferred route data comprises a collection of arcs representing a collection of routes that an entity finds preferable with respect to some unquantified criterion;

assigning arc costs to said arc, wherein said assigned arc cost is determined by synthesizing said preferred route data together with a distribution over baseline arc costs, and

applying said assigned arc costs to said first route planning digital map to generate said optimized route planning digital map.

57. The navigation system of claim 56, wherein said navigation system comprises at least one of:

GPS system, PDA, computer, mobile phone, or internet-enabled device.

58. A system for determining an optimum route planning digital map to be applied onto a first route planning digital map, said system comprising:

means for receiving a first route planning digital map data, said first route planning digital map data comprises a collection of nodes and arcs, wherein an arc is defined as a segment between a pair of nodes,

means for receiving preferred route data, said preferred route data comprises a collection of arcs representing a collection of routes that an entity finds preferable with respect to some unquantified criterion;

means for assigning arc costs to said arc, wherein said assigned arc cost is determined by synthesizing said preferred route data together with a distribution over baseline arc costs;

means for applying said assigned arc costs to said first route planning digital map to provide an optimized route planning digital map; and

means for communicating said optimized planning digital map for storage or output.