Hazard detection for a travel plan

• US 6,421,603 B1
• Filed: 08/11/1999
• Issued: 07/16/2002
• Est. Priority Date: 08/11/1999
• Status: Expired due to Term

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell International Inc.
• Inventors: Pratt, Stephen G., Hartmann, Gary L.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): PIPALA, EDWARD J
• Application Number:
  US09/372,632
• Time in Patent Office: 1,070 Days
• Field of Search: 701/4, 701/14, 701/9, 701/202, 701/206, 701/209, 701/208, 701/212, 701/300, 701/301, 244/158.R, 244/175, 340/961, 340/970, 342/26
• US Class Current: 701/206
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/0086 for monitoring terrain radar or analogous systems specially adapted for terrain avoidance G01S13/935

Abstract

A flight plan is modeled by a trajectory with a set of segments having finite lateral and altitude extents between nominal way points. A terrain database stores hierarchical patches with maximum and minimum altitudes and pointers or altitudes for subpatches. Linear-programming inequality constraints match segments with patches. A search finds any terrain locations that impinge upon the trajectory tube, indicating an error condition for the plan. Moving hazards are modeled with segmented trajectories. Conflict with a moving hazard occurs when moving bubbles within both of the trajectories overlap in both space and time.

Claims

1. A method of evaluating a predicted plan for conflict with a hazard, comprising:

defining the predicted plan as a trajectory including a set of segments having parameters denoting finite spatial extents, the parameters for all segments being specifiable arbitrarily and independently of those for any others of the segments;

representing a hazard as a collection of features having finite spatial extents;

determining whether at least a portion of at least one of the segments conflicts with any of the features of the hazard;

if so, signaling a conflict.

2. A medium bearing computer-readable representations of instructions and data for causing a programmable computer to perform the method of claim 1.

3. The method of claim 1 where the plan is a predicted aircraft flight plan.

4. The method of claim 1 where the hazard model includes a plurality of terrain patches in a geographic area, each patch having an altitude parameter.

5. The method of claim 4 where the trajectory segments have altitude parameters.

6. The method of claim 5 where conflict determination comprises detecting whether the altitude parameter of any segment does not exceed the altitude parameter of the terrain patches at the same location in the geographic area.

7. The method of claim 6 where each patch further includes a plurality of pointer to subpatches each having a maximum altitude.

8. The method of claim 1 where the hazard model includes a set of segments each having an independently specifiable finite extent in a plurality of dimensions.

9. The method of claim 8 where both of the models include bubbles having respective finite extents and times associated therewith.

10. The method of claim 9 where the detector determines whether the bubbles conflict with each other in both space and time.

11. A method of evaluating a predicted plan for conflict with a hazard, comprising:

defining the predicted plan as a trajectory including a plurality of segments each having independently and arbitrarily specifiable parameters denoting finite spatial extents;

storing a database of data representing terrain;

for each segment, determining whether at least a portion of at least one of the segments intersects the terrain represented by the data;

if so, signaling an error condition.

12. A medium bearing computer-readable representations of instructions and data for causing a programmable computer to perform the method of claim 11.

13. The method of claim 11 where the plan is a predicted aircraft flight plan.

14. The method of claim 11 where the plan includes altitude information, and wherein at least one of the parameters of each segment denotes the altitude information.

15. The method of claim 14 where the terrain data is stored as a hierarchical set of patches and subpatches each representing a certain part of the geographical area.

16. The method of claim 15 wherein the terrain data for each patch includes a maximum altitude for that patch, a minimum altitude for that patch, and at least one pointer to a subpatch for that patch.

17. The method of claim 14 wherein determining whether at least a portion of at least one of the segments intersects the terrain represented by the data comprises:

determining whether a first altitude of terrain in a certain area bears a first relation to a first altitude of one of the segments;

if not, repeating the above step for each of a plurality of subareas;

if so, signaling the error condition.

18. The method of claim 17 wherein determining whether at least a portion of at least one of the segments intersects the terrain represented by the data further comprises:

calculating a first altitude of the one segment associated with the certain area;

determining whether the first altitude associated with the area bears the first relation to the first altitude of one of the segments;

if so, omitting the signaling step.

19. The method of claim 11 further comprising:

modeling the segments as systems of inequality constraints;

modeling a plurality of patches of the terrain as systems of inequality constraints;

determining portions of the patches associated with particular ones of the segments as those portions that satisfy the systems of constraints.

20. The method of claim 19 wherein the determining step comprises:

constructing a cost function associated with the segments;

minimizing the cost function within the portions of the patches.

21. The method of claim 11 wherein the plan includes time information, and wherein at least one of the parameters of each segment denotes the time information.

22. The method of claim 11 further comprising:

constructing in the plan trajectory a plan bubble having parameters denoting finite spatial extents and times;

defining a hazard trajectory including a set of segments and a hazard bubble having parameters denoting finite spatial extents and times;

for each segment of the plan trajectory, determining whether the plan bubble overlaps the hazard bubble in both space and time;

if so, signaling the error condition.

23. The method of claim 11 wherein determining whether at least a portion of at least one of the segments intersects the terrain represented by the data is performed only in spatial coordinates, independently of time.

24. A method of evaluating a plan for conflict with a hazard, comprising:

