Communications: directive radio wave systems and devices (e.g. – Return signal controls radar system – Receiver
Patent
1995-03-14
1996-07-16
Hellner, Mark
Communications: directive radio wave systems and devices (e.g.,
Return signal controls radar system
Receiver
342 90, G01S 1300
Patent
active
055371191
ABSTRACT:
A method and system for real-time tracking of objects is disclosed. A region is repeatedly scanned providing a plurality of images or data sets having points corresponding to objects in the region to be tracked. Given a previously determined track for each object in the region, an M-dimensional combinatorial optimization assignment problem is formulated using the points from M-1 of the images or data sets, wherein each point is preferably used in extending at most one track. The M-dimensional problem is subsequently solved for an optimal or near-optimal assignment of the points to the tracks, extending the tracking of the objects so that a response to each object can be initiated by the system in real-time. Speed and accuracy is provided by an iterative Lagrangian Relaxation technique wherein a plurality of constraint dimensions are relaxed simultaneously to yield a reduced dimensional optimization problem whose solution is used to formulate an assignment problem of dimensionality less than M. The iterative reducing of dimensions terminates when exact solutions are determined for two-dimensional cases. A recovery procedure is used for determining a higher dimensional assignment problem solution from a problem having one less dimension. The procedure is useful when the reduced dimensional optimizational problem has two constraint dimensions.
REFERENCES:
patent: 3849779 (1974-11-01), Boyd
patent: 3869601 (1975-03-01), Metcalf
patent: 4042924 (1977-08-01), Evans et al.
patent: 4768034 (1988-08-01), Preikschat et al.
patent: 4823272 (1989-04-01), Inselberg
patent: 4839658 (1989-06-01), Kathol et al.
patent: 4975707 (1990-12-01), Smith
patent: 5058024 (1991-10-01), Inselberg
patent: 5138321 (1992-08-01), Hammer
patent: 5170440 (1992-12-01), Cox
patent: 5406289 (1995-04-01), Barker et al.
W. P. Pierskalla, The multi-dimensional assignment problem, Operations Research, 16 (1968), pp. 422-431.
D. B. Reid, An algorithm for tracking multiple targets, IEEE Transaction On Automatic Control, vol. AC-24, No. 6, Dec. 1979, pp. 843-854.
P. Wolfe, Finding the nearest point in a polytope, Mathematical Programming, 11 (1976), pp. 128-149.
A. M. Frieze, A bilinear programming formulation of the 3-dimensional assignment problem, Mathematical Programming, 7 (1974), pp. 376-379.
A. M. Frieze and J. Yadegar, An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice, Journal of the Operational Research Society, 32 (1981), pp. 989-995.
M. Held and R. M. Karp, The traveling salesman problem and minimal trees, Part II, Mathematical Programming, 1 (1971), pp. 6-25.
C. L. Morefield, Application of 0-1 integer programming to multitarget tracking problems, IEEE Transactions on Automatic Control, vol. AC-22, No. 3 Jun. 1977 pp. 302-312.
Y. Bar-Shalom, Tracking methods in a multitarget environment, IEEE Transactions on Automatic Control, vol. AC-23, No. Aug. 1978, pp. 618-626.
C. Lemarechal, Bundle methods in nonsmooth optimization, in C. Lemarechal and R. Mifflin, eds. Nonsmooth Optimization ILASA Proceedings 3, Pergamon, Oxcord, 1978, pp. 79-102.
R. W. Sittler, An Optimal data association problem in surveillance theory, IEEE Transactions on Military Electronics, Apr. 1964, pp. 125-139.
P. Wolfe, A method of conjugate subgradients for minimizing nondifferentiable functions, Mathematical Programming Study, 3 (1975), pp. 147-173.
A. M. Frieze, A bilinear programming formulation of the 3-dimensional assignment problem, Mathematical Programming, 7, pp. 376-379, 1974.
Somnath D., A new algorithm for the generalized multidimensional assignment problem, IEEE International Conf. on Systems, Man and Cybernetics, Chicago 92.
Danchick, R. A. Multisensor-Multitarget Data Association Algorithm for Heterogeneous Sensors, IEEE Transactions On Aerospace and Electronic Systems vol. 29, No. 2, Apr. 1993.
Somnath Deb, A S-dimenisonal assignment algorithm for track initiation, IEEE Systems Conf. Kobe Japan Sep. 1992.
Pattipati, A new relaxation algorithm and Passive Sensor Data Association, IEEE Transactions on Automatic Control vol. 37, No. 2, Feb. 1992 Computer Printout.
Rijavec, Nenad Dissertation, A Lagrangian Relaxation Algorithm For Some Multidimensional Assignment Problems, Submitted to Colorado State University, 1992.
A. B. Poore and N. Rijavec, Partitioning Multiple Data Sets: Multidimensional Assignments and Lagrangian Relaxation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, 1994, pp. 317-342.
Poore, A. B., Multidimensional Assignment Formulation of Data Association Problems Arising from Multitarget and Multisensor Tracking, Computational Optimization and Applications, 3, (1994), pp. 27-57.
A. B. Poore and N. Rijavec, A Numerical Study of Some Data Association Problems Arising in Multitarget Tracking, Large Scale Optimization: State of the Art, 1994, pp. 339-361.
A. B. Poore and N. Rijavec, Three Algorithms for a Class of Multidimensional Assignment Problems, Journal of Computing and Information Technology-CIT 2, No. 1, 1994, pp. 25-37.
A. B. Poore and N. Rijavec, A Relaxation Algorithm for Multidimensional Assignments, Proceedings of the Third Conference on Operations Research, Croatian Operational Research Society, Oct. 1993, pp. 107-116.
A. B. Poore and N. Rijavec, A New Class of Methods for Solving Data Association Problems Arising from Multitarget Tracking, Proceedings of the 1991 American Automatic Control Conference, vol. 3, pp. 2303-2304.
A. B. Poore and N. Rijavec, Multitarget Tracking and Multidimensional Assignment Problems, Proceedings of the 1991 SPIE Conference on Signal and Data Processing of Small Targets 1991, vol. 1481, 1991, pp. 345-356.
A. B. Poore and N. Rijavec, The Data Association Problem in Multitarget Tracking and Multidimensional Assignment Problems, the Proceedings of the SDI Panels on Tracking, Institute for Defense Analyses, Issue No. Feb. 1991, pp. 3-29, to 3-51.
A. B. Poore and N. Rijavec, Multitarget Tracking, Multidimensional Assignment Problems, and Lagrangian Relaxation, Proceedings of the SDI Panels on Tracking, Institute for Defense Analyses, Issue No. Feb. 1991, pp. 3-51, to 3-74.
A. B. Poore, N. Rijavec and T. Barker, Data association for track initiation and extension using multiscan windows, Signal and Data Processing of Small Targets 1992, Proc. SPIE 1698, 1992, pp. 432-441.
A. B. Poore and N. Rijavec, A Lagrangian Relaxation Algorithm for Multi-dimensional Assignment Problems Arising from Multitarget Tracking, SIAM Journal on Optimization, vol. 3, No. 3, 1993, pp. 544-563.
A. B. Poore, N. Rijavec, M. Liggins and V. Vannicola, Data association problems posed as multidimensional assignment problems; problem formulation, Signal and Data Processing of Small Targets 1954, Proc. SPIE, 1993, pp. 552-561.
A. B. Poore, N. Rijavec, T. Barker and M. Munger, Data association problems posed as multidimensional assignment problems: numerical simultions, Signal and Data Processing of Small Targets 1954, Proc. SPIE, 1993, pp. 564-573.
A. B. Poore, N. Rijavec, T. Barker and N. Munger, Data association problems posed as multidimensional assignment problems; algorithm development, Signal Processing, Sensor Fusion, and Target Recognition II 1955, Proc. SPIE, 1993, pp. 172-183.
A. B. Poore and N. Rijavec, A Comparison of Several Algorithms for Multidimensional Assignments, Proceedings of the 15th International Conference on Information Technology Interfaces, University Computing Centre, Croatia, Jun. 1993, pp. 413-418.
Colorado State University Research Foundation
Hellner Mark
LandOfFree
Method and system for tracking multiple regional objects by mult 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 regional objects by mult, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for tracking multiple regional objects by mult will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1787703