VLADIMIR J. LUMELSKY

A leap forward in the field of robotics

Until now, most of the advances in robotics have taken place in structured environments. Scientists and engineers have designed highly sophisticated robots, but most are still only able to operate and move in predetermined, planned environments designed specifically for the robots and typically at very high cost. This new book takes robotics to the next level by setting forth the theory and techniques needed to achieve robotic motion in unstructured environments. The ability to move and operate in an arbitrary, unplanned environment will lead to automating a wide range of new robotic tasks, such as patient care, toxic site cleanup, and planetary exploration.

The approach that opens the door for robots to handle unstructured tasks is known as Sensing-Intelligence-Motion (SIM), which draws from research in topology, computational complexity, control theory, and sensing hardware. Using SIM as an underlying foundation, the author's carefully structured presentation is designed to:
* Formulate the challenges of sensor-based motion planning and then build a theoretical foundation for sensor-based motion planning strategies
* Investigate promising algorithmic strategies for mobile robots and robot arm manipulators, in both cases addressing motion planning for the whole robot body
* Compare robot performance to human performance in sensor-based motion planning to gain better insight into the challenges of SIM and help build synergistic human-robot teams for tele-operation tasks. It is both exciting and encouraging to discover that robot performance decisively exceeds human performance in certain tasks requiring spatial reasoning, even when compared to trained operators
* Review sensing hardware that is necessary to realize the SIM paradigm

Some 200 illustrations, graphic sketches, and photos are included to clarify key issues, develop and validate motion planning approaches, and demonstrate full systems in operation.

As the first book fully devoted to robot motion planning in unstructured environments, Sensing, Intelligence, Motion is a must-read for engineers, scientists, and researchers involved in robotics. It will help them migrate robots from highly specialized applications in factories to widespread use in society where autonomous robot motion is needed.

VLADIMIR J. LUMELSKY, PhD, is Consolidated Papers Professor of Engineering, University of Wisconsin–Madison. Prior to his current appointment, he held positions with Ford Motor Research Laboratories, General Electric Research Center, and Yale University. Dr. Lumelsky is the author or coauthor of more than 200 scholarly publications.

"This book represents a very stimulating and personal contribution to the field of algorithmic robotics." (Pragmatics & Cognition)
"…a good text for senior undergraduates and graduate students with an interest in robot motion." (Computing Reviews.com, May 25, 2006)

