Method and system for tracking multiple objects

• US 6,704,692 B1
• Filed: 10/25/2000
• Issued: 03/09/2004
• Est. Priority Date: 10/25/1999
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: DeVun, Esmond Ernest Jr., Berge, Matthew Elden, Banerjee, Subhankar, Filipowski, Sharon Kay
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): TSAI, CAROL S W
• Application Number:
  US09/696,473
• Time in Patent Office: 1,231 Days
• Field of Search: 342/90, 342/91, 342/93, 342/94, 342/96, 342/102, 706/12, 706/14-20, 706/62, 707/2-6, 707/103, 707/104, 707/200-206, 700/100, 700/103, 700/173, 702/74, 702/81, 702/82, 702/84, 702/113, 702/42, 702/116-120, 702/122, 702/123, 702/142, 702/129, 702/135, 702/143, 702/149, 702/150, 702/152, 702/155, 702/158, 702/FOR.103, 702/FOR.113, 702/FOR.123, 702/FOR.135, 702/FOR.137, 702/FOR.141, 702/FOR-144, 702/FOR.151, 702/FOR.157, 702/FOR.160, 702/FOR-170
• US Class Current: 702/189
• CPC Class Codes: G01S 13/726 Multiple target tracking

Abstract

An improved method and system for solving a combinatorial optimization problem, such as a tracking problem, to define a plurality of associations of measurements taken of a plurality of objects is provided. In one aspect, a method, a system and a computer program product are provided for constructing a plurality of updated tracks by solving a Lagrangian dual in which each of the measurement constraints has been relaxed. In another aspect, a hybrid branch and bound and LR technique is provided to select a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs. In this regard, a search tree of the candidate tracks is ordered based upon the initial costs of the candidate tracks as adjusted by the dual variables that have been defined as a result of solving a Lagrangian dual. In order to attempt to increase the efficiency with which a Lagrangian dual is solved by nonsmooth optimization techniques, initial values for the dual variables and some of the subgradients are judiciously selected. The dual variables are initialized and some subgradients are provided based upon values of corresponding dual variables and some of the subgradients, respectively, that were determined during the solution of the prior problem. The method and system can be implemented in a parallel processing architecture that utilizes both coarse grain and fine grain techniques to evenly schedule a number of subproblems amongst a plurality of processors in order to obtain a solution in an efficient manner.

Claims

1. A method of constructing a plurality of updated tracks based upon associations of a plurality of measurements, wherein the measurements are subject to a plurality of constraints, and wherein the method comprises:

relaxing each of the constraints, said relaxing step comprising providing a dual variable for each constraint;

constructing a Lagrangian dual function that at least partially depends upon the dual variable for each constraint and a cost associated with each potential association;

determining a solution of a Lagrangian dual problem, said determining step comprising determining a value for each dual variable based upon an evaluation of the Lagrangian dual function; and

determining the associations that define the plurality of updated tracks based at least partially upon the value determined for the dual variable associated with each constraint.

2. A method according to claim 1 wherein determining the solution of the Lagrangian dual problem comprises maximizing the Lagrangian dual function.

3. A method according to claim 1 further comprising:

determining if a value of the Lagrangian dual function is acceptable prior to determining the associations that define the plurality of updated tracks; and

repeating said steps of constructing the Lagrangian dual function and evaluating the Lagrangian dual function if the prior value of the Lagrangian dual function is unacceptable.

4. A method according to claim 1 wherein providing the dual variable for each constraint comprises providing an initial value for the dual variable for each constraint, and wherein determining the value for each dual variable comprises determining an updated value for each dual variable in accordance with the solution of the Lagrangian dual problem.

5. A computer program product for constructing a plurality of updated tracks based upon associations of a plurality of measurements, each measurement being subject to a constraint, wherein the computer program product comprises a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising:

first computer-readable program code means for relaxing each of the constraints by providing a dual variable for each constraint;

second computer-readable program code means for constructing a Lagrangian dual function that at least partially depends upon the dual variable for each constraint and a cost associated with each potential association;

third computer-readable program code means for determining a solution of a Lagrangian dual problem by determining an associated value for each dual variable based upon an evaluation of the Lagrangian dual function; and

fourth computer-readable program code means for determining the associations that define the plurality of updated tracks based at least partially upon the value determined for the dual variable associated with each constraint.

