Luận án tiến sĩ: Semantic mapping using mobile robots

SEMANTIC MAPPING USING MOBILE ROBOTS by Denis Fernando Wolf A Dissertation Presented to the FACULTY OF THE GRADUATE SCHOOL UNIVERSITY OF SOUTHERN CALIFORNIA In Partial Fulfillment of the Requirements for the Degree DOCTOR OF PHILOSOPHY (COMPUTER SCIENCE) May 2006 Copyright 2006 Denis Fernando Wolf UMI Number: 3237125 ® UMI UMI Microform 3237125 Copyright 2006 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 Ackowledgments First of all I would like to thank my adviser Gaurav Sukhatme, whom I had the pleasure and the privilege to work with during the last four years. He was always nothing less than a great person since the first moment I met him. He will serve as a reference in the next steps of my career. Many thanks to all my lab-mates from RESL, for all their invaluable assistance and friendship.

Especially to Boyoon Jung, who was always ready to help with no matter what. I also thank Andrew Howard and Maria Yang for being part of my thesis committee. Warmest thanks to all my friends "perdidos". Their friendship and companion was always very important to me and made my life much more enjoyable during the four years I was in Los Angeles.

I am grateful to my friends Eduardo Marques e Vanderlei Bonato from USP. Even thousand of miles away, they always motivated me to achieve this goal. Finally, I cannot thank enough to my parents Eloi and Rosa, my brother William, and my girlfriend Monique, for all their unconditional love and support. This thesis is dedicated to them.

il Contents Ackowledgments ii List Of Tables vi List Of Figures vii Abstract x 1 Introduction 1 1.1 Challenges in Robotic Mapping .22000 eee ee ee 7 1. ga 11 14 Dissertation Outline .1 Mapping Static Environments .3 Extended Kalman Filter .4 Global Scan Alignment. Mapping Dynamic Environments .1 SLAM with DATMO.24 Temporal Occupancy Grids .3 Mapping Urban Environments.000000 eee eee eee 24 2. gà gà va 26 ill 3 Mapping Urban Outdoor Environments 27 SN" roi.1 GPS-based Localization .2 Prior map-based Localization .2 Point Cloud Mapping .1 Point Cloud MappingResults.2 Geometric Representation of Buildings.3 Planar Mapping Results .4 Natural Environmental Mapping Using NIMS.

50 4 Semantic Mapping Using Hidden Markov Models 52 4.1 Hidden Markov Models.2 Semantic Terrain Mapping.2220-- 60 43 Activity-Based Semantic Mapping. liaa ee ee ee 73 5 Semantic Mapping Using Support Vector Machines 75 5.1 Support Vector Machines .1 The non-linear case.3 Activity-Based Semantic Mapping .4 Multi-class SVM classification. 96 6 Semantic Mapping in Dynamic Environments 99 6. 0220002 eee ee eee 100 6.1 Static Map Ủpdate.2 Dynamic Map Update .1 First set of Experiments: Mapping .2 Second set of experiments: SLAM .200 gà ee 123 lv 7 Conclusion 125 7.1 Directions for Further Research .204058 128 Reference List 130 Appendix A Publications .0 eee ee ee 137 A.

- 0022 eee ee es 137 A. - HQ eee ee 137 A.0 00 ee ee ee 138 List Of Tables 4.1 Results of the HMM terrain semantic classification.2 Results of the HMM activity based semantic classification.1 Results of the SVM semantic classification for the walkway environment.2 Results of the SVM semantic classification for the garden environment.3 Results of the SVM semantic classification for the garden environment using just one property of the space.4 Results of the SVM activity-based semantic classification using the four properties of the space.9 Results of the SVM semantic classification for the learning and complete datasets using the properties (1) activity and (4) average size.6 Results of the SVM semantic classification using combinations of the prop- erties of the space.7 Results of the SVM semantic classification excluding the non used space.8 Results of the SVM multi class semantic classification.1 Inverse observation model for the static map.2 Inverse observation model for dynamic map .3 Static and dynamic landmark classification.4 Mapping dynamic environment results.- 116 vì List Of Figures 1.1 Occupancy grid map, fire evacuation map, and equivalent floor-plan.2 Part ofacity map.1 A Segway RMP equipped with laser range finders, GPS, and IMU.2 Robot trajectory estimates using particle filter based GPS approximation.3 Robot trajectory estimates using GPS and MCL.4 Coarse-scale localization using MCL. The particle filter estimate is indi- cated by the arrow.9 Part of USC campus and the corresponding 3D model.6 USC Gerontology building and the corresponding 3D model.7 USC bookstore and the corresponding 3D model.8 3D maps of Ft. Benning based on pose estimation and range data.9 USC Accounting Building.10 3D maps of Ft.

Benning built based on pose estimation and range data.11 3D maps of Ft. Benning built based on pose estimation and range data (closer view). TK TT TT va 47 3.12 NIMS node deployed in the Íorest.13 3D map build using a NIMS node.1 Robotic platforms used during the experiments with front mounted laser pitched down.2 Real environments and 3D models with the ground truth areas in dark gray 4.3 Gaussian pdfs for the A and U points of the walkway terrain.4 HMM based semantic classification, with and without MRF segmentation.5 Semantic classification of the Section A of the garden terrain.6 Environment used for the activity based semantic mapping and the space representation created by mobile robots. The gray frame corresponds to the mapped area, the black lines divide the street from the sidewalks, and the black squares are the position of the robots.7 Semantic classification based on different properties of the space.

