Multitarget-multisensor data association using the tree-reweighted max-product algorithm

Multitarget-MultisensorDataAsso ciationUsingtheTree-ReweightedMax-Pro ductAlgorithmLei Cheny,MartinJ.Wainwrightz,MujdatCetinAlan S.WillskyyLab oratory for Information andDecision Systems,EECS,MIT,Cambridge, MAzEECS,Univ.of California, Berkeley,CAABSTRACTDataasso ciationisafundamentalprobleminmultitarget-multisensortracking.Itentailsselectingthemostprobable asso ciation b etween sensor measurements and target tracks from a very large set of p ossibilities.WithNsensors andntargets in the detection range of each sensor, even with p erfect detection there are (!)Ndi erentcon gurations which renders infeasible a solution by direct computation even in mo destly-sized applications.Wedescrib e an iterative metho d for solving the optimal data asso ciation problem in a distributed fashion; the workexploits the framework of graphical mo dels, whichare a powerful to ol for enco ding the statistical dep endenciesof asetof random variables andare widely usedin manyapplications (e.g.,computer vision,error-correctingco des).Our basic idea is to treat the measurement assignment for each sensor as a random variable, whichis inturn represented as a no de in an underlying graph.Neighb oring no des are coupled by the targets visible to b othsensors.Thus we transform the data asso ciation problem to that of computing the maximumaposteriori(MAP)con guration in a graphical mo del to which ecienttechniques (e.g., the max-pro duct/min-sum algorithm) canb e applied.We use a tree-reweighted version of the usual max-pro duct algorithm that either outputs the MAPdata asso ciation, or acknowledges failure.For acyclic graphs, this message-passing algorithm can solve the dataasso ciation problem directly and recursively with complexityO(n!)2N.On graphs with cycles, the algorithmmayrequire more iterations toconverge,andneednotoutputanunambiguous assignment.However, forthedata asso ciation problems considered here, the coupling matrices involved in computations are inherently of lowrank,andexp erimentsshowthatthealgorithm converges very fast ndsMAPcon gurations inthiscase.Keywords:data asso ciation, max-pro duct/min-sum algorithm, multitarget-multisensor tracking, Markovran-dom elds, graphical mo dels1. INTRODUCTIONData asso ciation, with the goal of partitioning observations to match up with a particular origin, is a fundamentalproblemofmultipletargettracking.1, 2Thesp eci csthedataasso ciationvaryaccordingtodi erenttrackingapproachesandthemo dalitiesofsensorsbeingused.However,commonasp ect of the problem is to identify a pair of p oints, one from eachof two random p oint sets, that share the sameorigin.3The p oints in the rst setXprovide the prior knowledge ab out the distribution of target states that weare interested in, and are usually obtained from the prediction step of the tracking algorithm.ThusXis calledthe prediction set.The second setZis the measurement set and consists of noisy measurements of the targetstates pro duced by the sensors.The corresp ondence b etween p oints inXand p oinZis unknown and needsto b e resolved.The central task of data asso ciation is to gure out the correct mapping relationship based onthe observationZ=, sub ject to the constraints that eachz2is assigned to at most onexX, and eacgets no more than onez.Fig. 1(a) shows a trivial example with one sensor and two measurements for the threeFurther author information:(Send corresp ondence to Lei Chen)Lei Chen:E-mail:lchen@mit.edu, Address:LIDS, MIT, 77 Mass. Ave, Ro om 35-439, Cambridge, MA 02139Martin J. Wainwright:E-mail:martinw@eecs.b erkeley.edu, Address:So da Hall 485, EECS Dept., Univ. of California atBerkeley, Berk, CA 94720Mujdat Cetin:E-mail:mcetin@mit.eduAlan S. Willsky:E-mail:willsky@mit.edu