什么是occupancy-grid-map

MachinePerceptionandInteractionGroup(MPIG)@mpig.com.cnOccupancyGridMap金丹MPIGSeminar0047MachinePerceptionandInteractionGroup(MPIG)(MPIG)(MPIG)(MPIG)’sdefinitionOccupancygridmapaddresstheproblemofgeneratingconsistentmapsfromnoisyanduncertainmeasurementdata,undertheassumptionthattherobotposeisknown.Thebasicideaoftheoccupancygridsistorepresentthemapasafieldofrandomvariables,arrangedinanevenlyspacedgrid.Eachrandomvariableisbinaryandcorrespondstotheoccupancyofthelocationitcovers.Occupancygridmappingalgorithmsimplementapproximateposteriorestimationforthoserandomvariables.MachinePerceptionandInteractionGroup(MPIG)(MPIG)𝑝(𝑚|𝑧1:𝑡,𝑥1:𝑡)𝑚isthemap,𝑧1:𝑡thesetofallmeasureuptotime𝑡,and𝑥1:𝑡isthepathoftherobot,thatis,thesequenceofallitsposes.Let𝑚𝑖denotethegridcellwithindex𝑖.Anoccupancygridmappartitionsthespaceintofinitelymanygridcells:𝑚=𝑚𝑖𝑖MachinePerceptionandInteractionGroup(MPIG)(MPIG)“1”foroccupiedand“0”forfree.Thenotationp(𝑚𝑖=1)orp(𝑚𝑖)referstotheprobabilitythatagridcellisoccupied.Thestandardoccupancygridapproachbreaksdowntheproblemofestimatingthemapintoacollectionofseparateproblems,namelythatofestimating𝑝(𝑚𝑖|𝑧1:𝑡,𝑥1:𝑡)forallgridcell𝑚𝑖.Eachoftheseestimationproblemsisnowabinaryproblemwithstaticstate.MachinePerceptionandInteractionGroup(MPIG)(MPIG)𝑝(𝑚|𝑧1:𝑡,𝑥1:𝑡)=𝑝(𝑚𝑖|𝑧1:𝑡,𝑥1:𝑡)𝑖Testimationoftheoccupancyprobabilityforeachgridcellisnowabinaryestimationproblemwithstaticstate.thebinaryBayesfilterforthisproblemwasalreadydiscussedasfollow:MachinePerceptionandInteractionGroup(MPIG)(MPIG)(𝑙𝑡−1,𝑧𝑡):2:𝑙𝑡=𝑙𝑡−1+𝑙𝑜𝑔𝑝(𝑥|𝑧𝑡)1−𝑝(𝑥|𝑧𝑡)−𝑙𝑜𝑔𝑝(𝑥)1−𝑝(𝑥)3:return𝑙𝑡ThebinaryBayesfilterinlogoddsformwithaninversemeasurementmodel.Thealgorithmbinary_Bayes_filterMachinePerceptionandInteractionGroup(MPIG)(MPIG)𝑏𝑒𝑙𝑡𝑥=𝑝𝑥𝑧1:𝑡,𝑢1:𝑡=𝑝𝑥𝑧1:𝑡wherethestateischosenfromtwopossiblevalues,denotedby𝑥and¬𝑥.Inparticular,wehave𝑏𝑒𝑙𝑡¬𝑥=1−𝑏𝑒𝑙𝑡𝑥.Theoddsofastate𝑥isdefinedastheratiooftheprobabilityofthiseventdividedbytheprobabilityofitsnegate𝑝(𝑥)𝑝(¬𝑥)=𝑝(𝑥)1−𝑝(𝑥)Thelogoddsisthelogarithmofthisexpression𝑙𝑥∶=𝑙𝑜𝑔𝑝(𝑥)1−𝑝(𝑥)MachinePerceptionandInteractionGroup(MPIG)(MPIG)−∞to∞.TheBayesfilterforupdatingbeliefsinlogoddsrepresentationavoidstheprobabilitiescloseto0or1.Thebelief𝑏𝑒𝑙𝑡𝑥canberecoveredfromthelogoddsratio𝑙𝑡bythefollowingequation:𝑏𝑒𝑙𝑡𝑥=1−11+exp(𝑙𝑡)MachinePerceptionandInteractionGroup(MPIG)(MPIG)𝑝𝑥𝑧1:𝑡=𝑝(𝑧𝑡|𝑥,𝑧1:𝑡−1)𝑝(𝑥|𝑧1:𝑡−1)𝑝(𝑧𝑡|𝑧1:𝑡−1)=𝑝𝑧𝑡𝑥𝑝(𝑥|𝑧1:𝑡−1)𝑝(𝑧𝑡|𝑧1:𝑡−1)WenowapplyBayesruletothemeasurementmodel𝑝𝑧𝑡𝑥:𝑝𝑧𝑡𝑥=𝑝𝑥𝑧𝑡𝑝(𝑧𝑡)𝑝(𝑥)Andobtain𝑝𝑥𝑧1:𝑡=𝑝𝑥𝑧𝑡𝑝(𝑧𝑡)𝑝(𝑥|𝑧1:𝑡−1)𝑝(𝑥)𝑝(𝑧𝑡|𝑧1:𝑡−1)MachinePerceptionandInteractionGroup(MPIG)(MPIG)¬𝑥:𝑝¬𝑥𝑧1:𝑡=𝑝¬𝑥𝑧𝑡𝑝(𝑧𝑡)𝑝(¬𝑥|𝑧1:𝑡−1)𝑝(¬𝑥)𝑝(𝑧𝑡|𝑧1:𝑡−1)Dividing𝑝𝑥𝑧1:𝑡𝑝¬𝑥𝑧1:𝑡=𝑝𝑥𝑧𝑡𝑝¬𝑥𝑧𝑡𝑝𝑥𝑧1:𝑡−1𝑝¬𝑥𝑧1:𝑡−1𝑝(¬𝑥)𝑝(𝑥)=𝑝𝑥𝑧𝑡1−𝑝𝑥𝑧𝑡𝑝𝑥𝑧1:𝑡−11−𝑝𝑥𝑧1:𝑡−11−𝑝(𝑥)𝑝(𝑥)MachinePerceptionandInteractionGroup(MPIG)(MPIG)𝑏𝑒𝑙𝑡𝑥by𝑙𝑡𝑥.𝑙𝑡𝑥=𝑙𝑜𝑔𝑝𝑥𝑧𝑡1−𝑝𝑥𝑧𝑡+𝑙𝑜𝑔𝑝𝑥𝑧1:𝑡−11−𝑝𝑥𝑧1:𝑡−1+log1−𝑝(𝑥)𝑝(𝑥)=𝑙𝑜𝑔𝑝𝑥𝑧𝑡1−𝑝𝑥𝑧𝑡−𝑙𝑜𝑔𝑝𝑥1−𝑝𝑥+𝑙𝑡−1𝑥Here𝑝𝑥isthepriorprobabilityofthestate𝑥.MachinePerceptionandInteractionGroup(MPIG)(MPIG)𝑙0𝑥=log1−𝑝(𝑥)𝑝(𝑥)Ouroccupancygridmappingalgorithmusesthelogoddsrepresentationofoccupancy:𝑙𝑡,𝑖=𝑙𝑜𝑔𝑝(𝑚𝑖|𝑧1:𝑡,𝑥1:𝑡)1−𝑝(𝑚𝑖|𝑧1:𝑡,𝑥1:𝑡)Theprobabilitiesareeasilyrecoveredfromthelogoddsratio:𝑝𝑚𝑖𝑧1:𝑡,𝑥1:𝑡=1−11+exp{𝑙𝑡,𝑖}MachinePerceptionandInteractionGroup(MPIG)(MPIG)({𝑙𝑡−1