Track algorithm

A track algorithm is a radar and sonar performance enhancement strategy. Tracking algorithms provide the ability to predict future position of multiple moving objects based on the history of the individual positions being reported by sensor systems.

Historical information is accumulated and used to predict future position for use with air traffic control, threat estimation, combat system doctrine, gun aiming, missile guidance, and torpedo delivery. Position data is accumulated over the span of a few minutes to a few weeks.

There are four common track algorithms.[1]

• Nearest Neighbor
• Probabilistic Data Association
• Multiple Hypothesis Tracking
• Interactive Multiple Model (IMM)

History

The original tracking algorithms were built into custom hardware that became common during World War II. This includes storage tubes used with planned position indicator displays, range height indicator displays, and pen-plotting boards used for civilian air traffic control and waterway management. It also includes custom analog computers, like the Mark I Fire Control Computer used with radar data to aim guns, missiles, and torpedoes associated with military air traffic control and waterway management.

Track algorithms were migrated from analog equipment to digital computers from the 1950s through the 1980s. This was necessary to eliminate limitations that include mid-air collisions and other problems linked with obsolete equipment that was socialized by PATCO and United States Department of Defense. Similar migration trends occurred in other countries throughout the world for similar reasons.

Modern civilian air traffic and military combat systems depend upon a custom track algorithms used with real-time computing slaved to displays and peripherals.

Limitation for modern digital computing systems are processing speed, input-output throughput rate, the number of input-output devices, and software compatibility with upgrade parts.

Terminology

Tracking algorithms operate with a cartesian coordinate system. This is often called a rectangular coordinates, and is based on north-south, east-west, and altitude. Sensors operate using a polar coordinate system. This is often called spherical coordinates based on elevation, bearing, and range. Some common terminology is as follows.

Term	Meaning
Azimuth	Angle along the earth horizon
Bearing	Angle along the artificial horizon (deck)
Elevation	Angle above or below the horizon
Range	Distance along the plane established by the horizon
Slant Range	Distance along the true line of sight
True	Angle in earth coordinates with true north as the reference
Relative	Angle in deck-plane coordinates using vehicle heading as the reference
Rectangular	Cartesian coordinates typically known as X, Y, and Z
Spherical	Polar coordinates typically known as range, bearing, and elevation

Human Interface

Users are generally presented with several displays that show information from track data and raw detected signals.

• Plan position indicator
• Scrolling notifications for new tracks, split tracks, and join tracks
• Range amplitude display
• Range height indicator
• Angle error display
• Audible alerts (buzzer or voice)

The audible alert draws attention to the scrolling notification. This will present the track number for things like separation violation (impending collision) and lost track not located near a landing facility.

The scrolling notifications and audible alerts require no user action. Other displays activate to show additional information only when a track is selected by the user. The primary human interface for the tracking algorithm is a planned position indicator display. This typically puts up four pieces of information.

Term	Meaning
Raw video	Analog detection pulses from radar and sonar systems
Track	A symbol and number allowing operators to unambiguously identify the vehicle
Leader	A line showing where the vehicle will be in the future.
IFF	Transponder data showing identity. This may include speed, altitude, and heading in commercial aircraft.

The track algorithm produces symbology that is displayed on the Plan Position Indicator.

Users have a pointing device with several buttons that provides access to the track file through the Plan Position Indicator. The typical pointing device is a track ball, which operates as follows.

Term	Meaning
Activate Button	Bring a cursor to the center of the display.
Rolling Ball	Used to scroll the cursor near a track symbol or raw sensor video.
Hook Button	Select the track once the cursor is in the desired location.
Drop Button	Return the display to its normal operating condition (not associated with dropping tracks).

Hook action turns off the cursor and displays additional information from the track algorithm. The user can perform actions while the hook is active, such as communicate with the vehicle or notify other users regarding the vehicle associated with the track.

Operation

The nearest neighbor track algorithm is described here for simplicity.

Each new detection reported from incoming sensor data is fed into the track algorithm, which is used to drive displays.[2]

Track algorithm operation depends upon a track file, which contains historical track data, and a computer program that periodically updates the track file.[3]

Sensors information (radar, sonar, and transponder data) is provided to the track algorithm using a polar coordinate system, and this is converted to cartesian coordinate system for the track algorithm. The polar to Cartesian conversion uses navigation data for sensors mounted on vehicles, which eliminates sensor position changes caused by ship and aircraft motion that would otherwise corrupt track data.

