Binary Directional Marker Placement for Mobile Robot Localization by River Allen B.Sc., University of Victoria, 2011 A Thesis Submitted in Partial Ful(cid:28)llment of the Requirements for the Degree of MASTER OF SCIENCE in the Department of Computer Science (cid:13)c River Allen, 2014 University of Victoria All rights reserved. This thesis may not be reproduced in whole or in part, by photocopying or other means, without the permission of the author. ii Binary Directional Marker Placement for Mobile Robot Localization by River Allen B.Sc., University of Victoria, 2011 Supervisory Committee Dr. Sue Whitesides, Co-Supervisor (Department of Computer Science) Dr. Mantis Cheng, Co-Supervisor (Department of Computer Science) iii Supervisory Committee Dr. Sue Whitesides, Co-Supervisor (Department of Computer Science) Dr. Mantis Cheng, Co-Supervisor (Department of Computer Science) ABSTRACT This thesis looks at the problem of optimally placing binary directional proximity markers to assist a robot as it navigates waypoints through an environment. A simple planar (cid:28)ducial marker is developed to serve as the binary directional proximity marker. A scoring function is proposed for marker placement as well as a method for random generation of hallway maps. Several common metaheuristic algorithms are run to (cid:28)nd optimal marker placements with respect to the scoring function for a numberofrandomlygeneratedhallwaymaps. Fromtheseresults, placementsarethen evaluated by physical experimentation on an iRobot Create equipped with relatively inexpensive webcams. iv ACKNOWLEDGEMENTS I would like to begin by thanking my supervisor Dr. Sue Whitesides. Sue has mentored me throughout the thesis process, imparting valuable life knowledge and wisdom along the way. She has been the best supervisor a student could ask for. It has been an pleasure and an honour to be Sue’s student and I do not think I will ever be capable of putting into words just how thankful I am for the opportunity. I would also like to thank my co-supervisor, Dr. Mantis Cheng who sparked passion and interest in this subject. I have learned an unquanti(cid:28)able amount from Dr. Cheng during my time at UVic. Without his incredible ability to teach and inspire, I would not be here. I especially want to thank Dr. Dimitri Marinakis for his immense knowledge and for his encouragement during my graduate studies. Additionally, I thank Dr. Junaed Sattar for his valuable commentary in his role as external examiner. My family has always been vital to my success. During this thesis they have continued to give me the constant love, support and motivation that I will always be grateful for. The recent introduction of my niece and nephew into our family have been of great signi(cid:28)cance during this time. Last but not least, I would like to thank my CGAR lab mates and personal friends over the years. I give special thanks to Nishat who has been an incredible friend and collaborator throughout this period. Without the generous funding from NSERC sources, Howard E. Petch research scholarship and various UVic scholarships this thesis would not have been possible. v Contents Supervisory Committee ii Abstract iii Acknowledgements iv Table of Contents v List of Tables viii List of Figures ix 1 Introduction 1 1.1 Problem Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Related Work 8 2.1 Directional Sensor Placement . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Fiducial Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Approach, Methodology and Parameter Estimation 18 3.1 Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.1 Motion Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.2 Observation Model . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.3 Uniform Visibility Model . . . . . . . . . . . . . . . . . . . . . 27 3.1.4 Resampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Localization Patches and the Scoring Function . . . . . . . . . . . . . 30 3.2.1 A Theoretical Maximum Distance Deviation . . . . . . . . . . 33 vi 3.3 RedCometTag (cid:21) Fiducial Planar Marker . . . . . . . . . . . . . . . . 34 3.3.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.2 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.3 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . 39 3.3.4 Range and Angle . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.5 False Positives, True Negatives, Interconfusion and Occlusion . 40 3.3.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4 Simulation 48 4.1 Metaheuristic Optimization . . . . . . . . . . . . . . . . . . . . . . . 48 4.1.1 Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . 50 4.1.3 Coordinate Descent . . . . . . . . . . . . . . . . . . . . . . . . 53 4.1.4 Greedy Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.1.5 Uniform Placement . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2 Randomly Generated Hallway Environments for Marker Placement . 55 4.2.1 Marker Placement Poses . . . . . . . . . . . . . . . . . . . . . 58 4.2.2 Marker Placement Sampling . . . . . . . . . . . . . . . . . . . 59 4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5 Experimentation 63 5.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.4.1 Discussion of Results . . . . . . . . . . . . . . . . . . . . . . . 69 6 Conclusions 71 6.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.2 Alternative Scoring Functions . . . . . . . . . . . . . . . . . . . . . . 72 6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Bibliography 75 Glossary 81 A Gradient Visibility Model 82 vii B Reuleaux Triangle 85 C Box-and-whisker Plot 87 D Random Hallway Maps 89 E Experiment Runs Data 96 viii List of Tables Table 4.1 Score results with standard deviations on all maps for the four metaheuristic algorithms. The lower the score the (cid:16)better(cid:17) the placement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Table 4.2 Computingtimeresultswithstandarddeviationofsimulationson all maps for the metaheuristic algorithms. The greedy heuristic and uniform placement were only run once, so they have a stan- dard deviation of 0 (not shown). Repeated trials were deemed unnecessary as they are clearly faster than the others. . . . . . . 62 Table E.1 No Markers - Measured error from waypoints (meters). . . . . . 96 Table E.2 Best Score Placement - Measured error from waypoints (meters). 97 Table E.3 Uniform Placement - Measured error from waypoints (meters). . 97 Table E.4 No Markers - number of Bumps between waypoints. . . . . . . . 98 Table E.5 Best Score Placement - number of Bumps between waypoints. . 98 Table E.6 Uniform Placement - number of Bumps between waypoints. . . . 99 ix List of Figures Figure 1.1 An example of an o(cid:30)ce environment a robot could traverse through. Each pixel is a decimeter2. The dark blue pixels represent area that is non-navigable. Red pixels represent the path the robot is expected travel. Possible marker poses for this map are provided and are shown as orange pixels; in this case they correspond to corners. . . . . . . . . . . . . . . . . 3 Figure 1.2 A 2D annulus. The grey shaded area represents an annulus sector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Figure 2.1 The typical model for a sector-shaped directional sensor de- (cid:28)nedbythe(cid:28)veparameters: (x,y,θ,α,R). Thisdi(cid:27)ersslightly from our own visibility region model where α would be α in 2 their model. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Figure 2.2 a) QR code (image from wikipedia.com). b) MaxiCode (image from wikipedia.com). c) ARToolkit (image from ARToolkit software package). d) ARTag (image from [1]). e) Cantag, circle inner version (image from [2]) f) Fourier tag (image from [3]). g) robust pseudo-random array (cid:28)ducial marker (im- age from [4]). . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Figure 2.3 a) The remotely operated benthic crawler: Wally. b) An ex- ample of a markers (yellow ‘9’ sign) used by the teleoperaters of Wally to help them localize. The images are from Ocean Networks Canada. . . . . . . . . . . . . . . . . . . . . . . . . 16 Figure 3.1 Anillustrationoftherobot(graycircle)attimet−1movingto a new position at time t using the control inputs ut ,ut . 19 linear angular x Figure 3.2 Example of 5000 samples taken from a 3D (x,y,θ) zero mean multivariate Gaussian plotted in 2D (x,y). Each of these par- ticles can be seen to represent a possible initial pose of the robot. The orientation of each sample is not shown. . . . . . 23 Figure 3.3 The spread of particles at di(cid:27)erent intervals as the robot trav- els 40 meters from the bottom left to the top right. The par- ticles have been projected into 2D (x,y). . . . . . . . . . . . 24 Figure 3.4 The uniform visibility marker model. . . . . . . . . . . . . . 27 Figure 3.5 Particles in the particle (cid:28)lter before and after observation when the marker is detected. . . . . . . . . . . . . . . . . . . 30 Figure 3.6 a) The environment as an occupancy grid (orange is navigable area). b) The discrete annulus sector (blue). c) The visibility grid (teal) overlayed in the environment. The visibility grid considers line of sight. The visibility grid is outlined by the discrete annulus sector (blue). . . . . . . . . . . . . . . . . . 32 Figure 3.7 a) Visibility grid 1; b) Visibility grid 2; and c) The overlay grid comprised of the two visibility grids and environment oc- cupancy grid (the blue lines are added to help distinguish the shape of the visibility grids). Two example waypoints W1 and W2 are included. Using this marker placement, W1 will have a score of the area of the yellow region where the two visibil- ity grids overlap. This marker placement will also give W2 a score of the area of the large, orange, southern region of the occupancy grid where no visibility grids are present. . . . . . 32 Figure 3.8 The patch formed around the waypoint w by the markers at positionsmarked(cid:16)x(cid:17) isaReuleauxtriangle. Usingtheuniform sensing model seen in Figure 3.5a. Here are the particles: a) beforeobservingandb)afterobserving. Afterobservation, the particles are more densely inside the Reuleaux triangle patch. 34 Figure 3.9 Examples of the RedCometTag. . . . . . . . . . . . . . . . . 35 Figure 3.10 A histogram of the hamming distance between all valid codes and their three rotations. . . . . . . . . . . . . . . . . . . . . 37