Processing and fulfilling natural language travel requests

• US 10,275,810 B2
• Filed: 03/14/2012
• Issued: 04/30/2019
• Est. Priority Date: 03/14/2011
• Status: Active Grant

• Current Assignee: Amgine Technologies (US), Inc.
• Original Assignee: Amgine Technologies (US), Inc.
• Inventors: Miller, Jonathan David, Miller, Harold Roy, Seider, Steven Mark
• Primary Examiner(s): Vetter, Daniel
• Application Number:
  US13/420,179
• Publication Number:
  US 20120239443A1
• Time in Patent Office: 2,603 Days
• Field of Search: 705 5- 6
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions

Abstract

Systems and methods that process natural language travel requests are described herein. According to some embodiments, methods for processing natural language travel requests may include: (a) decoding itinerary components from a natural language travel request, (b) determining a node type for each of the itinerary components, (c) ascertaining dependencies between each of the itinerary components based upon respective node types, (d) generating an unconstrained schedule using the itinerary components and respective dependencies therebetween, and (d) allocating available inventory to each of the itinerary components according to the unconstrained schedule to fulfill the natural language travel request.

Claims

1. A method for processing natural language travel requests by a processor, the method comprising:

delimiting, by a parser executed by the processor, itinerary components from a natural language travel request;

parsing, by the parser, delimited strings from the natural language travel request and transmitting the delimited strings to a pattern recognition artificial intelligence module;

decoding, by the pattern recognition artificial intelligence module, the type of request by referencing a metadata database and an equivalence class database to recognize keywords in the delimited strings that direct the pattern recognition artificial intelligence module to appropriate content categories for the itinerary components included in the request;

wherein the pattern recognition artificial intelligence module employs an inference functionality which allows for variation among phraseology to account for different ways that natural language queries may be structured;

determining, by the parser, a node type for each of the itinerary components, the itinerary components comprising at least two node types, wherein the itinerary components include at least travel nodes and non-travel nodes, each of the non-travel nodes depending on one of the travel nodes;

ascertaining, by the parser, dependencies between each of the itinerary components based upon respective node types, wherein the dependencies between the travel nodes comprise at least a location and time dependency and wherein the dependencies between each of the non-travel nodes and one of the travel nodes comprise at least an activity dependency;

generating, by a scheduler, an unconstrained schedule using the itinerary components and respective dependencies therebetween, the unconstrained schedule including an earliest start and latest finish time based on the dependencies of the itinerary components including the travel nodes and non-travel nodes, the scheduler automatically extending a date of a particular non-travel node if the date of the particular non-travel node does not match a departure date of the travel node on which the particular non-travel node depends;

allocating, by the scheduler, available inventory to each of the itinerary components according to the unconstrained schedule to fulfill the natural language travel request;

notifying, by the scheduler, one or more of a plurality of suppliers about the natural language travel request, the one or more of the plurality of suppliers being associated with a notification condition concerning the natural language travel request, the notification condition being set by the one or more of the plurality of suppliers and including at least the itinerary components, wherein the itinerary components associated with the unconstrained schedule fulfill the notification condition and wherein the notifying includes providing at least the natural language travel request and the unconstrained schedule to the one or more of the plurality of suppliers;

receiving, by the scheduler, from the one or more of the plurality of suppliers, offers associated with the unconstrained schedule; and

generating, by the scheduler, at least one solution for the natural language travel request to be presented to a customer, the customer being associated with the natural language travel request, the at least one solution being associated with one of the offers, the at least one solution generated even if a constraint from the scheduler cannot be met.

2. The method according to claim 1, wherein generating the unconstrained schedule comprises:

generating an adjacency matrix using the itinerary components and their respective location and time dependencies;

creating a directed acyclic graph using the adjacency matrix; and

determining a topological ordering of itinerary components using the directed acyclic graph, the topological ordering comprising an arrangement of the itinerary components using their respective location and time dependencies.

3. The method according to claim 2, further comprising:

determining one or more implied dependencies between two or more inventory components before the step of creating a directed acyclic graph.

4. The method according to claim 3, wherein allocating comprises:

for each inventory component in the topological ordering, searching for inventory records on an exchange that correspond to itinerary requests, wherein each inventory record is represented by equivalent phrases for a set of metadata attributes of the inventory record as determined by pattern recognition artificial intelligence, the equivalent phrases representing possible natural language queries to which an inventory record may correspond;

determining possible matches between inventory records and itinerary components; and

allocating a possible match for at least one of the inventory components of the topological ordering to fulfill the natural language travel request.

5. The method according to claim 4, wherein determining possible matches comprises selecting a best match for each inventory component based upon a comparison of inventory records to travel preferences included in the natural language travel request.

6. The method according to claim 4, further comprising generating alternative fulfillments for the natural language travel request, wherein each of the alternative fulfillments comprise different allocations of inventory records to itinerary components, relative to one another.

