Patent ID: RE44807

Claim:
A method for tracking a plurality of objects, comprising: repeatedly scanning a region containing a set consisting of one or more moving objects and generating N sequential images or data sets of said region, a plurality of observations in said images or data sets providing positional information for objects in said set; determining a plurality of tracks, at least one track for each object in said set; determining a plurality of costs, wherein each cost is for assigning one of said observations to one of said tracks; defining a linear programming problem: Minimize ⁢ ⁢ ∑ i 1 ⁢ … ⁢ ⁢ i N ⁢ ⁢ c i 1 ⁢ … ⁢ ⁢ i N ⁢ z i 1 ⁢ … ⁢ ⁢ i N Subject ⁢ ⁢ To ⁢ ⁢ ∑ i 2 ⁢ i 3 ⁢ … ⁢ ⁢ i N ⁢ z i 1 ⁢ … ⁢ ⁢ i N = 1 , ( i 1 = 1 , … ⁢ , M 1 ) ⁢ ∑ i 1 ⁢ i 3 ⁢ … ⁢ ⁢ i N ⁢ z i 1 ⁢ … ⁢ ⁢ i N = 1 , ( i 2 = 1 , … ⁢ , M 2 ) ⁢ ∑ i 1 ⁢ … ⁢ ⁢ i p - 1 ⁢ i p + 1 ⁢ … ⁢ ⁢ i N ⁢ z i 1 ⁢ … ⁢ ⁢ i N = 1 ⁢ ( i p = 1 , … ⁢ , M p ⁢ ⁢ and ⁢ ⁢ p = 2 , … ⁢ , N - 1 ) ⁢ ∑ i 1 ⁢ i 2 ⁢ … ⁢ ⁢ i N - 1 ⁢ z i 1 ⁢ … ⁢ ⁢ i N = 1 ⁢ ⁢ ( i N = 1 , … ⁢ , M N ) ⁢ 0 ≤ z i 1 ⁢ … ⁢ ⁢ i N ≤ 1 ⁢ ⁢ for ⁢ ⁢ all ⁢ ⁢ i 1 , … ⁢ , i N , wherein each c i 1 . . t N is included in said plurality of costs, each M i , i=1, . . . ,N, being one of: (a) a number of observations in an i th image or data set of said N sequential images or data sets; (b) a sum of a number of tracks in said plurality of tracks, and a number of said observations in the i th image or data set not assigned to one of said tracks; and (c) a number of tracks in said plurality of tracks; solving said linear programming problem for values of z i 1 . . . i N for each i1 . . . iN; determining a value z 1 1 . . . i N in {0,1} for each i1 . . . iN corresponding to each z ij . . i N , wherein said values zi1 . . . iN provide an optimal or near optimal solution to said linear programming problem; taking one or more of the following actions based on said optimal or near-optimal assignment of said plurality of points to said plurality of tracks; sending a warning to aircraft or a ground or sea facility, controlling air traffic, controlling anti-aircraft or anti-missile equipment, taking evasive action, working on one of said one or more objects, surveilling one of said one or more objects.