Method and apparatus for a routing agent

• US 7,239,962 B2
• Filed: 12/17/2003
• Issued: 07/03/2007
• Est. Priority Date: 02/21/2003
• Status: Expired due to Term

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Plutowski, Mark Earl
• Primary Examiner(s): Nguyen, Cuong
• Application Number:
  US10/739,543
• Publication Number:
  US 20040167712A1
• Time in Patent Office: 1,294 Days
• Field of Search: 701200-202, 701207-210, 701213-214, 701/23, 701/117, 340990-995, 340/995.11, 340/995.14, 345/119, 345/123, 345/473, 342/357.06, 342/357.13, 342/357.17, 455/422, 707/2
• US Class Current: 701/209
• 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/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated

Abstract

A method and apparatus for a route calculation engine is described. The method of calculating a route to a resource comprises identifying a plurality of locations at which the resource may be available and creating an optimal route through the plurality of locations, the route assuring that the resource will be found regardless of availability at any one location.

Claims

1. A method of calculating a route to a resource, the method comprising:

identifying a plurality of locations at which a first resource may be available, each of the plurality of locations having an associated non-zero probability of availability for the first resource;

creating an optimal route through the plurality of locations to obtain the first resource, the route assuring that the first resource will be found regardless of availability at any one location, wherein creating the optimal route is based on a maximum expected value of each location calculated based on the probability of availability of the first resource at a location.

2. The method of claim 1, further comprising:

identifying a cost associated with each location; and

selecting a first location based on lowest cost, wherein the cost takes into account the probability of the resource being available at the first location.

3. The method of claim 2, wherein the cost comprises one or more of the following:

distance, monetary costs, trade-offs.

4. The method of claim 1, further comprising:

providing multi-step look-ahead to calculate the route from a first location to a second location, used if the resource is not available at the first location.

5. The method of claim 4, wherein the calculation of the multi-step look-ahead includes using user preferences for trade-offs for utilities.

6. The method of claim 1, further comprising:

calculating probability of availability of the resource at each potential location; and

selecting the first location based on lowest overall cost, wherein the lowest overall cost takes into account the probability of the resource being available, and additional costs, the additional costs including one or more of;

distance, time requirements, price differential.

7. The method of claim 1, further comprising:

providing multi-level reasoning permitting setting a preference along a continuum between optimization and speed.

8. The method of claim 7, wherein the multi-level reasoning provides speed when a valid plan is needed quickly, the method further comprising:

improving optimization of the valid plan as time permits.

9. The method of claim 7, wherein the multi-level reasoning provides optimization to provide a least expensive route.

10. An apparatus to implement a route calculation engine comprising:

a location fetching logic to identify a plurality of locations at which a resource may be available, each location having an associated probability of availability of the resource;

a route calculation logic to create an optimal route through the plurality of locations, the route assuring that the resource will be found regardless of availability at any one location, the route calculation logic taking into account the probability of availability of the resource at each of the plurality of locations.

11. The apparatus of claim 10, further comprising:

a goal receiving logic to receive a resource identification from a user, the resource identification identifying the sought resource.

12. The apparatus of claim 10, further comprising:

a utility evaluation logic to identify a cost associated with each location.

13. The apparatus of claim 12, wherein the cost comprises one or more of the following:

distance, monetary costs, trade-offs.

14. The apparatus of claim 10, further comprising:

the route calculation logic further to provide multi-step look-ahead to calculate the route from a first location to a second location, used if the resource is not available at the first location.

15. The apparatus of claim 14, wherein the goal receiving logic is further to prompt a user to select preferences for trade-offs for utilities.

16. The apparatus of claim 10, further comprising:

a probability calculation logic to calculate the probability of availability of the resource at each potential location, the probability calculation logic taking into account one or more of the following;

availability, purchase cost, acquisition cost, and acquisition time of the resource, at each of the plurality of locations.

17. The apparatus of claim 10, further comprising:

a preference setting logic to provide multi-level reasoning permitting setting a preference along a continuum between optimization and speed.

18. The apparatus of claim 17, wherein the preference setting logic enables the route calculation logic to provide speed when a valid plan is needed quickly, and to improve the optimization of the valid plan as time permits.

19. The apparatus of claim 17, wherein the preference setting logic enables the route calculation logic to provide optimization to provide a least expensive route if calculation time is not limited.

20. A machine readable medium having stored thereon data representing sequences of instructions, which when executed by a computer system, cause said computer system to calculate a route to a resource, by performing the acts of:

identifying a plurality of locations at which the resource may be available, each of the plurality locations having an associated probability of availability of the resource;

creating a route through the plurality of locations, the route assuring that the resource will be found regardless of availability at any one location, and ordering the locations in the route based on the probability of availability of the resource at each of the locations.

21. The machine readable medium of claim 20, having stored thereon additional data, which when executed by the computer system cause the computer system to further:

identify a cost associated with each location, the cost comprising one or more of the following;

distance, monetary costs, trade-offs.

22. The machine readable medium of claim 20, having stored thereon additional data, which when executed by the computer system cause the computer system to further:

provide multi-step look-ahead to calculate the route from a first location to a second location, used if the resource is not available at the first location.

23. The machine readable medium of claim 20, further comprising calculating maximal expected value of each location, wherein the minimal expected cost is equal to the probability of availability of the resource at each potential location multiplied by an acquisition cost.

24. A system comprising:

a server to receive the request from a user system, the server including a route calculation engine comprising;

a location fetching logic to identify a plurality of locations at which the resource may be available, each of the plurality of locations having an associated probability of availability of the resource;

a utility evaluation logic to identify a cost of obtaining the resource at each location, the cost including a location cost and variable costs; and

a route calculation logic to create an optimal route through the plurality of locations, the route assuring that the resource will be found regardless of availability at any one location.

25. The system of claim 24, further comprising:

a probability evaluation logic to calculate a probability that the resource is available at each of the plurality of locations, the probabilities being input to the route calculation logic.

26. The apparatus of claim 24, wherein the cost comprises one or more of the following:

distance, monetary costs, trade-offs.

27. The apparatus of claim 24, further comprising:

the route calculation logic further to provide multi-step look-ahead to calculate the route from a first location to a second location, used if the resource is not available at the first location.

28. The apparatus of claim 24, further comprising:

a route sending logic to send a calculated route to the user system.

29. The apparatus of claim 28, further comprising:

the user system to receive the calculated route from the server for display to a user.

30. The apparatus of claim 29, further comprising:

a miss detection logic in the user system to detect if a primary path in the calculated route was not followed.

31. The apparatus of claim 30, further comprising:

an alternate route logic to retrieve an alternate path included within the calculated route, the alternate path designed to route the user back onto the primary path.

32. The apparatus of claim 29, further comprising:

a feedback logic to send relevant information back to the server.

33. A route calculation engine comprising:

a means to receive a resource request from a user;

a locating means to identify a plurality of locations at which a resource may be available, each of the plurality of location having an associated probability of availability of the resource;

a calculating means to calculate a cost of acquisition of the resource at each of the plurality of locations, the cost of acquisition including location cost and variable costs; and

a means to create an optimal route through the plurality of locations, the route assuring that the resource will be found regardless of availability at any one location.

34. The apparatus of claim 33, further comprising:

a means to identify a cost associated with each location.

35. The apparatus of claim 34, wherein the cost comprises one or more of the following:

distance, monetary costs, trade-offs.

36. The apparatus of claim 33, further comprising:

a means to calculate the route from a first location to a second location, used if the resource is not available at the first location.