Multiple-hypothesis-tracking-for-multiple-target-t

MultipleHypothesisTrackingForMultipleTargetTrackingSAMUELS.BLACKMANRaytheonMultiplehypothesistracking(MHT)isgenerallyacceptedasthepreferredmethodforsolvingthedataassociationprobleminmodernmultipletargettracking(MTT)systems.ThispapersummarizesthemotivationsforMHT,thebasicprinciplesbehindMHTandthealternativeimplementationsincommonuse.ItdiscussesthemannerinwhichthemultipledataassociationhypothesesformedbyMHTcanbecombinedwithmultiplefiltermodels,suchasusedbytheinteractingmultiplemodel(IMM)method.AnoverviewofthestudiesthatshowtheadvantagesofMHTovertheconventionalsinglehypothesisapproachisgiven.ImportantcurrentapplicationsandareasoffutureresearchanddevelopmentforMHTarediscussed.ManuscriptreceivedFebruary22,2003;revisedApril27,2003.Author’scurrentaddress:Raytheon,RE/R07/P572,POBox920,ElSegundo,CA90245,E-mail:([e-mail]).0018-9251/04/$17.00c°2004IEEEI.INTRODUCTIONTargettrackingisanessentialrequirementforsurveillancesystemsemployingoneormoresensors,togetherwithcomputersubsystems,tointerprettheenvironment.Typicalsensorsystems,suchasradar,infrared(IR),andsonar,reportmeasurementsfromdiversesources:targetsofinterest,physicalbackgroundobjectssuchasclutter,orinternalerrorsourcessuchasthermalnoise.Thetargettrackingobjectiveistocollectsensordatafromafieldofview(FOV)containingoneormorepotentialtargetsofinterestandtothenpartitionthesensordataintosetsofobservations,ortracksthatareproducedbythesameobject(ortarget).Notethatthetermtargetisusedinageneralsense.Oncetracksareformedandconfirmed(sothatbackgroundandotherfalsetargetsarereduced),thenumberoftargetsofinterestcanbeestimatedandquantities,suchastargetvelocity,futurepredictedposition,andtargetclassificationcharacteristics,canbecomputedforeachtrack.Sincemostsurveillancesystemsmusttrackmultipletargets,multipletargettracking(MTT)isthemostimportanttrackingapplication.Fig.1,takenfrom[1],showsthebasicelementsofatypicalMTTsystem.Assumethattrackshavebeenformedfrompreviousdataandanewsetofinputobservationsbecomesavailable.Ingeneralobservationscanbereceivedatregularintervalsoftime(scansordataframes)ortheycanoccurirregularlyintime.Here,wewillusethegeneraltermscantorefertoanysetofinputmeasurementsthatwereallproducedatthesametime.Then,theinputobservationsareconsideredforinclusioninexistingtracksandforinitiationofnewtracks.First,agate,baseduponthemaximumacceptablemeasurementplustrackingpredictionerrormagnitudes,isplacedaroundthepredictedtrack.Onlythoseobservationsthatarewithinthetrackgateareconsideredforupdateofthetrack.Whencloselyspacedtargetsproducecloselyspacedobservationstherewillbeconflictssuchthattheremaybemultipleobservationswithinatrack’sgateandanobservationmaybewithinthegatesofmultipletracks.ThisishandledbytheObservation-to-TrackAssociationandTrackMaintenancefunctions.Fig.2,alsotakenfrom[1],showsatypicalconflictsituationinwhichtrackgatesareplacedaroundthepredictedpositions(P1,P2)oftwotracks,andthreeobservations(O1,O2,O3)satisfythegatesofeither(orboth)ofthetracks.Theconventionaldataassociationmethodisdenotedtheglobalnearestneighbor(GNN)approach.Itfindsthebest(mostlikely)assignmentofinputobservationstoexistingtracks,whichforexample,wouldprobablybeO1totrack1andO2totrack2.Thetermglobalisusedtorefertothefactthattheassignmentismadeconsideringallpossible(withingates)associationsIEEEA&ESYSTEMSMAGAZINEVOL.19,NO.1JANUARY2004PART2:TUTORIALS–BLACKMAN5Fig.1.BasicelementsofaconventionalMTTsystem.Fig.2.Exampleoftypicaldataassociationconflictsituation.undertheconstraintthatanobservationcanbeassociatedwithatmostonetrack.ThisdistinguishesGNNfromthearchaic(butapparentlystillusedinsomesystems)nearestneighbor(NN)approachinwhichatrackisupdatedwiththeclosestobservationevenifthatobservationmayalsobeusedbyanothertrack.Onlythosetracksthatareincludedinthebestassignmentarekept.Unassignedobservations,inthiscaseO3,initiatenewtracks.Trackconfirmationanddeletionaretypicallydeterminedbyrules,suchas3detectionsin4framesofdataforconfirmationandNconsecutivemisses(typicallyN=4to7)fortrackdeletion.InherentinthestandardGNNassignmentistheassumptionthatanobservationwasproducedbyasingletarget.Tracksthatdonotshareanycommonobservationswillbedefinedtobecompatible.Thus,onlycompatibletrackscanappearinthesameassignmentsolution.Relaxationofthisconstrainttoallowfortheprovisionofunresolvedtargetsthatproduceasinglemeasurementwillbediscussedlater.Onceobservationsareassignedtotracks,thesetracksareupdatedduringthefilteringprocess.ConventionalsystemstypicallyuseasingleKalmanfilter.However,asdiscussedbelow,modernsystemsshouldusetheinteractingmultiplemodel(IMM)approachinwhichseveralKalmanfilters,tunedtodifferenttypesoftargetmaneuver,areruninparallel[1,2].Finally,alltracksarepredictedtothetimeofthenextsetofmeasurements.TheKalmanfilterpredictioncovariancesprovidetheuncertainty,inthepredictedstateestimate,thatisrequiredforthegatingandassociationprocesses.TheGNNapproach,whichonlyconsidersthesinglemostlikelyhypothesisfortrackupdateandnewtrackinitiation,onlyworkswellinthecaseofwidelyspacedtargets,accuratemeasurements,andfewfalsealarm