SLAM Algorithm - Institute of Computer Engineering (E191)

1 IntroductionSimultaneous localization And MappingSteps in SLAMSLAM AlgorithmSimultaneous localization And MappingAlbin Frischenschlager, 0926427 December 17, 2013 Albin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMO utline1 IntroductionDefinitionLocalization ExampleMapping Example2 simultaneous localization And MappingWhat is slam ? slam ExampleFlowchart3 Steps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMD efinitionLocalization ExampleMapping ExampleWhat is ..Robot- a device, that moves through the environmentLandmark- characteristic, reobservable point in theenvironmentLocalization- estimating the robot s locationMapping- building a mapAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMD efinitionLocalization ExampleMapping ExampleLocalization ExampleEstimate the robot s pose given landmarksAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMD efinitionLocalization ExampleMapping ExampleLocalization ExampleEstimate the robot s pose given landmarksAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMD efinitionLocalization ExampleMapping ExampleMapping ExampleEstimate the landmarks given the robot s posesAlbin Frischenschlager.

2 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMD efinitionLocalization ExampleMapping ExampleMapping ExampleEstimate the landmarks given the robot s posesAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartWhat is slam ? slam - Computing the robot s pose and the map of theenvironment at the same time do localization andmapping simultaneouslyit s a chicken-or-egg problem:a map is needed for localization anda pose is needed for mappingit s a hard problem map and pose estimates correlateit s a important problemAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ?

3 slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM ExampleAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ?

4 slam ExampleFlowchartSLAM AlgorithmThere isn t the slam algorithmSLAM is just a problem, but luckily there a possibilities tosolve itAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMWhat is slam ? slam ExampleFlowchartSLAM flowchartAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionLandmark ExtractionExtract from the environmental sensors characteristic pointsInput can be a camera image, array of measurements, ..Algorithms for array of measurements:SpikeRANSAC (Random Sampling Consensus)Scan-MatchingGeometric polygon extractionAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionLandmark ExtractionAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionData AssociationMatching observed landmarks with those previously stored inthe mapWrong association can have catastrophic consequences(divergence)(gated)

5 Nearest-neighbor approach using Euclidean distanceor Mahalanobis distanceAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionPrediction and Filter UpdateKalman FilterExtended Kalman FilterInformation FilterUnscented Kalman FilterSparse Extended Information FilterParticle FilterAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionExtended Kalman FilterEstimate state of a (non-linear) dynamic system, given:model of the systemcontrol inputsmodel of the sensorsmeassurements with noise from the sensorsSet of mathematical equations in a recursive fashionTwo steps:PredictionCorrectionAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionEKF in SLAMS ystem state: x=[ R M]= R Ln Covariances matrix:P=[PRRPRMPMRPMM]= Goal: keep the map x,Pup to date at all timesAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionPredictionMovement function (part of the system model):x f(x,u,n) vectorp(n) N(0,Q)EKF prediction step in slam .

6 R fR( R,u,0)PRR fR RPRR fR R + fR nQ fR n PRM fR RPRMPMR P RMAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionCorrectionObservation function (part of the sensor model):y=h(x) + noisep(v) N(0,R)EKF correction step in slam for every landmarkLi: z=yi hi( R, Li) innovation Z=[HRHLi][PRRPRLiPLiRPLiLi][H RH Li]+RK=[PRRPRLiPLiRPLiLi][H RH Li]Z 1 Kalman gain x x+K zP P KZK HR= hi( R, Li) R,HLi= hi( R, Li) LiAlbin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAML andmark ExtractionData AssociationPrediction and Filter UpdateMap InsertionMap InsertionLn+1=g( R,yn+1)GR= g( R,yn+1) RGyn+1= g( R,yn+1) yn+1 PLL=GRPRRG R+Gyn+1RG yn+1 PLx=GRPRx=GR[PRRPRM] x [ xLn+1]P [PP LxPLxPLL]Albin Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMS ourcesSLAM for Dummies by S ren Riisgaard and Morten RufusBlasA simultaneous localization and mapping implementationusing inexpensive hardware by Todd Michael AycockOnline Video: Course.

7 Frischenschlager, 0926427 slam AlgorithmIntroductionSimultaneous localization And MappingSteps in SLAMT hank you for your attention!Albin Frischenschlager, 0926427 slam Algorithm