Final Report – The Cartographer An Autonomous Mapping Robot Submitted To: Dr. Christine Julien Dr. Chien-Liang Fok ––– The UT Pharos Project ––– Emily Richardson Prepared By: Alex Aur Kevin Boos Aaron Chen Xiaomeng Wu EE464 Senior Design Project Electrical and Computer Engineering Department University of Texas at Austin Spring 2011ii CONTENTS TABLES .................................................................................................................................. iv FIGURES ................................................................................................................................. v EXECUTIVE SUMMARY ................................................................................................... vi 1.0 INTRODUCTION .......................................................................................................... 1 2.0 DESIGN PROBLEM STATEMENT ........................................................................... 2 2.1 REQUIREMENTS AND SPECIFICATIONS ...................................................... 2 2.2 CONSTRAINTS ....................................................................................................... 3 3.0 DESIGN PROBLEM SOLUTION ............................................................................... 5 3.1 HIGH-LEVEL SYSTEM SOLUTION .................................................................. 5 3.2 HARDWARE DESIGN ........................................................................................... 5 3.3 SOFTWARE DESIGN ............................................................................................ 7 3.3.1 Player Interface ............................................................................................... 7 3.3.2 Location Tracker ............................................................................................ 7 3.3.3 World View ...................................................................................................... 7 3.3.4 Path Planner .................................................................................................... 9 3.3.5 Map Generator ...................................................................................... 10 3.4 ECONOMIC ANALYSIS ..................................................................................... 10 4.0 DESIGN IMPLEMENTATION ................................................................................. 12 4.1 HARDWARE DESIGN MODIFICATIONS ...................................................... 12 4.2 SOFTWARE DESIGN MODIFICATIONS ........................................................ 13 4.2.1 Player Interface Modifications .................................................................... 13 4.2.2 Location Tracker Modifications .................................................................. 14 4.2.3 World View Modifications ........................................................................... 14 4.2.4 Path Planner Modifications ......................................................................... 14 4.2.4.1 MapSector-Node Algorithm ................................................................ 15 4.2.4.2 Frontier Exploration Algorithm .......................................................... 17 4.2.4.3 Path Planner Decision ........................................................................ 18 4.2.5 Map Generator Modifications ..................................................................... 20 5.0 TEST AND EVALUATION ........................................................................................ 21 5.1 COMPONENT LEVEL TESTS ........................................................................... 21 5.1.1 IR Sensor Testing .......................................................................................... 21 5.1.2 Roomba Odometry Testing .......................................................................... 22 5.2 MODULE LEVEL TESTING .............................................................................. 22 5.2.1 Player Interface Testing ............................................................................... 23 5.2.2 Location Tracker Module Testing ............................................................... 23 5.2.3 World View Module Testing ........................................................................ 23 5.3 SYSTEM LEVEL / PATH PLANNER TESTING ............................................. 24iii 6.0 TIME AND COST CONSIDERATIONS .................................................................. 27 7.0 SAFETY AND ETHICAL ASPECTS OF DESIGN ................................................. 28 8.0 RECOMMENDATIONS ............................................................................................. 29 9.0 CONCLUSIONS .......................................................................................................... 31 REFERENCES ...................................................................................................................... 32 APPENDIX A – Software Interaction and Data Flow Diagrams ................................... A-1 APPENDIX B – Infrared Sensor and Odometry Testing Graphs ................................. B-1 APPENDIX C – Project Materials Costs Table ............................................................... C-1 APPENDIX D – Project Schedule ..................................................................................... D-1iv TABLES 1 IR Sensor Beam Width Measurements ............................................................................................. 22v FIGURES 1 High-Level System Diagram ................................................................................................ 5 2 Infrared Sensor Placement and Orientation on Sensor Plane ............................................... 6 3 Output World View Map ...................................................................................................... 8 4 MapSector with A* Traversal ............................................................................................. 15 5 Node-Stack Exploration Method ........................................................................................ 16 6 Frontier Mapping ................................................................................................................ 17 7 Frontier