6. A computer program product according to claim 5 wherein said third computer-readable program code means comprises computer-readable program code means for maximizing the Lagrangian dual function.

7. A computer program product according to claim 5 further comprising fifth computer-readable program code means for determining if a value of the Lagrangian dual function is acceptable prior to determining the associations that define the plurality of updated tracks, wherein said second and third computer-readable program code means repeat the construction of the Lagrangian dual function and the evaluation of the Lagrangian dual function if the prior value of the Lagrangian dual function is unacceptable.

8. A computer program product according to claim 5 wherein said first computer-readable program code means provides an initial value for the dual variable for each constraint, and wherein said third computer-readable program code means determines an updated value for each dual variable in accordance with the solution of the Lagrangian dual problem.

9. A method of selecting a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs, wherein the candidate tracks are based upon associations between a plurality of measurements having respective dual variables, and wherein the method comprises:

determining an adjusted cost and an adjusted cost per non-zero measurement for each candidate track based upon the initial cost and the dual variable for each measurement that is associated to create the candidate track;

placing the candidate tracks in an order based upon the adjusted cost per non-zero measurement;

searching, by a depth first search, at least a portion of a search tree having a plurality of levels, said searching step comprises;

examining at least a portion of a level 1+1 dependent upon a level 1, wherein the level 1 comprises candidate tracks that are each;

(1) feasible with respect to all candidate tracks lying in the unique path from the respective candidate track to a root node, and (2) later in the order of adjusted cost per non-zero measurement in which the candidate tracks have been placed than the candidate track of level 1 from which the respective candidate track descends, and wherein said examining comprises examining the candidate tracks at level 1+1 that descend from a respective track of level 1 in the order in which the candidate tracks have been placed; and

repeating said examining step for at least portions of other levels of the search tree that descend from the level 1+1; and

identifying the updated tracks based upon the search of at least a portion of the search tree including candidate tracks from the plurality of levels.

10. A method according to claim 9 wherein said searching step further comprises:

sequentially searching a plurality of nodes of the search tree; and

identifying a completely feasible set of candidate tracks comprised of a plurality of nodes from different levels of the search tree that has the lowest cumulative adjusted cost from amongst those completely feasible sets of candidate tracks that were examined.

11. A method according to claim 10 wherein sequentially searching the plurality of nodes comprises:

determining a total number of feasible candidate tracks that have been skipped; and

terminating the search of a respective branch if the total number of feasible candidate tracks that are skipped exceeds a threshold value.

12. A method according to claim 10 wherein said searching step further comprises:

maintaining a count of the lowest cumulative adjusted cost of the completely feasible sets of candidate tracks identified during the sequential search of the nodes of the search tree; and

terminating the search of a respective branch if a sum of the cumulative adjusted cost of the current partially feasible set of candidate tracks and the lowest estimate of the cumulative adjusted cost associated with the measurements that remain unused is at least as great as the count of the lowest cumulative adjusted cost.

13. A method according to claim 9 wherein the candidate tracks of the level 1+1 that depend from a respective candidate track of the level 1 are arranged in order of increasing adjusted cost per non-zero measurement.

14. A computer program product for selecting a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs, the candidate tracks being based upon associations between a plurality of measurements having respective dual variables, wherein the computer program product comprises a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising:

first computer-readable program code means for determining an adjusted cost and an adjusted cost per non-zero measurement for each candidate track based upon the initial cost and the dual variable for each measurement that is associated to create the candidate track;

second computer-readable program code means for placing the candidate tracks in an order based upon the adjusted cost per non-zero measurement;

third computer-readable program code means for searching, by a depth first search, at least a portion of a search tree having a plurality of levels, said second computer-readable program code means comprising;

computer-readable program code means for examining at least a portion of a level 1+1 dependent upon a level 1, wherein the level 1 comprises candidate tracks that are each;

(1) feasible with respect to all candidate tracks lying in the unique path from the respective candidate track to a root node, and (2) later in the order of adjusted cost per non-zero measurement in which the candidate tracks have been placed than the candidate track of level 1 from which the respective candidate track descends, and wherein said computer-readable program code means for examining comprises examining the candidate tracks at level 1+1 that descend from a respective track of level 1 in the order in which the candidate tracks have been placed; and

computer-readable program code means for repeating the examination for at least portions of other levels of the search tree that descend from the level 1+1; and

