Note: Descriptions are shown in the official language in which they were submitted.
:: :
2~2~3
EARLY WARNING TRACKING SYSTEM
BACKGROUND OF THE INVEN~ION
,: ..
Field of the Invention
This invention relates generally to
computerized methods to provide early warning of
collision for a tracking system and pertains more
particularly to a process for predicting the
probability that an object being tracked will intrude
into a predefined polygonal zone.
Description of the Related Art
A variety of computerized systems have been
developed that are capable of predicting if and when an
approaching object will intrude into a predefined
region of space. Such systems are typically employed
to protect secure zones, such as, for example military
installations, to enable appropriate counter measures
to be invoked on a timely basis. In addition, these
systems are employed in air traffic control systems to
assist air traffic controllers in discerning which
amongst a potentially large number of objects being
tracked are likely to present the possibility of a
collision with the ground, restrlcted airspace or
off designated air routes.
Performance of previous systems, especially
those with relatively simple tracking and collision
prediction algorithms, often is limited in that in
order to solve the probabilities presented by modern
vehicle performance envelopes and a relatively large
number o closely spaced vehicles being tracked, large
amounts of calculations are performed for too many of
the objects being tracked. Since the data processing
resources available are generally limited, this
naturally serves to limit the number of objects such
systems can process and increases the probability that
.
. . ~ . . ~ .. ; , ~
-`` 23~23~3
: -2-
false alarms of intrusion or collision will increase,
especially when the objects are moving at high speeds,
or are capable of rapid and unpredicted changes in
path. All of these limitations are exacerbated by
uncertainties in th'~;positon or velocities of the
vehicle being tracked.
A significant aspect of the shortcomings of
some prior art systems is the manner in which the
uncertainty of positional determinations and velocity
vector determinations are accommodated in the
calculations. Typically, buffer zones are placed both
inside and outside the predefined polygonal reglon to
be protected to take into consideration the probable
extent of potential tracking errors. If a tracked
ob~ect is predicted to pierce the inside zone, then a
sure lateral intrusion is declared. If, on the other
hand, a tracked ob;ect i8 predicted not to pierce the
outside zone, then a sure non-intrusion is declared.
An unsure intrusion is declared if the object is
predicted to penetrate somewhere between the
peripheries of the inside and outside bu~fer zones.
The problem with this method is determining the actual
boundaries of the buffer zones. An accurate
construction of the zones based on track variances has
proved intractable. Not only do such systems have
trouble accommodating large numbers of ob;ects,
especially ones moving at high velocities, but often
false alarms and undetected intrusions result.
Therefore, there remains a need for a method
of calculating the probability that a large number of
ob~ects being tracked will niether collide with one
another or intrude on a predefined area within the
` tracking region. Furthermore, it would be highly
beneficial if such a system were economical in its data
processing requirement and was adaptable to a wide
variety of accessories.
':
::
.
::;
`'`'
,
. . .
.. , - .
.. ..
., : :: . :. . .. -......... : ;. ::
..
2~22~1 3
-3-
SUMMARY OF THE INVENTION
The general purpose of the invention is to
provide an early warning tracking system that is
quickly able to discern whether an approaching object
: will intrude into a predefined
polygonal zone. To attain this goal, the present
invention first projects an uncertainty region in the
inætantaneous direction of travel of each approaching
object and then makes decisions regarding the potential
for intrusion, depending on the location of the
predefined polygonal zone and its relationship to the
location of the uncertainty region. To further
simplify all subsequent calculations, the coordinate
system is reoriented along the velocity vector for each
approaching ob;ect. The new coordinates of the
periphery of the predefined polygonal zone resulting
from the reorientation are then considered with respect
to the uncertainty region of each approaching object.
The limits of the uncertainty regions are determined by
the variances associated with the posltional and
dynamic determinations of the objects being tracked.
The potential for intrusion is first
considered in two dimensions to simplify processing.
If no lateral intrusion is indicated, no further
consideration is given to that particular ob;ect. Only
after a possible lateral intrusion is indicated, is
the object's perceived height and rate of change of
height considered to further determine whether an
intrusion into the predefined polygonal zone is
probable.
The association of a uni~ue uncertainty region
with each approaching object, as opposed to the
redefinition of buffer zones about the polygonal zone
for each approaching object, greatly simplifies the
required calculations and thereby enables the system of
, : ~': - ~' . . ..
:
the present invention to more quickly and reliably yield
information regarding the potential for intrusion into the
~: predefined polygonal zone.
An aspect of this invention is as follows:
A system for providing an early warning of
. imminent intrusion by a tracked moving object into a
: predefined three-dimensional polygonal zone, such zone's
periphery being defined by its projection onto a two-
dimensional plane and its maximum height above said plane,
characterized by:
means for ascertaining apparent position and
velocity of such ob;ect as pro;ected onto such plane, in
addition to variances and a covariance associated with said
apparent position and velocity;
:~ 15 means for extending out in front of said moving
object's apparent position along such plane, an uncertainty
region indicative of possible future positions of such
object based on said ascertained position, velocity,
variances and covariance;
means for determining whether such object moving
within said uncertainty region could cross through such
: predefined polygonal zone as projected onto such plane;
means for calculating an earliest possible entry
time for such object moving within said uncertainty region
: 25 on such plane into said projection of such predefined
polygonal zone;
means for calculating a latest possible exit time
for such object moving within said uncertainty region on
such plane from said projection of such predefined
polygonal zone;
:` means for ascertaining such object's height and
rate of height change above such plane, in addition to
variances and covariances associated with said height and
rate of height change;
means for predicting possible future heights of
~:~ such object based on said ascertained height, rate of
. height change, variances and covariance;
... . ..
4a
means for predicting when such object's height
. could fall below such polygonal zone's maximum height;
means for determining whether a predicted height
below such predefined polygonal zone's maximum height
occurs after said calculated earliest possible entry time
-~ and before said calculated latest possible exit time
thereby indicating an intrusion: and
means for issuing an alert when said intrusion
could occur within a predefined period of time.
Other features and advantages of the present
invention will become apparent from the following detailed
description, taken in conjunction with the accompanying
drawings, which illustrate by way of example, the
principles of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 is a schematic representation of a
scenario for which employment of the present invention is
f~ well suited;
Figure 2 is a flow chart illustrating the order
i and organization by which the various determinations and
;~ calculations of the present invention are performed;
Figure 3 is a flow chart illustrating in more
detail the method of determination 91 illustrated in
Figure 2;
Figure 4 illustrates the reorientation of the
coordinate system by the system of the present invention;
Figure 5 illustrates all possible orientations of
predefined polygonal zones relative to an approaching
ob~ect's uncertainty zone.
~'~ Detailed Description
Fig. 1 generally illustrates the situation and
conditions for which the deployment of the system and
methods of the present invention are intended.
Schematically illustrated in a top plan view is the
airspace in and around a predefined polygonal region 61
~'' `
~:: A
~
~22313
-5-
(having vertices 69-74) in which a multitude of objects
are moving at different speeds and directions. Each
such object's position is depicted by a dot 63 while
its velocity vector, depicted by an arrow 65, is an
indication of the speed and direction of its
trajectory. It is the function of the present
invention to predict which of the multitude of objects
presents a high likelihood of intruding into region 61
at a predefined critical time. This system and its
methods can for example assist air traffic controllers
in monitoring and controlling the air space in and
around a busy airport by directing attention to only
those aircraft that are on direct approach, or, help
prioritize the deployment of countermeasures for the
protection of a restricted military zone.
Figure 2 illustrates the overall flow of
decisions and logic employed to issue a timely alert
regarding an impending intrusion. Upon detection of
the presenae of an ob;ect by an associated tracking
system, the sy6tem of the pre~ent invention first makes
a determination 91 whether the ob~ect is sure to
intrude laterally, will surely not intrude laterally,
or might intrude laterally. This determination is
based on the object's perceived position and track
velocity as projected onto a horizontal plane presumes
that it will not deviate from its flight path and also
takes into consideration the uncertainty inherent in
the tracking measurements. At this point only the
lateral intrusion into the predefined region is of
concern and therefore, position and movement are
considered only in two dimensions as depicted in Figure
1 .
The chronology of decisions that are made and
computations that are performed to provide this first
determination 91 are set forth in more detail in Figure
3. As mentioned a~ove, the tracking system provides an
'``,~
;:~
,.; . ~ ., .. . ,. : . , ~, ........ , , - .:
. . . :: . : .- . . , ::: . .-.. .- :. .,. ; . ; ,.. : ~ .
~2~3
-6-
object's position (xjy) in a horizontal plane as well
as its horizontal velocity vector (X,Y). If the
ob;ect's perceived track speed is below a predefined
level:
x2 + y2 < Ql (1)
the object is considered to be moving too slowly to
warrant attention and no further processing is
performed. If however the object's track speed is
above the predefined level Ql, processing continues by
reorienting the entire coordinate system along the
object's velocity vector to simplify subsequent
calculations.
Figure 4 illustrates an object at 75
approaching a predefined polygonal region 79. The
position of each vertex ~80-83) of the region 79 is
initially de~ined by (ai,bi) coordinates. Upon
reorienting this coordinate system along the object's
velocity vector 77, centered at the object's position
75, each vertex is redefined as (Ai,Bi) while the
object's position would necessarily be defined by
(0,0). This reorientation is accomplished as follows:
(a.-x)X + (b.-y)Y
Ai = (X2 + y2 ~ i = 1,2, ... n (2)
(a.-x)Y + (bi-y)X
~i = (X2 + y2)~ i = 1,2, ... n (3)
Once reoriented in this fashion it is a simple matter
to determine whether an object is approaching or
departing from the predefined region. A positive Ai
indicates an approach while a negative Ai is
indicative of the object's departure from the
particular vertex. If:
- .,: -.
. ~ . ~ ' '' : ~
,:. .
:
2~223~
-7-
Ai < O for all i (4)
then the object is moving away from the entire
predefined region and no further proceseing is
performed for such an object.
If however Ai is positive for even a single
vertex and the object has sufficient speed (Equation 1)
then the uncertainties associated with the tracking
system's positional and velocity measurements for the
approaching object are considered in determining
whether an intrusion is likely.
A J parameter is calculated for each vertex
using the vertex's reoriented coordinates (Ai,Bi)
as well as the position variance (P~, velocity variance
(V) and position-velocity covariance (C) as follows:
B. i = 1,2 ... n (5)
Ji ~ 1 + A2
P 2CAi V i
The uncertainty of the ob~ect' 8 positional and
velocity measurements are interrelated in the
denominator of Equation 5 and in effect serve to
project an uncertainty zone 84 out in front of the
moving object 78 as illustrated in Figure 5. A number
of different combinations and permutations are then
possible regarding the relationship of a particular
predefined region relative to the uncertainty zone 84,
i.e., the region can either lie wholly outside 85,86 or
wholly inside 87 the zone 84. Alternatively, the
region 88,89 can lie partly inside and partly outside
the zone or the region 90 can wholly envelope the
uncertainty zone. If:
:`
Ji ~ Q2 for all i (6)
wherein Q2 is a predefined parameter and the sign of
all Bi is the same, then the predefined region is
.. .. .... ~.. -
: ~. .: ..
,. . .;, . ~-: .. ..
- , : ~- . ~ -
3 ~ 3
located in a position generally depicted by either 85
or 86 in Figure 5. Such a situation is indicative of a
"sure non-intrusion" and no further processing is
performed for that object.
If on the other hand, if for any two vertices
j and k:
J; > Q3 (7)
Jk > Q3 (8)
wherein Q~ is a predefined parameter and the sign of
Bj does not equal the sign of Bk, the situation
depicted by reference numeral 90 of Figure 5 is
indicated, "sure intrusion" is therefore imminent and
processing continues accordingly. For all other
situations (87, 88, 89) a lateral intrusion may or may
not occur and processing continues as appropriate for
an "unsure intrusion~'.
The next step for either a sure intrusion 90
or an unsure intrusion (87, 88, 89) condition entails
calculating the lateral entry time 93 of the
approaching object 78 into the predefined polygonal
region. This is accomplished by considering the vertex
closest to the approaching object i.e. the smallest
Ai which shall be designated Aj.
If Jj < Q3 (see Equation 5), the closest
vertex lies within the uncertainty zone 84 and:
I A~ ~
Tl - max ' S~ (9)
where S is the speed of the object:
S = (X2 ~ y2)1/2 (10)
: .
... .. ,: .,
-
. . :
- , ~ - :
~2~
If on the other hand, J; > Q3, i.e., the
closest vertex lies outside the uncertainty zone 84,
and the next closest vertex, designated (Ak, Bk)
the sign of Bk does not equal the sign of Bj, then:
~ ~ ¦ ~ k~ k I ~ (11)
wherein:
L = ~k + 1 if Bk ~ (12)
¦k - 1 if Bk ~
If Jj ~ Q~;and the sign of Bk e~uals the
s~gn of Bji then:
Ak ~l
Tl = max ~ ~ S ) (13)
once the lateral entry time T, has been
estimated, it is compared to the minimum and maximum
look-ahead time in the time decision check step 95 of
Figure 2. The maximum look-ahead time TmaX is a
predefined parameter while the minimum look ahead time
is the longer of either a predefined parameter Q4 based
on the response time of an appropriate counter measure
or a function of how quickly the approaching object can
climb over the top of the predefined polygonal region:
Tm~n = max ~Q~ ~ T~ ~ (14
.: .
- ~ . , :
2~22~ 3
-10-
wherein:
(Tl)
Te= S tan e ( 15)
Wherein h(T ~ is the predicted height of the
approaching object at time T1, which is the predicted
time of lateral entry. HU is the upper height limit of
the predefined region and e is a predefined escape
climb rate parameter. In order to perform the above
calculation, height and rate of height change must have
been provided by the tracking system. If Tl > TmaX
no alert is indicated- If Tl < Tmin' processing
continues towards the height final alert process 105.
If Tl i8 in between Tmin and Tmax' then
processing continues towards height decision alert
process 103.
The time delay filter 97 is invoked when an
unsure intrusion (87, 88, 89) had been indicated in the
lateral intrusion determination 91. If Tl ~ Tmin
then no alert is indicated. If Tl < Tmin,
processing continues on towards the height final alert
process 105.
In the lateral final alert process 99, a
deci6ion whether to indicate an alert condition or not
is made depending on whether missed detections are to
be controlled at the expense of false alarms or vice
versa. If missed detections are to be controlled at
the expense of false alarms, and if:
Ji > Q7 for any i (16)
then processing continues. Otherwise no alert i8
issued. If on the other hand, false alarms are to be
. .
- ' ' . . '
- :
~ ,, ' ' - ;
~2~ ~ ~
controlled at the expense of missed detections, a
second predefined parameter Q8 i5 considered and if for
any two indices ; and k:
J; > Q8 (17)
Jk > Q8 (18)
and the sign of Bj equals the sign of Bk then
processing continues. Otherwise no alert is issued.
In order to determine whether an ob;ect will
intrude into the predefined polygonal region by
descending into the region from above, it is necessary
to know both the entry time of lateral intrusion T
as well as the exit time of lateral intrusion T2.
Generally, the knowledge that an approaching object is
above the predefined region at the time of lateral
entry does not preclude the possibility of an
intrusion. It must therefore also be determined
whether the approaching object still has sufficient
altitude at the time the predefined polygonal zone is
laterally exited. To that end, the lateral exit time
T2 ls calculated 101 in a manner analogous to the
calculation o~ the entry time Tl 93. The vertex
furthest from the approaching object, i.e. the vertex
with the largest Ai which shall be designated (A
Bm) is considered. If Jm < Q9 (a predefined
parameter) then:
} (19)
Wherein Q6 i8 a predefined maximum time limit. If on
the other hand, Jm > Q9 and the vertex therefore lies
outside the uncertainty zone, the second furthest
. ~
: -. .,: ~ ...
-, ~ .. - "
: . - . .
, , .. ~ ~ .
~2~3:~3
-12-
vertex, designated (An~ Bn) is considered. If, the
sign of Bm does not equal the sign of Bn~ then:
2 min { IBpl+lBn I ¦Bp¦+¦Bn¦ ' Q } (20)
wherein:
¦ n - 1 if Bn > (21)
~n + 1 if Bn ~
If J > Q9 and the sign of Bm eguals the sign of Bn~
then:
T2 = min ~ n, Q6 ~ (22)
Once both Tl and T2 are known in addition
to the previously provided height h and height rate H
data, the height variance HP, height rate variance HV
and height-height rate covariance HC are considered in
con~unction with the upper height limit HU and lower
height limit HL to provide the final decisions
regarding the potential for intrusion.
In the height decision alert proce~s 103 two
more parameters need be calculated:
El = Q10 (HP + 2HC-T + HV-T12)1~2 (23)
E2 = Qll (HP + 2HC-T + HV-T12)1/2 (24)
wherein Q10 and Qll are predefined parameters. An alert
will be i~sued if any of the following four conditions
(equations 25-28) are satisfied:
HL + E1 < h + H-Tl < HU - El (25)
HL + E2 < h + H'T2 < HU - E2 (26)
:, ...... ...
. :: : . ,.
2~2~
-13-
h + H Tl ~ HU - El
and (27)
h + H-T2 < HL - E2
h + H Tl ~ HL - El
and (28)
h + H-T2 > HU - E2
otherwise no alert will be is6ued.
If, on the other hand, the approaching objeots
Tl < Tmin, whether a sure intrusion or an unsure
intrusion, an alert will be issued at 105 if any of the
following conditions (equations 29-32) are satisfied:
HL < h + H-Tl ~ HU (29)
HL ~ h + H T2 < HU (30)
h + H Tl ~ HU
and (31)
h + H T2 < HL
h + H Tl ~ HL
and (32)
h + H-T2 > HU
otherwise no alert will be.issued.
Once an alert has is6ued, and as an object's
position and trajectory can be more precisely be
predicted, the alert i6 turned off if a lateral sure
non-intrusion i8 indicated (Equations 7 & 8) or if
either of the following conditions regarding the
approaching objects height dynamics are indicated:
.. , . ~.. , ; :
,, . ~ - ,, - - , -
- -: ,:, . - :,
-. . :: . ,: .- . ~. :
..
. -.~ ., . , . -
2~3~
HL - El > h + H Tl
and (33)
HL - E2 > h + H T2
HV ~ El < h + H-Tl
and (34)
HU ~ E~ < h + H-T2
In operation, the system and methods of the
present invention are employed in conjunction with a
tracking system which is capable of supplying
positional as well as dynamic data for a plurality of
moving ob~ects. In addition, the perimeter of the
predefined polygonal æone is precisely known. The
first consideration made is whether a particular object
is moving fast enough and in fact toward the predefined
polygonal zone. Each object that survives these two
considerations then in effect has an uncertainty region
pro~ected along its velocity vector. The predefined
polygonal zone i5 then considered in relation to the
uncertainty region and depending on its positional
relationship the determination whether a sure intrusion
exists, a sure non-intrusion exists, or an unsure
intrusion is indicated can then be made. If an
intrusion is possible, the time for lateral entry and
exit is calculated after which the height position and
dynamics are taken into consideration. The various
parameters employed in the various calculations and
determinations are selected according to the
requirements of a specific installation. Appropriate
adjustment of the values of these various parameters
will ultimately determine whether tracking errors will
tend to yield false alarms or undetected intrusions.
While a particular form of the invention has
been illustrated and described, it will also be
apparent to those skilled in the art that various
modifications can be made without departing from the
, ~. .. ~
,
, ~, ' '
~22~
-15-
spirit and scope o~ the invention. Accordingly, it is
not intended that the invention be limited except as by
the appended claims.
:,: . ,
: : , ... . . , . : :,
-: , -.. , ~
: ~ , . - : :: :.
:: : : : : , : ~ .
. . . ~ : .: :.. -
- : - ~ : .
, - :: ~: .: : . . .
.. . . ..
