Probabilistic Robotics - Pomona

1 ProbabilisticRoboticsProbabilisticRoboti csSebastianThrunWolframBurgardDieterFoxT heMITP ressCambridge,MassachusettsLondon,Englan d 2006 MassachusettsInstituteofTechnologyAll rights reserved. No part of this book may be reproduced in any form by anyelectronic or mechanical means (including photocopying, recording, or informationstorageandretrieval) use. For information, please email orwrite to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge, . ,Sebastian,1967 Probabilisticrobotics/SebastianThrun,Wol framBurgard, (Intelligentroboticsandautonomousagentss eries) : 978-0-262-20162-9( )1. Robotics . 2.

2 Probabilities. ,Wolfram. ,Dieter. 92 dc222005043346109876563 Brief ContentsI Basics 11 Introduction32 Recursive State Estimation133 Gaussian Filters394 Nonparametric Filters855 Robot Motion1176 Robot Perception149II Localization1897 Mobile Robot localization : Markov and Gaussian1918 Mobile Robot localization : Grid And Monte Carlo237 III Mapping 2799 Occupancy Grid Mapping28110 simultaneous localization and Mapping30911 The GraphSLAM Algorithm33712 The Sparse Extended Information Filter38513 The FastSLAM Algorithm437IV Planning and Control 48514 Markov Decision Processes48715 Partially Observable Markov Decision Processes513viBrief Contents16 Approximate POMDP Techniques54717 Exploration569 ContentsPrefacexviiAcknowledgmentsxixI Basics UncertaintyinRobotics ProbabilisticRobotics Implications RoadMap TeachingProbabilisticRobotics BibliographicalRemarks 112 Recursive State

3 Introduction BasicConceptsinProbability RobotEnvironmentInteraction State EnvironmentInteraction ProbabilisticGenerativeLaws BeliefDistributions BayesFilters TheBayesFilterAlgorithm Example MathematicalDerivationoftheBayesFilter TheMarkovAssumption RepresentationandComputation Summary BibliographicalRemarks Exercises 363 Gaussian Introduction TheKalmanFilter LinearGaussianSystems TheKalmanFilterAlgorithm Illustration MathematicalDerivationoftheKF TheExtendedKalmanFilter WhyLinearize? LinearizationViaTaylorExpansion TheEKFA lgorithm MathematicalDerivationoftheEKF PracticalConsiderations TheUnscentedKalmanFilter LinearizationViatheUnscentedTransform TheUKFA lgorithm TheInformationFilter CanonicalParameterization TheInformationFilterAlgorithm MathematicalDerivationoftheInformationFi lter TheExtendedInformationFilterAlgorithm MathematicalDerivationoftheExtendedInfor mationFilter PracticalConsiderations Summary BibliographicalRemarks Exercises 814 Nonparametric TheHistogramFilter TheDiscreteBayesFilterAlgorithm ContinuousState

4 MathematicalDerivationoftheHistogramAppr oximation DecompositionTechniques BinaryBayesFilterswithStaticState TheParticleFilter BasicAlgorithm ImportanceSampling MathematicalDerivationofthePF PracticalConsiderationsandPropertiesofPa rticleFilters Summary BibliographicalRemarks Exercises 1155 Robot Introduction Preliminaries KinematicConfiguration ProbabilisticKinematics VelocityMotionModel ClosedFormCalculation SamplingAlgorithm MathematicalDerivationoftheVelocityMotio nModel OdometryMotionModel ClosedFormCalculation SamplingAlgorithm MathematicalDerivationoftheOdometryMotio nModel MotionandMaps Summary BibliographicalRemarks Exercises 1456 Robot Introduction Maps BeamModelsofRangeFinders TheBasicMeasurementAlgorithm AdjustingtheIntrinsicModelParameters MathematicalDerivationoftheBeamModel PracticalConsiderations LimitationsoftheBeamModel LikelihoodFieldsforRangeFinders BasicAlgorithm Extensions Correlation-BasedMeasurementModels Feature-BasedMeasurementModels FeatureExtraction LandmarkMeasurements SensorModelwithKnownCorrespondence SamplingPoses FurtherConsiderations

5 PracticalConsiderations Summary BibliographicalRemarks Exercises 185II Localization1897 Mobile Robot localization : Markov and ATaxonomyofLocalizationProblems MarkovLocalization IllustrationofMarkovLocalization EKFL ocalization Illustration TheEKFL ocalizationAlgorithm MathematicalDerivationofEKFL ocalization PhysicalImplementation EstimatingCorrespondences EKFL ocalizationwithUnknownCorrespondences MathematicalDerivationoftheMLDataAssocia tion Multi-HypothesisTracking UKFL ocalization MathematicalDerivationofUKFL ocalization Illustration PracticalConsiderations Summary BibliographicalRemarks Exercises 2348 Mobile Robot localization .

