Page 9 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

viii CONTENTS

2.9.3 Sensor-Based Motion Planning 66
2.10 Exercises 71

3 Motion Planning for a Mobile Robot 73
3.1 The Model 78
3.2 Universal Lower Bound for the Path Planning Problem 80

3.3 Basic Algorithms 84
3.3.1 First Basic Algorithm: Bug1 84
3.3.2 Second Basic Algorithm: Bug2 90
3.4 Combining Good Features of Basic Algorithms 100

3.5 Going After Tighter Bounds 103
3.6 Vision and Motion Planning 104
3.6.1 The Model 106
3.6.2 Algorithm VisBug-21 110
3.6.3 Algorithm VisBug-22 120
3.7 From a Point Robot to a Physical Robot 123

3.8 Other Approaches 124
3.9 Which Algorithm to Choose? 127
3.10 Discussion 130

3.11 Exercises 135

4 Accounting for Body Dynamics: The Jogger’s Problem 139
4.1 Problem Statement 139
4.2 Maximum Turn Strategy 144
4.2.1 The Model 144
4.2.2 Sketching the Approach 146
4.2.3 Velocity Constraints. Minimum Time Braking 148
4.2.4 Optimal Straight-Line Motion 149
4.2.5 Dynamics and Collision Avoidance 152
4.2.6 The Algorithm 154
4.2.7 Examples 157
4.3 Minimum Time Strategy 159
4.3.1 The Model 160
4.3.2 Sketching the Approach 161
4.3.3 Dynamics and Collision Avoidance 164