Method and apparatus for multi-sensor, multi-target tracking using intelligent search techniques

• US 5,793,931 A
• Filed: 11/18/1996
• Issued: 08/11/1998
• Est. Priority Date: 11/18/1996
• Status: Expired due to Fees

• Current Assignee: United States Department of the Army
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: Hillis, David
• Primary Examiner(s): Davis, George B.
• Application Number:
  US08/752,461
• Time in Patent Office: 631 Days
• Field of Search: 395/13
• US Class Current: 706/13
• CPC Class Codes: G01S 13/726 Multiple target tracking

Abstract

A method and apparatus wherein a Genetic Algorithm or an Evolutionary Program 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 hypotheses as lists of associations between the sensor reports; constructing at least one track for each of the hypotheses; scoring each of the hypotheses; searching through a portion of the hypotheses, using an intelligent search algorithm, to find a good hypothesis; and determining the state of the tracked objects.

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 hypotheses as lists of associations between the sensor reports;

constructing at least one track for each of the hypotheses;

scoring each of the hypotheses;

searching through a portion of the hypotheses, using an intelligent search algorithm, to find a good hypothesis; and

determining, using a computer, a state of the at least one object.

2. The method of claim 1, wherein the intelligent search algorithm is a genetic algorithm (GA) and further comprising forming a genotype for the genetic algorithm (GA) using the lists of associations such that a population in the GA comprises a group of the lists.

3. The method of claim 2, further comprising forming additional lists of associations using at least one of a crossover operation and a mutation operation.

4. The method of claim 3, wherein the crossover and mutation operations include a gating test to eliminate undesirable hypotheses.

5. The method of claim 2, further comprising testing mutation operations for some of the portion of the hypotheses, using a local improvement operator.

6. The method of claim 1, wherein the intelligent search algorithm is an evolutionary program.

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

8. The method of claim 1, wherein multiple objects are tracked and further comprising detaining, using the computer, states of the multiple objects.

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

10. The method of claim 1, wherein the formulating step includes the step of subjecting the hypotheses to a gating test to eliminate undesirable hypotheses.

11. 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 new hypotheses as lists of associations between a portion of the sensor reports and the additional sensor reports;

constructing at least one track for each of the new hypotheses;

scoring each of the new hypotheses;

searching through a portion of the new hypotheses, using an intelligent search algorithm, to find a second good hypothesis; and

determining, using a computer, a second state of the at least one object.

12. The method of claim 11, further comprising repeating the steps of the claim for multiple windows.

13. 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;

modifying the hypotheses to add associations for the additional sensor reports and delete associations for the sensor reports that are outside the second window;

constructing at least one track for each of the modified hypotheses;

scoring each of the modified hypotheses;

searching through a portion of the modified hypotheses, using an intelligent search algorithm, to find a second good hypothesis; and

determining, using the computer, a second state of the at least one object.

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

means for receiving sensor reports from at least one sensor over multiple time scans;

means for formulating hypotheses as lists of associations between the sensor reports;

means for constructing at least one track for each of the hypotheses;

means for scoring each of the hypotheses;

means for searching through a portion of the hypotheses, using an intelligent search algorithm, to find a good hypothesis; and

computer means for determining a state of the at least one object.

15. The apparatus of claim 14, wherein the intelligent search algorithm is a genetic algorithm (GA) and further comprising means for forming a genotype for the genetic algorithm (GA) using the lists of associations such that a population in the GA comprises a group of the lists.

16. The apparatus of claim 15, further comprising means for forming additional lists of associations using at least one of a crossover operation and a mutation operation.

17. The apparatus of claim 15, further comprising means for testing mutation operations for some of the portion of the hypotheses, using a local improvement operator.

18. The apparatus of claim 14, wherein the intelligent search algorithm is an evolutionary program.

19. The apparatus of claim 14, wherein the means for formulating includes means for subjecting the hypotheses to a gating test to eliminate undesirable hypotheses.

20. A method of tracking at least one point on an object, comprising:

receiving sensor reports from at least one sensor over multiple time scans;

formulating hypotheses as lists of associations between the sensor reports;

constructing at least one track for each of the hypotheses;

scoring each of the hypotheses;

searching through a portion of the hypotheses, using an intelligent search algorithm, to find a good hypothesis; and

determining, using a computer a state of the at least one point.