System and method for routing decisions in a separation management system

BACKGROUND

The present disclosure relates generally to routing of vehicles to maintain separation of vehicles and to avoid obstacles. More particularly, the present disclosure relates to systems and methods of supporting routing decisions in a separation management system.

Aircraft and other vehicles in motion may encounter many moving and stationary obstacles. Moving obstacles include other aircraft, flocks of birds, and weather systems. Stationary obstacles include natural objects, such as terrain, and man-made objects, such as towers and buildings. An aircraft moving along its flight path may be required to change headings numerous times due to expected and unexpected obstacles. The operator of the aircraft may seek to execute heading changes that maintain adherence to scheduled arrival time while observing constraints regarding speed, altitude, safety, and passenger comfort.

SUMMARY

The present invention is set out in the independent claims, with some optional features set out in the claims dependent thereto.

The illustrative embodiments provide for a method using a computer in conjunction with a non-transitory computer readable storage medium. The method comprises the computer receiving at least one of time-referenced and location-referenced state data for an object of interest. The method also comprises the computer determining a present location of a control vehicle within two presently overlapping fat paths wherein a fat path comprises a homotopically distinct region of travel. The method also comprises the computer determining distance of the control vehicle from a point of divergence of the fat paths, the fat paths diverging to avoid the object of interest. The method also comprises the computer generating a decision boundary reachable prior in time to the point of divergence wherein the decision boundary is in advance of the present location of the control vehicle. The method also comprises the computer generating a first set of feasible headings and a second set of feasible headings for the control vehicle, the first set and the second set respectively associated with a projected first crossing point and a projected second crossing point of the decision boundary by the control vehicle wherein feasible headings promote positioning of the control vehicle in one of the fat paths beyond the point of divergence. The method also comprises the computer sending the first set of feasible headings and the second set of feasible headings to the control vehicle prior to the control vehicle reaching the decision boundary.

The illustrative embodiments also provide an apparatus. The apparatus comprises an aircraft comprising a fuselage configured for flight and a computer, comprising a bus, a processor connected to the bus, and a memory connected to the bus, the memory storing program code which, when executed by the processor, performs a computer-implemented method. The program code comprises program code for performing, using the processor, receiving time-referenced state data for an object of interest. The program code also comprises program code for performing, using the processor, determining feasible routing path options for at least the aircraft. The program code also comprises program code for performing, using the processor, generating at least one decision boundary for selection of at least one routing path option from the feasible routing path options. The program code also comprises program code for performing, using the processor, determining at least one heading range from a crossing point of the decision boundary within the at least one routing path option, wherein the at least one heading range keeps multiple fork options open and promotes avoidance of the object of interest by the aircraft, the object of interest comprising at least one of a moving vehicle, a stationary object, a terrain object, a no-fly zone, a restricted operating zone, and a weather system proximate the aircraft.

The illustrative embodiments also provide a method using a computer in conjunction with a non-transitory computer readable storage medium. The method comprises a computer receiving four-dimensional virtual predictive radar data for a control vehicle from a separation management system. The method also comprises the computer determining intersections of fat paths for the control vehicle extracted from the four dimensional virtual predictive radar data, wherein fat paths comprise homotopically distinct regions of travel. The method also comprises the computer determining intersection forks associated with the intersections of the fat routing paths. The method also comprises the computer selecting a first intersection fork based on metrics calculated for the determined intersection forks. The method also comprises the computer determining at least one event horizon associated with the first intersection fork, wherein observation of the at least one event horizon by the control vehicle prevents the control vehicle from entering an area containing forbidden heading ranges.

A method using a computer in conjunction with a non-transitory computer readable storage medium, the method comprising the computer receiving at least one of time-referenced and location-referenced state data for an object of interest; the computer determining a present location of a control vehicle within two presently overlapping fat paths wherein a fat path comprises a homotopically distinct region of travel; the computer determining distance of the control vehicle from a point of divergence of the fat paths, the fat paths diverging to avoid the object of interest; the computer generating a decision boundary reachable prior in time to the point of divergence wherein the decision boundary is in advance of the present location of the control vehicle; the computer generating a first set of feasible headings and a second set of feasible headings for the control vehicle, the first set and the second set respectively associated with a projected first crossing point and a projected second crossing point of the decision boundary by the control vehicle wherein feasible headings promote positioning of the control vehicle in one of the fat paths beyond point of divergence; and the computer sending the first set of feasible headings and the second set of feasible headings to the control vehicle prior to the control vehicle reaching the decision boundary.

The method wherein the object of interest comprises at least one of a moving vehicle, a stationary object, a terrain object, a no-fly zone, a restricted operating zone, and a weather system proximate the control vehicle and combinations thereof. The method wherein the control vehicle and the at least one moving vehicle are one of aircraft, watercraft, submarines, and ground vehicles. The method further comprising the computer generating maneuver manifold information for the control vehicle. The method wherein the first set of feasible headings and the second set of feasible headings direct the control vehicle to a first fork option and a second fork option, respectively, and wherein following one of the first fork option and the second fork option promotes reaching a destination on schedule and promotes meeting of maneuver constraints and operational constraints.

The method wherein the at least one decision boundary comprises one or more points in at least one of space and time past which an operator of the control vehicle cannot invoke a change of heading from a first routing path to a second routing path while meeting constraints described in the maneuver manifold information. The method wherein the computer is at least one of installed aboard the control vehicle, installed aboard an unmanned aircraft system, and installed at an air traffic control center. The method wherein the determined heading range is communicated to one of a human operator of the control vehicle, a non-human operator of the control vehicle, and an air traffic controller. The method wherein the computer generates optimal heading to maximize routing options of the control vehicle.

An aircraft comprising a fuselage configured for flight; a computer, comprising a bus; a processor connected to the bus; and a memory connected to the bus, the memory storing program code which, when executed by the processor, performs a computer-implemented method, the program code comprising program code for performing, using the processor, receiving time-referenced state data for an object of interest; program code for performing, using the processor, determining feasible routing path options for at least the aircraft; program code for performing, using the processor, generating at least one decision boundary for selection of at least one routing path option from the feasible routing path options; and program code for performing, using the processor, determining at least one heading range from a crossing point of the decision boundary within the at least one routing path option, wherein the at least one heading range keeps multiple fork options open and promotes avoidance of the object of interest by the aircraft, the object of interest comprising at least one of a moving vehicle, a stationary object, a terrain object, a no-fly zone, a restricted operating zone, and a weather system proximate the aircraft.

The aircraft of wherein the program code further performs, using the processor, receiving maneuver manifold information for the aircraft comprising maneuver constraints and operational constraints. The aircraft wherein the program code determines heading ranges from points where the aircraft is located and from points where the aircraft is not located. The aircraft wherein the at least one decision boundary comprises a point in one of space and time after which an operator of the aircraft cannot invoke a change of heading from a first routing path to a second routing path while meeting constraints described in the maneuver manifold information. The aircraft wherein the computer generates optimal heading to maximize routing options of the aircraft.

A method using a computer in conjunction with a non-transitory computer readable storage medium, the method comprising a computer receiving four-dimensional virtual predictive radar data for a control vehicle from a separation management system; the computer determining intersections of fat paths for the control vehicle extracted from the four dimensional virtual predictive radar data, wherein fat paths comprise homotopically distinct regions of travel; the computer determining intersection forks associated with the intersections of the fat paths; the computer selecting a first intersection fork based on metrics calculated for the determined intersection forks; and the computer determining at least one event horizon associated with the first intersection fork, wherein observation of the at least one event horizon by the control vehicle prevents the control vehicle from entering an area containing forbidden heading ranges.

The method wherein the at least one event horizon comprises a boundary in one of space and time wherein a decision must be acted upon regarding choice of routing path. The method wherein upon choice of routing path, a change of heading cannot be safely invoked if operational constraints are to be met.

The method wherein operational constraints are associated with the control vehicle and comprise at least one of speed, location, and altitude. The method wherein the object of interest comprises at least one of a moving vehicle, a stationary object, a terrain object, a no-fly zone, a restricted operating zone, and a weather system proximate the control vehicle. The method wherein the virtual predictive radar data comprises the routing paths, information about obstacles, time rings, intended route of control vehicle, operational constraints, and maneuver constraints.

