Probabilistic robotics

Probabilistic robotics is a new and growing area in robotics, concerned with perception and control in the face of uncertainty. Building on the field of mathematical statistics, probabilistic robotics endows robots with a new level of robustness in real-world situations. This book introduces the reader to a wealth of techniques and algorithms in the field. All algorithms are based on a single overarching mathematical foundation. Each chapter provides example implementations in pseudo code, detailed mathematical derivations, discussions from a practitioner's perspective, and extensive lists of exercises and class projects. The book's Web site, www.probabilistic-robotics.org, has additional material. The book is relevant for anyone involved in robotic software development and scientific research. It will also be of interest to applied statisticians and engineers dealing with real-world sensor data.

Author Notes

Sebastian Thrun is Associate Professor in the Computer Science Department at Stanford University and Director of the Stanford Al Lab
Wolfram Burgard is Associate Professor and Head of the Autonomous Intelligent Systems Research Lab in the Department of Computer Science at the University of Freiburg
Dieter Fox is Associate Professor and Director of the Robotics and State Estimation Lab in the Department of Computer Science and Engineering at the University of Washington

Preface	p. xvii
Acknowledgments	p. xix
I Basics	p. 1
1 Introduction	p. 3
1.1 Uncertainty in Robotics	p. 3
1.2 Probabilistic Robotics	p. 4
1.3 Implications	p. 9
1.4 Road Map	p. 10
1.5 Teaching Probabilistic Robotics	p. 11
1.6 Bibliographical Remarks	p. 11
2 Recursive State Estimation	p. 13
2.1 Introduction	p. 13
2.2 Basic Concepts in Probability	p. 14
2.3 Robot Environment Interaction	p. 19
2.4 Bayes Filters	p. 26
2.5 Representation and Computation	p. 34
2.6 Summary	p. 35
2.7 Bibliographical Remarks	p. 36
2.8 Exercises	p. 36
3 Gaussian Filters	p. 39
3.1 Introduction	p. 39
3.2 The Kalman Filter	p. 40
3.3 The Extended Kalman Filter	p. 54
3.4 The Unscented Kalman Filter	p. 65
3.5 The Information Filter	p. 71
3.6 Summary	p. 79
3.7 Bibliographical Remarks	p. 81
3.8 Exercises	p. 81
4 Nonparametric Filters	p. 85
4.1 The Histogram Filter	p. 86
4.2 Binary Bayes Filters with Static State	p. 94
4.3 The Particle Filter	p. 96
4.4 Summary	p. 113
4.5 Bibliographical Remarks	p. 114
4.6 Exercises	p. 115
5 Robot Motion	p. 117
5.1 Introduction	p. 117
5.2 Preliminaries	p. 118
5.3 Velocity Motion Model	p. 121
5.4 Odometry Motion Model	p. 132
5.5 Motion and Maps	p. 140
5.6 Summary	p. 143
5.7 Bibliographical Remarks	p. 145
5.8 Exercises	p. 145
6 Robot Perception	p. 149
6.1 Introduction	p. 149
6.2 Maps	p. 152
6.3 Beam Models of Range Finders	p. 153
6.4 Likelihood Fields for Range Finders	p. 169
6.5 Correlation-Based Measurement Models	p. 174
6.6 Feature-Based Measurement Models	p. 176
6.7 Practical Considerations	p. 182
6.8 Summary	p. 183
6.9 Bibliographical Remarks	p. 184
6.10 Exercises	p. 185
II Localization	p. 189
7 Mobile Robot Localization: Markov and Gaussian	p. 191
7.1 A Taxonomy of Localization Problems	p. 193
7.2 Markov Localization	p. 197
7.3 Illustration of Markov Localization	p. 200
7.4 EKF Localization	p. 201
7.5 Estimating Correspondences	p. 215
7.6 Multi-Hypothesis Tracking	p. 218
7.7 UKF Localization	p. 220
7.8 Practical Considerations	p. 229
7.9 Summary	p. 232
7.10 Bibliographical Remarks	p. 233
7.11 Exercises	p. 234
8 Mobile Robot Localization: Grid And Monte Carlo	p. 237
8.1 Introduction	p. 237
8.2 Grid Localization	p. 238
8.3 Monte Carlo Localization	p. 250
8.4 Localization in Dynamic Environments	p. 267
8.5 Practical Considerations	p. 273
8.6 Summary	p. 274
8.7 Bibliographical Remarks	p. 275
8.8 Exercises	p. 276
III Mapping	p. 279
9 Occupancy Grid Mapping	p. 281
9.1 Introduction	p. 281
9.2 The Occupancy Grid Mapping Algorithm	p. 284
9.3 Learning Inverse Measurement Models	p. 294
9.4 Maximum A Posteriori Occupancy Mapping	p. 299
9.5 Summary	p. 304
9.6 Bibliographical Remarks	p. 305
9.7 Exercises	p. 307
10 Simultaneous Localization and Mapping	p. 309
10.1 Introduction	p. 309
10.2 SLAM with Extended Kalman Filters	p. 312
10.3 EKF SLAM with Unknown Correspondences	p. 323
10.4 Summary	p. 330
10.5 Bibliographical Remarks	p. 332
10.6 Exercises	p. 334
11 The GraphSLAM Algorithm	p. 337
11.1 Introduction	p. 337
11.2 Intuitive Description	p. 340
11.3 The GraphSLAM Algorithm	p. 346
11.4 Mathematical Derivation of GraphSLAM	p. 353
11.5 Data Association in GraphSLAM	p. 362
11.6 Efficiency Consideration	p. 368
11.7 Empirical Implementation	p. 370
11.8 Alternative Optimization Techniques	p. 376
11.9 Summary	p. 379
11.10 Bibliographical Remarks	p. 381
11.11 Exercises	p. 382
12 The Sparse Extended Information Filter	p. 385
12.1 Introduction	p. 385
12.2 Intuitive Description	p. 388
12.3 The SEIF SLAM Algorithm	p. 391
12.4 Mathematical Derivation of the SEIF	p. 395
12.5 Sparsification	p. 398
12.6 Amortized Approximate Map Recovery	p. 402
12.7 How Sparse Should SEIFs Be?	p. 405
12.8 Incremental Data Association	p. 409
12.9 Branch-and-Bound Data Association	p. 415
12.10 Practical Considerations	p. 420
12.11 Multi-Robot SLAM	p. 424
12.12 Summary	p. 432
12.13 Bibliographical Remarks	p. 434
12.14 Exercises	p. 435
13 The FastSLAM Algorithm	p. 437
13.1 The Basic Algorithm	p. 439
13.2 Factoring the SLAM Posterior	p. 439
13.3 FastSLAM with Known Data Association	p. 444
13.4 Improving the Proposal Distribution	p. 451
13.5 Unknown Data Association	p. 457
13.6 Map Management	p. 459
13.7 The FastSLAM Algorithms	p. 460
13.8 Efficient Implementation	p. 460
13.9 FastSLAM for Feature-Based Maps	p. 468
13.10 Grid-based FastSLAM	p. 474
13.11 Summary	p. 479
13.12 Bibliographical Remarks	p. 481
13.13 Exercises	p. 482
IV Planning and Control	p. 485
14 Markov Decision Processes	p. 487
14.1 Motivation	p. 487
14.2 Uncertainty in Action Selection	p. 490
14.3 Value Iteration	p. 495
14.4 Application to Robot Control	p. 503
14.5 Summary	p. 507
14.6 Bibliographical Remarks	p. 509
14.7 Exercises	p. 510
15 Partially Observable Markov Decision Processes	p. 513
15.1 Motivation	p. 513
15.2 An Illustrative Example	p. 515
15.3 The Finite World POMDP Algorithm	p. 527
15.4 Mathematical Derivation of POMDPs	p. 531
15.5 Practical Considerations	p. 536
15.6 Summary	p. 541
15.7 Bibliographical Remarks	p. 542
15.8 Exercises	p. 544
16 Approximate POMDP Techniques	p. 547
16.1 Motivation	p. 547
16.2 QMDPs	p. 549
16.3 Augmented Markov Decision Processes	p. 550
16.4 Monte Carlo POMDPs	p. 559
16.5 Summary	p. 565
16.6 Bibliographical Remarks	p. 566
16.7 Exercises	p. 566
17 Exploration	p. 569
17.1 Introduction	p. 569
17.2 Basic Exploration Algorithms	p. 571
17.3 Active Localization	p. 575
17.4 Exploration for Learning Occupancy Grid Maps	p. 580
17.5 Exploration for SLAM	p. 593
17.6 Summary	p. 600
17.7 Bibliographical Remarks	p. 602
17.8 Exercises	p. 604
Bibliography	p. 607
Index	p. 639

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents