Data processing: measuring – calibrating – or testing – Measurement system – Measured signal processing
Reexamination Certificate
2000-10-25
2004-03-09
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Measured signal processing
C702S042000, C702S074000, C702S081000, C702S084000, C702S116000, C702S155000, C342S096000
Reexamination Certificate
active
06704692
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a method and system for solving a combinatorial optimization problem to select from a larger set, a plurality of associations of measurements taken of a plurality of objects and, more particularly, to a method and system for constructing a plurality of updated tracks based upon associations of a plurality of measurements of a plurality of objects.
BACKGROUND OF THE INVENTION
It is useful in many applications to track a plurality of objects. In addition to identifying the location of an object, various state variables, such as the velocity and acceleration of each object can be tracked. An analysis of the track of an object therefore permits the future path of the object to be predicted such that appropriate action can be taken. For example, in a commercial air traffic control application, a plurality of aircraft in the vicinity of an airport must be tracked in order to ensure that the respective courses of the aircraft are sufficiently spaced from one another. In addition, in military applications, enemy aircraft or missiles may be tracked to permit appropriate responses, such as interceptions, to be planned and executed.
In most aerospace applications, aircraft or other vehicles and missiles are tracked by radar that scans a region and obtains a number of sensor measurements based upon signals that have been returned from the object. While radar is prevalent, other types of interrogation systems can be utilized for tracking objects, including infrared systems or sonar systems for underwater tracking applications. Based upon the return signals or sensor measurements, the track of the object can be determined. In this regard, tracking is typically defined as the process of associating a sequence of measurements to define the track of a respective object.
In instances in which the region that is interrogated has only one object or has only a small number of objects that are widely spaced from one another, tracking of the object(s) is not difficult. However, in instances in which a plurality of objects are positioned in the same region, tracking becomes much more difficult. This difficulty in tracking is further exacerbated in instances in which the objects are closely spaced, highly maneuverable or have low observability since it will be difficult to determine which of the return signals or sensor measurements are attributable to which of the objects. Notwithstanding these difficulties, correctly associating measurements with respective objects is paramount to tracking applications since the integrity of the tracking process is otherwise compromised.
Most tracking systems that are currently deployed utilize data association techniques that extend a set of maintained tracks into a single additional scan of sensor measurements. In this regard, these deployed tracking systems maintain a track for each object based upon associations of prior sensor measurements with the respective object. Following each successive scan of the region, the additional sensor measurements are associated with a respective object and the track that has been maintained for that object is extended to include the additional sensor measurement. These tracking systems do not revisit the associations of sensor measurements that have been previously determined in order to generate the set of maintained tracks. As such, any errors that arise in defining the tracks will be maintained for a significant period of time since additional sensor measurements are merely tacked onto a maintained track in order to update or extend the track.
Typically, the extension of a set of maintained tracks into a single additional scan of sensor measurements is formulated and solved as either a bipartite two-dimensional assignment problem or by a greedy algorithm. For example, D. P. Bertsekas,
Linear Network Optimization—Algorithms and Codes
, The MIT Press, Cambridge, Mass. (1991), and R. Jonker and A. Volgenant,
A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems
, Computing 38, pp. 325-340 (1987) describe the formulation and solution of a bipartite two-dimensional assignment problem, while S. S. Blackman,
Multiple Target Tracking with Radar Applications
, Artech House, Dedham, Mass., (1990) describes the formulation and solution of a greedy algorithm. Once the best set of associations of the maintained tracks with the single additional scan of sensor measurements has been determined, the tracks are updated and the process is repeated for the next scan of sensor measurements. This technique can provide real-time solutions for relatively easy tracking problems, but has been found to be inadequate in instances in which the objects are closely spaced, highly maneuverable and/or have low observability.
More recently, tracking systems have been investigated that update tracks based upon multiple scans of sensor measurements to improve tracking accuracy. As such, the sensor measurements that were associated to define the prior maintained track for a particular object can be revisited in the course of defining the updated track. While computationally more difficult, this multi-scan-tracking scheme is believed to be more accurate.
The multi-scan tracking technique is typically implemented in a sliding window tracking architecture as shown in FIG.
1
. In this technique, a set of tracks for the objects is maintained based upon the prior S scans of sensor measurements. As such, the window is broad enough to include S scans of sensor measurements. Upon receiving a new scan, the window is slid such that the oldest of the S scans of sensor measurements falls out of the window and the new scan of sensor measurements is inserted into the window. See blocks
10
and
12
. Thereafter, a number of potential associations of the maintained tracks and the S scans of sensor measurements within the window are determined and are termed candidate tracks. See block
14
. In addition, a cost of each candidate track is determined. The cost is generally based on the likelihood that the measurements are actually part of the candidate track. In most instances, each cost is determined by a negative log likelihood function which includes terms to account for the deviation of the measurements from the candidate track, sensor errors, and events related to track initiation, track termination, track maneuver, false alarms and missed detections. See, for example A. Poore and N. Rijavec,
A Lagrangian Relaxation Algorithm for Multidimensional Assignment Problems Arising from Multitarget Tracking
, SIAM J. Optimization 3, No. 3, pp. 544-563 (August 1993), S. Deb, M. Yeddanapudi, K. Pattipati, and Y. Bar-Shalom,
A Generalized S
-
D Assignment Algorithm for Multisensor
-
Multitarget State Estimation
, IEEE Transactions on Aerospace and Electronic Systems 33, No. 2, pp. 523-536 (April 1997), and Y. Bar-Shalom, ed.,
Multitarget
-
Multisensor Tracking: Advanced Applications
, Artech House, Dedham, Mass. (1990) that discuss the generation of candidate tracks and the computation of costs for the candidate tracks.
After determining the set of candidate tracks and the cost of each candidate track, the most probable set of candidate tracks is determined by solving the resulting data association problem. See block
16
. In particular, the data association problem is solved by selecting the subset of associations of minimum total cost while accounting for each maintained track and each sensor measurement. For S scans of measurements and a set of maintained tracks, this data association problem can be formulated as a multi-dimensional assignment problem (MAP) of dimensionality S+1. Once the data association problem is solved, the solution is utilized to extend the set of maintained tracks by the additional scan of sensor measurements. See block
18
. The window then slides again to admit a new scan of sensor measurements while dropping the oldest scan and the generation of candidate tracks and respective costs as well as the solution of the data association problem are repeat
Banerjee Subhankar
Berge Matthew Elden
DeVun, Jr. Esmond Ernest
Filipowski Sharon Kay
Alston & Bird LLP
Hoff Marc S.
The Boeing Company
Tsai Carol S
LandOfFree
Method and system for tracking multiple objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for tracking multiple objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for tracking multiple objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220025