Table of Contents
Dedication v
Preface|vii
List of Tables xv
List of Figures Xvii
1 Introduction 1
1.1 Robots 1
1.2 Cluster Computing 4
1.3 Overview of the Book 6
2 Clusters and Robots 9
2.1 Parallel Computation 9
2.1.1 Parallel Architectures 11
2.1.2 Multiprocessor 12
2.1.3 Multicomputer 13
2.2 Clusters 15
2.2.1 Terminology 16
2.2.2 Cluster Configuration 17
2.2.3 Programming the Cluster 18
2.2.4 Configuring the Cluster 19
2.2.5 Simple Cluster Configuration with Open MPI 19
2.2.6 Connecting the Cluster to the Robot 20
2.3 Summary 23
References 23
3 Cluster Programming 25
3.1 Approaches to Parallel Programming 25
3.2 Programming with MPI 29
3.2.1 Message-Passing 30
3.2.2 Single Program Multiple Data(SPMD) Model 31
3.2.3 Collective Communication 32
3.3 Compiling and Running MPI Programs 34
3.4 Analyzing Parallel Computation Time 36
3.4.1 Speedup and Amdhal's Law 37
3.4.2 Communication and Calculation 38
3.4.3 Communication Models 38
3.5 Summary 41
References 42
4 Robot Motion 43
4.1 Motion of a Mobile Robot in Two Dimensions 45
4.2 Calculation of Location by Dead-Reckoning 46
4.2.1 Partitioning: Block Data Decomposition 47
4.2.2 Program Design 48
4.2.3 Analysis 52
4.3 Dead-Reckoning with Intermediate Results 54
4.3.1 Partitioning 55
4.3.2 Program Design 56
4.3.3 Analysis 57
4.4 Dead-Reckoning for a Team of Robots 57
4.4.1 Partitioning 59
4.4.2 Program Design 60
4.4.3 Analysis 61
4.4.4 Local and Global Buffers 62
4.5 Summary 64
References 64
5 Sensors 67
5.1 Transforming Sensor Readings 68
5.1.1 Partitioning: Single Robot Location 71
5.1.2 Analysis 71
5.1.3 Partitioning: Multiple Robot Locations 73
5.1.4 Analysis 74
5.2 Drawing a Map from Sonar Data 75
5.2.1 Finding Straight Lines with the Hough Transform 76
5.2.2 Partitioning 77
5.2.3 Program Design 78
5.2.4 Analysis 80
5.2.5 Load Balanced Hough Calculation 80
5.2.6 Analysis 82
5.3 Aligning Laser Scan Measuremens 82
5.3.1 Polar Scan Matching 84
5.3.2 Partitioning and Analysis 86
5.3.3 Program Design 87
5.4 Summary 91
References 91
6 Mapping and Localization 93
6.1 Constructing a Spatial Occupancy Map 95
6.1.1 Probabilistic Sonar Model 96
6.1.2 Bayesian Filtering 97
6.1.3 Partitioning by Map 98
6.1.4 Program Design 100
6.1.5 Analysis 105
6.1.6 Partitioning by Sensor Readings 107
6.1.7 Program Design 108
6.1.8 Analysis 109
6.2 Monte-Carlo Localization 109
6.2.1 Partitioning 112
6.2.2 Program Design 112
6.2.3 Analysis 114
6.2.4 Improving the Serial Fraction 115
6.3 Summary 118
References 118
7 Vision and Tracking 121
7.1 Following the Road 123
7.2 Iconic Image Processing 124
7.2.1 Partitioning 125
7.2.2 Program Design 126
7.2.3 Analysis 127
7.2.4 Spatial Pixel Operations 128
7.2.5 Partitioning 130
7.2.6 Program Design 130
7.3 Multiscale Image Processing 132
7.3.1 Partitioning 133
7.4 Video Tracking 134
7.4.1 Spatial Histograms 135
7.4.2 Condensation 137
7.4.3 Partitioning 138
7.4.4 Program Design 139
7.5 Summary 141
References 143
8 Learning Landmarks 145
8.1 Landmark Spatiograms 147
8.2 K-Means Clustering 149
8.2.1 Partitioning 150
8.2.2 Program Design 150
8.2.3 Analysis 152
8.3 EM Clustering 153
8.3.1 Partitioning 154
8.3.2 Program Design 154
8.3.3 Analysis 156
8.4 Summary 156
References 157
9 Robot Architectures 159
9.1 Behavior-Based Robotics 159
9.2 Static Behavior-Based Architecture 162
9.2.1 Partitioning 164
9.2.2 Program Design 165
9.2.3 Analysis 169
9.3 Dynamic Behavior-Based Architecture 172
9.3.1 Program Design 173
9.3.2 Analysis 176
9.4 Summary 177
References 178
Appendix I Summary of OpenMPI Man Page for mpirun 181
Appendix II MPI Datatypes 187
Appendix III MPI Reduction Operations 189
Appendix IV MPI Application Programmer Interface 191
Bibliography 199
Index 207