The features, functions, and benefits may be achieved independently in various embodiments of the present disclosure or may be combined in yet other embodiments in which further details can be seen with reference to the following description and drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the illustrative embodiments are set forth in the appended claims. The illustrative embodiments, however, as well as a preferred mode of use, further objectives and features thereof, will best be understood by reference to the following detailed description of an illustrative embodiment of the present disclosure when read in conjunction with the accompanying drawings, wherein: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001"><b>Figure 1</b></figref> is an illustration of a block diagram of a system of routing decisions in a separation management system.</li><li><figref idref="f0002"><b>Figure 2</b></figref> is a flowchart of a method for routing systems in a separation management system in accordance with an illustrative embodiment.</li><li><figref idref="f0003"><b>Figure 3</b></figref> is a diagram providing a schematic view of illustrative safe separation windows for aircraft with varying degrees of uncertainty according to an embodiment of the present disclosure.</li><li><figref idref="f0004"><b>Figure 4</b></figref> is a diagram of a system of virtual predictive radar in accordance with an illustrative embodiment.</li><li><figref idref="f0005"><b>Figure 5</b></figref> is a chart illustrating routing decision software in use with a routing manifold generating application in accordance with an illustrative embodiment.</li><li><figref idref="f0006"><b>Figure 6</b></figref> is a diagram of a virtual predictive radar in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0007"><b>Figure 7</b></figref> is a diagram of a portion of a virtual predictive radar in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0007"><b>Figure 8</b></figref> is a diagram of a portion of a virtual predictive radar in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0008"><b>Figure 9</b></figref> is a diagram of a virtual predictive radar in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0009"><b>Figure 10</b></figref> is a diagram illustrating a use case in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0010"><b>Figure 11</b></figref> is an aircraft option graph in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0010"><b>Figure 12</b></figref> is an aircraft progress graph in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0011"><b>Figure 13</b></figref> is an aircraft progress graph in accordance with an embodiment of the present disclosure.</li><li><figref idref="f0011"><b>Figure 14</b></figref> is a flowchart of a method for routing systems in a separation management system in accordance with an illustrative embodiment.</li><li><figref idref="f0012"><b>Figure 15</b></figref> is an illustration of a data processing system, in accordance with an illustrative embodiment.</li></ul>

DETAILED DESCRIPTION

An aircraft may follow at least one homotopically distinct region of travel, referred to herein as a "fat path." A plurality of fat paths may be calculated between a time referenced position of an aircraft and reference point based on maneuvering characteristics of the aircraft and a probabilistic zone of interest for other aircraft. A separation management system receives and filters aircraft and airspace information about a control aircraft and other aircraft the control aircraft seeks to avoid. Trajectory windows for each aircraft may be determined and monitored with respect to time and probable location. The separation management system determines when trajectory overlap may occur and may reroute the control vehicle. A virtual predictive radar screen may display a plurality of trajectory paths for a control vehicle and may include time rings predicting the location of the control vehicle in three-dimensional space. Based on maneuverability characteristics and speed of the control vehicle, constraints may be placed on the control vehicle. When a second vehicle is detected near one of the time rings of the control vehicle, a fat path may be generated along a subset of the plurality of trajectory paths to maintain separation of the control vehicle from the second vehicle.

Homotopically distinct regions of travel, hereinafter "fat paths", separation management systems, virtual predictive radar, and their supporting methods and systems are described in further detail in "Automated Separation Manager", <patcit id="pcit0001" dnum="US8060295B"><text>U.S. Patent No. 8,060,295 dated November 15, 2011</text></patcit>. Also relevant is <patcit id="pcit0002" dnum="US69263312A" dnum-type="L"><text>U.S. Patent Application No. 13/692633</text></patcit> entitled "Systems and Methods for collaboratively Controlling At Least One Aircraft", filed December 3, 2012.

The illustrative embodiments recognize and take into account the issues described above regarding the need for a control vehicle, for example an aircraft, to be provided navigation and heading information well in advance of reaching decision points. The illustrative embodiments provide methods for aiding decision-making in maintaining safe separation between an aircraft and other objects and regions of avoidance. State data for objects of interest, for example other aircraft, that are referenced by time and location is gathered. Maneuver manifold information for the subject aircraft including constraints for speed, altitude, safety and passenger comfort is received. Currently feasible routing options for the subject aircraft are determined. Based on information about the objects of interest, maneuver manifold information, and the currently feasible routing path options, the illustrative embodiments provide for determination of decision boundaries and heading ranges for the subject aircraft. Heading ranges may be determined from points where the subject aircraft is located and from points where the subject aircraft is not located. Illustrative embodiments provide methods for determining heading ranges that are feasible and for determining heading ranges that are forbidden.

At any point along an aircraft flight path, objects of interest may lie between the aircraft and points ahead of the aircraft along an intended flight path of the aircraft. One or more homotopically distinct regions of travel, referred to herein as fat paths, may be mapped for the aircraft between any point on its path and destination points. The fat paths are based on distance to destination, maneuver constraints, and objects of interest to be avoided along the way, some of which may themselves be in motion.

As an aircraft travels, it may have options of several fat paths to follow. At times, two or more fat paths may overlap one another. The aircraft may be flying within two or more fat paths during some periods. When the aircraft is presently traveling in an intersection of two fat paths and is approaching an obstacle, the fat paths may diverge to avoid the obstacle. Two or more overlapping fat paths may diverge for reasons unrelated to obstacles.

When overlapping fat paths diverge or are known to be diverging ahead, whether in the face of an obstacle or not, options available to the aircraft are called "fork options." The operator of the aircraft or other party in control may choose which fork option to take. In other words, the operator may choose which fat path or combinations of overlapping fat paths to follow. The decision of which fork option to choose may be made while remaining on schedule to reach the destination on time, all the while observing the constraints including speed, altitude, safety, and comfort. The illustrative embodiments may assist in achieving these objectives.

Prior to the points in time and in space wherein two or more overlapping fat paths diverge in the face of an increasingly proximate stationary or moving obstacle, the illustrative embodiments provide that a decision boundary may be determined for the aircraft. The decision boundary is a simply connected set of points reached by the aircraft before the divergence point. The decision boundary is located far enough in advance of the obstacle and the fat path divergence point that the aircraft may be provided a range of choices of safe headings from which to choose. For each point along the decision boundary that the aircraft may cross, illustrative embodiments provide at least one heading range for the aircraft to safely follow. The heading ranges may keep open multiple fork options. In other words, even after reaching the decision boundary, the aircraft may have two or more available options of fat paths to follow to bypass the obstacle. The illustrative embodiments provide heading ranges that may be optimized so that routing options are maximized for the aircraft.

The decision boundary may also be a time or location at which the aircraft must be on a route to at least one of the fork options in order to maintain the maneuver and safety constraints. The decision boundary may be expressed as a range of times or simply as a connected set of points at which the aircraft must initiate an action to turn or maintain course on a route to one of the routing options to maintain the maneuver and safety constraints. Because the decision boundary is determined in advance of the aircraft reaching it, it may not be known where along the decision boundary that the aircraft will cross the decision boundary. Since headings may depend on the aircraft's location at the time it crosses the decision boundary, the illustrative embodiments provide for a plurality of headings to be calculated and made available to the aircraft, ground control, or others at the time the decision boundary is determined.

Attention is now turned to the figures. <figref idref="f0001"><b>Figure 1</b></figref> is an illustration of a block diagram of a system <b>100</b> of routing decisions in a separation management system. System <b>100</b> includes control vehicle <b>102,</b> computer <b>104,</b> application <b>106,</b> obstacle <b>108,</b> obstacle <b>110,</b> obstacle <b>112,</b> fat path <b>114,</b> fat path <b>116,</b> fat path <b>118,</b> origination point <b>120,</b> destination point <b>122,</b> decision boundary <b>124,</b> and routing manifold <b>126.</b>

Control vehicle <b>102</b> may be an aircraft including fixed wing airplane, helicopter, glider, balloon, blimp, or unmanned aircraft. Control vehicle <b>102</b> may be watercraft including ship or submarine. Control vehicle <b>102</b> may be a land-based vehicle.

Computer <b>104</b> may be a general purpose computer. General purpose computers are described with respect to <figref idref="f0012"><b>Figure 15</b></figref><b>.</b> Computer <b>104</b> may be situated aboard control vehicle <b>102.</b> Computer <b>104</b> may be situated at a ground location, for example at an air traffic control center. Computer <b>104</b> may be multiple computers working together towards a goal, including computers in different physical locations.

Application <b>106</b> may execute on computer <b>104</b> and may execute the actions provided herein regarding setting boundaries in time and space in which operators of control vehicle <b>102</b> make decisions regarding headings. In an embodiment, portions of application <b>106</b> may execute on more than one computer <b>104</b> that may be situated at more than one location or aboard more than one aircraft or other vehicle.

Obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112</b> may include aircraft, balloons, gliders, unmanned aerial vehicles that may be stationary or in motion. Obstacle <b>108,</b> obstacle <b>110,</b> obstacle <b>112</b> also may include flocks of birds, weather systems, and any other object either stationary or in motion that control vehicle <b>102</b> desires to avoid. Obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112</b> may also be ground-based and be a natural object such as terrain comprising mountain ranges for example, or may be man-made, for example a communications tower, a building, or a no-fly zone. In maritime embodiments, obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112</b> may be other ships, submarines, buoys, terrain, both submerged or not, and weather systems.

Fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118</b> are homotopically distinct regions of travel. Fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118</b> may be calculated between a time referenced position of control vehicle <b>102</b> and a reference point based on maneuvering characteristics of control vehicle <b>102</b> and a probabilistic zone of interest for obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112</b> including other aircraft. Fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118</b> is a maximal simply connected region contained in routing manifold <b>126</b> wherein the region is such that for each point in the region there exists a feasible route for control vehicle <b>102</b> that contains the point, that begins at origination point <b>120</b> and ends at destination point <b>122.</b> A route for control vehicle <b>102</b> is feasible if the route satisfies scheduling requirements and constraints and is physically possible.

Given a set of obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112</b> to avoid, maneuver and operational constraints for control vehicle <b>102,</b> origination point <b>120,</b> destination point <b>122,</b> and routing manifold <b>126</b> may be a union of possible paths in space and time from a start state to an end state that satisfy constraints and avoid obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112.</b> Maneuver and operational constraints may include speed, altitude, safety, and passenger comfort.

Decision boundary <b>124</b> is a simply connected set of points in at least one of time and space. In order to maintain a feasible path, upon reaching a point along decision boundary <b>124,</b> control vehicle <b>102</b> must be either on a path that transitions to a fork option including one or more of fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118</b> or initiate a change of heading onto a different fat path that transitions to a different one of fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118.</b> Decision boundary <b>124</b> is also referred herein to as an "event horizon" and as a "practical event horizon."

Additional components and concepts are defined herein. A fat path identifier is a number, symbol, word or phrase that uniquely identifies any one of fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118</b> in routing manifold <b>126.</b> If "FP" is one of a fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118,</b> then FP=(R,i) where R is a region of time and space encompassed by FP and "i" is the identifier of FP.

A theoretical event horizon is a boundary associated with a fat path intersection and includes points in the fat path intersection such that there exists a feasible heading at the points such that a transition to each fat path option abutting an end point is theoretically possible. A theoretical event horizon is a simply connected set of points that partitions a maximal fat path intersection (described below) point set into a first and second connected sets such that, for any point in the first set, there exists a forbidden heading range (described below) located at the point. For any point in the second set there exists no forbidden heading range at the point.

A practical event horizon region is a region bounded by a decision boundary <b>124</b> and boundaries of one or more of fat path <b>114,</b> fat path <b>116,</b> and fat path <b>118.</b> A theoretical event horizon region is a region bounded by theoretical event horizon and fat path boundaries.

An event horizon avoidance boundary is a boundary associated with decision boundary <b>124</b> or an event horizon wherein in order to avoid a practical event horizon region, control vehicle <b>102</b> must have initiated a maneuver onto a fat path option at the time of reaching event horizon avoidance boundary and may be unable to safely invoke a change of heading onto a different fat path option after reaching decision boundary <b>124,</b> if the practical event horizon region is to be avoided. A forbidden heading fan is associated with a point in a fat path fork and includes a contiguous range of headings that are not feasible for any fork option.

An avoidance heading fan is associated with a point in a fat path fork and includes a contiguous range of headings that are not feasible for any fork option. A splitting curve is a curve in a fat path intersection where each curve point is associated with a heading and the curve splits available options according the heading behavior of control vehicle 102 along the curve. Maximum options are retained if a heading of control vehicle <b>102</b> at a point on the curve is the splitting curve associated heading.

If <i>"FPI"</i> is a maximal fat path intersection then <i>FPI</i> is associated with a region <maths id="math0001" num=""><math display="inline"><mrow><mi>R</mi><mfenced><mi mathvariant="italic">FPI</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><mrow><mstyle displaystyle="false"><mrow><munderover><mrow><mo>∩</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mrow></mstyle><msub><mi mathvariant="italic">fp</mi><mi>i</mi></msub><mo>,</mo></mrow></mstyle></mrow></math><img file="EP2811477B1_D0001.tif" /></maths> where the <i>fp_i</i> are fat paths and if <i>fp</i> is any fat path with <i>fp</i> ∩ <i>R(FPI)</i> ≠ Ø then <i>fp = fp_i</i> for some <i>i</i> = 1,...,<i>n</i>. <i>FPI</i> is also associated with a set of labels<maths id="math0002" num=""><math display="inline"><mrow><mi>L</mi><mfenced><mi mathvariant="italic">FPI</mi></mfenced><mo>=</mo><msubsup><mfenced open="{" close="}" separators=""><mi>L</mi><mfenced><msub><mi mathvariant="italic">fp</mi><mi>i</mi></msub></mfenced></mfenced><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo></mrow></math><img file="EP2811477B1_D0002.tif" /></maths> where for each <i>i, L</i>(<i>fp_i</i>) is a fat path identifier that uniquely identifies fat path <i>fp_i.</i> A fork option for <i>FPI</i> is a maximal fat path intersection <i>FPI⁰</i> such that 1) <i>L</i>(<i>FPI⁰</i>) ⊂ <i>L</i>(<i>FPI</i>)<i>;</i> 2) <i>L</i>(<i>FPI</i>) ⊄ <i>L</i>(<i>FPI⁰</i>)<i>;</i> 3) <i>closure</i>(<i>FPI⁰</i>) ∩ <i>closure</i>(<i>FPI</i>) <i>≠</i> Ø; 4) there is a feasible path for control vehicle <b>102</b> that transitions from <i>R</i>(<i>FPI</i>) to <i>R</i>(<i>FPI⁰</i>)<i>.</i>

Let <i>FPI</i> be a maximal fat path intersection and <i>p</i> be a point in <i>R</i>(<i>FPI</i>)<i>.</i> Then a feasible heading range <i>HR</i> at <i>p</i> is a contiguous set of headings such that if <i>h</i> ∈ <i>HR</i> then there is a feasible path through <i>p</i> such that control vehicle <b>102</b> following the path would have the heading <i>h</i> at <i>p</i>. A maximal feasible heading range is a feasible heading range that cannot be made larger.

A feasible heading range with respect to a fork option is a feasible heading range such that any heading in the heading range is feasible for the fork option. In this case there exists a path that transitions from the maximal fat path intersection to the fork option. A maximal feasible heading range with respect to a fork option is a feasible heading range with respect to a fork option that cannot be made larger.

A forbidden heading range at a point is a contiguous set of headings such that there exists no feasible path through the point such that control vehicle <b>102</b> following the path would have the heading at the point. Forbidden heading range with respect to a fork is defined as follows: given a point in a maximal fat path intersection, a forbidden heading range at the point is a contiguous set of headings such that for any heading in the range, there is no fork option for which the heading is feasible.

The illustrative embodiments shown in <figref idref="f0001"><b>Figure 1</b></figref> are not meant to imply physical or architectural limitations to the manner in which different illustrative embodiments may be implemented. Other components in addition to and/or in place of the ones illustrated may be used. Some components may be unnecessary in some illustrative embodiments. Also, the blocks are presented to illustrate some functional components. One or more of these blocks may be combined and/or divided into different blocks when implemented in different illustrative embodiments.

<figref idref="f0002"><b>Figure 2</b></figref> is a flowchart of a method for routing systems in a separation management system in accordance with an illustrative embodiment. Method <b>200</b> shown in <figref idref="f0002"><b>Figure 2</b></figref> may be implemented using system <b>100</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> The process shown in <figref idref="f0002"><b>Figure 2</b></figref> may be implemented by a processor, such as processor unit <b>1504</b> of <figref idref="f0012"><b>Figure 15</b></figref><b>.</b> The process shown in <figref idref="f0002"><b>Figure 2</b></figref> may be a variation of the processes shown in <figref idref="f0001"><b>Figure 1</b></figref> and <figref idref="f0003"><b>Figure 3</b></figref> through <figref idref="f0011"><b>Figure 14</b></figref><b>.</b> Although the operations presented in <figref idref="f0002"><b>Figure 2</b></figref> are described as being performed by a "process," the operations are being performed by at least one tangible processor or using one or more physical devices, as described elsewhere herein. The term "process" also includes computer instructions stored on a non-transitory computer readable storage medium.

