Howie Choset, Kevin M. Lynch,
Seth Hutchinson, George Kantor,
Wolfram Burgard, Lydia E. Kavraki,
and Sebastian Thrun
foreword by Jean-Claude Latombe
Principles of
Robot Motion
Theory, Algorithms,
and Implementations
Choset-79066
book
February 23, 2005
13:40
Principles
of
Robot
Motion
Choset-79066
book
February 23, 2005
13:40
Intelligent Robotics and Autonomous Agents
Ronald C. Arkin, editor
Behavior-Based Robotics, Ronald C. Arkin, 1998
Robot Shaping: An Experiment in Behavior Engineering, Marco Dorigo and Marco
Colombetti, 1998
Layered Learning in Multiagent Systems: A Winning Approach to Robotic Soccer, Peter
Stone, 2000
Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing
Machines, Stefano Nolfi and Dario Floreano, 2000
Reasoning about Rational Agents, Michael Wooldridge, 2000
Introduction to AI Robotics, Robin R. Murphy, 2000
Strategic Negotiation in Multiagent Environments, Sarit Kraus, 2001
Mechanics of Robotic Manipulation, Matthew T. Mason, 2001
Designing Sociable Robots, Cynthia L. Breazeal, 2001
Introduction to Autonomous Mobile Robots, Roland Siegwart and Illah R. Nourbakhsh, 2004
Principles of Robot Motion: Theory, Algorithms, and Implementations, Howie Choset, Kevin
Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia Kavraki and Sebastian
Thrun, 2005
Choset-79066
book
February 23, 2005
13:40
Principles
of
Robot Motion
Theory, Algorithms,
and Implementation
Howie Choset, Kevin Lynch, Seth Hutchinson,
George Kantor, Wolfram Burgard, Lydia Kavraki,
and Sebastian Thrun
A Bradford Book
The MIT Press
Cambridge, Massachusetts
London, England
Choset-79066
book
February 23, 2005
13:40
©2005 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, 5 Cambridge Center, Cambridge, MA 02142.
This book was set in LATEX2e by Interactive Composition Corporation and was printed and
bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Principles of robot motion : theory, algorithms, and implementation/Howie Choset [et al.].
p. cm.
(Intelligent robotics and autonomous agents)
“A Bradford book.”
Includes bibliographical references and index.
ISN 0-262-03327-5 (alk. paper)
1. Robots—Motion. I. Choset, Howie M. II. Series.
TJ211.4.P75 2004
629.8
92—dc22
10 9 8 7 6 5 4 3 2 1
2004044906
Choset-79066
book
February 23, 2005
13:40
To our families
Choset-79066
book
February 23, 2005
13:40
Choset-79066
book
February 23, 2005
13:40
Contents
Foreword
xv
Preface
xvii
Acknowledgments
xxi
1 Introduction
1
Overview of Concepts in Motion Planning
Overview of the Book
1.1
1.2
1.3 Mathematical Style
12
13
2 Bug Algorithms
9
31
2.1
2.2
2.3
17
17
Bug1 and Bug2
Tangent Bug
Implementation
2.3.1 What Information: The Tangent Line
2.3.2
23
30
How to Infer Information with Sensors: Distance
and Gradient
How to Process Sensor Information:
Continuation Methods
32
35
2.3.3
3 Configuration Space
39
3.1
3.2
3.3
40
Specifying a Robot’s Configuration
Obstacles and the Configuration Space
43
3.2.1
3.2.2
45
The Dimension of the Configuration Space
Circular Mobile Robot
Two-Joint Planar Arm
43
47