Preface.
Acknowledgments.
1 Motion Planning—Introduction.
1.1 Introduction.
1.2 Basic Concepts.
1.2.1 Robot? What Robot?
1.2.2 Space. Objects.
1.2.3 Input Information. Sensing.
1.2.4 Degrees of Freedom. Coordinate Systems.
1.2.5 Motion Control.
1.2.6 Robot Programming.
1.2.7 Motion Planning.
2 A Quick Sketch of Major Issues in Robotics.
2.1 Kinematics.
2.2 Statics.
2.3 Dynamics.
2.4 Feedback Control.
2.5 Compliant Motion.
2.6 Trajectory Modification.
2.7 Collision Avoidance.
2.8 Motion Planning with Complete Information.
2.9 Motion Planning with Incomplete Information.
2.9.1 The Beginnings.
2.9.2 Maze-to-Graph Transition.
2.9.3 Sensor-Based Motion Planning.
2.10 Exercises.
3 Motion Planning for a Mobile Robot.
3.1 The Model.
3.2 Universal Lower Bound for the Path Planning Problem.
3.3 Basic Algorithms.
3.3.1 First Basic Algorithm: Bug1.
3.3.2 Second Basic Algorithm: Bug2.
3.4 Combining Good Features of Basic Algorithms.
3.5 Going After Tighter Bounds.
3.6 Vision and Motion Planning.
3.6.1 The Model.
3.6.2 Algorithm VisBug-21.
3.6.3 Algorithm VisBug-22.
3.7 From a Point Robot to a Physical Robot.
3.8 Other Approaches.
3.9 Which Algorithm to Choose?
3.10 Discussion.
3.11 Exercises.
4 Accounting for Body Dynamics: The Jogger’s Problem.
4.1 Problem Statement.
4.2 Maximum Turn Strategy.
4.2.1 The Model.
4.2.2 Sketching the Approach.
4.2.3 Velocity Constraints. Minimum Time Braking.
4.2.4 Optimal Straight-Line Motion.
4.2.5 Dynamics and Collision Avoidance.
4.2.6 The Algorithm.
4.2.7 Examples.
4.3 Minimum Time Strategy.
4.3.1 The Model.
4.3.2 Sketching the Approach.
4.3.3 Dynamics and Collision Avoidance.
4.3.4 Canonical Solution.
4.3.5 Near-Canonical Solution.
4.3.6 The Algorithm.
4.3.7 Convergence. Computational Complexity.
4.3.8 Examples.
5 Motion Planning for Two-Dimensional Arm Manipulators.
5.1 Introduction.
5.1.1 Model and Definitions.
5.2 Planar Revolute–Revolute (RR) Arm.
5.2.1 Analysis.
5.2.2 Algorithm.
5.2.3 Step Planning.
5.2.4 Example.
5.2.5 Motion Planning with Vision and Proximity Sensing.
5.2.6 Concluding Remarks.
5.3 Distinct Kinematic Configurations of RR Arm.
5.4 Prismatic–Prismatic (PP, or Cartesian) Arm.
5.5 Revolute–Prismatic (RP) Arm with Parallel Links.
5.6 Revolute–Prismatic (RP) Arm with Perpendicular Links.
5.7 Prismatic–Revolute (PR) Arm.
5.8 Topology of Arm’s Free Configuration Space.
5.8.1 Workspace; Configuration Space.
5.8.2 Interaction Between the Robot and Obstacles.
5.8.3 Uniform Local Connectedness.
5.8.4 The General Case of 2-DOF Arm Manipulators.
5.9 Appendix.
5.10 Exercises.
6 Motion Planning for Three-Dimensional Arm Manipulators.
6.1 Introduction.
6.2 The Case of the PPP (Cartesian) Arm.
6.2.1 Model, Definitions, and Terminology.
6.2.2 The Approach.
6.2.3 Topology of W-Obstacles and C-Obstacles.
6.2.4 Connectivity of C.
6.2.5 Algorithm.
6.2.6 Examples.
6.3 Three-Link XXP Arm Manipulators.
6.3.1 Robot Arm Representation Spaces.
6.3.2 Monotonicity of Joint Space.
6.3.3 Connectivity of Jf.
6.3.4 Retraction of Jf.
6.3.5 Configuration Space and Its Retract.
6.3.6 Connectivity Graph.
6.3.7 Lifting 2D Algorithms into 3D.
6.3.8 Step Planning.
6.3.9 Discussion.
6.4 Other XXX Arms.
7 Human Performance in Motion Planning.
7.1 Introduction.
7.2 Preliminary Observations.
7.2.1 Moving in a Maze.
7.2.2 Moving an Arm Manipulator.
7.2.3 Conclusions and Plan for Experiment Design.
7.3 Experiment Design.
7.3.1 The Setup.
7.3.2 Test Protocol.
7.4 Results—Experiment One.
7.4.1 Principal Components Analysis.
7.4.2 Nonparametric Statistics.
7.4.3 Univariate Analysis of Variance.
7.4.4 Two-Way Analysis of Variance.
7.4.5 Implementation: Two-Way Analysis for Path Length.
7.4.6 Implementation: Two-Way Analysis for Completion Time.
7.5 Results—Experiment Two.
7.5.1 The Technique.
7.5.2 Implementation Scheme.
7.5.3 Results and Interpretation.
7.6 Discussion.
8 Sensitive Skin—Designing an All-Sensitive Robot Arm Manipulator.
8.1 Introduction.
8.2 Salient Characteristics of a Sensitive Skin.
8.3 Skin Design.
8.4 Examples.
9 Suggested Course Projects.
References.
Index.