Method <b>200</b> may begin as the process receives at least one of time-referenced and location-referenced state data for an object of interest (operation <b>202).</b> Thus, computer <b>104</b> may receive at least one of time-referenced and location-referenced state data for an object of interest of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> An object of interest may be one of obstacle <b>108,</b> obstacle <b>110,</b> and obstacle <b>112</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b>

Next, the process may determine a present location of control vehicle within two presently overlapping fat paths. (operation <b>204).</b> Thus, for example, computer <b>104</b> may determine a present location of control vehicle <b>102</b> within two presently overlapping fat paths, such as fat path <b>114</b> and fat path <b>116 of</b><figref idref="f0001"><b>Figure 1</b></figref><b>.</b>

The process may determine distance of control vehicle from a point of divergence of fat paths diverging to avoid the object of interest (operation <b>206).</b> For example, computer <b>104</b> may determine a distance of control vehicle <b>102</b> from a point of divergence of fat path <b>114</b> and fat path <b>116,</b> fat path <b>114</b> and fat path <b>116</b> diverging to avoid the object of interest (operation <b>206).</b>

Next, the process may generate a decision boundary reachable prior in time to the point of divergence wherein decision boundary is in advance of the present location of control vehicle (operation <b>208).</b> For example, computer <b>104</b> may generate decision boundary <b>124</b> reachable prior in time to the point of divergence, wherein decision boundary <b>124</b> is in advance of the present location of control vehicle <b>102</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b>

Next, the process may generate a first set of feasible headings and a second set of feasible headings for control vehicle, first set and second set respectively associated with a projected first crossing point and a projected second crossing point of decision boundary by control vehicle wherein feasible headings promote positioning of control vehicle in one of a first fat path and a second fat path beyond the point of divergence (operation <b>210).</b> For example, computer <b>104</b> may generate a first set of feasible headings and a second set of feasible headings for control vehicle <b>102,</b> first set and second set respectively associated with a projected first crossing point and a projected second crossing point of decision boundary <b>124</b> by control vehicle <b>102</b> wherein feasible headings promote positioning of control vehicle <b>102</b> in one of fat path <b>114</b> and fat path <b>116</b> beyond point of divergence of <figref idref="f0001">Figure 1</figref>.

Next, the process may send a first set of feasible headings and second set of feasible headings to control vehicle prior to control vehicle reaching decision boundary (operation <b>212).</b> For example, computer <b>104</b> may send a first set of feasible headings and second set of feasible headings to control vehicle <b>102</b> prior to control vehicle <b>102</b> reaching decision boundary <b>124</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Method <b>200</b> may terminate thereafter.

<figref idref="f0003"><b>Figure 3</b></figref> is a diagram providing a schematic view of illustrative safe separation windows for aircraft with varying degrees of uncertainty according to an embodiment of the present disclosure. <figref idref="f0003"><b>Figure 3</b></figref> is at least partially adapted from <patcit id="pcit0003" dnum="US8060295B"><text>U.S. Patent no. 8,060,295</text></patcit>. <figref idref="f0003"><b>Figure 3</b></figref> is provided for illustration purposes and depicts uncertainties to be considered in a separation management system upon which the systems and methods of the present disclosure may partially be based. Components shown in <figref idref="f0003"><b>Figure 3</b></figref> are indexed to components shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Control vehicle <b>302</b> shown in <figref idref="f0003"><b>Figure 3</b></figref> corresponds to control vehicle <b>102</b> shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Obstacle <b>308</b> shown in <figref idref="f0003"><b>Figure 3</b></figref> corresponds to obstacle <b>108</b> shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b><figref idref="f0003"><b>Figure 3</b></figref> is a schematic view showing safe separation windows for aircraft with varying degrees of uncertainty.

<figref idref="f0003"><b>Figure 3</b></figref> depicts two separate scenarios, labeled as <b>300a</b> and <b>300b.</b> Scenario <b>300a</b> depicts an undesirable situation for control vehicle <b>302</b> because trajectory window <b>R2</b> for control vehicle <b>302</b> is too broad such that collision with obstacle <b>308</b> may occur. Scenario <b>300b</b> depicts conditions of safe separation for control vehicle <b>302</b> because trajectory window <b>R3</b> is narrow such that control vehicle <b>302</b> and obstacle <b>308</b> will safely pass. Trajectory windows are further described in section <b>300c</b> of <figref idref="f0003"><b>Figure 3</b></figref> with trajectory window <b>R1</b> resulting from environmental conditions, instrumentation limitations and/or tolerances, or other factors bearing on aircraft trajectory.

Routing manifold <b>126</b> may contain information about regions of uncertainty for pilots, ground control personnel and others, and may also contain information about regions of trajectories for control vehicle <b>102</b> of <figref idref="f0001"><b>Figure 1</b></figref> and obstacle <b>108.</b> System <b>100</b> also includes decision boundary <b>124</b> which provides a simply connected set of points, whereon being reached, operator of control vehicle <b>102</b> must make decisions regarding heading while still observing prior established constraints which may include information about regions of uncertainty and regions of trajectories.

<figref idref="f0004"><b>Figure 4</b></figref> is a diagram of a system of virtual predictive radar in accordance with an illustrative embodiment. Components shown in <figref idref="f0004"><b>Figure 4</b></figref> are indexed to components shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Control vehicle <b>402</b> shown in <figref idref="f0004"><b>Figure 4</b></figref> corresponds to control vehicle <b>102</b> shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Obstacle <b>408,</b> obstacle <b>410,</b> obstacle <b>412</b> shown in <figref idref="f0004"><b>Figure 4</b></figref> correspond to obstacle <b>108,</b> obstacle <b>110,</b> obstacle <b>112</b> shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Fat path <b>414,</b> fat path <b>416,</b> fat path <b>418</b> shown in <figref idref="f0004"><b>Figure 4</b></figref> correspond to fat path <b>114,</b> fat path <b>116,</b> fat path <b>118</b> shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Origination point <b>420</b> and destination point <b>422</b> shown in <figref idref="f0004"><b>Figure 4</b></figref> correspond to origination point <b>120</b> and destination point <b>122,</b> respectively, shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b><figref idref="f0004"><b>Figure 4</b></figref> also depicts several components that do not correspond to components depicted in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b><figref idref="f0004"><b>Figure 4</b></figref> depicts two additional obstacles, obstacle <b>428</b> and obstacle <b>430.</b>

<figref idref="f0004"><b>Figure 4</b></figref> also depicts time rings, two of which are labeled for discussion purposes, time ring <b>432</b> and time ring <b>434.</b> While depicted in <figref idref="f0004"><b>Figure 4</b></figref> as a ring, time ring <b>432</b> and time ring <b>434</b> may not be shaped in a ringlike fashion and may take on various shapes. Probabilities of vehicle arrival at a particular point at a particular time may also be associated with at least one of time ring <b>432</b> and time ring <b>434.</b> Time ring <b>432</b> and time ring <b>434</b> may take on various dimensions in order to reflect uncertainty of location of control vehicle <b>402</b> at a given time. Time ring <b>432</b> and time ring <b>434</b> are not components of a system or method per se, but are rather representations of boundaries in time. As control vehicle <b>402</b> departs from origination point <b>420</b> and moves in the direction of destination point <b>422,</b> control vehicle <b>402</b> crosses boundaries that may be set by application <b>106</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>,</b> including time ring <b>432</b> and time ring <b>434.</b> Time ring <b>432</b> and time ring <b>434</b> may be used in calculating a time until control vehicle <b>402</b> would be expected to reach a divergence point of any combination of fat path <b>414,</b> fat path <b>416,</b> and fat path <b>418.</b> Thus, these time rings may be valuable in determining locations of decision boundary <b>124.</b> A decision boundary is not depicted in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b> Time ring <b>432</b> and time ring <b>434</b> would also be useful in determining positions of obstacle <b>408,</b> obstacle <b>410,</b> and obstacle <b>412,</b> particularly if obstacle <b>408,</b> obstacle <b>410,</b> and obstacle <b>412</b> are in motion.

