粒子滤波的原理和实现-渥太华大学-Theory-and-Implementation-of-Particle-FiltersPPT课件

12Nov2004,.,1,TheoryandImplementationofParticleFilters,MiodragBolicAssistantProfessorSchoolofInformationTechnologyandEngineeringUniversityofOttawambolicsite.uottawa.ca,12Nov2004,.,2,Bigpicture,Goal:EstimateastochasticprocessgivensomenoisyobservationsConcepts:BayesianfilteringMonteCarlosampling,sensor,t,Observedsignal1,t,Observedsignal2,ParticleFilter,t,Estimation,12Nov2004,.,3,Particlefilteringoperations,ParticlefilterisatechniqueforimplementingrecursiveBayesianfilterbyMonteCarlosamplingTheidea:representtheposteriordensitybyasetofrandomparticleswithassociatedweights.Computeestimatesbasedonthesesamplesandweights,Samplespace,Posteriordensity,12Nov2004,.,4,Outline,MotivationApplicationsFundamentalconceptsSampleimportanceresamplingAdvantagesanddisadvantagesImplementationofparticlefiltersinhardware,12Nov2004,.,5,Motivation,ThetrendofaddressingcomplexproblemscontinuesLargenumberofapplicationsrequireevaluationofintegralsNon-linearmodelsNon-Gaussiannoise,12Nov2004,.,6,SequentialMonteCarloTechniques,BootstrapfilteringThecondensationalgorithmParticlefilteringInteractingparticleapproximationsSurvivalofthefittest,12Nov2004,.,7,History,FirstattemptssimulationsofgrowingpolymersM.N.RosenbluthandA.W.Rosenbluth,“MonteCarlocalculationoftheaverageextensionofmolecularchains,”JournalofChemicalPhysics,vol.23,no.2,pp.356359,1956.Firstapplicationinsignalprocessing-1993N.J.Gordon,D.J.Salmond,andA.F.M.Smith,“Novelapproachtononlinear/non-GaussianBayesianstateestimation,”IEEProceedings-F,vol.140,no.2,pp.107113,1993.BooksA.Doucet,N.deFreitas,andN.Gordon,Eds.,SequentialMonteCarloMethodsinPractice,Springer,2001.B.Ristic,S.Arulampalam,N.Gordon,BeyondtheKalmanFilter:ParticleFiltersforTrackingApplications,ArtechHousePublishers,2004.TutorialsM.S.Arulampalam,S.Maskell,N.Gordon,andT.Clapp,“Atutorialonparticlefiltersforonlinenonlinear/non-gaussianBayesiantracking,”IEEETransactionsonSignalProcessing,vol.50,no.2,pp.174188,2002.,12Nov2004,.,8,Outline,MotivationApplicationsFundamentalconceptsSampleimportanceresamplingAdvantagesanddisadvantagesImplementationofparticlefiltersinhardware,12Nov2004,.,9,Applications,SignalprocessingImageprocessingandsegmentationModelselectionTrackingandnavigationCommunicationsChannelestimationBlindequalizationPositioninginwirelessnetworks,Otherapplications1)Biology&BiochemistryChemistryEconomics&BusinessGeosciencesImmunologyMaterialsSciencePharmacology&ToxicologyPsychiatry/PsychologySocialSciences,A.Doucet,S.J.Godsill,C.Andrieu,OnSequentialMonteCarloSamplingMethodsforBayesianFiltering,StatisticsandComputing,vol.10,no.3,pp.197-208,2000,12Nov2004,.,10,Bearings-onlytracking,Theaimistofindthepositionandvelocityofthetrackedobject.Themeasurementstakenbythesensorarethebearingsorangleswithrespecttothesensor.Initialpositionandvelocityareapproximatelyknown.SystemandobservationnoisesareGaussian.Usuallyusedwithapassivesonar.,12Nov2004,.,11,Bearings-onlytracking,States:positionandvelocityxk=xk,Vxk,yk,VykTObservations:anglezk,Observationequation:zk=atan(yk/xk)+vkStateequation:,xk=Fxk-1+Guk,12Nov2004,.,12,Bearings-onlytracking,BlueTruetrajectoryRedEstimates,12Nov2004,.,13,Carpositioning,Observationsarethevelocityandturninformation1)AcarisequippedwithanelectronicroadmapTheinitialpositionofacarisavailablewith1kmaccuracyInthebeginning,theparticlesarespreadevenlyontheroadsAsthecarismovingtheparticlesconcentrateatoneplace,1)Gustafssonetal.,“ParticleFiltersforPositioning,Navigation,andTracking,”IEEETransactionsonSP,2002,12Nov2004,.,14,DetectionofdatatransmittedoverunknownRayleighfadingchannelThetemporalcorrelationinthechannelismodeledusingAR(r)processAtanyinstantoftimet,theunknownsare,and,andourmainobjectiveistodetectthetransmittedsymbolsequentially,Detectionoverflat-fadingchannels,12Nov2004,.,15,Outline,MotivationApplicationsFundamentalconceptsSampleimportanceresamplingAdvantagesanddisadvantagesImplementationofparticlefiltersinhardware,12Nov2004,.,16,Fundamentalconcepts,StatespacerepresentationBayesianfilteringMonte-CarlosamplingImportancesampling,Statespacemodel,Solution,Problem,Estimateposterior,Difficulttodrawsamples,Integralsarenottractable,MonteCarloSampling,ImportanceSampling,12Nov2004,.,17,Representationofdynamicsystems,ThestatesequenceisaMarkovrandomprocessStateequation:xk=fx(xk-1,uk)xkstatevectorattimeinstantkfxstatetransitionfunctionukprocessnoisewithknowndistributionObservationequation:zk=fz(xk,vk)zkobservationsattimeinstantkfxobservationfunctionvkobservationnoisewithknowndistribution,12Nov2004,.,18,Representationofdynamicsystems,Thealternativerepresentationofdynamicsystemisbydensities.Stateequation:p(xk|xk-1)Observationequation:p(zk|xk)Theformofdensitiesdependson:Functionsfx()andfz()Densitiesofukandvk,12Nov2004,.,19,BayesianFiltering,Theobjectiveistoestimateunknownstatexk,basedonasequenceofobservationszk,k=0,1,.ObjectiveinBayesianapproachFindposteriordistributionp(x0:k|z1:k)Byknowingposteriordistributionallkindsofestimatescanbecomputed:,12Nov2004,.,20,Updateandpropagatesteps,k=0BayestheoremFilteringdensity:Predictivedensity:,Propagate,Update,Propagate,Propagate,Update,Update,p(x0),p(x0|z0),p(x1|z1),p(x1|z0),p(x2|z1),p(xk|zk-1),p(xk|zk),p(xk+1|zk),z0,z1,z2,12Nov2004,.,21,Updateandpropagatesteps,k0DerivationisbasedonBayestheoremandMarkovpropertyFilteringdensity:Predictivedensity:,12Nov2004,.,22,Meaningofthedensities,Bearings-onlytrackingproblemp(xk|z1:k)posteriorWhatistheprobabilitythattheobjectisatthelocationxkforallpossiblelocationsxkifthehistoryofmeasurementsisz1:k?p(xk|xk-1)priorThemotionmodelwherewilltheobjectbeattimeinstantkgiventhatitwaspreviouslyatxk-1?p(zk|xk)likelihoodThelikelihoodofmakingtheobservationzkgiventhattheobjectisatthelocationxk.,12Nov2004,.,23,Bayesianfiltering-problems,OptimalsolutioninthesenseofcomputingposteriorThesolutionisconceptualbecauseintegralsarenottractableClosedformsolutionsarepossibleinasmallnumberofsituationsGaussiannoiseprocessandlinearstatespacemodelOptimalestimationusingtheKalmanfilterIdea:useMonteCarlotechniques,12Nov2004,.,24,MonteCarlomethod,Example:EstimatethevarianceofazeromeanGaussianprocessMonteCarloapproach:SimulateMrandomvariablesfromaGaussiandistributionComputetheaverage,12Nov2004,.,25,Importancesampling,ClassicalMonteCarlointegrationDifficulttodrawsamplesfromthedesireddistributionImportancesamplingsolution:Drawsamplesfromanother(proposal)distributionWeightthemaccordingtohowtheyfittheoriginaldistributionFreetochoosetheproposaldensityImportant:ItshouldbeeasytosamplefromtheproposaldensityProposaldensityshouldresembletheoriginaldensityascloselyaspossible,12Nov2004,.,26,Importancesampling,EvaluationofintegralsMonteCarloapproach:SimulateMrandomvariablesfromproposaldensity(x)Computetheaverage,12Nov2004,.,27,Outline,MotivationApplicationsFundamentalconceptsSampleimportanceresamplingAdvantagesanddisadvantagesImplementationofparticlefiltersinhardware,12Nov2004,.,28,Sequentialimportancesampling,Idea:UpdatefilteringdensityusingBayesianfilteringComputeintegralsusingimportancesamplingThefilteringdensityp(xk|z1:k)isrepresentedusingparticlesandtheirweightsComputeweightsusing:,x,Posterior,12Nov2004,.,29,Sequentialimportancesampling,LettheproposaldensitybeequaltothepriorParticlefilteringstepsform=1,M:1.Particlegeneration2a.Weightcomputation2b.Weightnormalization3.Estimatecomputation,12Nov2004,.,30,Resampling,Problems:WeightDegenerationWastageofcomputationalresourcesSolutionRESAMPLINGReplicateparticlesinproportiontotheirweightsDoneagainbyrandomsampling,12Nov2004,.,31,Resampling,x,12Nov2004,.,32,Particlefilteringalgorithm,Initializeparticles,1,2,M,.,Particlegeneration,Newobservation,Exit,Normalizeweights,1,2,M,.,Weigthcomputation,Resampling,yes,no,12Nov2004,.,33,Bearings-onlytrackingexample,MODELStates:xk=xk,Vxk,yk,VykTObservations:zkNoiseStateequation:xk=Fxk-1+GukObservationequation:zk=atan(yk/xk)+vk,ALGORITHMParticlegenerationGenerateMrandomnumbersParticlecomputationWeightcomputationWeightnormalizationResamplingComputationoftheestimates,12Nov2004,.,34,Bearings-OnlyTrackingExample,12Nov2004,.,35,Bearings-OnlyTrackingExample,12Nov2004,.,36,Bearings-OnlyTrackingExample,12Nov2004,.,37,Generalparticlefilter,Iftheproposalisapriordensity,thentherecanbeapooroverlapbetweenthepriorandposteriorIdea:includetheobservationsintotheproposaldensityThisproposaldensityminimize,12Nov2004,.,38,Outline,MotivationApplicationsFundamentalconceptsSampleimportanceresamplingAdvantagesanddisadvantagesImplementationofparticlefiltersinhardware,12Nov2004,.,39,Advantagesofparticlefilters,AbilitytorepresentarbitrarydensitiesAdaptivefocusingonprobableregionsofstate-spaceDealingwithnon-GaussiannoiseTheframeworkallowsforincludingmultiplemodels(trackingmaneuveringtargets),12Nov2004,.,40,Disadvantagesofparticlefilters,HighcomputationalcomplexityItisdifficulttodetermineoptimalnumberofparticlesNumberofparticlesincreasewithincreasingmodeldimensionPotentialproblems:degeneracyandlossofdiversityThechoiceofimportancedensityiscrucial,12Nov2004,.,41,Variations,Rao-Blackwellization:SomecomponentsofthemodelmayhavelineardynamicsandcanbewellestimatedusingaconventionalKalmanfilter.TheKalmanfilteriscombinedwithaparticlefiltertoreducethenumberofparticlesneededtoobtainagivenlevelofperformance.,12Nov2004,.,42,Variations,GaussianparticlefiltersApproximatethepredictiveandfilteringdensitywithGaussiansMomentsofthesedensitiesarecomputedfromtheparticlesAdvantage:thereisnoneedforresamplingRestriction:filteringandpredictivedensitiesareunimodal,12Nov2004,.,43,Outline,MotivationApplicationsFundamentalconceptsSampleimportanceresamplingAdvantagesanddisadvantagesImplementationofparticlefiltersinhardware,12Nov2004,.,44,Challengesandresults,ChallengesReducingcomputationalcomplexityRandomnessdifficulttoexploitregularstructuresinVLSIExploitingtemporalandspatialconcurrencyResultsNewresamplingalgorithmssuitableforhardwareimplementationFastparticlefilteringalgorithmsthatdonotusememoriesFirstdistributedalgorithmsandarchitecturesforparticlefilters,12Nov2004,.,45,Complexity,4Mrandomnumbergenerations,Propagationoftheparticles,Mexponentialandarctangentfunctions,Bearings-onlytrackingproblemNumberofparticlesM=1000,Complexity,Initializeparticles,1,2,M,.,Particlegeneration,Newobservation,Exit,Normalizeweights,1,2,M,.,Weigthcomputation,Resampling,yes,no,12Nov2004,.,46,Mappingtotheparallelarchitecture,ProcessingElement1,ProcessingElement4,ProcessingElement2,CentralUnit,Start,Newobservation,Exit,2,.,Particlegeneration,Resampling,2,.,Weightcomputation,Propagationofparticles,ProcessingElement3,Processingelements(PE)ParticlegenerationWeightCalculation,CentralUnitAlgorithmforparticlepropagationResampling,12Nov2004,.,47,Propagationofparticles,ProcessingElement1,ProcessingElement4,ProcessingElement2,CentralUnit,ProcessingElement3,Disadvantagesoftheparticle