The right sidewalk is not correctly classified.8 Semantic classification based on different properties of the space. The street in the center is correctly identified.3 Semantic classification results for the walkway terrain. The walkway in the center is correctly Identiied. QẶ Q Q HQ ga 5.4 Data points in the property space (A in gray and U in black).9 Semantic classification results for the garden terrain.

The walkway in the center is correctly identified.6 Results of the SVM semantic classification (W in light gray and S in dark gray). Different from the RBF kernel, the linear kernel correctly distinguish the street from the sidewalks.7 Results of the SVM semantic classification for the learning and complete datasets using the properties (1) activity and (4) average size.8 Results of the SVM semantic classification for the three categories. Results of the categories A and B have correctly distinguished the street and the sidewalks.9 Results of the SVM semantic classification (W in light gray, S in dark gray, and non used space in white). HH vo 94 Vili 5.10 Multi class classification ground truth (S in dark gray, w in light gray, and Finblack).

ee ee ee.11 Results of the SVM multi class semantic classification using the polynomial kernel. Most part of the static entities in the environment have been identified 97 6.1 Update for the static and dynamic maps.2 Map of landmarks.00002 peepee eee eee 111 6.3 Pioneer robots at the California Science Center.4 Maps of the computer science building at USC.5 Simulation with 6 moving objects: the white circle R represents the robot, the moving entities Ä⁄ƒ are detected as dynamic, and the box B .6 Simulation with 6 moving objects.7 Results of no localization and no dynamic obstacles detection in the map- ping task.8 Map with people moving around the robot. The robot (R) detected all the moving entities (P) and represented them appropriately in the map 2. 122 ix Abstract Robotic mapping is the process of automatically constructing an environment represen- tation using mobile robots.

We address the problem of semantic mapping, which consists of using mobile robots to create maps that represent not only metric occupancy but also other properties of the environment. Specifically, we develop techniques to build maps that represent mobility, navigability, and activity of the environment. In doing so, we also develop techniques which partially address two important cases in robotic mapping; dynamic environments and large-scale environments. Our approach to semantic mapping is to combine machine learning techniques with standard mapping algorithms.

Supervised learning methods are used to automatically as- sociate properties of space to the desired classification patterns. We present two methods, the first based on hidden Markov models and the second on support vector machines. Both approaches have been tested and validated in two problem domains: terrain mapping and activity-based mapping. For the most part, previous mobile robotics mapping research has concentrated on static environments.

The explicit semantic identification of dynamic entities improves the accuracy of the localization and mapping processes. We extend the well-known occupancy grid approach to simultaneously maintain parallel occupancy grids for static and dynamic portions of the environment. A Bayesian inference mechanism is used to infer the map from sensed data and prior distributions on these grids. Finally, we address the problem of scale.

Most previous mapping algorithms have been designed for small structured environments (e. indoor office-like spaces). Through robust outdoor localization, we provide initial solutions for mapping large urban spaces. xi Chapter 1 Introduction Creating an internal representation (map) of the physical environment is one of the most basic and important capabilities in mobile robotics.

Most tasks to be performed by mobile robots requires some type of internal knowledge of the environment. Given the impor- tance of map making in the robotics field, scientists have been actively working on this topic for about two decades, and several mapping techniques have been proposed in the literature over this time. Robotic mapping has been performed in different types of envi- ronments with many distinct robotic platforms. Undersea mapping has been performed by submarine robots [55].

Aerial robots such as helicopters, planes, and blimps have also been successfully used for mapping [49] [56] [76]. And, of course, a considerable amount of robotic mapping has been performed with ground robots (see [74] for a survey). In general, the main focus of the research on mapping has been on representing the geometry of the environment with high accuracy. Although robot-built maps are success- fully used for tasks like path planning, navigation, and localization, they are very limited in describing details of the environment other than distinguishing between occupied and empty areas.

Virtually any property of space can be represented in a map, but the large majority of the maps built by mobile robots consists of only metric representations of the occupancy of the space. During the mapping task, most mapping techniques neglect a considerable amount of information that describe other aspects of the environment like the navigability, or the nature of the activity that occurs there. As the tasks performed by mobile robots become more complex, it also becomes necessary to have more sophisticated representations for the environment. This dissertation addresses the problem of semantic mapping using mobile robots, which consists of creating maps that represent not only metric occupancy but also other properties (semantics) of the environment.

Specifically, we develop techniques to build maps that represent mobility, navigability, and activity of the environment.1 Challenges in Robotic Mapping Although there have been considerable advances in robotic mapping in the last decade, there are still challenges and open questions to be answered in this field of research. Some of the important challenges in the area of robotic mapping are: the imprecision of the sensor information, environment representation, dynamic environments, and information retrieval from sensor data. Sensor imprecision: Sensors have limitations. They are always subject to impre- cision.

One of the most important characteristics about the inherent error of sensor measurements is that they are statistically dependent. This implies that some sensor er- rors impact the interpretation of others. For example if the robot localization drifts, the range sensor data is incorrectly registered with the map. One of the hardest problems caused by imprecise sensors is to estimate the position of the robot related to the map.

Dead reckoning is widely used to estimate the robot’s pose when it moves. Unfortunately, the information provided by dead reckoning is not accurate, usually due to drift. Other types of sensors used to estimate the robot’s pose (e.