<figref idref="f0005"><b>Figure 5</b></figref> is a chart illustrating routing decision software in use with a routing manifold generating application in accordance with an illustrative embodiment. <figref idref="f0005"><b>Figure 5</b></figref> provides an illustration of the use of routing decision software. Inputs include airspace information <b>502</b> including aircraft states and intent <b>504.</b> Airspace information also includes information about no-go regions <b>506</b> that may include obstacle <b>408,</b> obstacle <b>410,</b> and obstacle <b>412</b> of <figref idref="f0004"><b>Figure 4</b></figref><b>,</b> other aircraft, no-fly zones, weather systems, terrain, and man-made objects. Inputs also include information including constraints and operational rules <b>508.</b> Inputs also include intended flight path <b>510</b> of control vehicle <b>402</b> of <figref idref="f0004"><b>Figure 4</b></figref><b>.</b>

An automated separation management module <b>512,</b> which may be a component of application <b>106</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>,</b> may generate routing manifold <b>514.</b> Output from routing manifold <b>514</b> may be stored in virtual predictive radar data structures <b>516</b> that are provided to decision point application <b>518.</b> Decision point application 518 may be a component of application <b>106</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Output including decision point information <b>520</b> is generated which includes options and annotated virtual predictive radar information. Output is fed to decision information module <b>522</b> that includes human-machine interface components and machine-machine interface components <b>524,</b> represented respectively in <figref idref="f0005"><b>Figure 5</b></figref> as HMI and MMI. Presentable output, using human-machine interface components and machine-machine interface components, is appropriately formatted for human or machine use <b>526.</b> For human use, output <b>528</b> may be presented on a display for a human controller, operator, and/or pilot <b>530.</b> For machine use, output is presented on computer systems <b>532.</b>

<figref idref="f0006"><b>Figure 6</b></figref> is a diagram of a virtual predictive radar in accordance with an embodiment of the present disclosure. Components shown in <figref idref="f0006"><b>Figure 6</b></figref> are indexed to components shown in <figref idref="f0001"><b>Figure 1</b></figref><b>and</b><figref idref="f0004"><b>Figure 4</b></figref><b>.</b> Control vehicle <b>602</b> shown in <figref idref="f0006"><b>Figure 6</b></figref> corresponds to control vehicle <b>102</b> shown in <figref idref="f0001"><b>Figure 1</b></figref> and control vehicle <b>402</b> shown in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b> Obstacle <b>608,</b> obstacle <b>610,</b> obstacle <b>612</b> shown in <figref idref="f0006"><b>Figure 6</b></figref> correspond to obstacle <b>108,</b> obstacle <b>110,</b> obstacle <b>112</b> shown in <figref idref="f0001"><b>Figure 1</b></figref> and obstacle <b>408,</b> obstacle <b>410,</b> obstacle <b>412</b> shown in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b> Fat path <b>614,</b> fat path <b>616,</b> fat path <b>618</b> shown in <figref idref="f0006"><b>Figure 6</b></figref> correspond to fat path <b>114,</b> fat path <b>116,</b> fat path <b>118</b> shown in <figref idref="f0001"><b>Figure 1</b></figref> and fat path <b>414,</b> fat path <b>416,</b> and fat path <b>418</b> shown in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b> Origination point <b>620,</b> destination point <b>622,</b> and decision boundary <b>624a,</b> decision boundary <b>624b,</b> and decision boundary <b>624c</b> shown in <figref idref="f0006"><b>Figure 6</b></figref> correspond to origination point <b>120,</b> destination point <b>122,</b> and decision boundary <b>124,</b> respectively, shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Origination point <b>620</b> and destination point <b>622</b> in <figref idref="f0006"><b>Figure 6</b></figref> correspond to origination point <b>420</b> and destination point <b>422,</b> respectively, shown in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b><figref idref="f0006"><b>Figure 6</b></figref> depicts two additional obstacles not depicted in <figref idref="f0001"><b>Figure 1</b></figref><b>,</b> obstacle <b>628</b> and obstacle <b>630</b> that correspond to obstacle <b>428</b> and obstacle <b>430</b> in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b>

<figref idref="f0006"><b>Figure 6</b></figref> depicts several components not previously enumerated or depicted. <figref idref="f0006"><b>Figure 6</b></figref> depicts fat path intersection <b>636,</b> fat path intersection <b>638,</b> and fat path intersection <b>640.</b><figref idref="f0006"><b>Figure 6</b></figref> also depicts theoretical event horizon <b>642,</b> theoretical event horizon <b>644,</b> and theoretical event horizon <b>646.</b>

Fat path intersection <b>636</b> is an intersection of a boundary of fat path <b>614</b> and a boundary of fat path <b>616.</b> Fat path intersection <b>638</b> is an intersection of boundary of fat path <b>614,</b> boundary of fat path <b>616,</b> and boundary of fat path <b>618.</b> Fat path intersection <b>640</b> is an intersection of boundary of fat path <b>616</b> and boundary of fat path <b>618.</b>

Theoretical event horizon <b>642</b> is associated with decision boundary <b>624a,</b> theoretical event horizon <b>644</b> is associated with decision boundary <b>624b,</b> and theoretical event horizon <b>646</b> is associated with decision boundary <b>624c.</b>

At any point along one of decision boundary <b>624a,</b> decision boundary <b>624b,</b> or decision boundary <b>624c,</b> control vehicle <b>602</b> would be provided at least one heading that would enable control vehicle <b>602</b> to safely choose a fork option to avoid at least one obstacle while observing constraints provided in routing manifold <b>126</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> For example, control vehicle <b>602</b> may be concurrently flying in fat path <b>616</b> and fat path <b>608</b> in the direction of obstacle <b>610.</b> By the time control vehicle <b>602</b> reaches decision boundary <b>624c,</b> application <b>106</b> will have evaluated speed, altitude, schedule adherence and other factors associated with control vehicle <b>602,</b> and application <b>106</b> will have provided to control vehicle <b>602</b> or to ground control at least one heading. The at least one heading will promote control vehicle <b>602</b> to safely avoid obstacle <b>610</b> while continuing to observe constraints provided in routing manifold <b>126</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> In choosing from at least one heading, control vehicle <b>602</b> will choose a fork option that includes following fat path <b>616</b> or will choose a fork option that includes following fat path <b>618,</b> both of which safely bypass obstacle <b>610.</b>

<figref idref="f0007"><b>Figure 7</b></figref> is a diagram of a portion of a virtual predictive radar in accordance with an embodiment of the present disclosure. Components in <figref idref="f0007"><b>Figure 7</b></figref> correspond to components in <figref idref="f0006"><b>Figure 6</b></figref><b>.</b> Fat path <b>714,</b> fat path <b>716,</b> and fat path <b>718</b> shown in <figref idref="f0007"><b>Figure 7</b></figref> correspond to fat path <b>614,</b> fat path <b>616,</b> and fat path <b>608</b> shown in <figref idref="f0006"><b>Figure 6</b></figref><b>.</b> Obstacle <b>708</b> shown in <figref idref="f0007"><b>Figure 7</b></figref> corresponds to obstacle <b>608</b> shown in <figref idref="f0006"><b>Figure 6</b></figref><b>.</b> Decision boundary <b>724a</b> shown in <figref idref="f0007"><b>Figure 7</b></figref> corresponds to decision boundary <b>624a</b> shown <b>in</b><figref idref="f0006"><b>Figure 6</b></figref><b>.</b> Fat path intersection <b>736</b> shown in <figref idref="f0007"><b>Figure 7</b></figref> corresponds to fat path intersection <b>636</b> shown in <figref idref="f0006"><b>Figure 6</b></figref><b>.</b><figref idref="f0007"><b>Figure 7</b></figref> depicts practical event horizon region <b>748</b> which is a shaded region bounded by decision boundary <b>724a,</b> a boundary of fat path <b>714,</b> and a boundary of fat path <b>716.</b>

When control vehicle <b>102</b> of <figref idref="f0001"><b>Figure 1</b></figref> crosses decision boundary <b>724a</b> and enters event horizon region <b>748,</b> application <b>106</b> of <figref idref="f0001"><b>Figure 1</b></figref> will have provided at least one heading to control vehicle <b>102</b> to avoid obstacle <b>708.</b> Application <b>106</b> may also provide at least one range of forbidden headings to control vehicle <b>102 of</b><figref idref="f0001"><b>Figure 1</b></figref><b>.</b> The middle of the three smaller triangles within event horizon region <b>748</b> is pointed to. Within event horizon region <b>748,</b> control vehicle <b>102</b> cannot have headings in a forbidden heading range while maintaining constraints provided in routing manifold <b>126</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Should control vehicle <b>102</b> be situated in that triangular section of event horizon region, control vehicle <b>102</b> might be required to take action to avoid collision with obstacle <b>708</b> and will likely violate constraints regarding speed, altitude, safety, or passenger comfort. Arrows depicted in <figref idref="f0007"><b>Figure 7</b></figref> are associated with various headings control vehicle <b>102</b> may assume, some of which may promote control vehicle observing constraints and safely avoiding obstacle <b>708.</b>