fourth computer-readable program code means for identifying the updated tracks based upon the search of at least a portion of the search tree including candidate tracks from the plurality of levels.

15. A computer program product according to claim 14 wherein said third computer-readable program code means comprises:

computer-readable program code means for sequentially searching a plurality of nodes of the search tree; and

computer-readable program code means for identifying a completely feasible set of candidate tracks comprised of a plurality of nodes from different levels of the same tree that has the lowest cumulative adjusted cost from amongst those completely feasible sets of candidate tracks that were examined.

16. A computer program product according to claim 15 wherein said computer-readable program code means for sequentially searching the plurality of nodes comprises:

computer-readable program code means for determining a total number of feasible candidate tracks that have been skipped; and

computer-readable program code means for terminating the search of a respective branch if the total number of feasible candidate tracks that are skipped exceeds a threshold value.

17. A computer program product according to claim 15 wherein said third computer-readable program code means further comprises:

computer-readable program code means for maintaining a count of the lowest cumulative adjusted cost of the sets of candidate tracks identified during the sequential search of the nodes of the search tree; and

computer-readable program code means terminating the search of a respective branch if a sum of the cumulative adjusted cost of the current set of candidate tracks and the lowest estimate of the cumulative adjusted cost associated with the measurements that remain unused is at least as great as the count of the lowest cumulative adjusted cost.

18. A computer program product according to claim 15 wherein the candidate tracks of the level 1+1 that depend from a respective candidate track of the level 1 and arranged in order of increasing adjusted cost per non-zero measurement.

19. A method of selecting a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs, wherein the candidate tracks are based upon associations between a plurality of measurements having respective dual variables, and wherein the method comprises:

searching, by a depth first search, at least a portion of a search tree having a plurality of levels, wherein each level is comprised of at least one candidate track, said searching step comprises;

sequentially searching along a unique path from a root node to a candidate track of level 1 of the search tree, wherein sequentially searching comprises;

(1) determining a total number of feasible candidate tracks that have been skipped during the sequential search along the unique path, and (2) terminating the search along the unique path if the total number of feasible candidate tracks that are skipped exceeds a threshold value; and

identifying the updated tracks based upon the search of at least a portion of the search tree including candidate tracks from the plurality of levels.

20. A method according to claim 19 wherein the candidate tracks of the level 1+1 that depend from a respective candidate track of the level 1 are arranged in order of increasing adjusted cost per non-zero measurement.

21. A computer program product for selecting a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs, the candidate tracks being based upon associations between a plurality of measurements having respective dual variables, wherein the computer program product comprises a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising:

first computer-readable program code means for searching, by a depth first search, at least a portion of a search tree having a plurality of levels, wherein each level is comprised of at least one candidate track, and wherein said first computer-readable program code means comprising;

computer-readable program code means for sequentially searching along a unique path from a root node to a candidate track of level 1 of the search tree, wherein sequentially searching comprises;

(1) determining a total number of feasible candidate tracks that have been skipped during the sequential search along the unique path, and (2) terminating the search along the unique path if the total number of feasible candidate tracks that are skipped exceeds a threshold value; and

second computer-readable program code means for identifying the updated tracks based upon the search of at least a portion of the search tree including candidate tracks from the plurality of levels.

22. A computer program product according to claim 21 wherein the candidate tracks of the level 1+1 that depend from a respective candidate track of level 1 are arranged in order of increasing adjusted cost per non-zero measurement.

23. A method of constructing a plurality of updated tracks based upon associations of a plurality of measurements, wherein the measurements are subject to a plurality of constraints, and wherein the method comprises:

constructing an approximation of a Lagrangian dual function based at least in part upon dual variables associated with the measurements and also in part upon subgradients of the Lagrangian dual function;

initializing the dual variables and providing at least some of the subgradients based upon values of corresponding dual variables and subgradients, respectively, determined during a solution of a prior Lagrangian dual problem;

maximizing the Lagrangian dual function; and

determining the associations that define the plurality of updated tracks based at least partially upon the maximized Lagrangian dual function.

24. A method according to claim 23 further comprising determining if a solution of a Lagrangian dual problem based upon the maximized Lagrangian dual function is acceptable prior to determining the associations that define the plurality of updated tracks.

25. A method according to claim 24 further comprising:

updating the dual variables and the subgradients based at least in part upon a current value of the Lagrangian dual function; and

repeating an evaluation on the Lagrangian dual function if the prior value of the Lagrangian dual function is unacceptable.

