List of Contributors xi
Preface xiii
Acknowledgments xv
About the Companion Website xvii
Introduction 1
Eugene Kagan, Nir Shvalb, and Irad Ben-Gal
I.1 Early History of Robots 1
I.2 Autonomous Robots 2
I.3 Robot Arm Manipulators 6
I.4 Mobile Robots 8
I.5 Multi-Robot Systems and Swarms 12
I.6 Goal and Structure of the Book 16
References 17
1 Motion-Planning Schemes in Global Coordinates 21
Oded Medina and Nir Shvalb
1.1 Motivation 21
1.2 Notations 21
1.2.1 The Configuration Space 22
1.2.2 The Workspace 23
1.2.3 The Weight Function 23
1.3 Motion-Planning Schemes: Known Configuration Spaces 25
1.3.1 Potential-Field Algorithms 25
1.3.2 Grid-Based Algorithms 27
1.3.3 Sampling-Based Algorithms 29
1.4 Motion-Planning Schemes: Partially Known Configuration Spaces 30
1.4.1 BUG0 (Reads Bug-Zero) 31
1.4.2 BUG1 32
1.4.3 BUG2 32
1.5 Summary 33
References 33
2 Basic Perception 35
Simon Lineykin
2.1 Basic Scheme of Sensors 35
2.2 Obstacle Sensor (Bumper) 36
2.3 The Odometry Sensor 48
2.4 Distance Sensors 52
2.4.1 The ToF Range Finders 52
2.4.2 The Phase Shift Range Finder 56
2.4.3 Triangulation Range Finder 59
2.4.4 Ultrasonic Rangefinder 60
2.5 Summary 63
References 63
3 Motion in the Global Coordinates 65
Nir Shvalb and Shlomi Hacohen
3.1 Models of Mobile Robots 65
3.1.1 Wheeled Mobile Robots 65
3.1.2 Aerial Mobile Robots 67
3.2 Kinematic and Control of Hilare-Type Mobile Robots 69
3.2.1 Forward Kinematics of Hilare-Type Mobile Robots 69
3.2.2 Velocity Control of Hilare-Type Mobile Robots 71
3.2.3 Trajectory Tracking 72
3.3 Kinematic and Control of Quadrotor Mobile Robots 74
3.3.1 Dynamics of Quadrotor-Type Mobile Robots 74
3.3.2 Forces and Torques Generated by the Propellers 75
3.3.3 Relative End Global Coordinates 76
3.3.4 The Quadrotor Dynamic Model 78
3.3.5 A Simplified Dynamic Model 79
3.3.6 Trajectory Tracking Control of Quadrotors 80
3.3.7 Simulations 84
References 85
4 Motion in Potential Field and Navigation Function 87
Nir Shvalb and Shlomi Hacohen
4.1 Problem Statement 87
4.2 Gradient Descent Method of Optimization 89
4.2.1 Gradient Descent Without Constraints 89
4.2.2 Gradient Descent with Constraints 92
4.3 Minkowski Sum 94
4.4 Potential Field 95
4.5 Navigation Function 99
4.5.1 Navigation Function in Static Deterministic Environment 99
4.5.2 Navigation Function in Static Uncertain Environment 102
4.5.3 Navigation Function and Potential Fields in Dynamic Environment 104
4.5.3.1 Estimation 105
4.5.3.2 Prediction 105
4.5.3.3 Optimization 106
4.6 Summary 106
References 107
5 GNSS and Robot Localization 109
Roi Yozevitch and Boaz Ben-Moshe
5.1 Introduction to Satellite Navigation 109
5.1.1 Trilateration 109
5.2 Position Calculation 111
5.2.1 Multipath Signals 111
5.2.2 GNSS Accuracy Analysis 112
5.2.3 DoP 112
5.3 Coordinate Systems 113
5.3.1 Latitude, Longitude, and Altitude 113
5.3.2 UTM Projection 113
5.3.3 Local Cartesian Coordinates 114
5.4 Velocity Calculation 115
5.4.1 Calculation Outlines 115
5.4.2 Implantation Remarks 116
5.5 Urban Navigation 116
5.5.1 Urban Canyon Navigation 117
5.5.2 Map Matching 117
5.5.3 Dead Reckoning - Inertial Sensors 118
5.6 Incorporating GNSS Data with INS 118
5.6.1 Modified Particle Filter 118
5.6.2 Estimating Velocity by Combining GNSS and INS 119
5.7 GNSS Protocols 120
5.8 Other Types of GPS 121
5.8.1 A-GPS 121
5.8.2 DGPS Systems 122
5.8.3 RTK Navigation 122
5.9 GNSS Threats 123
5.9.1 GNSS Jamming 123
5.9.2 GNSS Spoofing 123
References 123
6 Motion in Local Coordinates 125
Shraga Shoval
6.1 Global Motion Planning and Navigation 125
6.2 Motion Planning with Uncertainties 128
6.2.1 Uncertainties in Vehicle Performance 128
6.2.1.1 Internal Dynamic Uncertainties 128
6.2.1.2 External Dynamic Uncertainties 129
6.2.2 Sensors Uncertainties 129
6.2.3 Motion-Planning Adaptation to Uncertainties 130
6.3 Online Motion Planning 131
6.3.1 Motion Planning with Differential Constraints 132
6.3.2 Reactive Motion Planning 134
6.4 Global Positioning with Local Maps 135
6.5 UAV Motion Planning in 3D Space 137
6.6 Summary 139
References 140
7 Motion in an Unknown Environment 143
Eugene Kagan
7.1 Probabilistic Map-Based Localization 143
7.1.1 Beliefs Distribution and Markov Localization 145
7.1.2 Motion Prediction and Kalman Localization 150
7.2 Mapping the Unknown Environment and Decision-Making 154
7.2.1 Mapping and Localization 155
7.2.2 Decision-Making under Uncertainties 161
7.3 Examples of Probabilistic Motion Planning 169
7.3.1 Motion Planning in Belief Space 169
7.3.2 Mapping of the Environment 176
7.4 Summary 178
References 179
8 Energy Limitations and Energetic Efficiency of Mobile Robots 183
Michael Ben Chaim
8.1 Introduction 183
8.2 The Problem of Energy Limitations in Mobile Robots 183
8.3 Review of Selected Literature on Power Management and Energy Control in Mobile Robots 185
8.4 Energetic Model of Mobile Robot 186
8.5 Mobile Robots Propulsion 188
8.5.1 Wheeled Mobile Robots Propulsion 189
8.5.2 Propulsion of Mobile Robots with Caterpillar Drive 190
8.6 Energetic Model of Mechanical Energies Sources 192
8.6.1 Internal Combustion Engines 193
8.6.2 Lithium Electric Batteries 194
8.7 Summary 195
References 195
9 Multi-Robot Systems and Swarming 199
Eugene Kagan, Nir Shvalb, Shlomi Hacohen, and Alexander Novoselsky
9.1 Multi-Agent Systems and Swarm Robotics 199
9.1.1 Principles of Multi-Agent Systems 200
9.1.2 Basic Flocking and Methods of Aggregation and Collision Avoidance 208
9.2 Control of the Agents and Positioning of Swarms 218
9.2.1 Agent-Based Models 219
9.2.2 Probabilistic Models of Swarm Dynamics 234
9.3 Summary 236
References 238
10 Collective Motion with Shared Environment Map 243
Eugene Kagan and Irad Ben-Gal
10.1 Collective Motion with Shared Information 243
10.1.1 Motion in Common Potential Field 244
10.1.2 Motion in the Terrain with Sharing Information About Local Environment 250
10.2 Swarm Dynamics in a Heterogeneous Environment 253
10.2.1 Basic Flocking in Heterogeneous Environment and External Potential Field 253
10.2.2 Swarm Search with Common Probability Map 259
10.3 Examples of Swarm Dynamics with Shared Environment Map 261
10.3.1 Probabilistic Search with Multiple Searchers 261
10.3.2 Obstacle and Collision Avoidance Using Attraction/Repulsion Potentials 264
10.4 Summary 270
References 270
11 Collective Motion with Direct and Indirect Communication 273
Eugene Kagan and Irad Ben-Gal
11.1 Communication Between Mobile Robots in Groups 273
11.2 Simple Communication Protocols and Examples of Collective Behavior 277
11.2.1 Examples of Communication Protocols for the Group of Mobile Robots 278
11.2.1.1 Simple Protocol for Emulating One-to-One Communication in the Lego NXT Robots 278
11.2.1.2 Flocking and Preserving Collective Motion of the Robot's Group 284
11.2.2 Implementation of the Protocols and Examples of Collective Behavior of Mobile Robots 287
11.2.2.1 One-to-One Communication and Centralized Control in the Lego NXT Robots 287
11.2.2.2 Collective Motion of Lego NXT Robots Preserving the Group Activity 291
11.3 Examples of Indirect and Combined Communication 293
11.3.1 Models of Ant Motion and Simulations of Pheromone Robotic System 293
11.3.2 Biosignaling and Destructive Search by the Group of Mobile Agents 297
11.4 Summary 300
References 301
12 Brownian Motion and Swarm Dynamics 305
Eugene Khmelnitsky
12.1 Langevin and Fokker-Plank Formalism 305
12.2 Examples 307
12.3 Summary 316
References 316
13 Conclusions 317
Nir Shvalb, Eugene Kagan, and Irad Ben-Gal
Index 319