Track mode begins when a sensor produces a sustained detection in a specific volume of space.

The track algorithm takes one of four actions when this new sensor data arrives.

Action	Explanation
Store	Sensor data is stored temporarily for capture and track evaluation
Drop	Stored sensor data failed to fall within track volume or capture volume within the time limit (discarded)
Capture	Sensor data falls near previous sensor data not associated with a track and a new track is developed
Track	Sensor data falls within the volume of an existing track and is added to track history for that track

Each separate object has its own independent track information. This is called track history. This could be as much as an hour for airborne objects. Track history for underwater objects can extend back several weeks.

Each different kind of sensor produces different kinds of track data. A 2D radar with a fan beam produces no altitude information. A 4D radar with a pencil beam will produce radial Doppler velocity in addition to bearing, elevation, and slant range.

Store

New sensor data is stored for a limited period of time. This occurs before track, capture and drop processing.

Stored data needs to be held for a limited time to allow time for comparison with existing tracks. Stored data must also be held long enough to complete processing required to develop new tracks.

Drop

Data quickly loses any purpose for sensor systems that use an M out of N detection strategy. Stored data is often dropped after N scans have expired with fewer than M detections within a specific volume.

Drop processing takes place only after track and capture processing takes place. Drop data may sometimes be extracted from main memory and recorded onto storage media along with the track file for offsite analysis.

Capture

The capture strategy depends upon the kind of sensor.

Capture processing takes place only after stored sensor data has been compared with all existing tracks.

Non-Doppler

Each sensor detection is surrounded by a capture volume. This is shaped like a box. The size of the capture volume is approximately the distance the fastest vehicle can travel between successive scans of that same volume of space.

Sensors (radar) scan a volume of space periodically.

As an example, a capture distance of 10 miles require periodic scans no more than 15 seconds apart in order to detect vehicles traveling at mach 3. This is a performance limitation for non-Doppler systems.

Transition to track begins when the capture volume for two detections overlap.

${\displaystyle {\text{Capture (3D)}}\;{\begin{cases}\left\vert X({\text{new}})-X(s)\right\vert <{\text{Separation}}\\\left\vert Y({\text{new}})-Y(s)\right\vert <{\text{Separation}}\\\left\vert Z({\text{new}})-Z(s)\right\vert <{\text{Separation}}\end{cases}}}$

${\displaystyle {\text{Capture (2D)}}\;{\begin{cases}\left\vert X({\text{new}})-X(s)\right\vert <{\text{Separation}}\\\left\vert Y({\text{new}})-Y(s)\right\vert <{\text{Separation}}\end{cases}}}$

Each new detection not paired with a track is compared with every other detection not yet be paired with a track (cross correlation with all stored data).

Transition to track typically involves an M out of N strategy, such as at least 3 detections out of a maximum of 5 scans.

This strategy produces a large number of false tracks due to clutter near the horizon and in the viscidity of weather phenomenon and biologicals. Birds, insects, trees, waves, and storms generate enough sensor data to slow down the track algorithm.

Excessive false tracks degrade performance because the track algorithm loading will cause it to fail to update all of the information in the track file before sensors begin the next scan begins. Chaff is intended to deny detection by exploiting this weakness.

Moving target indication (MTI) is typically used to reduce false clutter tracks to avoid overwhelming the track algorithm. Systems that lack MTI must reduce receiver sensitivity or prevent transition to track in heavy clutter regions.

Doppler

Lock and radial velocity are unique requirement for Doppler sensors that add additional layers of complexity to the track algorithm.

The radial velocity of the reflector is determined directly in Doppler systems by measuring the frequency of the reflector over the short span of time associated with detection. This frequency is converted to radial velocity.

The radial velocity of the reflector is also determined by comparing the distance for successive scans.

The two are subtracted, and the difference is averaged briefly.

${\displaystyle {\text{Lock criteria}}\;{\begin{cases}\mathrm {\left\vert \left({\frac {\Delta R}{\Delta T}}\right)-\left({\frac {C\times {\text{Doppler Frequency}}}{2\times {\text{Transmit Frequency}}}}\right)\right\vert <{\text{Threshold}}} \end{cases}}}$

If the average difference falls below a threshold, then the signal is a lock.

Lock means that the signal obeys Newtonian mechanics. Valid reflectors produce a lock. Invalid signals do not. Invalid reflections include things like helicopter blades, where Doppler does not correspond with the velocity that the vehicle is moving through the air. Invalid signals include microwaves made by sources separate from the transmitter, such as radar jamming and deception.

