Cluster Computing For Robotics And Computer Vision

by Damian M Lyons

Overview

In this book, we look at how cluster technology can be leveraged to build better robots. Algorithms and approaches in key areas of robotics and computer vision, such as map building, target tracking, action selection and landmark learning, are reviewed and cluster implementations for these are presented.The objective of the book is to give professionals working in the beowulf cluster or robotics and computer vision fields a concrete view of the strong synergy between the areas as well as to spur further fruitful exploitation of this connection. The book is written at a level appropriate for an advanced undergraduate or graduate student. The key concepts in robotics, computer vision and cluster computing are introduced before being used to make the text useful to a wide audience in these fields.

Product Details

ISBN-13:	9789812836359
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	08/08/2011
Pages:	236
Product dimensions:	5.80(w) x 9.00(h) x 0.90(d)

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