Method and apparatus for an itinerary planner

• US 8,050,948 B2
• Filed: 01/11/2011
• Issued: 11/01/2011
• Est. Priority Date: 02/26/2003
• Status: Expired due to Fees

• 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: Purang, Khemdut, Plutowski, Mark Earl
• Primary Examiner(s): Hayes; John
• Assistant Examiner(s): JOSEPH, TONYA S
• Application Number:
  US13/004,761
• Publication Number:
  US 20110167028A1
• Time in Patent Office: 294 Days
• Field of Search: 705 5- 6
• US Class Current: 705/5
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation

Abstract

A method and apparatus for providing an itinerary planner is described. The itinerary planner generates itineraries for visiting locations which are personalized to the user'"'"'s preferences. Unknown conditions are handled by contingency plans that the itinerary planner generates in an anytime manner. The first itineraries are derived in a short time, and as more computation time is allowed, additional itineraries that better suit the preferences of the user are obtained.

Claims

1. An apparatus to create an itinerary comprising:

a memory to store a plurality of user preferences and a plurality of possible plan elements, each element having one or more categories associated with the element;

a processor coupled to the memory, the processor being configured to;

calculate a user value for each plan element,

automatically generate a conditional plan comprising a plurality of plan items and defining at least one decision point to detect during execution of the conditional plan whether a user is following an original plan item that is associated with the decision point, wherein the conditional plan is generated based on the calculated user values for the plan elements and the at least one decision point is defined prior to execution of the conditional plan and has an associated original plan item and at least one associated alternative plan item that are pre-determined prior to execution of the conditional plan,

present the conditional plan in a user system,

detect the at least one defined decision point during execution of the conditional plan,

determine at the defined decision point that a user is not following the original plan item that is associated with the defined decision point, and

present during execution of the conditional plan the pre-determined alternative plan item that is associated with the defined decision point in the user system based on the determination that the user is not following the original plan item that is associated with the defined decision point.

2. The apparatus of claim 1, wherein to generate the conditional plan further comprises the processor being configured to:

identify a first plan having a utility above a set utility threshold, the utility being a match between the categories associated with the plan elements and the user preferences.

3. The apparatus of claim 2, further comprising the processor being configured to:

generate a plurality of complete plans, wherein each complete plan is generated based on the calculated user values for each of the plan elements;

upon indication by the user that the first plan is rejected, identify a second plan having a utility a predefined delta above the utility of the first plan; and

select the second plan.

4. The apparatus of claim 3, further comprising the processor being configured to:

for each of the plurality of complete plans, determine whether the complete plan has a utility of a predefined delta greater than the utility of the current selected plan;

select a new plan having the utility of the predefined delta greater than the utility of the current selected plan as the current selected plan when a determination is made that there is a plan of greater utility than the first and the second plan.

5. The apparatus of claim 1, wherein to automatically generate the conditional plan further comprises the processor being configured to:

identify a starting location;

connect together a plurality of plan segments, the plurality of segments fitting within an allotted time period.

6. The apparatus of claim 5, wherein the allotted time period is received from a user.

7. The apparatus of claim 6, wherein each plan segment has associated with it an expected time to complete the plan segment.

8. The apparatus of claim 7, wherein the expected time includes an average time, and a minimum time, to complete the plan segment.

9. The apparatus of claim 1, wherein to store a plurality of user preferences further comprises the processor being configured to:

receive a user identification from a user; and

retrieve a plurality of user preferences associated with the user identification from a database.

10. The apparatus of claim 1, wherein to store a plurality of user preferences further comprises the processor being configured to receive one or more of the following a starting location, an available time, a plurality of categories.

11. The apparatus of claim 10, wherein the categories, for an itinerary planner, include one or more of the following:

shopping, movies, nature, technology, museums.

12. The apparatus of claim 11, wherein the categories available to the user for user preferences, reflect the categories of the plan elements available to the user.

13. An apparatus to generate an itinerary comprising:

a means to store a plurality of user preferences and a plurality of possible plan elements, each element having one or more categories associated with the element;

a means to receive a plurality of user preferences;

