System for determination of optimal travel path in a multidimensional space

• US 6,085,147 A
• Filed: 09/26/1997
• Issued: 07/04/2000
• Est. Priority Date: 09/26/1997
• Status: Expired due to Term

• Current Assignee: University Corporation For Atmospheric Research
• Original Assignee: University Corporation For Atmospheric Research
• Inventors: Myers, William Loring
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Beaulieu, Yonel
• Application Number:
  US08/938,246
• Time in Patent Office: 1,012 Days
• Field of Search: 701/209, 701/120, 701/300-2, 701/123, 701/200, 701/201, 701/202, 342/26-30, 342/33, 342/4, 342/36-8
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G05D 1/0005 with arrangements to save energy

Abstract

The present automated vehicle travel path determination system which computes a travel path for a vehicle from an origination point to a destination point based on the operating characteristics of the vehicle as well as phenomena extant in the multidimensional space, which phenomena have an impact on the cost of operation of the vehicle. This vehicle travel path determination system can concurrently consider a plurality of vehicle operating characteristics in selecting the travel path. The travel path is optimized for a weighted selection of a number of cost factors, which weighted selection represents a desired combination of cost factors for the operation of this particular vehicle. This vehicle travel path determination system also considers the time varying nature of the phenomena that exist within the multidimensional space and the impact these time varying phenomena have on the vehicle as it traverses the travel path. The present automated vehicle travel path determination system is disclosed as a flight path calculation system for aircraft, although the concepts of this system are applicable to any form of vehicle travel.

Claims

1. A system for determining a travel path for a vehicle from a first locus to a second locus through a multidimensional space comprising:

means for storing vehicle performance data which identifies operating characteristics of at least one vehicle which is operable to traverse said multidimensional space from said first locus to said second locus;

means for determining a presence, locus and extent of vehicle performance effecting phenomena extant in said multidimensional space; and

means for computing a travel path from said first locus to said second locus through said multidimensional space for a said vehicle as a function of said vehicle performance data associated with said vehicle and said determined vehicle performance effecting phenomena.

2. The system of claim 1 further comprising:

means for transmitting said travel path to said vehicle.

3. The system of claim 2 further comprising:

means for periodically activating said means for computing and said means for transmitting for producing periodic updates of said travel path for said vehicle.

4. The system of claim 2 further comprising:

means, responsive to communication signals received from said vehicle, for activating said means for computing and said means for transmitting for producing an update of said travel path for said vehicle.

5. The system of claim 1 wherein said means for storing vehicle performance data comprises:

means for receiving data from said vehicle which uniquely identifies said vehicle.

6. The system of claim 5 wherein said means for storing vehicle performance data further comprises:

means for receiving data from said vehicle which defines operating characteristics of said vehicle.

7. The system of claim 1 wherein said means for determining comprises:

means for identifying meteorological phenomena extant in said multidimensional space.

8. They system of claim 7 wherein said means for determining further comprises:

means for mapping said meteorological phenomena into at least one region of hazard.

9. The system of claim 1 further comprising:

means for identifying the presence and locus of vehicles extant in said multidimensional space; and

wherein said means for computing is responsive to vehicle presence and locus data received from said means for identifying vehicles for altering said travel path as a function of proximity of other vehicles to said travel path.

10. The system of claim 1 wherein said means for computing comprises:

means for partitioning said multidimensional space, at least between said first locus and said second locus, into a directed graph containing a plurality of nodes and directed edges which interconnect said plurality of nodes, said directed graph extending in at least two dimensions;

means for assigning a cost of vehicle travel to each of said directed edges, said cost of vehicle travel being representative of a predetermined measure of vehicle travel performance for said vehicle traversing said directed edge; and

means for determining a sequence of said directed edges from said first locus to said second locus representative of a desired cost of vehicle travel, said sequence of said directed edges comprising said travel path.

11. The system of claim 10 wherein said means for partitioning creates a three-dimensional array of nodes and directed edges with each node in a two-dimensional plane of said array being connected by a directed edge to every other node in said array which is closer to said second locus than said each node.

12. The system of claim 10 wherein said cost of vehicle travel assigned to each of said directed edges is a function of time, said means for determining a sequence of said directed edges comprises:

means for determining a departure time from said first locus for said vehicle;

means for computing each said cost of vehicle travel for each of said directed edges as a function of said departure time and a time required for said vehicle to reach each of said directed edges; and

means, responsive to said means for computing cost of vehicle travel producing data indicative of a temporal value of cost of vehicle travel for each of said directed edges, for determining said desired cost as a temporally-dependent quantity.

13. The system of claim 12 wherein said means for determining a sequence of said directed edges further comprises:

means for periodically activating said means for computing cost of vehicle travel and said means for determining said desired cost for producing periodic updates of said sequence of said directed edges.

14. The system of claim 12 wherein said means for determining a sequence of said directed edges further comprises:

means for activating said means for computing cost of vehicle travel and said means for determining said desired cost from a present locus of said vehicle on said travel path to said second locus for producing an update of said sequence of said directed edges from said present locus to said second locus.

