Reliable Robot Localization

Preface xi

Notations xiii

Abbreviations xvii

Introduction xix

Part 1. Interval Tools 1

Introduction to Part 1 3

Chapter 1. Static Set-membership State Estimation 5

1.1. Introduction 5

1.2. Interval analysis 8

1.2.1. Once upon a time 8

1.2.2. Intervals 10

1.2.3. Inclusion functions 14

1.2.4. Pessimism and wrapping effect 16

1.3. Constraint propagation 19

1.3.1. Constraint networks 19

1.3.2. Contractors 21

1.3.3. Application to static range-only robot localization 24

1.4. Set-inversion via interval analysis 25

1.4.1. Subpaving 25

1.4.2. SIVIA algorithm for set-inversion 28

1.4.3. Illustration involving contractions 29

1.4.4. Kernel characterization of an interval function 33

1.5. Discussions 35

1.5.1. From sensors to reliable results 36

1.5.2. Numerical libraries 37

1.5.3. Reliable tool for proof purposes 38

1.6. Conclusion 38

Chapter 2. Constraints Over Sets of Trajectories 41

2.1. Towards dynamic state estimation 41

2.1.1. Overall motivations 41

2.1.2. The approach presented in this book 43

2.2. Tubes 44

2.2.1. Definitions 44

2.2.2. Tube analysis 45

2.2.3. Contractors 48

2.3. Implementation 50

2.3.1. Data structure 52

2.3.2. Build a tube from real datasets 54

2.3.3. Tubex, dedicated tube library 57

2.4. Application: dead-reckoning of a mobile robot 57

2.4.1. Test case 58

2.4.2. Constraint network 58

2.4.3. Resolution 59

2.5. Discussions 60

2.5.1. Limits 60

2.5.2. Extract the most probable trajectory from a tube 61

2.5.3. Application to path planning 62

2.6. Conclusion 63

Part 2. Constraints-related Contributions 65

Introduction to Part 2 67

Chapter 3. Trajectories under Differential Constraints 69

3.1. Introduction 69

3.1.1. The differential problem 69

3.1.2. Attempts with set-membership methods 70

3.1.3. Contribution of this work 72

3.2. Differential contractor for L d/dt: ?(?) = v(?) 73

3.2.1. Definition and proof 74

3.2.2. Contraction of the derivative 79

3.2.3. Implementation 80

3.3. Contractor-based approach for state estimation 82

3.3.1. Constraint network of state equations 84

3.3.2. Fixed-point propagations 85

3.3.3. Theoretical example of interest ? = ?sin(x) 87

3.4. Robotic applications 90

3.4.1. Causal kinematic chain 90

3.4.2. Higher-order differential constraints 93

3.4.3. Kidnapped robot problem 93

3.4.4. Actual experiment with the Daurade AUV 94

3.5. Conclusion 99

Chapter 4. Trajectories Under Evaluation Constraints 101

4.1. Introduction 101

4.1.1. Contribution of this work 101

4.1.2. Motivations to deal with time uncertainties 102

4.2. Generic contractor for trajectory evaluation 105

4.2.1. Tube contractor for the constraint Leval : z = y(t) 105

4.2.2. Implementation 111

4.2.3. Application to state estimation 113

4.3. Robotic applications 114

4.3.1. Range-only robot localization with low-cost beacons 114

4.3.2. Reliable correction of a drifting clock 121

4.4. Conclusion 127

Part 3. Robotics-related Contributions 129

Introduction to Part 3 131

Chapter 5. Looped Trajectories: From Detections to Proofs 133

5.1. Introduction 133

5.1.1. The difference between detection and verification 133

5.1.2. Proprioceptive versus exteroceptive measurements 134

5.1.3. The two-dimensional case 135

5.2. Proprioceptive loop detections 135

5.2.1. Formalization 136

5.2.2. Loop detections in a bounded-error context 137

5.2.3. Approximation of the solution set T 138

5.3. Proving loops in detection sets 141

5.3.1. Formalism: zero verification 141

5.3.2. Topological degree for zero verification 141

5.3.3. Loop existence test 145

5.3.4. Reliable number of loops 149

5.4. Applications 151

5.4.1. The Redermor mission 152

5.4.2. The Daurade mission 156

5.4.3. Optimality of the approach 159

5.5. Conclusion 163

Chapter 6. A Reliable Temporal Approach for the SLAM Problem 165

6.1. Introduction 165

6.1.1. Motivations 165

6.1.2. SLAM formalism 167

6.1.3. Inter-temporalities 169

6.2. Temporal SLAM method 172

6.2.1. General assumptions 172

6.2.2. Temporal resolution 173

6.2.3. Lp?z: inter-temporal implication constraint 174

6.2.4. The Cp?z contractor 178

6.2.5. Temporal SLAM algorithm 186

6.3. Underwater application: bathymetric SLAM 190

6.3.1. Context 190

6.3.2. Daurade's underwater mission, October 20, 2015 194

6.3.3. Daurade's underwater mission, October 19, 2015 199

6.3.4. Overview of the environment 202

6.4. Discussions 203

6.4.1. Relation to the state of the art 203

6.4.2. About a Bayesian resolution 205

6.4.3. Biased sensors 205

6.4.4. Fluctuating measurements 205

6.5. Conclusion 207

Conclusion 211

References 217

Index 229