26. A computer program product for constructing a plurality of updated tracks based upon associations of a plurality of measurements, each measurement being subject to a constraint, wherein the computer program product comprises a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising:

first computer-readable program code means for constructing an approximation of a Lagrangian dual function based at least in part upon dual variables associated with the measurements and also in part upon subgradients of the Lagrangian dual function;

second computer-readable program code means for initializing the dual variables and providing at least some of the subgradients based upon values of corresponding dual variables and subgradients, respectively, determined during a solution of a prior Lagrangian dual problem;

third computer-readable program code means for maximizing the Lagrangian dual function; and

fourth computer-readable program code means for determining the associations that define the plurality of updated tracks based at least partially upon the maximized Lagrangian dual function.

27. A computer program product according to claim 26 further comprising computer-readable program code means for determining if a solution of a Lagrangian dual problem based on the maximized Lagrangian dual function is acceptable prior to determining the associations that define the plurality of updated tracks.

28. A computer program product according to claim 27 further comprising computer-readable program code means for updating the dual variables and the subgradients based at least in part upon a current value of the Lagrangian dual function, wherein said third computer-readable program code means repeats an evaluation of the Lagrangian dual function if the prior value of the Lagrangian dual function is unacceptable.

29. A method of constructing a plurality of updated tracks based upon associations of a plurality of measurements in a parallel computing architecture having a plurality of processors, the method comprising:

decomposing data representative of the plurality of measurements into a plurality of subproblems having respective sizes;

evaluating the sizes of the subproblems to determine if the subproblems are capable of being assigned to the plurality of processors in a balanced manner;

assigning the plurality of subproblems to respective ones of the plurality of processors; and

executing the plurality of subproblems in parallel on the respective processors to determine the associations of the plurality of measurements of each subproblem in order to define the plurality of updated tracks, said executing step comprising dividing at least one subproblem into parts and assigning at least one part of the divided subproblem to a different processor if said evaluating step determines that the subproblems are otherwise incapable of being assigned to the plurality of processors in a balanced manner.

30. A method according to claim 29 wherein executing a subproblem on a respective processor comprises:

constructing a Lagrangian dual function representative of the respective subproblem; and

maximizing the Lagrangian dual function.

31. A method according to claim 30 wherein each potential association has an initial cost, wherein constructing the Lagrangian dual function comprises determining a dual variable for each measurement and determining an adjusted cost for each potential association based upon the initial cost and the dual variable for each measurement that is associated to create the potential association, and wherein said assigning step comprises assigning the determination of the adjusted cost to a different processor.

32. A method according to claim 29 wherein said evaluating step comprises evaluating at least one of the number of associations and the number of measurements included within the subproblem to determine the size of the subproblem.

33. A method according to claim 29 wherein said evaluating step comprises:

determining a maximum variation between the cumulative size of the subproblems assigned to the respective processors; and

determining that the subproblems are capable of being assigned to the plurality of processors in a balanced manner if the maximum variation is less than a predetermined threshold.

34. A computer program product for constructing a plurality of updated tracks based upon associations of a plurality of measurements in a parallel computing architecture having a plurality of processors, wherein the computer program product comprises a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising:

first computer-readable program code means for decomposing data representative of the plurality of measurements into a plurality of subproblems having respective sizes;

second computer-readable program code means for evaluating the sizes of the subproblems to determine if the subproblems are capable of being assigned to the plurality of processors in a balanced manner;

third computer-readable program code means for assigning the plurality of subproblems to respective ones of the plurality of processors; and

fourth computer-readable program code means for executing the plurality of subproblems in parallel on the respective processors to determine the associations of the plurality of measurements of each subproblem in order to define the plurality of updated tracks, said fourth computer-readable program code means for comprising computer-readable program code means for dividing at least one subproblem into parts and assigning at least one part of the divided subproblem to a different processor if said second computer-readable program code means for determines that the subproblems are otherwise incapable of being assigned to the plurality of processors in a balanced manner.

35. A computer program product according to claim 34 wherein said fourth computer-readable program code means comprises:

computer-readable program code means for constructing a Lagrangian dual function representative of a respective subproblem; and

computer-readable program code means for maximizing the Lagrangian dual function.