15. The system of claim 1 wherein said vehicle performance data comprises at least one variable from the class of variables which include but are not limited to:

speed, fuel consumption, measure of safety, complexity of travel path, measures of atmospheric conditions.

16. The system of claim 1 wherein said means for computing a travel path comprises:

means for computing cost of vehicle travel data from said first locus to said second locus for each of a plurality of cost of vehicle travel variables;

means for storing data indicative of weighting factors for each of said cost of vehicle travel variables; and

means for computing a desired cost of vehicle travel from said cost of vehicle travel data and said weighting factors.

17. The system of claim 1 wherein said vehicle comprises an aircraft and said multidimensional space includes an airspace located between said first locus and said second locus, said means for computing a travel path determines a series of headings, operating altitudes and distances, which series comprises a flight plan for said aircraft.

24. The method of claim 1 wherein said step of determining comprises:

identifying meteorological phenomena extant in said multidimensional space.

25. They method of claim 24 wherein said step of determining further comprises:

mapping said meteorological phenomena into at least one region of hazard.

18. A method for determining a travel path for a vehicle from a first locus to a second locus through a multidimensional space comprising the steps of:

storing in a memory vehicle performance data which identifies operating characteristics of at least one vehicle which is operable to traverse said multidimensional space from said first locus to said second locus;

determining a presence, locus and extent of vehicle performance effecting phenomena extant in said multidimensional space; and

computing a travel path from said first locus to said second locus through said multidimensional space for said vehicle as a function of said vehicle performance data associated with said vehicle and said determined vehicle performance effecting phenomena.

19. The method of claim 18, wherein said method is operable on a computer system located remote from said vehicle, said method further comprises the step of:

transmitting said travel path to said vehicle.

20. The method of claim 19 further comprising the step of:

periodically activating said step of computing and said step of transmitting for producing periodic updates of said travel path for said vehicle.

21. The method of claim 19 further comprising the step of:

activating, in response to communication signals received from said vehicle, said step of computing and said step of transmitting for producing an update of said travel path for said vehicle.

22. The method of claim 18 wherein said step of storing vehicle performance data comprises:

receiving data from said vehicle which uniquely identifies said vehicle.

23. The method of claim 22 wherein said step of storing vehicle performance data further comprises:

receiving data from said vehicle which defines operating characteristics of said vehicle.

26. The method of claim 18 further comprising the step of:

identifying the presence and locus of vehicles extant in said multidimensional space; and

wherein said step of computing is responsive to vehicle presence and locus data received from said step of identifying vehicles for altering said travel path as a function of proximity of other vehicles to said travel path.

27. The method of claim 18 wherein said step of computing comprises:

partitioning said multidimensional space, at least between said first locus and said second locus, into a directed graph containing a plurality of nodes and directed edges which interconnect said plurality of nodes, said directed graph extending in at least two dimensions;

assigning a cost of vehicle travel to each of said directed edges, said cost of vehicle travel being representative of a predetermined measure of vehicle travel performance for said vehicle traversing said directed edge; and

determining a sequence of said directed edges from said first locus to said second locus representative of a desired cost of vehicle travel, said sequence of said directed edges comprising said travel path.

28. The method of claim 27 wherein said step of partitioning comprises:

creating a three-dimensional array of nodes and directed edges with each node in a two-dimensional plane of said array being connected by a directed edge to every other node in said array which is closer to said second locus than said each node.

29. The method of claim 27 wherein said cost of vehicle travel assigned to each of said directed edges is a function of time, said step of determining a sequence of said directed edges comprises:

determining a departure time from said first locus for said vehicle;

computing each said cost of vehicle travel for each of said directed edges as a function of said departure time and a time required for said vehicle to reach each of said directed edges; and

determining, in response to said step of computing cost of vehicle travel producing data indicative of a temporal value of cost of vehicle travel for each of said directed edges, said desired cost as a temporally-dependent quantity.

30. The method of claim 29 wherein said step of determining a sequence of said directed edges further comprises:

periodically activating said step of computing cost of vehicle travel and said step of determining said desired cost for producing periodic updates of said sequence of said directed edges.

31. The method of claim 29 wherein said step of determining a sequence of said directed edges further comprises:

activating said step of computing cost of vehicle travel and said step of determining said desired cost from a present locus of said vehicle on said travel path to said second locus for producing an update of said sequence of said directed edges from said present locus to said second locus.

32. The method of claim 18 wherein said vehicle performance data comprises at least one variable from the class of variables which include but are not limited to:

speed, fuel consumption, measure of safety, complexity of travel path, measures of atmospheric conditions.

33. The method of claim 18 wherein said step of computing a travel path comprises:

computing cost of vehicle travel data from said first locus to said second locus for each of a plurality of cost of vehicle travel variables;

storing data indicative of weighting factors for each of said cost of vehicle travel variables; and

computing a desired cost of vehicle travel from said cost of vehicle travel data and said weighting factors.

34. The method of claim 18 wherein said vehicle comprises an aircraft and said multidimensional space includes an airspace located between said first locus and said second locus, said step of computing a travel path comprises:

determining a series of headings, operating altitudes and distances, which series comprises a flight plan for said aircraft.