1. Field of the Invention
A neural network system having a "barometer" neuron to enhance system stability which improves surveillance capabilities, particularly when the system is used in a track-while-scan operation.
Track-while-scan systems have as an important feature plot/track association which consists of assigning radar plots to predicted track positions. Applying neural network technology to the plot/track association problem in accordance with the invention achieves good global solutions for track-while-scan systems.
However, neural networks have recurring instability problems.
2. Description of Related Art
A neural network implementation of plot/track association consists of assigning radar plots to predicted track positions and is an important feature of all track-while-scan systems. Plot to track association is the middle step in a track while scan (TWS) cycle. The cycle begins by correlating plots generated by the radar with predicted track positions, producing potential parings. Next, in the association step, potential pairings are compared to produce some set of "best" associations. Each track's associated plot is then used to update the track's parameters and predict the track's position in the next cycle.
The problem is complicated in regions of high target density because many conflicting associations are possible. Also, the blip/scan ratio, i.e., the ratio of the number of scans in which a return is received for a given track to the total number of scans, is always less than one. This means that not all tracks should be assigned an associated plot.
Association can be viewed as an example of the classical assignment problem. The optimal solution to an assignment problem minimizes some cost function, in this case a total distance which is the sum of all of the individual plot/track distances. Frequently, the globally optimal solution contains pairings which are not necessarily between nearest neighbors. An array of techniques has been propounded to solve assignment problems, including the Munkres algorithm, the Ford-Fulkerson method, and the Hungarian method, which are all more efficient than an exhaustive search of the possible solutions.
Correct association is vital to tracking. Incorrect associations over subsequent scans can lead to filter divergence and eventual loss of track continuity.
Neural networks are information processing systems made up of (large) numbers of simple processors which are extensively interconnected. Neural networks are attempts at processing architectures similar to naturally occurring, biological ones, which solve problems that have not yielded to traditional computer methods and architectures. The name "neural network" derives from the biological "neuron," which is what each simple processor is called.
A frequently used model of such a processor and the processor used in the networks of the invention is shown by FIG. 1.
In the processor of FIG. 1, each neuron has a large group of inputs taken directly from the outputs of other neurons V.sub.j (k). Associated with each input line there is a connection weight T.sub.nj. This weight describes the relative contribution of the line's input in computing the neuron's next state. A zero weight indicates that there is effectively no contribution. A negative weight value indicates an inhibitory relationship. A positive weight shows an excitatory relationship.
A single neuron's operation is relatively simple. At cycle k+1, it scans all of its inputs (which are the outputs of the other neurons at cycle k), multiplies each input by the weight associated with that input, forming V.sub.j T.sub.nj, and sums these products. Then, the weighted sum is passed through a "transfer" function to form the neuron's output for cycle k+1, V.sub.n (k+1).
A variety of transfer functions are used, but a common one is the sigmoid function, which is defined as: ##EQU1## where x is the sum of the weighted inputs.
There are many ways in which neurons are connected and in which computations are ordered within networks. Nearly all, however, have in common that the network's "knowledge" or "expertise" is distributed over the entire network and actually resides in the connection weights. As long as the weights are equal, the network is "symmetric" and seeks a stable equilibrium.
Some of the best documented results using neural networks to solve problems describe the use of nets to solve the Travelling Salesman Problem (TSP). [J. J. Hopfield and D. W. Tank paper: "Neural" Computation of Decisions in Optimization Problems. Biol. Cybern. 52, 141-152 (1985); hereinafter "Hopfield TSP"]
These results using neural networks are applicable to modern air defense systems which must become more and more sophisticated to handle increasingly complex projected threats, such as low-observable (LO) targets and potentially massive raid situations. In order to detect LO targets, sensor sensitivity must be greatly increased (resulting in significantly more false alarms) or the suite of sensors must be augmented to include a variety of sensors, such as infrared radiation (IR) or electronic support measures (ESM), and then fuse their respective information. In either case, it becomes necessary to process significantly more and more data.
Conventional signal processing techniques are ill-equipped to handle extremely dense situations and very low signal-to-noise ratio (SNR) conditions. Neural-networks when applied to detection and tracking technology could make a significant performance improvement in plot/track association.
What is plot/track association? Plot/track association consists of assigning radar plots to predicted track positions. It is a critical but computationally intensive element of track-while-scan (TWS) systems. Incorrect associations over consecutive scans can lead to filter divergence and eventual loss of track continuity.
In benign conditions with sparse spatial density of targets and false plots, a nearest neighbor assignment protocol is often satisfactory. However, as the density increases and exceeds on the average 1.2 returns per correlation gate, the misassociation errors using a nearest neighbor assignment become prohibitive. This can occur as the number of plots increases or as the size of the correlation gate increases. The latter was found to be the case in tracking with a bistatic radar, where the correlation gates tend to be significantly larger as a result of larger measurement errors.
To exploit the massive, computational processing capability of neural networks, the plot/track association problem can be formulated in a basic framework very similar to that of the classic Travelling Salesman Problem (TSP).
The TSP can be defined as follows: given a number of cities to visit, what is the shortest circuit of all the cities, visiting each one once and then returning to the original city, that a salesman could take? The problem is NP-complete, meaning that it is of the class of problems whose exact solution becomes intractable when the problem grows large. For example in a 10 city TSP there are about 181,000 different tours to check, while for a 20 city TSP there are about 6.08.times.10.sup.16 tours to check!
If rows in the Hopfield TSP neural network are allowed to represent plots instead of cities and columns represent tracks instead of positions, then the network is well-suited for the plot/track association problem. Thus, each possible plot/track pairing is assigned a dedicated neuron. FIG. 2 illustrates the similarities between the PRIOR ART TSP and the problem of plot/track association.
In view of Hopfield's teachings, the solution to the plot/track association problem can be interpreted in a similar way: there should be exactly one cell "on" per row (one association per plot) and one "on" per column (one association per track). The network's solution state should have a number of cells "on" corresponding to the minimum of these two counts if they are not equal.
A distance measurement is also being minimized for this plot/track association problem: the essential difference is that distance is measured from track-to-plot rather than city-to-city. The optimal solution to the association problem produces that set of assignments which, taken all together, minimize the sum of all of the distances from each plot to the predicted position of the track to which it is assigned.
Track-to-plot association then is the final step in a track-while-scan (TWS) cycle. The TWS cycle begins by predicting each track's position. Plots generated by the radar hardware (and preprocessing software) are then correlated against the predicted track positions and a correlation score is developed by each potential pairing. Finally, in the association step, correlation scores are compared to produce some set of "best" associations. Each track's associated plot is then used to update the track's parameters for prediction in the next cycle.
The problem is complicated in regions of high target density because many conflicting associations are possible. Also, the blip/scan ratio (the ratio of the number of scans in which a return is received for a given track to the total number of scans) is always less than 1.0, meaning that not all tracks will be assigned an associated plot.
To represent this plot/track association problem then as applied, for example to a modern air defense system, interconnection weights are computed somewhat differently than in Hopfield's TSP network. The weight equation for the computation of the connection weights .sup.T XXiYj becomes (with X and Y as plots, i and j as tracks, and d.sub.Xi as the distance from plot X to track i): ##EQU2## where -A coefficient represents the inhibition between cells in a row, the -B coefficient represents the inhibition between cells in a column, and the -C coefficient represents the inhibition between the global or network of cells which are "on".
The external bias equation is: EQU I.sub.Xi =+Cn (1)
and remains unchanged from Hopfield's energy equation. (See Prof. J. J. Hopfield and D. W. Tank's paper, supra).
The coefficients -A, -B, and -C are also unchanged from Hopfield's equation. However, the -D coefficient in equation (1) does differ from the -D coefficient in Hopfield's equation.
In the Hopfield TSP, when two cells in adjoining columns are "on", then the distance between the two cities in whose rows the cells lie is part of the total distance of the tour. In the plot/track association network, when any two cells (not in the same row or column) are "on", then a distance proportional to the sum of the two plot/track distances is added to the global solution. The actual distance added is: ##EQU3##
This 2(n-1) factor takes into account that for any neuron which has value 1, in the solution there will be (n-1) other neurons also of value 1, and the -D coefficient will be added in 2(n-1) times for each neuron because of the double summation of the neuron values weighted products. Since the D term is a constant coefficient multiplied into the distance, the (n-1) factor can be incorporated into D. The value actually substituted into the weight equation (1) for (d.sub.Xi +d.sub.Yj) is: ##EQU4##
In the solution of the Hopfield TSP, an additional parameter, u.sub.o, is added and another, n, is redefined. The parameter n, originally representing the number of cities (and the desired number of cells "on"), "was used to adjust the neutral position of the amplifiers which would otherwise also need an adjustable offset parameter in their gain functions." (See Hopfield and Tank, id.) The n parameter appears in Hopfield's energy equation and also in equation (2) above; it basically functions to define the amount of external excitation the network is given. The U.sub.o parameter is used as a gain in the modified sigmoid function: ##EQU5##
This plot/track association network has been tested with simulation systems running on known processors. This network was implemented as a 3.times.3 network (i.e., 3 tracks and 3 plots) using connection weights as specified by equation (1) with coefficient values of A=B=D=5, C=2, n=4.5 (same ratios as taught by Hopfield). With a gain of u.sub.0 =0.02, no valid solutions were obtained, so it was greatly increased (gain was decreased) with values near 1.0 finally used. Having arrived at an appropriate value for n, valid solutions were obtained on problem instances of this size.
However, as the network's size increases (for example, 8 tracks and 8 plots) no set of system parameters that yielded stable solutions, valid or invalid, could be found. The literature suggests that network instability is a recognized problem. [See Wilson, G. V., Pawley, G. S.: "On the stability of the traveling salesman problem algorithm of Hopfield and Tank." Biol. Cybern. 58: 63-70 (1988)] Hopfield networks of this type frequently enter oscillatory, unstable states with alternating cycles of all units being "off" followed by all being "on."
An informal analysis of the instability reveals an imbalance between system excitation and inhibition. When there is too much inhibition, the activation values of all neurons are driven to near 0.0; the opposite happens when there is too little inhibition. If all neurons' activation values in one cycle are 0.0, then the majority of the inhibition (from one neuron to another) disappears, and the excitation (which is global and external) causes all neurons' values to go to 1.0 on the next cycle. Inhibition once again becomes great enough to overcome all excitation, and on the next cycle all values are again driven to 0.0.
With this imbalance as a cause of a neural networks' instability, a solution is needed to enhance network stability.