Method and apparatus for multi-sensor, multi-target tracking using a genetic algorithm

• US 6,055,523 A
• Filed: 07/15/1997
• Issued: 04/25/2000
• Est. Priority Date: 07/15/1997
• Status: Expired due to Fees

• Current Assignee: United States Of America As Represented By The Secretary Of The Army (Government of the United States of America)
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: Hillis, David B.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Starks, Wilbert L.
• Application Number:
  US08/903,197
• Time in Patent Office: 1,015 Days
• Field of Search: 706/13, 706/14, 706/12
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and apparatus wherein a Genetic Algorithm is used as an intelligent search technique addresses the problem of assigning sensor reports in multi-target tracking with one or more sensors. The inventive technique of tracking objects includes receiving sensor reports from at least one sensor over multiple time scans; formulating individuals in a GA population as permutations of the sensor reports; using each permutation to construct a hypothesis containing at least one track by a process of taking each sensor report in turn (in the order determined by the permutation) and making the best assignment available (either to an existing track or as the start of a new track); scoring each of the hypotheses; searching through a portion of the possible hypotheses, using a GA, to find a good hypothesis; and determining the state of the tracked object.

Claims

1. A method of tracking at least one object, comprising:

receiving sensor reports from at least one sensor over a window comprised of multiple time scans;

formulating individuals in a GA population as permutations of the sensor reports;

using each permutation to construct a hypothesis containing at least one track by a process of;

taking each sensor report in turn in the order determined by the permutation;

calculating for each sensor report the cost of assigning the sensor report to each of the tracks already formed (if any) and a start of a new track;

making the lowest cost assignment available of the sensor reports until all of the sensor reports have been assigned to tracks;

scoring each of the hypotheses;

searching through a portion of the possible hypotheses, using a GA, to find a good hypothesis; and

determining the state of the tracked object.

2. The method of claim 1, wherein the good hypothesis is an optimal hypothesis across the window of multiple time scans.

3. The method of claim 1, wherein multiple objects are tracked and further comprising determining states of the multiple objects.

4. The method of claim 1, wherein the method is performed over a sliding window of multiple time scans.

5. The method of claim 1, further comprising:

forming a second window of multiple time scans that overlaps the window;

receiving additional sensor reports from at least one sensor over the second window;

formulating individuals in a GA population as permutations of the reports falling within the second window;

using each permutation to construct a hypothesis containing at least one track by a process of taking each sensor report in turn in the order determined by the permutation and making the best assignment available to one of an existing track and a start of a new track;

scoring each of the hypotheses;

searching through a portion of the possible hypotheses, using a GA, to find a good hypothesis; and

determining a second state of the at least one object.

6. The method of claim 5, further comprising repeating the steps of the claim for multiple windows.

7. An apparatus for tracking at least one object, comprising:

means for receiving sensor reports from at least one sensor over a window comprised of multiple time scans;

means for formulating individuals in a GA population as permutations of the sensor reports;

means for using each permutation to construct a hypothesis containing at least one track by a process of;

taking each sensor report in turn in the order determined by the permutation;

calculating for each sensor report the cost of assigning the sensor report to each of the tracks already formed (if any) and a start of a new track;

making the lowest cost assignment available of the sensor reports until all of the sensor reports have been assigned to tracks;

means for scoring each of the hypotheses;

means for searching through a portion of the possible hypotheses, using a GA, to find a good hypothesis; and

means for determining the state of the tracked object.

8. The apparatus of claim 7, further comprising:

means for forming a second window of multiple time scans that overlaps the window;

means for receiving additional sensor reports from at least one sensor over the second window; and

means for formulating individuals in a GA population as permutations of the reports falling within the second window.

9. A method of tracking at least one object, comprising:

(a) receiving sensor reports from at least one sensor over a window comprised of multiple time scans;

(b) formulating individuals in a GA population as permutations of the sensor reports;

(c) decoding each permutation to construct a hypothesis for each permutation containing at least one track by a process of using each permutation to construct a hypothesis containing at least one track by a process of;

taking each sensor report in turn in the order determined by the permutation;

calculating for each sensor report the cost of assigning the sensor report to each of the tracks already formed (if any) and a start of a new track;

making the lowest cost assignment available of the sensor reports until all of the sensor reports have been assigned to tracks;

(d) scoring each of the hypotheses based on best overall fitness;

(e) using a GA to find a good hypothesis comprising;

(i) selecting a subpopulation of individuals for offspring production based at least in part on fitness;

(ii) producing a next generation of individuals from the subpopulation;

(iii) mutating the next generation of individuals stochastically;

(iv) scoring the offspring according to fitness;

(f) repeating step (e) at least once to arrive at at least one successor generation of individuals;

(g) selecting the highest scoring individual from the at least one successor generation and declaring the individual to be a tentative hypothesis;

(h) receiving new sensor reports from the at least one sensor over a window comprised of at least one scan occurring later in time than the reports from step (a);

(i) adding the new sensor reports to at least some of the sensor reports from step (a);

(j) repeating steps (b) through (g) at least once.