Probabilistic robotics / Sebastian Thrun, Wolfram Burgard, Dieter Fox.

CONTENIDO
I Basics 1
1 Introduction 3
1.1 Uncertainty in Robotics 3
1.2 Probabilistic Robotics 4
1.3 Implications 9
1.4 Road Map 10
1.5 Teaching Probabilistic Robotics 11
1.6 Bibliographical Remarks 11
2 Recursive State Estimation 13
2.1 Introduction 13
2.2 Basic Concepts in Probability 14
2.3 Robot Environment Interaction 19
2.3.1 State 20
2.3.2 Environment Interaction 22
2.3.3 Probabilistic Generative Laws 24
2.3.4 Belief Distributions 25
2.4 Bayes Filtres 26
2.4.1 The Bayes Filter Algorithm 26
2.4.2 Example 28
2.4.3 Mathematical Derivation of the Bayes Filter 31
2.4.4 The Markov Assumption 33
2.5 Representation and Computation 34
3 Gaussian Filters 39
3.1 Introduction 39
3.2 The Kalman Filter 40
3.2.1 Linear Gaussian Systems 40
3.2.2 The Kalman Filter Algorithm 43
3.2.3 Illustration 44
3.2.4 Mathematical Derivation of the KF 45
3.3 The Extended Kalman Filter 54
3.3.1 Why Linearize? 54
3.3.2 Linearization Via Taylor Expansion 56
3.3.3 The EKF Algorithm 59
3.3.4 Mathematical Derivation of the EKF 59
3.3.5 Practical Considerations 61
3.4 The Unscented Kalman Filter 65
3.4.1 Linearization Via the Unscented Transform 65
3.4.2 The UKF Algorithm 67
3.5 The Information Filter 71
3.5.1 Canonical Parameterization 71
3.5.2 The Information Filter Algorithm 73
3.5.3 Mathematical Derivation of the Information Filter 74
3.5.4 The Extended Information Filter Algorithm 75
3.5.5 Mathematical Derivation of the Extended Information Filter 76
3.5.6 Practical Considerations 77
4 Nonparantetric Filtres 85
4.1 The Histogram Filter 86
4.1.1 The Discrete Bayes Filter Algorithm 86
4.1.2 Continuous State 87
4.1.3 Mathematical Derivation of the Histogram Approximation 89
4.1.4 Decomposition Techniques 92
4.2 Binary Bayes Filters with Static State 94
4.3 The Particle Filter 96
4.3.1 Basic Algorithm 96
4.3.2 Importance Sampling 100
4.3.3 Mathematical Derivation of the PF 103
4.3.4 Practical Considerations and Properties of Particle Filters 104
5 Robot Motion 117
5.1 Introduction 117
5.2 Preliminaries 118
5.2.1 Kinematic Configuration 118
5.2.2 Probabilistic Kinematics 119
5.3 Velocity Motion Model121
5.3.1 Closed Form Calculation 121
5.3.2 Sampling Algorithm 122
5.3.3 Mathematical Derivation of the Velocity Motion Model 125
5.4 Odometry Motion Model 132
5.4.1 Closed Form Calculation 133
5.4.2 Sampling Algorithm 137
5.4.3 Mathematical Derivation of the Odometry Motion Model 137
5.5 Motion and Maps140
6 Robot Perception 149
6.1 Introduction 149
6.2 Maps 152
6.3 Beam Models of Range Finders 153
6.3.1 The Basic Measurement Algorithm 153
6.3.2 Adjusting the Intrinsic Model Parameters 158
6.3.3 Mathematical Derivation of the Beam Model 162
6.3.4 Practical Considerations 167
6.3.5 Limitations of the Beam Model 168
6.4 Likelihood Fields for Range Finders 169
6.4.1 Basic Algorithm 169
6.4.2 Extensions 172
6.5 Correlation-Based Measurement Models 174
6.6 Feature-Based Measurement Models 176
6.6.1 Feature Extraction 176
6.6.2 Landmark Measurements 177
6.6.3 Sensor Model with Known Correspondence 178
6.6.4 Sampling Poses 179
6.6.5 Further Considerations 180
II Localization 189
7 Mobile Robot Localization: Markov and Gaussian 191
7.1 A Taxonomy of Localization Problems 193
7.2 Markov Localization 197
7.3 Illustration of Markov Localization 200
7.4 EKF Localization 201
7.4.1 Illustration 201
7.4.2 The EKF Localization Algorithm 203
7.4.3 Mathematical Derivation of EKF Localization 205
7.4.4 Physical Implementation 210
7.5 Estimating Correspondences 215
7.5.1 EKF Localization with Unknown Correspondences 215
7.5.2 Mathematical Derivation of the ML Data Association 216
7.6 Multi-Hypothesis Tracking 218
7.7 UKF Localization 220
7.7.1 Mathematical Derivation of UKF Localization 220
7.7.2 Illustration 223
8 Mobile Robot Localization: Grid And Monte Carlo 237
8.1 Introduction 237
8.2 Grid Localization 238
8.2.1 Basic Algorithm 238
8.2.2 Grid Resolutions 239
8.2.3 Computational Considerations 243
8.2.4 Illustration 245
8.3 Monte Carlo Localization 250
8.3.1 Illustration 250
8.3.2 The MCL Algorithm 252
8.3.3 Physical Implementations 253
8.3.4 Properties of MCL 253
8.3.5 Random Particle MCL: Recovery from Failures 256
8.3.6 Modifying the Proposal Distribution 261
8.3.7 KLD-Sampling: Adapting the Size of Sample Sets 263
8.4 Localization in Dynamic Environments 267
III Mapping 279
9 Occupancy Grid Mapping 281
9.1 Introduction 281
9.2 The Occupancy Grid Mapping Algorithm 284
9.2.1 Multi-Sensor Fusion 293
9.3 Learning Inverse Measurement Models 294
9.3.1 Inverting the Measurement Model 294
9.3.2 Sampling from the Forward Model 295
9.3.3 The Error Function 296
9.3.4 Examples and Further Considerations 298
9.4 Maximum A Posteriori Occupancy Mapping 299
9.4.1 The Case for Maintaining Dependencias 299
9.4.2 Occupancy Grid Mapping with Forward Models 301
10 Simultaneous Localization and Mapping 309
10.1 Introduction 309
10.2 SLAM with Extended Kalman Filters 312
10.2.1 Setup and Assumptions 312
10.2.2 SLAM with Known Correspondence 313
10.2.3 Mathematical Derivation of EKF SLAM 317
10.3 EKF SLAM with Unknown Correspondences 323
10.3.1 The General EKF SLAM Algorithm 323
10.3.2 Examples 324
10.3.3 Feature Selection and Map Management 328
11 The GraphSLAM Algorithm 337
11.1 Introduction 337
11.2 Intuitive Description 340
11.2.1 Building Up the Graph 340
11.2.2 Inference 343
11.3 The GraphSLAM Algorithm 346
11.4 Mathematical Derivation of GraphSLAM 353
11.4.1 The Full SLAM Posterior 353
11.4.2 The Negative Log Posterior 354
11.4.3 Taylor Expansion 355
11.4.4 Constructing the Information Form 357
11.4.5 Reducing the Information Form 360
11.4.6 Recovering the Path and the Map 361
11.5 Data Association in GraphSLAM 362
11.5.1 The GraphSLAM Algorithm with Unknown Correspondence 363
11.5.2 Mathematical Derivation of the Correspondence Test 366
11.6 Efficiency Consideration 368
11.7 Empirical Implementation 370
11.8 Alternative Optimization Techniques 376
12 The Sparse Extended Information Filter 385
12.1 Introduction 385
12.2 Intuitive Description 388
12.3 The SEIF SLAM Algorithm 391
12.4 Mathematical Derivation of the SEIF 395
12.4.1 Motion Update 395
12.4.2 Measurement Updates 398
12.5 Sparsification 398
12.5.1 General Idea 398
12.5.2 Sparsification in SEIFs 400
12.5.3 Mathematical Derivation of the Sparsification 401
12.6 Amortized Approximate Map Recovery 402
12.7 How Sparse Should SEIFs Be? 405
12.8 Incremental Data Association 409
12.8.1 Computing Incremental Data Association Probabilities 409
12.8.2 Practical Considerations 411
12.9 Branch-and-Bound Data Association 415
12.9.1 Recursive Search 416
12.9.2 Computing Arbitrary Data Association Probabilities 416
12.9.3 Equivalence Constraints 419
12.10 Practical Considerations 420
12.11 Multi-Robot SLAM 424
12.11.1 Integrating Maps 424
12.11.2 Mathematical Derivation of Map Integration 427
12.11.3 Establishing Correspondence 429
13 The FastSLAM Algorithm 437
13.1 The Basic Algorithm 439
13.2 Factoring the SLAM Posterior 439
13.2.1 Mathematical Derivation of the Factored SLAM Posterior 442
13.3 FastSLAM with Known Data Association 444
13.4 Improving the Proposal Distribution 451
13.4.1 Extending the Path Posterior by Sampling a New Pose 451
13.4.2 Updating the Observed Feature Estimate 454
13.4.3 Calculating Importance Factors 455
13.5 Unknown Data Association 457
13.6 Map Management 459
13.7 The FastSLAM Algorithms 460
13.8 Efficient Implementation 460
13.9 FastSLAM for Feature-Based Maps 468
13.9.1 Empirical Insights 468
13.9.2 Loop Closure 471
13.10 Grid-based FastSLAM 474
13.10.1 The Algorithm 474
13.10.2 Empirical Insights 475
IV Planning and Control 485
14 Markov Decision Processes 487
14.1 Motivation 487
14.2 Uncertainty in Action Selection 490
14.3 Value Iteration 495
14.3.1 Goals and Payoff 495
14.3.2 Finding Optimal Control Policies for the Fully Observable Case 499
14.3.3 Computing the Value Function 501
14.4 Application to Robot Control 503
15 Partially Observable Markov Decision Processes 513
15.1 Motivation 513
15.2 An Illustrative Example 515
15.2.1 Setup 515
15.2.2 Control Choice 516
15.2.3 Sensing 519
15.2.4 Prediction 523
15.2.5 Deep Horizons and Pruning 526
15.3 The Finite World POMDP Algorithm 527
15.4 Mathematical Derivation of POMDPs 531
15.4.1 Value Iteration in Belief Space 531
15.4.2 Value Function Representation 532
15.4.3 Calculating the Value Function 533
15.5 Practical Considerations 536
16 Approximate POMDP Techniques 547
16.1 Motivation 547
16.2 QMDPs 549
16.3 Augmented Markov Decision Processes 550
16.3.1 The Augmented State Space 550
16.3.2 The AMDP Algorithm 551
16.3.3 Mathematical Derivation of AMDPs 553
16.3.4 Application to Mobile Robot Navigation 556
16.4 Monte Carlo POMDPs 559
16.4.1 Using Particle Sets 559
16.4.2 The MC-POMDP Algorithm 559
16.4.3 Mathematical Derivation of MC-POMDPs 562
16.4.4 Practical Considerations 563
17 Exploration 569
17.1 Introduction 569
17.2 Basic Exploration Algorithms 571
17.2.1 Information Gain 571
17.2.2 Greedy Techniques 572
17.2.3 Monte Carlo Exploration 573
17.2.4 Multi-Step Techniques 575
17.3 Active Localization 575
17.4 Exploration for Learning Occupancy Grid Maps 580
17.4.1 Computing Information Gain 580
17.4.2 Propagating Gain 585
17.4.3 Extension to Multi-Robot Systems 587
17.5 Exploration for SLAM 593
17.5.1 Entropy Decomposition in SLAM 593
17.5.2 Exploration in FastSLAM 594
17.5.3 Empirical Characterization 598