a retrieving means to retrieve a plurality of possible plan elements from a memory, each element having one or more categories associated with the element;

a calculation means to calculate a user value for each plan element;

a generation means to automatically generate a conditional plan comprising a plurality of plan items and defining at least one decision point to detect during execution of the conditional plan whether a user is following an original plan item that is associated with the decision point, wherein the conditional plan is generated based on the calculated user values for the plan elements and the at least one decision point is defined prior to execution of the conditional plan and has an associated original plan item and at least one associated alternative plan item that are pre-determined prior to execution of the conditional plan;

a detection means to detect the at least one defined decision point during execution of the conditional plan and to determine at the defined decision point that a user is not following the original plan item that is associated with the defined decision point; and

a presentation means to present the conditional plan in a user system; and

to presenting during execution of the conditional plan the pre-determined alternative plan item that is associated with the defined decision point in the user system based on the determination that the user is not following the original plan item that is associated with the defined decision point.

14. A non-transitory machine readable medium having stored thereon data representing sequences of instructions, which when executed by a computer system, cause said computer system to create an itinerary, by performing the steps of:

receiving a plurality of user preferences through an interface;

retrieving a plurality of possible plan elements, each element having one or more categories associated with the element;

calculating a user value for each plan element;

automatically generating a conditional plan comprising a plurality of plan items and defining at least one decision point to detect during execution of the conditional plan whether a user is following an original plan item that is associated with the decision point, wherein the conditional plan is generated based on the calculated user values for the plan elements and the at least one decision point is defined prior to execution of the conditional plan and has an associated original plan item and at least one associated alternative plan item that are pre-determined prior to execution of the conditional plan;

presenting the conditional plan in a user system;

detecting the at least one defined decision point during execution of the conditional plan;

determining at the defined decision point that a user is not following the original plan item that is associated with the defined decision point; and

presenting during execution of the conditional plan the pre-determined alternative plan item that is associated with the defined decision point in the user system based on the determination that the user is not following the original plan item that is associated with the defined decision point.

15. The non-transitory machine readable medium of claim 14, wherein generating the conditional plan comprises:

identifying a first plan having a utility above a set utility threshold, the utility being a match between the categories associated with the plan elements and the user preferences.

16. The non-transitory machine readable medium of claim 15, further comprising:

generating a plurality of complete plans, wherein each complete plan is generated based on the calculated user values for each of the plan elements;

upon indication by the user that the first plan is rejected, identifying a second plan having a utility a predefined delta above the utility of the first plan; and

selecting the second plan.

17. The non-transitory machine readable medium of claim 16, further comprising:

for each of the plurality of complete plans, determining whether the complete plan has a utility of a predefined delta greater than the utility of the current selected plan;

selecting a new plan having the utility of the predefined delta greater than the utility of the current selected plan as the current selected plan when a determination is made that there is a plan of greater utility than the first and the second plan.

18. The non-transitory machine readable medium of claim 14, wherein automatically generating the conditional plan comprises:

identifying a starting location;

connecting together a plurality of plan segments, the plurality of segments fitting within an allotted time period.

19. The non-transitory machine readable medium of claim 18, wherein the allotted time period is received from a user.

20. The non-transitory machine readable medium of claim 19, wherein each plan segment has associated with it an expected time to complete the plan segment.

21. The non-transitory machine readable medium of claim 20, wherein the expected time includes an average time, and a minimum time, to complete the plan segment.

22. The non-transitory machine readable medium of claim 14, wherein receiving a plurality of user preferences comprises:

receiving a user identification from a user; and

retrieving a plurality of user preferences associated with the user identification from a database.

23. The non-transitory machine readable medium of claim 14, wherein receiving a plurality of user preferences comprises receiving one or more of the following:

a starting location, an available time, a plurality of categories.

24. The non-transitory machine readable medium of claim 23, wherein the categories, for an itinerary planner, include one or more of the following:

shopping, movies, nature, technology, museums.

25. The non-transitory machine readable medium of claim 24, wherein the categories available to the user for user preferences, reflect the categories of the plan elements available to the user.