Within event horizon region <b>748,</b> in order to maintain constraints control vehicle <b>102</b> of <figref idref="f0001"><b>Figure 1</b></figref> must maintain heading towards one particular fork option. Heading fan <b>750</b> is associated with a point within event horizon region <b>748</b> and contains all headings that direct control vehicle <b>102</b> from that point toward the fork option in fat path <b>714.</b> At a point on decision boundary <b>724a,</b> a heading orthogonal to decision boundary <b>724a</b> at that point may be the only heading that is feasible for both fat path <b>714</b> and fat path <b>716.</b> If control vehicle <b>102</b> reaches a location within event horizon region <b>748,</b> then a decision on which of fat path <b>714</b> and fat path <b>716</b> has already been made. Each point within event horizon region <b>748</b> may have an associated fan of forbidden headings. If control vehicle <b>102</b> has a forbidden heading, control vehicle <b>102</b> may be unable to avoid incursion or may be unable to avoid violating current maneuver constraints. As used herein a "forbidden area" means an area in which constraints must be modified in order to avoid incursion with obstacle <b>708.</b>

<figref idref="f0007"><b>Figure 8</b></figref> is a diagram of a portion of a virtual predictive radar in accordance with an embodiment of the present disclosure. Components in <figref idref="f0007"><b>Figure 8</b></figref> correspond to some components in <figref idref="f0007"><b>Figure 7</b></figref><b>.</b> Fat path <b>814,</b> fat path <b>816,</b> and fat path <b>818</b> shown in <figref idref="f0007"><b>Figure 8</b></figref> correspond to fat path <b>714,</b> fat path <b>716,</b> and fat path <b>718</b> shown in <figref idref="f0007"><b>Figure 7</b></figref><b>.</b> Obstacle <b>808</b> shown in <figref idref="f0007"><b>Figure 8</b></figref> corresponds to obstacle <b>708</b> shown in <figref idref="f0007"><b>Figure 7</b></figref><b>.</b> Decision boundary <b>824a</b> shown in <figref idref="f0007"><b>Figure 8</b></figref> corresponds to decision boundary <b>724a</b> shown in <figref idref="f0007"><b>Figure 7</b></figref><b>.</b> Fat path intersection <b>836</b> shown in <figref idref="f0007"><b>Figure 8</b></figref> corresponds to fat path intersection <b>736</b> shown in <figref idref="f0007"><b>Figure 7</b></figref><b>.</b> Practical event horizon region <b>848</b> shown in <figref idref="f0007"><b>Figure 8</b></figref> corresponds to practical event horizon region <b>748</b> shown in <figref idref="f0007"><b>Figure 7</b></figref><b>.</b>

<figref idref="f0007"><b>Figure 8</b></figref> depicts event horizon avoidance boundary <b>852</b> which is associated with decision boundary <b>824a</b> and is a maximal intersection of fat path <b>814,</b> fat path <b>816,</b> and fat path <b>818.</b> Control vehicle <b>102</b> of <figref idref="f0001"><b>Figure 1</b></figref> must have initiated a maneuver onto an option for at least one of fat path <b>814,</b> fat path <b>816,</b> and fat path <b>818</b> at the time of reaching event horizon avoidance boundary <b>852.</b> Control vehicle <b>102</b> may be unable to safely invoke a change of heading onto a different option after reaching decision boundary <b>824a,</b> assuming practical event horizon region <b>848</b> is to be avoided.

<figref idref="f0008"><b>Figure 9</b></figref> is a diagram of a virtual predictive radar in accordance with an embodiment of the present disclosure. Fat path <b>914,</b> fat path <b>916,</b> and fat path <b>918</b> shown in <figref idref="f0008"><b>Figure 9</b></figref> correspond to fat path <b>814,</b> fat path <b>816,</b> and fat path <b>818</b> shown in <figref idref="f0007"><b>Figure 8</b></figref><b>.</b><figref idref="f0008"><b>Figure 9</b></figref> depicts an alternate use of components of system <b>100.</b><figref idref="f0008"><b>Figure 9</b></figref> depicts unmanned aerial vehicle <b>954,</b> satellite <b>956,</b> radar <b>958,</b> aircraft <b>960,</b> aircraft <b>962,</b> aircraft <b>964,</b> communications relay <b>966,</b> and automatic dependence surveillance-broadcast (ADS-B) station <b>968.</b> Unmanned aerial vehicle <b>954</b> receives data on aircraft <b>960,</b> aircraft <b>962,</b> aircraft <b>964</b> including their flight paths. Unmanned aerial vehicle <b>954</b> accesses software on board and generates routing segments for aircraft <b>960,</b> aircraft <b>962,</b> aircraft <b>964</b> using methods provided herein.

Unmanned aerial vehicle <b>954</b> may receive information on other aircraft <b>960,</b> aircraft <b>962,</b> and aircraft <b>964</b> in the region. Software or other components that may be aboard unmanned aerial vehicle <b>954</b> may route and reroute segments using the four-dimensional virtual protective radar method with decision point enhancement.

<figref idref="f0009"><b>Figure 10</b></figref> is a diagram illustrating a use case in accordance with an embodiment of the present disclosure. Control vehicle <b>1002</b> shown in <figref idref="f0009"><b>Figure 10</b></figref> corresponds to control vehicle <b>602</b> shown in <figref idref="f0006"><b>Figure 6</b></figref> and control vehicle <b>102</b> shown in <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Airport <b>1070</b> is depicted in <figref idref="f0009"><b>Figure 10</b></figref><b>.</b> The systems and methods provided herein could be used to coordinate assets in a mission scenario or sequencing into an arrival stream at airport <b>1070.</b> Interoperation of a feasible heading fan and an avoidance heading fan may be reversed so that heading avoidance range becomes feasible heading range for reaching a target and feasible heading range becomes avoidance heading range.

Use of decision boundaries may be modified in cases such as depicted in <figref idref="f0009"><b>Figure 10</b></figref> such that, for instance, a theoretical event horizon may be a time and location at which control vehicle <b>1002</b> must be on a heading orthogonal to decision boundary. Such a requirement of control vehicle <b>1002</b> being on a heading orthogonal to decision boundary may be appropriate to assure or increase likelihood of reaching target at correct time given speed of control vehicle <b>1002</b> and anticipated trajectory or location of target. Target may be a virtual moving point in a case when sequencing aircraft into an arrival stream of airport <b>1070</b> or joining or maintaining a formation of aircraft.

<figref idref="f0010"><b>Figure 11</b></figref> is an aircraft option graph <b>1100</b> in accordance with an embodiment of the present disclosure. <figref idref="f0010"><b>Figure 11</b></figref> depicts fat path bar <b>1102,</b> fat path bar <b>1104,</b> fat path bar <b>1106,</b> fat path bar <b>1108,</b> fat path <b>1110,</b> and fat path bar <b>1112.</b> Fat path bar <b>1102</b> and fat path bar <b>1110</b> are labeled by "1" and "3" respectively, to indicate that fat path bar <b>1102</b> and fat path bar <b>1110</b> represent portions of fat path 1 and fat path 3, respectively, that intersect no other fat path. Fat path bar <b>1104,</b> fat path bar <b>1106,</b> and fat path bar <b>1108</b> represent maximal fat path intersections associated with fat path labels "1,2", "1,2,3", and "2,3" respectively. Fat path intersections represented by fat path bar <b>1104</b> and fat path bar <b>1108</b> are also fork options for fat path intersection represented by fat path bar <b>1106.</b> A number of directed arrows are provided wherein each directed arrow from one fat path bar to other fat path bars represents a feasible transition from the fat path intersection represented by the fat path bar to a fork option. Divergence point <b>1114,</b> divergence point <b>1116,</b> and divergence point <b>1118</b> are each represented by an end of a fat path bar with directed arrows. A bar with all arrows directed from it represents a fork. Decision boundaries and event horizon regions may also be represented. Aircraft option graphs may contain geometric objects that represent objects or areas to avoid. <figref idref="f0010"><b>Figure 11</b></figref> depicts obstacle <b>1120,</b> obstacle <b>1122,</b> obstacle <b>1124,</b> obstacle <b>1126,</b> and obstacle <b>1128.</b> Aircraft option graphs may contain curves that represent time progress.