36. A computer program product according to claim 35 wherein each potential association has an initial cost, wherein said computer-readable program code means for constructing the Lagrangian dual function comprises computer-readable program code means for determining a dual variable for each measurement and determining an adjusted cost for each potential association based upon the initial cost and the dual variable for each measurement that is associated to create the potential association, and wherein said computer-readable program code means for assigning at least one part of the divided subproblem to a different processor comprises computer-readable program code means for assigning the determination of the adjusted cost to a different processor.

37. A computer program product according to claim 34 wherein said second computer-readable program code means comprises computer-readable program code means for evaluating at least one of the number of associations and the number of measurements included within the subproblem to determine the size of the subproblem.

38. A computer program product according to claim 34 wherein said second computer-readable program code means comprises:

computer-readable program code means for determining a maximum variation between the cumulative size of the subproblems assigned to the respective processors; and

computer-readable program code means for determining that the subproblems are capable of being assigned to the plurality of processors in a balanced manner if the maximum variation is less than a predetermined threshold.

39. A system for constructing a plurality of updated tracks based upon associations of a plurality of measurements of a plurality of objects, wherein the measurements are subject to a plurality of constraints, and wherein the system comprises:

at least one sensor for obtaining the measurements of the plurality of objects;

a processing architecture, responsive to said at least one sensor, comprising;

means for relaxing each of the constraints by providing a dual variable for each constraint;

means for constructing a Lagrangian dual function that at least partially depends upon the dual variable for each constraint and a cost associated with each potential association;

means for determining a solution of a Lagrangian dual problem by determining an associated value for each dual variable based upon an evaluation of the Lagrangian dual function; and

means for determining the associations that define the plurality of updated tracks based at least partially upon the value determined for the dual variable associated with each constraint.

40. A system according to claim 39 wherein said means for determining the solution of the Lagrangian dual function comprises means for maximizing the Lagrangian dual function.

41. A system according to claim 39 further comprising means for determining if a value of the Lagrangian dual function is acceptable prior to determining the associations that define the plurality of updated tracks such that the construction of the Lagrangian dual function and the evaluation of the Lagrangian dual function are repeated if the prior value of the Lagrangian dual function is unacceptable.

42. A system according to claim 39 wherein means for relaxing each of the constraints comprises means for providing an initial value for the dual variable for each constraint, and wherein said means for determining the solution of the Lagrangian dual problem comprises means for determining an updated value for each dual variable in accordance with the solution of the Lagrangian dual problem.

43. A system for solving a combinatorial optimization problem to define a plurality of associations of measurements taken of a plurality of objects, wherein the measurements are subject to a plurality of constraints, and wherein the system comprises:

means for relaxing each of the constraints by providing a dual variable for each constraint;

means for constructing a Lagrangian dual function that at least partially depends upon the dual variable for each constraint and a cost associated with each potential association;

means for determining a solution of a Lagrangian dual problem by determining an associated value for each dual variable based upon an evaluation of the Lagrangian dual function; and

means for determining the associations of measurements-taken of the plurality of objects based at least partially upon the value determined for the dual variable associated with each constraint.

44. A system according to claim 43 wherein said means for determining the solution of the Lagrangian dual function comprises means for maximizing the Lagrangian dual function.

45. A system according to claim 43 further comprising means for determining if a value of the Lagrangian dual function is acceptable prior to determining the associations of measurements taken of the plurality of objects such that the construction of the Lagrangian dual function and the evaluation of the Lagrangian dual-function are repeated if the prior value of the Lagrangian dual function is unacceptable.

46. A system according to claim 43 wherein means for relaxing each of the constraints comprises means for providing an initial value for the dual variable for each constraint, and wherein said means for determining the solution of the Lagrangian dual problem comprises means for determining an updated value for each dual variable in accordance with the solution of the Lagrangian dual problem.

47. In a tracking system having at least one sensor for providing scan data from a plurality of scans:

a set partitioning problem solver resident on a processor in communication with the sensor for operating on the scan data to define associations in the data from scan to scan in a sliding window architecture using a Lagrangian Relaxation combinatorial optimization approximation, including relaxation of all constraints in the Lagrangian Relaxation approximation.

48. A tracking system according to claim 47 wherein the solver solves set partitioning problems.

49. A tracking system according to claim 47 wherein the processor includes parallel processors and the solver distributes its workload to the processors according to a combination of both course grain and fine grain techniques.

50. The tracking system according to claim 47 wherein said sensor provides data in an asynchronous manner.