A statistical approach to simultaneous mapping and

arXiv:0708.4337v1[stat.AP]31Aug2007TheAnnalsofAppliedStatistics2007,Vol.1,No.1,66–84DOI:10.1214/07-AOAS115cInstituteofMathematicalStatistics,2007ASTATISTICALAPPROACHTOSIMULTANEOUSMAPPINGANDLOCALIZATIONFORMOBILEROBOTS1ByAnitaAraneda1,StephenE.Fienberg2andAlvaroSoto1PontificiaUniversidadCat´olicadeChile,CarnegieMellonUniversityandPontificiaUniversidadCat´olicadeChileMobilerobotsrequirebasicinformationtonavigatethroughanenvironment:theyneedtoknowwheretheyare(localization)andtheyneedtoknowwheretheyaregoing.Forthelatter,robotsneedamapoftheenvironment.Usingsensorsofavarietyofforms,robotsgatherinformationastheymovethroughanenvironmentinordertobuildamap.Inthispaperwepresentanovelsamplingalgorithmtosolvingthesimultaneousmappingandlocalization(SLAM)probleminindoorenvironments.WeapproachtheproblemfromaBayesianstatisticsperspective.Thedatacorrespondtoasetofrangefinderandodometermeasurements,obtainedatdiscretetimeinstants.Wefocusontheestimationoftheposteriordistributionoverthespaceofpossiblemapsgiventhedata.Byexploitingdifferentfactorizationsofthisdistribution,wederivethreesamplingalgorithmsbasedonimportancesampling.WeillustratetheresultsofourapproachbytestingthealgorithmswithtworealdatasetsobtainedthroughrobotnavigationinsideofficebuildingsatCarnegieMellonUniversityandthePontificiaUniversidadCatolicadeChile.1.Introduction.Mobilerobotsrequirebasicinformationtonavigatethroughanenvironment:theyneedtoknowwheretheyare(localization)andtheyneedtoknowwheretheyaregoing.Forthelatter,robotsneedamapoftheenvironment.Usingsensorsofavarietyofforms,robotsgatherinformationastheymovethroughanenvironmentinordertobuildamap.Therearemanyalgorithmicapproachestodealwiththisproblem;forex-ample,seethediscussionin[4].InthispaperweexaminedatagatheredbyReceivedJanuary2007;revisedApril2007.1SupportedbyFondecytGrant1050653atthePontificiaUniversidadCat´olicadeChile.2SupportedinpartbyNSFGrantSES-9720374toCarnegieMellonUniversityandNSFGrantDMS-04-39734totheInstituteforMathematicsandItsApplicationattheUniversityofMinnesota.Supplementarymaterialavailabletofiltering,SLAM.ThisisanelectronicreprintoftheoriginalarticlepublishedbytheInstituteofMathematicalStatisticsinTheAnnalsofAppliedStatistics,2007,Vol.1,No.1,66–84.Thisreprintdiffersfromtheoriginalinpaginationandtypographicdetail.12A.ARANEDA,S.E.FIENBERGANDA.SOTOtwomobilerobots,executingatraversalthroughtwodifferentofficeenvi-ronments,usinganodometerandasimplesetoflaserreadingsfromsensors.Inthepast,theprocessingofsuchdatahasbenefitedenormouslyfromaprobabilisticapproachthatattemptstousethedatatoformestimatesanddensityfunctionsofthebasicquantitiesofinterest[4,10,24,26].Theliteratureon“probabilisticrobotics”hasfocusedheavilyontheprob-lemsoflocalization,knowingpreciselywheretherobotis,andofmappingtheenvironment.Theseareintertwined,thatis,tobuildamapofanenviron-ment,therobotneedstoknowthelocationsithasvisited,butknowingthelocationsrequireknowledgeofamap.Therefore,theprobabilisticroboticsprobleminvolvestheperformanceofthesedualtasksandisknownasSi-multaneousMappingandLocalization(SLAM)[16].ItisnaturaltothinkofaddressingSLAMusingaBayesianapproachwhichputsaposteriordistri-butionoverthespaceofallpossiblemapsandthenupdatesthedistributionusingtheinformationthattherobotacquiresasitmovesthroughtheenvi-ronment.ThisBayesiansolutioninsomesensemaximizestheinformationavailableforSLAM[5].MostoftheroboticsliteratureonSLAMutilizesavarietyofapproximationsthatallowforreal-timecalculationsandupdatingandthus,ofnecessity,simplifiesthisBayesianconceptualformulationoftheSLAMproblem.Ourfirstdatasetcomesfromanexperimentconductedwithamobilerobot,Pearl,atCarnegieMellonUniversityinWeanHall(seeFigure1).Ourseconddatasetcomesfromasecondrobot,thisonenavigatinginsidetheComputerScienceDepartmentatthePontificiaUniversidadCatolicadeChile.Bothdatasetsconsistofasetofnoisymeasurementsobtainedbyanodometerandalaserrangefindermountedontherobot.Odometerreadingsconveyinformationabouttherobot’srelativelocation.Theycorrespondtorotationalandtranslationalmeasuresoftherobotmovements.Laserread-ingsconveyinformationaboutthelocationoflandmarks,withrespecttotherobot’slocation.Theycorrespondtoasetofscalarquantitiesindicatingthedistancesfromtherobottothenearestobstacleinasetofpreviouslyspecifieddirections.Usingthistypeofdata,weproposeacompleteprobabilisticrepresentationoftheSLAMproblemandobtainaBayesiansolution.Weformalizetheproblemofmappingastheproblemoflearningtheposteriordistributionofthemapgiventhedata.Ourkeyideaisbasedonnotingthattheposteriordistributionofthemapisdeterminedbytheposteriorjointdistributionofthelocationsvisitedbytherobotandthedistancestotheobstaclesfromthoselocations.Wederiveexpressionsforthisposteriorjointdistributionoflocationsanddistancesandshowthatthereisnoclosedformforit.Byexploitingdifferentfactorizationsofthisdistribution,wederivethreesamplingalgorithmsbasedonimportancesampling.SLAMFORMOBILEROBOTS3Theoutlineofthepaperisasfollows.InSe