For example, control vehicle <b>102</b> of <figref idref="f0001"><b>Figure 1</b></figref> may be traveling along fat path bar <b>1104.</b> From fat path bar <b>1104</b> control vehicle <b>102</b> may proceed on either fat path bar <b>1102</b> or fat path bar <b>1112</b> and thereby avoid obstacle <b>1122.</b>

<figref idref="f0010"><b>Figure 12</b></figref> and <figref idref="f0011"><b>Figure 13</b></figref> are aircraft progress graph <b>1200</b> and aircraft progress graph <b>1300,</b> respectively, that contain a plurality of distinct bars, one for each feasible intersection of fat paths. <figref idref="f0010"><b>Figure 12</b></figref> depicts fat path bar <b>1202,</b> fat path bar <b>1204,</b> fat path bar <b>1206,</b> fat path bar <b>1208,</b> fat path <b>1210,</b> and fat path bar <b>1212.</b><figref idref="f0011"><b>Figure 13</b></figref> depicts fat path bar <b>1302,</b> fat path bar <b>1304,</b> fat path bar <b>1306,</b> and fat path bar <b>1308.</b> A number of directed arrows are provided wherein each directed arrow from one fat path bar to other fat path bars represent a feasible transition from a fat path intersection to a fork option. <figref idref="f0010"><b>Figure 12</b></figref> also depicts divergence point <b>1214,</b> divergence point <b>1216,</b> and divergence point <b>1218.</b><figref idref="f0011"><b>Figure 13</b></figref> depicts divergence point <b>1310</b> and divergence point <b>1312.</b> A bar with all arrows directed from it represents a fork. Decision boundaries and event horizon regions may also be represented. Vehicle progress graphs may contain geometric objects that represent objects or areas to avoid. <figref idref="f0010"><b>Figure 12</b></figref> depicts obstacle <b>1220,</b> obstacle <b>1222,</b> obstacle <b>1224,</b> obstacle <b>1226,</b> and obstacle <b>1228.</b><figref idref="f0011"><b>Figure 13</b></figref> depicts obstacle <b>1314,</b> obstacle <b>1316,</b> obstacle <b>1318,</b> obstacle <b>1320,</b> and obstacle <b>1322.</b> The vehicle progress graphs shown may contain a number of curves that represent time progress.

In vehicle progress graphs, graph elements occurring prior to the current time are erased. Graph elements representing options no longer available due to vehicle progress are erased. Graph elements representing remaining options that necessitate a change in vehicle heading in order to remain feasible may be shown with particular coloring or other symbolic indication such as being cross hatched. Necessary or desired heading changes may also be indicated. Optimal headings for sequence of times within each bar may be indicated. Depictions of current vehicle locations are contained. If a vehicle enters a forbidden heading zone, an indication such as the vehicle flashing or turning color may be displayed.

<figref idref="f0011"><b>Figure 13</b></figref> may be viewed as continuation of <figref idref="f0010"><b>Figure 12</b></figref><b>.</b> Control vehicle <b>102</b> depicted in <figref idref="f0001"><b>Figure 1</b></figref> is depicted in <figref idref="f0010"><b>Figure 12</b></figref> as control vehicle <b>1230</b> and is depicted in <figref idref="f0011"><b>Figure 13</b></figref> as control vehicle <b>1324.</b> As control vehicle <b>1230</b> moves along fat path <b>1206,</b> the operator of control vehicle <b>1230</b> or another party or component may choose to follow an option leading to fat path bar <b>1204</b> and fat path bar <b>1208.</b> Transitioning to <figref idref="f0011"><b>Figure 13</b></figref><b>,</b> control vehicle <b>1324</b> (control vehicle <b>1230</b> in <figref idref="f0010"><b>Figure 12</b></figref><b>)</b> is depicted entering an event horizon region. Options no longer remaining (fat path bar <b>1210</b> and <b>1212</b> depicted in <figref idref="f0010"><b>Figure 12</b></figref><b>)</b> have been erased in <figref idref="f0011"><b>Figure 13</b></figref> relative to <figref idref="f0010"><b>Figure 12</b></figref><b>,</b> and thus are not depicted in <figref idref="f0011"><b>Figure 13</b></figref><b>.</b>

<figref idref="f0011"><b>Figure 14</b></figref> is a flowchart of a method for routing systems in a separation management system in accordance with an illustrative embodiment. Method <b>1400</b> shown in <figref idref="f0011"><b>Figure 14</b></figref> may be implemented using system <b>100</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> The process shown in <figref idref="f0002"><b>Figure 2</b></figref> may be implemented by a processor, such as processor unit <b>1504</b> of <figref idref="f0012"><b>Figure 15</b></figref><b>.</b> The process shown in <figref idref="f0011"><b>Figure 14</b></figref> may be a variation of the processes shown in <figref idref="f0001"><b>Figure 1</b></figref> and <figref idref="f0003"><b>Figure 3</b></figref> through <figref idref="f0011"><b>Figure 13</b></figref><b>.</b> Although the operations presented in <figref idref="f0011"><b>Figure 14</b></figref> are described as being performed by a "process," the operations are being performed by at least one tangible processor or using one or more physical devices, as described elsewhere herein. The term "process" also includes computer instructions stored on a non-transitory computer readable storage medium.

Method <b>1400</b> may begin as the process receives four-dimensional virtual predictive radar data for a control vehicle from a separation management system (operation <b>1402).</b> Thus, computer <b>104</b> may receive four-dimensional virtual predictive radar data for a control vehicle from a separation management system. Next, the process may determine intersections of fat paths for the control vehicle extracted from the four dimensional virtual predictive radar data, wherein fat paths comprise homotopically distinct regions of travel (operation <b>1404).</b> For, example, computer <b>104</b> may determine intersections of fat paths for the control vehicle extracted from the four dimensional virtual predictive radar data, wherein fat paths comprise homotopically distinct regions of travel.

The process may determine intersection forks associated with the intersections of the fat routing paths (operation <b>1406).</b> Next, the process may select a first intersection fork based on metrics calculated for the determined intersection forks (operation <b>1408).</b> Next, the process may determine at least one event horizon associated with the first intersection fork, wherein observation of the at least one event horizon by the control vehicle prevents the control vehicle from entering an area containing forbidden heading ranges (operation <b>1410).</b> Operations <b>1406, 1408,</b> and <b>1410</b> may be implemented using computer <b>104</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Method <b>1400</b> may terminate thereafter.

Turning now to <figref idref="f0012"><b>Figure 15</b></figref><b>,</b> an illustration of a data processing system is depicted in accordance with an illustrative embodiment. Data processing system <b>1500</b> in <figref idref="f0012"><b>Figure 15</b></figref> is an example of a data processing system that may be used to implement the illustrative embodiments, such as system <b>100</b> of <figref idref="f0001"><b>Figure 1</b></figref><b>,</b> or any other module or system or process disclosed herein. In this illustrative example, data processing system <b>1500</b> includes communications fabric <b>1502,</b> which provides communications between processor unit <b>1504,</b> memory <b>1506,</b> persistent storage <b>1508,</b> communications unit <b>1510,</b> input/output (I/O) unit <b>1512,</b> and display <b>1514.</b>

Processor unit <b>1504</b> serves to execute instructions for software that may be loaded into memory <b>1506.</b> Processor unit <b>1504</b> may be a number of processors, a multi-processor core, or some other type of processor, depending on the particular implementation. A number, as used herein with reference to an item, means one or more items. Further, processor unit <b>1504</b> may be implemented using a number of heterogeneous processor systems in which a main processor is present with secondary processors on a single chip. As another illustrative example, processor unit <b>1504</b> may be a symmetric multi-processor system containing multiple processors of the same type.

Memory <b>1506</b> and persistent storage <b>1508</b> are examples of storage devices <b>1516.</b> A storage device is any piece of hardware that is capable of storing information, such as, for example, without limitation, data, program code in functional form, and/or other suitable information either on a temporary basis and/or a permanent basis. Storage devices <b>1516</b> may also be referred to as computer readable storage devices in these examples. Memory <b>1506,</b> in these examples, may be, for example, a random access memory or any other suitable volatile or nonvolatile storage device. Persistent storage <b>1508</b> may take various forms, depending on the particular implementation.

