PROCESSING AND FULFILLING NATURAL LANGUAGE TRAVEL REQUESTS

• US 20120239443A1
• Filed: 03/14/2012
• Published: 09/20/2012
• 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
• Granted Patent: US 10,275,810 B2
• Time in Patent Office: Days
• US Class Current: 705/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, the method comprising:

decoding itinerary components from a natural language travel request;

determining a node type for each of the itinerary components;

ascertaining dependencies between each of the itinerary components based upon respective node types;

generating an unconstrained schedule using the itinerary components and respective dependencies therebetween; and

allocating available inventory to each of the itinerary components according to the unconstrained schedule to fulfill the natural language travel request.

2. The method according to claim 1, wherein pattern recognition artificial intelligence is utilized to decode the itinerary components by determining phraseology and keywords of the natural language travel request.

3. The method according to claim 1, wherein dependencies comprise any of a location, a time, a traveler preference, or any combination thereof.

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

generating an adjacency matrix using the itinerary components and their respective 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.

5. The method according to claim 4, further comprising:

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

6. The method according to claim 1, wherein allocating comprises:

for each inventory component in the topological ordering, searching for inventory records on an exchange that correspond to the 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.

7. The method according to claim 6, 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.

8. The method according to claim 6, 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.

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

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

during execution of the 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 cause by modification of the travel itinerary.

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

a memory for storing executable instructions;

a processor for executing the instructions;

a parsing module stored in memory and executable by the processor, the parsing module utilizing pattern recognition artificial intelligence to decode itinerary components from a natural language travel request; and

determine a node type for each of the itinerary components;

ascertain dependencies between each of the itinerary components based upon respective node types;

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

generate an unconstrained schedule using the itinerary components and respective dependencies therebetween; and

allocate available inventory to each of the itinerary components according to the unconstrained schedule to fulfill the natural language travel request.

12. The system according to claim 11, wherein parsing module utilizes pattern recognition artificial intelligence to decode the itinerary components by determining phraseology and keywords of the natural language travel request.

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

14. The system according to claim 11, wherein the parsing module further:

generates an adjacency matrix using the itinerary components and their respective 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.

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

16. The system according to claim 11, wherein for each inventory component in the topological ordering, the scheduling module further:

searches for inventory records on an exchange that correspond to the 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.

17. The system according to claim 16, wherein the searching module 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.

18. The system according to claim 16, wherein the searching module 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.

19. The system according to claim 16, wherein the searching module allocates at least one possible match to each inventory component of the topological ordering to fulfill the natural language travel request.

20. The system according to claim 11, further comprising a modification module stored in memory and executable by the processor to:

receive a modification to the 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 cause by modification of the travel itinerary.