7. The method according to claim 4, wherein allocating comprises allocating at least one possible match to each inventory component of the topological ordering to fulfill the natural language travel request.

8. The method according to claim 1, further comprising:

during execution of a travel itinerary, receiving a modification to the travel itinerary; and

adjusting the allocation of available inventory for each itinerary component remaining in the travel itinerary based upon one or more dependency adjustments caused by modification of the travel itinerary.

9. The method of claim 1, wherein the natural language travel request is an audio request received from the customer.

10. A system for processing natural language travel requests, the system comprising:

a memory for storing executable instructions;

a processor for executing the instructions;

a parser stored in memory and executable by the processor, the parser utilizing pattern recognition artificial intelligence to;

delimit itinerary components from a natural language travel request;

parse delimited strings from the natural language travel request and transmit the delimited strings to a pattern recognition artificial intelligence module stored in memory and executable by a processor to;

decode the type of request by referencing a metadata database and an equivalence class database to recognize keywords in the delimited strings that direct the pattern recognition artificial intelligence module to appropriate content categories for the itinerary components included in the request;

wherein the pattern recognition artificial intelligence module employs an inference functionality which allows for variation among phraseology to account for different ways that natural language queries may be structured;

wherein the itinerary components are in a non-chronological ordering in the natural language travel request, and wherein a portion of the itinerary components are non-travel nodes with at least one non-travel node relating to an activity, and a portion of the itinerary components are travel nodes with at least one travel node relating to a transportation method, each of the non-travel nodes depending on one of the travel nodes;

determine a node type for each of the itinerary components; and

ascertain dependencies between each of the itinerary components based upon respective node types, wherein the dependencies between the travel nodes comprise at least a location and time dependency and wherein the dependencies between the each of the non-travel nodes and one of the travel nodes comprise at least an activity dependency; and

a scheduler stored in memory and executable by the processor to;

generate an unconstrained schedule using the itinerary components and respective dependencies therebetween, wherein the unconstrained schedule includes an earliest start and latest finish for all nodes that are inferred from the dependencies of the itinerary components including the travel nodes and non-travel nodes, and wherein a date of a particular non-travel node is automatically extended if the date of the particular non-travel node does not match a departure date of the travel node on which the particular non-travel node depends;

allocate available inventory to each of the itinerary components according to the unconstrained schedule to fulfill the natural language travel request and provide the unconstrained schedule to a customer;

notify one or more of a plurality of suppliers about the natural language travel request, the one or more of the plurality of suppliers being associated with a notification condition concerning the natural language travel request, the notification condition being set by the one or more of the plurality of suppliers and including at least the itinerary components, wherein the itinerary components associated with the unconstrained schedule fulfill the notification condition, and wherein the notifying includes providing at least the natural language travel request and the unconstrained schedule to the one or more of the plurality of suppliers;

receive from the one or more of the plurality of suppliers, offers associated with the unconstrained schedule; and

generate at least one solution for the natural language travel request to be presented to the customer, the customer being associated with the natural language travel request, the at least one solution being associated with one of the offers, the at least one solution generated even if a constraint from the scheduler cannot be met.

11. The system according to claim 10, wherein dependencies comprise any of a location, a time, a traveler preference, or any combination thereof.

12. The system according to claim 10, wherein the parser further:

generates an adjacency matrix using the itinerary components and their respective location and time dependencies;

creates a directed acyclic graph using the adjacency matrix; and

determines a topological ordering of itinerary components using the directed acyclic graph, the topological ordering comprising an arrangement of the itinerary components using their respective location and time dependencies.

13. The system according to claim 12, wherein the parser further determines one or more implied dependencies between two or more inventory components before the step of creating a directed acyclic graph.

14. The system according to claim 13, wherein for each inventory component in the topological ordering, the scheduler further:

searches for inventory records on an exchange that correspond to itinerary requests, wherein each inventory record is represented by equivalent phrases for a set of metadata attributes of the inventory record as determined by pattern recognition artificial intelligence, the equivalent phrases representing possible natural language queries to which an inventory record may correspond;

determines possible matches between inventory records and itinerary components; and

allocates at least one possible match to each inventory component of the topological ordering to fulfill the natural language travel request.

15. The system according to claim 14, wherein the scheduler determines possible matches by selecting a best match for each inventory component based upon a comparison of inventory records to travel preferences included in the natural language travel request.

16. The system according to claim 14, wherein the scheduler generates alternative fulfillments for the natural language travel request, wherein each of the alternative fulfillments comprise different allocations of inventory records to itinerary components, relative to one another.

17. The system according to claim 14, wherein the scheduler allocates at least one possible match to each inventory component of the topological ordering to fulfill the natural language travel request.

18. The system according to claim 10, further comprising a modifier stored in memory and executable by the processor to:

receive a modification to [[the]]a travel itinerary; and

adjust the allocation of available inventory for each itinerary component remaining in the travel itinerary based upon one or more dependency adjustments caused by modification of the travel itinerary.