Reflectors that do not produce a lock signal cannot be tracked using the conventional technique. This means the feedback loop must be opened for objects like helicopters because the main body of the vehicle can be below the rejection velocity (only the blades are visible).

Transition to track is automatic for detections that produce a lock. This is essential for semi-active radar homing that requires velocity information obtained by the launch platform radar.

Transition to track is manual for non-Newtonian signal sources, but additional signal processing can be used to automate the process. Doppler velocity feedback must be disabled in the vicinity of reflectors like helicopters, where Doppler velocity measurement does not match radial velocity of the vehicle.

Pulse-Doppler sensor data includes object area, radial velocity, and lock state, which are part of the decision logic involving join tracks and split tracks.

Passive

Passive sensor information includes only angle data or time. Passive listening is used when the tracking system is not emitting any energy, such as with underwater systems, with electronic counter countermeasures, and with projectile sensors.

The three strategies are bi-static, synthetic aperture, and time of arrival.

Bistatic measurements involves comparing data from multiple sensors that can produce only angular data. Distance is identified using parallax.

Synthetic aperture involves taking multiple angular measurements while the emitter maneuvers. The process is similar to celestial mechanics where orbit is found from line of site data. The distance to a vehicle traveling at constant velocity will fall at discrete points along a straight line transecting the line of site. The coriolis effect can be used to determine the distance to this line when the object maintains constant speed during a turn. This strategy is normally used with semi-active radar homing and with underwater systems.

Time measurements are used to identify signals from impulse sources, such as from projectiles and bombs. Bombs produce a single impulse, and the location can be identified by comparing the time of arrival as the shock wave passes over 3 or more sensors. Projectiles produce an initial impulse from the muzzle blast with a shock wave traveling radially outward perpendicular to the path of the supersonic projectile. The shock wave from the projectile arrives before the muzzle blast for inbound fire, so both signals must be paired by the tracking algorithm. Subsonic projectiles emit a shock wave that arrives after the muzzle blast.

The signal emission signature must be used to match up angular data to accomplish track capture when multiple signal sources arrive at the sensor simultaneously.

Track

All new sensor data is compared with existing tracks first before capture or drop processing takes place.

Track position and velocity information establishes a track volume at a future position. New sensor data that falls inside that track box is appended to the track history for that track and deleted from temporary storage.

${\displaystyle {\text{Append}}\;{\begin{cases}{\text{Size}}>\left\vert X_{s}-(X_{o}+V_{x}\cdot \Delta T)\right\vert \\{\text{Size}}>\left\vert Y_{s}-(Y_{o}+V_{y}\cdot \Delta T)\right\vert \\{\text{Size}}>\left\vert Z_{s}-(Z_{o}+V_{z}\cdot \Delta T)\right\vert \end{cases}}}$

During operation, XYZ sensor measurements for each vehicle are appended to the track file associated with that vehicle. This is the track history that is used to keep track of position and velocity. XYZ velocity is determined by subtracting successive values and dividing by the time difference between the two scans.

${\displaystyle {\text{Velocity}}\;{\begin{cases}Vx=(X_{1}-X_{0})/\Delta T\\Vy=(Y_{1}-Y_{0})/\Delta T\\Vz=(Z_{1}-Z_{0})/\Delta T\end{cases}}}$

Tracks where the vehicle continues to produces a detection are called active tracks. The track volume is much smaller than the capture volume.

The track is continued briefly in the absence of any detections. Tracks with no detections become coasted tracks. The velocity information is used to move the track volume through space briefly as the track volume is expanded.

New tracks that fall within the capture volume of a coasted track are cross correlated with the track history of the nearby coasted track. If position and speed are compatible, then the coasted track history is combined with the new track. This is called a join track.

A new track that begins in or near the capture volume of an active track is called a split track.

Coasted track, joined track, and split track trigger an operator alert. For example, a track coast can result from an aircraft collision, so the cause needs to be determined otherwise supervisory personnel need to be notified.

Civilian air traffic control personnel use leaders produced by the track algorithm to alert pilots when the future position of two tracks violate the separation limit.

Track data is usually recorded in the event that an investigation is required to establish the root cause for an aircraft loss.

This is a special case of the Kalman filter.

References

1. "Fundamentals of Radar Tracking". Applied Technology Institute.
2. "Local Tracking". Radar Tutorial Dot EU.
3. "Performance Comparison of Tracking Algorithms for a Ground Based Radar" (PDF). Ankara University.