For example, persistent storage <b>1508</b> may contain one or more components or devices. For example, persistent storage <b>1508</b> may be a hard drive, a flash memory, a rewritable optical disk, a rewritable magnetic tape, or some combination of the above. The media used by persistent storage <b>1508</b> also may be removable. For example, a removable hard drive may be used for persistent storage <b>1508.</b>

Communications unit <b>1510,</b> in these examples, provides for communications with other data processing systems or devices. In these examples, communications unit <b>1510</b> is a network interface card. Communications unit <b>1510</b> may provide communications through the use of either or both physical and wireless communications links.

Input/output (I/O) unit <b>1512</b> allows for input and output of data with other devices that may be connected to data processing system <b>1500.</b> For example, input/output (I/O) unit <b>1512</b> may provide a connection for user input through a keyboard, a mouse, and/or some other suitable input device. Further, input/output (I/O) unit <b>1512</b> may send output to a printer. Display <b>1514</b> provides a mechanism to display information to a user.

Instructions for the operating system, applications, and/or programs may be located in storage devices <b>1516,</b> which are in communication with processor unit <b>1504</b> through communications fabric <b>1502.</b> In these illustrative examples, the instructions are in a functional form on persistent storage <b>1508.</b> These instructions may be loaded into memory <b>1506</b> for execution by processor unit <b>1504.</b> The processes of the different embodiments may be performed by processor unit <b>1504</b> using computer implemented instructions, which may be located in a memory, such as memory <b>1506.</b>

These instructions are referred to as program code, computer usable program code, or computer readable program code that may be read and executed by a processor in processor unit <b>1504.</b> The program code in the different embodiments may be embodied on different physical or computer readable storage media, such as memory <b>1506</b> or persistent storage <b>1508.</b>

Program code <b>1518</b> is located in a functional form on computer readable media <b>1520</b> that is selectively removable and may be loaded onto or transferred to data processing system <b>1500</b> for execution by processor unit <b>1504.</b> Program code <b>1518</b> and computer readable media <b>1520</b> form computer program product <b>1522</b> in these examples. In one example, computer readable media <b>1520</b> may be computer readable storage media <b>1524</b> or computer readable signal media <b>1526.</b> Computer readable storage media <b>1524</b> may include, for example, an optical or magnetic disk that is inserted or placed into a drive or other device that is part of persistent storage <b>1508</b> for transfer onto a storage device, such as a hard drive, that is part of persistent storage <b>1508.</b> Computer readable storage media <b>1524</b> also may take the form of a persistent storage, such as a hard drive, a thumb drive, or a flash memory, that is connected to data processing system <b>1500.</b> In some instances, computer readable storage media <b>1524</b> may not be removable from data processing system <b>1500.</b>

Alternatively, program code <b>1518</b> may be transferred to data processing system <b>1500</b> using computer readable signal media <b>1526.</b> Computer readable signal media <b>1526</b> may be, for example, a propagated data signal containing program code <b>1518.</b> For example, computer readable signal media <b>1526</b> may be an electromagnetic signal, an optical signal, and/or any other suitable type of signal. These signals may be transmitted over communications links, such as wireless communications links, optical fiber cable, coaxial cable, a wire, and/or any other suitable type of communications link. In other words, the communications link and/or the connection may be physical or wireless in the illustrative examples.

In some illustrative embodiments, program code <b>1518</b> may be downloaded over a network to persistent storage <b>1508</b> from another device or data processing system through computer readable signal media <b>1526</b> for use within data processing system <b>1500.</b> For instance, program code stored in a computer readable storage medium in a server data processing system may be downloaded over a network from the server to data processing system <b>1500.</b> The data processing system providing program code <b>1518</b> may be a server computer, a client computer, or some other device capable of storing and transmitting program code <b>1518.</b>

The different components illustrated for data processing system <b>1500</b> are not meant to provide architectural limitations to the manner in which different embodiments may be implemented. The different illustrative embodiments may be implemented in a data processing system including components in addition to or in place of those illustrated for data processing system <b>1500.</b> Other components shown in <figref idref="f0012"><b>Figure 15</b></figref> can be varied from the illustrative examples shown. The different embodiments may be implemented using any hardware device or system capable of running program code. As one example, the data processing system may include organic components integrated with inorganic components and/or may be comprised entirely of organic components excluding a human being. For example, a storage device may be comprised of an organic semiconductor.

In another illustrative example, processor unit <b>1504</b> may take the form of a hardware unit that has circuits that are manufactured or configured for a particular use. This type of hardware may perform operations without needing program code to be loaded into a memory from a storage device to be configured to perform the operations.

For example, when processor unit <b>1504</b> takes the form of a hardware unit, processor unit <b>1504</b> may be a circuit system, an application specific integrated circuit (ASIC), a programmable logic device, or some other suitable type of hardware configured to perform a number of operations. With a programmable logic device, the device is configured to perform the number of operations. The device may be reconfigured at a later time or may be permanently configured to perform the number of operations. Examples of programmable logic devices include, for example, a programmable logic array, programmable array logic, a field programmable logic array, a field programmable gate array, and other suitable hardware devices. With this type of implementation, program code <b>1518</b> may be omitted because the processes for the different embodiments are implemented in a hardware unit.

In still another illustrative example, processor unit <b>1504</b> may be implemented using a combination of processors found in computers and hardware units. Processor unit <b>1504</b> may have a number of hardware units and a number of processors that are configured to run program code <b>1518.</b> With this depicted example, some of the processes may be implemented in the number of hardware units, while other processes may be implemented in the number of processors.

As another example, a storage device in data processing system <b>1500</b> is any hardware apparatus that may store data. Memory <b>1505,</b> persistent storage <b>1508,</b> and computer readable media <b>1520</b> are examples of storage devices in a tangible form.

In another example, a bus system may be used to implement communications fabric <b>1502</b> and may be comprised of one or more buses, such as a system bus or an input/output bus. Of course, the bus system may be implemented using any suitable type of architecture that provides for a transfer of data between different components or devices attached to the bus system. Additionally, a communications unit may include one or more devices used to transmit and receive data, such as a modem or a network adapter. Further, a memory may be, for example, memory <b>1505,</b> or a cache, such as found in an interface and memory controller hub that may be present in communications fabric <b>1502.</b>

Data processing system <b>1500</b> may also include associative memory <b>1528.</b> Associative memory <b>1528</b> may be in communication with communications fabric <b>1502.</b> Associative memory <b>1528</b> may also be in communication with, or in some illustrative embodiments, be considered part of storage devices <b>1516.</b> While one associative memory <b>1528</b> is shown, additional associative memories may be present.

The different illustrative embodiments can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment containing both hardware and software elements. Some embodiments are implemented in software, which includes but is not limited to forms, such as, for example, firmware, resident software, and microcode.

Furthermore, the different embodiments can take the form of a computer program product accessible from a computer usable or computer readable medium providing program code for use by or in connection with a computer or any device or system that executes instructions. For the purposes of this disclosure, a computer usable or computer readable medium can generally be any tangible apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

The computer usable or computer readable medium can be, for example, without limitation an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, or a propagation medium. Non-limiting examples of a computer readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, and an optical disk. Optical disks may include compact disk - read only memory (CD-ROM), compact disk - read/write (CD-R/W), and DVD.

Further, a computer usable or computer readable medium may contain or store a computer readable or usable program code such that when the computer readable or usable program code is executed on a computer, the execution of this computer readable or usable program code causes the computer to transmit another computer readable or usable program code over a communications link. This communications link may use a medium that is, for example without limitation, physical or wireless.

A data processing system suitable for storing and/or executing computer readable or computer usable program code will include one or more processors coupled directly or indirectly to memory elements through a communications fabric, such as a system bus. The memory elements may include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some computer readable or computer usable program code to reduce the number of times code may be retrieved from bulk storage during execution of the code.

Input/output or I/O devices can be coupled to the system either directly or through intervening I/O controllers. These devices may include, for example, without limitation, keyboards, touch screen displays, and pointing devices. Different communications adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Non-limiting examples of modems and network adapters are just a few of the currently available types of communications adapters.

The description of the different illustrative embodiments has been presented for purposes of illustration and description, and is not intended to be exhaustive or limited to the embodiments in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. Further, different illustrative embodiments may provide different features as compared to other illustrative embodiments. The embodiment or embodiments selected are chosen and described in order to best explain the principles of the embodiments, the practical application, and to enable others of ordinary skill in the art to understand the disclosure for various embodiments with various modifications as are suited to the particular use contemplated.