PROBABILISTIC
ROBOTICS
Sebastian THRUN
Stanford University
Stanford, CA
Wolfram BURGARD
University of Freiburg
Freiburg, Germany
Dieter FOX
University of Washington
Seattle, WA
EARLY DRAFT—NOT FOR DISTRIBUTION
c
Sebastian Thrun, Dieter Fox, Wolfram Burgard, 1999-2000
CONTENTS
1 INTRODUCTION 1
1.1 Uncertainty in Robotics 1
1.2 Probabilistic Robotics 3
1.3 Implications 5
1.4 Road Map 6
1.5 Bibliographical Remarks 7
2 RECURSIVE STATE ESTIMATION 9
2.1 Introduction 9
2.2 Basic Concepts in Probability 10
2.3 Robot Environment Interaction 16
2.3.1 State 16
2.3.2 Environment Interaction 18
2.3.3 Probabilistic Generative Laws 20
2.3.4 Belief Distributions 22
2.4 Bayes Filters 23
2.4.1 The Bayes Filter Algorithm 23
2.4.2 Example 24
2.4.3 Mathematical Derivation of the Bayes Filter 28
2.4.4 The Markov Assumption 30
2.5 Representation and Computation 30
2.6 Summary 31
2.7 Bibliographical Remarks 32
3 GAUSSIAN FILTERS 33
3.1 Introduction 33
3.2 The Kalman Filter 34
v
vi PROBABILISTIC ROBOTICS
3.2.1 Linear Gaussian Systems 34
3.2.2 The Kalman Filter Algorithm 36
3.2.3 Illustration 37
3.2.4 Mathematical Derivation of the KF 39
3.3 The Extended Kalman Filter 48
3.3.1 Linearization Via Taylor Expansion 49
3.3.2 The EKF Algorithm 50
3.3.3 Mathematical Derivation of the EKF 51
3.3.4 Practical Considerations 53
3.4 The Information Filter 55
3.4.1 Canonical Representation 55
3.4.2 The Information Filter Algorithm 57
3.4.3 Mathematical Derivation of the Information Filter 58
3.4.4 The Extended Information Filter Algorithm 60
3.4.5 Mathematical Derivation of the Extended Information
Filter 61
3.4.6 Practical Considerations 62
3.5 Summary 64
3.6 Bibliographical Remarks 65
4 NONPARAMETRIC FILTERS 67
4.1 The Histogram Filter 68
4.1.1 The Discrete Bayes Filter Algorithm 69
4.1.2 Continuous State 69
4.1.3 Decomposition Techniques 73
4.1.4 Binary Bayes Filters With Static State 74
4.2 The Particle Filter 77
4.2.1 Basic Algorithm 77
4.2.2 Importance Sampling 80
4.2.3 Mathematical Derivation of the PF 82
4.2.4 Properties of the Particle Filter 84
4.3 Summary 89
4.4 Bibliographical Remarks 90
5 ROBOT MOTION 91
5.1 Introduction 91
Contents vii
5.2 Preliminaries 92
5.2.1 Kinematic Configuration 92
5.2.2 Probabilistic Kinematics 93
5.3 Velocity Motion Model 95
5.3.1 Closed Form Calculation 95
5.3.2 Sampling Algorithm 96
5.3.3 Mathematical Derivation 99
5.4 Odometry Motion Model 107
5.4.1 Closed Form Calculation 108
5.4.2 Sampling Algorithm 111
5.4.3 Mathematical Derivation 113
5.5 Motion and Maps 114
5.6 Summary 118
5.7 Bibliographical Remarks 119
6 MEASUREMENTS 121
6.1 Introduction 121
6.2 Maps 123
6.3 Beam Models of Range Finders 124
6.3.1 The Basic Measurement Algorithm 124
6.3.2 Adjusting the Intrinsic Model Parameters 129
6.3.3 Mathematical Derivation 134
6.3.4 Practical Considerations 138
6.4 Likelihood Fields for Range Finders 139
6.4.1 Basic Algorithm 139
6.4.2 Extensions 143
6.5 Correlation-Based Sensor Models 145
6.6 Feature-Based Sensor Models 147
6.6.1 Feature Extraction 147
6.6.2 Landmark Measurements 148
6.6.3 Sensor Model With Known Correspondence 149
6.6.4 Sampling Poses 150
6.6.5 Further Considerations 152
6.7 Practical Considerations 153
6.8 Summary 154