defining the predicted plan as a plan trajectory including a set of segments each having parameters denoting finite spatial extents;

defining the hazard as a hazard trajectory including a set of segments each having separate and independently specifiable parameters denoting finite spatial extents;

for each segment, determining whether the plan bubble overlaps the hazard bubble in both space and time;

if so, signaling the error condition.

25. A medium bearing computer-readable representations of instructions and data for causing a programmable computer to perform the method of claim 24.

26. The method of claim 24 where the plan is a predicted aircraft flight plan.

27. The method of claim 24 where the trajectories include altitude information, and wherein at least one of the parameters of each segment denotes the altitude information.

28. The method of claim 24 further comprising:

modeling the bubbles as systems of inequality constraints;

determining bubble overlap as regions that satisfy all the systems of constraints.

29. The method of claim 28 where determining bubble overlap comprises:

constructing a cost function associated with the bubbles;

detecting a certain value of the cost function within the regions.

30. The method of claim 24 where one of the spatial extents of a hazard bubble depends upon at least one of the spatial extents of the hazard-trajectory segment in which it is located, and another of the spatial extents of the hazard bubble is independent of the spatial extents of such hazard segment.

31. The method of claim 30 where the other of the hazard-bubble spatial extents is constant for all segments of the hazard trajectory.

32. The method of claim 30 where the other of the hazard-bubble spatial extents depends upon a characteristic of the hazard.

33. A system for evaluating a predicted plan with a hazard, comprising:

a trajectory model including a set of segments within a geographic area, each of the segments having a finite extent in a plurality of dimensions;

a hazard model including data representing predetennined features of a hazard as a plurality of nested patches and subpatches within the geographic area of the trajectory model;

a detector for determining whether at least a portion of any of the segments conflicts with the hazard model within any portion of the geographic area;

an indicator responsive to the detector for producing an error condition indicating the conflict.

34. The system of claim 33 where the plan is a predicted aircraft flight plan.

35. The system of claim 33 where each of the trajectory segments has an altitude extent.

36. The system of claim 35 where the hazard model includes data representing altitudes of terrain over the geographic area.

37. The system of claim 36 where the detector determines whether the altitude extent of any segment does not exceed an altitude of the terrain at any point in the trajectory model.

38. The system of claim 36 where the hazard model represents the geographic area as a plurality of patches each having maximum altitudes.

39. The system of claim 38 where each patch further includes a plurality of pointers to subpatches each having a maximum altitude.

40. The system of claim 33 where the detector determines conflicts on the basis of spatial extents, independently of time.

41. A system for evaluating a predicted plan with a hazard, comprising:

means for modeling a trajectory including a set of segments within a geographic area, each of the segments having a finite independently specifiable extent in a plurality of dimensions;

means for modeling a hazard including data representing predetermined features of a hazard within the geographic area of the trajectory model;

means for determining whether at least a portion of any of the segments conflicts with the hazard model within any portion of the geographic area;

means responsive to the determining means for producing an error condition indicating the conflict.

42. The system of claim 41 where both the trajectory segments and the hazard data include altitude information, and where the determining means detects a conflict between the altitude information in the trajectory segments and that in the hazard data.

43. The system of claim 41 where the hazard data includes a further set of segments within the geographic area and having a finite extent in a plurality of dimensions, and where the determining means detects a conflict in both space and time between the trajectory segments and the hazard segments.

44. A data structure for evaluating a predicted plan, comprising a predicted trajectory including a plurality of segments defined by waypoints, each of the segments including a horizontal path having a lateral extent parameter and a vertical path including an altitude extent parameter, at least one of the parameters for each segment is independent of the corresponding parameter for all other segments in the same trajectory.

45. The data structure of claim 44 where the trajectory is a predicted flight plan for an aircraft.

46. The data structure of claim 44 where each of the waypoints has parameters denoting both a geographical position and an altitude.

47. The data structure of claim 44 where the trajectory forms a parallelopiped defined by a system of inequality constraints.

48. The data structure of claim 44 further comprising a second trajectory including a second plurality of segments defined by waypoints and each including a path having a lateral extent parameter.

49. The data structure of claim 48 where the second trajectory is a predicted track of a hazard.

50. The data structure of claim 48 where at least some of the second plurality of segments have altitude extent parameters.

51. The data structure of claim 48 where the second trajectory further includes a bubble having a spatial extent and an associated time.

52. The data structure of claim 51 where the first trajectory also includes a bubble having a spatial extent and an associated time.

53. The data structure of claim 44 where both the lateral extent parameter and the altitude extent parameter for each segment are independent of those for all other segments in the trajectory.

54. A data structure for evaluating a predicted plan, comprising a hierarchical plurality of patches and subpatches together forming a geographic area, each patch containing an altitude parameter and at least one pointer to a subpatch representing a smaller portion of the area covered by its parent patch.

55. The data structure of claim 54 where at least some of the subpatches themselves contain the altitude parameter for all of their parent patches.

56. The data structure of claim 54 where at least some of the subpatches themselves contain at least one pointer to a further subpatch and also contain at least one altitude parameter for another further subpatch.

57. The data structure of claim 54 where the patches and subpatches are organized so as to denote their geographic position within the area implicitly, and where the patches and subpatches themselves contain no explicit position information.