Probabilistic
Robotics
Probabilistic
Robotics
Sebastian Thrun
Wolfram Burgard
Dieter Fox
The MIT Press
Cambridge, Massachusetts
London, England
© 2006 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any
electronic or mechanical means (including photocopying, recording, or information
storage and retrieval) without permission in writing from the publisher.
MIT Press books may be purchased at special quantity discounts for business or sales
promotional use. For information, please email special_sales@mitpress.mit.edu or
write to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge,
MA 02142.
Typeset in 10/13 Lucida Bright by the authors using LATEX 2ε.
Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Thrun, Sebastian, 1967–
Probabilistic robotics / Sebastian Thrun, Wolfram Burgard, Dieter Fox.
p. cm. – (Intelligent robotics and autonomous agents series)
Includes bibliographical references and index.
ISBN-13: 978-0-262-20162-9 (alk. paper)
1. Robotics. 2. Probabilities. I. Burgard, Wolfram. II. Fox, Dieter. III. Title. IV. In-
telligent robotics and autonomous agents.
TJ211.T575 2005
629.8’92–dc22
2005043346
10
9
8
7
6
5
6
3
Brief Contents
1
3
Introduction
Recursive State Estimation
Gaussian Filters
I Basics
1
2
3
4 Nonparametric Filters
117
5
6
Robot Motion
Robot Perception
149
39
13
85
II Localization
7 Mobile Robot Localization: Markov and Gaussian
8 Mobile Robot Localization: Grid And Monte Carlo
189
191
237
279
III Mapping
9 Occupancy Grid Mapping
10 Simultaneous Localization and Mapping
11 The GraphSLAM Algorithm
12 The Sparse Extended Information Filter
13 The FastSLAM Algorithm
281
337
437
309
385
IV Planning and Control
14 Markov Decision Processes
15 Partially Observable Markov Decision Processes
485
487
513
vi
Brief Contents
16 Approximate POMDP Techniques
17 Exploration
569
547
Contents
Preface
xvii
Acknowledgments
xix
I Basics
1
1 Introduction
3
3
1.1 Uncertainty in Robotics
1.2
1.3
1.4
1.5
1.6
Probabilistic Robotics
Implications
Road Map
Teaching Probabilistic Robotics
Bibliographical Remarks
11
9
10
4
11
2 Recursive State Estimation
13
2.1
2.2
2.3
2.4
13
26
28
14
19
20
State
Environment Interaction
Probabilistic Generative Laws
Belief Distributions
Introduction
Basic Concepts in Probability
Robot Environment Interaction
2.3.1
2.3.2
2.3.3
2.3.4
Bayes Filters
2.4.1
2.4.2
2.4.3 Mathematical Derivation of the Bayes Filter
2.4.4
The Bayes Filter Algorithm
Example
The Markov Assumption
25
22
24
26
33
31