Method and apparatus for an itinerary planner

• US 8,050,949 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,766
• Publication Number:
  US 20110161271A1
• 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. A method to create an itinerary comprising:

receiving, by a server computing system, user preferences for a plan utility;

selecting a plan element having a positive utility above a threshold value;

creating, by the server computing system, a personalized plan based on the selected plan elements, wherein the personalized plan defines at least one decision point to detect during execution of the personalized plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the personalized plan and has an associated original plan element and at least one associated alternative plan element that are pre-determined prior to execution of the personalized plan.

2. The method of claim 1, further comprising:

determining if there is additional time remaining for more plan elements; and

if there is additional time remaining, selecting an additional plan element.

3. The method of claim 1, wherein plan elements are selected based on the utility and a relative location of the plan element.

4. The method of claim 1, wherein receiving a user preference comprises receiving:

a starting time, a starting location, an available time.

5. An apparatus to create an itinerary comprising:

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

a processor coupled to the memory; and

a plan utility evaluation logic executed from the memory by the processor to select a plan element for a personalized plan, the plan element having a utility, the utility being a match between the categories associated with the plan element and user preferences, and

a plan creation logic executed from the memory by the processor to generate a plan using the plan element by identifying a plan element having a utility above a set utility threshold, wherein the plan defines at least one decision point to detect during execution of the plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the plan and has an associated original plan element and at least one associated alternative plan element that are pre-determined prior to execution of the plan.

6. The apparatus of claim 5, further comprising:

a user interface to receive plan acceptance and plan rejections from the user;

upon indication by the user that the plan is rejected, the plan creation logic further to select a second plan having a utility a predefined delta above the utility of the first plan; and

selecting the second plan.

7. The apparatus of claim 6, wherein the plan creation logic further iterates the process until no plans with a higher utility are present.

8. The apparatus of claim 5, further comprising:

an acquisition engine executed from the memory by the processor to acquire plan elements, the acquisition engine to acquire plan elements and categorize the plan elements.

9. The apparatus of claim 8, wherein categorizing the plan elements comprises identifying which one or more categories the plan element satisfies, the categories corresponding to the selectable user preferences.

10. An apparatus to generate an itinerary comprising:

a first means to receive a plurality of user preferences;

a generation means to generate a plan using plan elements, wherein the plan elements have a utility above a threshold value;

an evaluation means to identify a utility of the plan, the utility being a match between the categories associated with the plan elements in the plan and the user preferences; and

a selection means to select a personalized plan from the plurality of plans, wherein the selected plan defines at least one decision point to detect during execution of the selected plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the selected plan and has an associated original plan element and at least one associated alternative plan element that are pre-determined prior to execution of the selected plan.

11. The apparatus of claim 10, wherein the plan elements comprise travel destinations available to the user, to construct a travel itinerary.

12. The apparatus of claim 10, wherein the plan elements comprise virtual locations defined by Universal Resource Indicators (URIs) to construct a web services itinerary.

13. The apparatus of claim 10, further comprising:

an acquisition means to acquire plan elements; and

a categorization means to assign categories to the plan elements, the categories corresponding to categories selected by a user as user preferences.

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:

identifying a plurality of user preferences;

selecting one or more plan elements having a positive utility above a threshold value; and

constructing a personalized plan including the one or more plan elements, the personalized plan having the highest available utility and defining at least one decision point to detect during execution of the personalized plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the personalized plan and has an associated original plan element and at least one associated alternative plan element that are pre-determined prior to execution of the personalized plan.

15. The non-transitory machine readable medium of claim 14, further having stored thereon data representing sequences of instructions, which when executed by a computer system, cause the computer to perform the steps of:

identifying a first plan having a utility above a set utility threshold;

presenting the first plan to a user;

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

presenting the second plan to the user.

16. The non-transitory machine readable medium of claim 14, further having stored thereon data representing sequences of instructions, which when executed by a computer system, cause the computer to generate a plurality of plans, causing the computer to perform the steps of:

identifying a starting location;

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

17. A method of creating a plan comprising:

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

receiving a category value for each category associated with each element;

automatically generating a first complete plan using the plan elements and the category values for each category;

determining, by a server computing system, whether to generate a new complete plan and based on the determination that a new plan should be generated, automatically generating the new complete plan,

wherein the new complete plan defines at least one decision point to detect during execution of the new complete plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the new complete plan and has an associated original plan element and at least one associated alternative plan element that are predetermined prior to execution of the new complete plan; and

determining, by the server computing system, whether to select the new complete plan as a final complete plan.

18. The method of claim 17, wherein automatically generating a first complete plan comprises:

calculating a user value for each element using the category values;

selecting the element having the highest user value as part of the first complete plan;

determining whether to select another element to add to the first complete plan;

re-calculating a user value for each element based on the selected element;

selecting the element having the highest user value; and

calculating a user value for the first complete plan using each of the user values of the selected elements.

19. The method of claim 18, wherein determining whether to select another element to add to the first complete plan is based on time available in the first complete plan.

20. The method of claim 17, wherein determining whether to generate a new complete plan comprises:

determining whether to select the first complete plan as the final complete plan; and

generating the new complete plan when the first complete plan is not selected as the final complete plan.

21. The method of claim 17, wherein automatically generating the new complete plan comprises identifying a new complete plan having a utility at least a delta above a utility of the first complete plan.

22. The method of claim 17, wherein determining whether to select the new complete plan as a final complete plan comprises:

determining whether a user request to identify a complete plan having a utility of at least a delta above the utility of the new complete plan is received; and

selecting the new complete plan as the final complete plan when a user request is not received.

23. The method of claim 17, wherein the category value for each category is based on one or more of:

a user input and a history of user behavior.

24. A method of creating a plan comprising:

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

receiving a plurality of user preferences, wherein the user preferences include a user value for each category;

receiving a minimum utility for a final complete plan, wherein the minimum utility is a predefined value, the minimum utility being the minimum user value for the final complete plan based on the plan elements and user values for each category;

automatically constructing, by a server computing system, a first complete plan having at least the minimum utility;

identifying, by the server computing system, a new complete plan having a utility at least a delta above the utility of the first complete plan, wherein the new complete plan defines at least one decision point to detect during execution of the new complete plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the new complete plan and has an associated original plan element and at least one associated alternative plan element that are pre-determined prior to execution of the new complete plan; and

determining, by the server computing system, whether to select the new complete plan as the final complete plan.

25. The method of claim 24, wherein determining whether to identify a new complete plan comprises:

determining whether to select the first complete plan as the final complete plan; and

identifying the new complete plan when the first complete plan is not selected as the final complete plan.

26. The method of claim 24, wherein determining whether to select the new complete plan as the final complete plan comprises:

determining whether a user request to identify a complete plan having a utility of at least a delta above the new complete plan is received; and

selecting the new complete plan as the final complete plan when a user request is not received.

27. A computer-implemented method of creating a plan on a planning server computing system, the method comprising:

receiving a plurality of user preferences through an interface;

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

determining, by the planning server computing system, at least one of the plurality of plan elements is a multi-step activity;

separating the at least one plan element that is a multi-step activity into sub-elements, wherein the sub-elements include a constraint defining a relationship between the sub-elements;

automatically generating, by the planning server computing system, a plurality of complete plans by a processor, wherein each complete plan is generated based on the at least one constraint defining the relationship between the sub-elements; and

selecting, by the planning server computing system, a personalized plan from the plurality of complete plans by the processor, the personalized plan having a utility, the utility being a match between the categories associated with the plan elements and the user preferences, wherein the personalized plan defines at least one decision point to detect during execution of the new complete plan whether a user is following an original plan element that is associated with the decision point, and wherein the at least one decision point is defined prior to execution of the personalized plan and has an associated original plan element and at least one associated alternative plan element that are pre-determined prior to execution of the personalized plan.

28. The computer-implemented method of claim 27, wherein the constraint is a dependency of one of the sub-elements on another sub-element.

29. The computer-implemented method of claim 27, wherein the constraint is a temporal constraint.