6 Grid And Monte Introduction GridLocalization BasicAlgorithm GridResolutions ComputationalConsiderations Illustration MonteCarloLocalization Illustration TheMCLA lgorithm PhysicalImplementations PropertiesofMCL RandomParticleMCL:RecoveryfromFailures ModifyingtheProposalDistribution KLD-Sampling: AdaptingtheSizeofSampleSets LocalizationinDynamicEnvironments PracticalConsiderations Summary BibliographicalRemarks Exercises 276 III Mapping 2799 Occupancy Grid Introduction TheOccupancyGridMappingAlgorithm Multi-SensorFusion LearningInverseMeasurementModels InvertingtheMeasurementModel SamplingfromtheForwardModel TheErrorFunction ExamplesandFurtherConsiderations MaximumAPosterioriOccupancyMapping TheCaseforMaintainingDependencies OccupancyGridMappingwithForwardModels Summary BibliographicalRemarks Exercises 30710 simultaneous localization and

7 Introduction SLAM withExtendedKalmanFilters SetupandAssumptions SLAM withKnownCorrespondence MathematicalDerivationofEKFSLAM EKFSLAM withUnknownCorrespondences TheGeneralEKFSLAMA lgorithm Examples FeatureSelectionandMapManagement Summary BibliographicalRemarks Exercises 33411 The GraphSLAM Introduction IntuitiveDescription BuildingUptheGraph Inference TheGraphSLAMA lgorithm MathematicalDerivationofGraphSLAM TheFullSLAMP osterior TheNegativeLogPosterior TaylorExpansion ConstructingtheInformationForm ReducingtheInformationForm RecoveringthePathandtheMap DataAssociationinGraphSLAM TheGraphSLAMA lgorithmwithUnknownCorrespondence MathematicalDerivationoftheCorrespondenc eTest EfficiencyConsideration EmpiricalImplementation AlternativeOptimizationTechniques Summary BibliographicalRemarks Exercises 38212 The Sparse Extended Information Introduction IntuitiveDescription TheSEIFSLAMA lgorithm MathematicalDerivationoftheSEIF MotionUpdate MeasurementUpdates Sparsification GeneralIdea SparsificationinSEIFs MathematicalDerivationoftheSparsificatio n AmortizedApproximateMapRecovery

8 HowSparseShouldSEIFsBe? IncrementalDataAssociation ComputingIncrementalDataAssociationProba bilities PracticalConsiderations Branch-and-BoundDataAssociation RecursiveSearch ComputingArbitraryDataAssociationProbabi lities EquivalenceConstraints PracticalConsiderations Multi-RobotSLAM IntegratingMaps MathematicalDerivationofMapIntegration EstablishingCorrespondence Example Summary BibliographicalRemarks Exercises 43513 The FastSLAM TheBasicAlgorithm FactoringtheSLAMP osterior MathematicalDerivationoftheFactoredSLAMP osterior FastSLAM withKnownDataAssociation ImprovingtheProposalDistribution ExtendingthePathPosteriorbySamplingaNewP ose UpdatingtheObservedFeatureEstimate CalculatingImportanceFactors UnknownDataAssociation MapManagement TheFastSLAMA lgorithms EfficientImplementation FastSLAMforFeature-BasedMaps EmpiricalInsights LoopClosure Grid-basedFastSLAM TheAlgorithm EmpiricalInsights Summary BibliographicalRemarks Exercises 482IV Planning and Control 48514 Markov Decision Motivation UncertaintyinActionSelection ValueIteration GoalsandPayoff FindingOptimalControlPoliciesfortheFully ObservableCase

9 ComputingtheValueFunction ApplicationtoRobotControl Summary BibliographicalRemarks Exercises 510 Contentsxv15 Partially Observable Markov Decision Motivation AnIllustrativeExample Setup ControlChoice Sensing Prediction DeepHorizonsandPruning TheFiniteWorldPOMDPA lgorithm MathematicalDerivationofPOMDPs ValueIterationinBeliefSpace ValueFunctionRepresentation CalculatingtheValueFunction PracticalConsiderations Summary BibliographicalRemarks Exercises 54416 Approximate POMDP Motivation QMDPs AugmentedMarkovDecisionProcesses TheAugmentedStateSpace TheAMDPA lgorithm MathematicalDerivationofAMDPs ApplicationtoMobileRobotNavigation MonteCarloPOMDPs UsingParticleSets TheMC-POMDPA lgorithm MathematicalDerivationofMC-POMDPs PracticalConsiderations Summary BibliographicalRemarks Exercises Introduction BasicExplorationAlgorithms InformationGain GreedyTechniques MonteCarloExploration Multi-StepTechniques ActiveLocalization ExplorationforLearningOccupancyGridMaps ComputingInformationGain PropagatingGain ExtensiontoMulti-RobotSystems ExplorationforSLAM Ent