Real-Time Acquisition of Compact Volumetric Mapswith Mobile RobotsChristian Martin and Sebastian ThrunSchool of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213AbstractThis paper describes an online algorithm for generating com-pact 3D maps of mobile robot environments. Maps generatedby our approach consist of small numbers of planar surfaces,which are augmented by fine-grained polygons for non-flat en-vironmental features. Our approach builds on the expectationmaximization (EM) algorithm, but develops a new, incremen-tal version that can be executed in real-time. Experimentalresults obtained in corridor-type environments illustrate thatcompact and accurate maps can be acquired in real-time, fromrange and camera data collected by a mobile robot.1 IntroductionThis paper presents an algorithm for generating compact mod-els of indoor environments in real-time from range and camerameasurements. The vast majority of successful robot mappingalgorithms represent maps by grids [4], raw point measure-ments [5, 7], or line segments [1]. While such representationsappear to be sufficient for navigation, they suffer from two ma-jor disadvantages. First, there are intrinsic scaling limitations.For example, while two-dimensional occupancy maps requirerelatively little memory, the memory requirements of the sameapproach in 3D are prohibitive (despite recent work on thistopic[9]). Second, and more importantly, such maps fail tocapture the true nature of indoor environments. Indoor envi-ronments are often composed of walls, furniture, doors, win-dows etc, many of which are characterized by specific geomet-ric features (e.g., are flat). An understanding of such objectsand their geometric properties (e.g., flatness) will inevitablylead to new, more powerful mapping algorithms that can gen-erate more accurate maps.This paper provides a step in the direction of building morecompact maps, using a simple object representation. We de-scribe an algorithm that identifies flat rectangular surfacesform the sensor data, such as walls, ceilings, and doors. Themathematical approach for finding such objects is the expec-tation maximization (EM) algorithm [2]. The EM approachcombines a phase of searching for a compact map with planarrectangular surfaces, with one that associates measurementswith individual surfaces. By doing so, it can generate accu-rate surface maps even at the boundary of different surfaces.In addition, our approach allows for objects that are not partof any rectangular surface, which are then represented usingfine-grained polygons.EM has previously been proposed for building 3D maps [6].A well-known limitation of the classical EM algorithm is itsinherent offline nature [8]. This is because EM requires mul-tiple passes through the entire data set when generating maps.This is problematic for many application scenarios, such asrobot exploration [11], where map building and control is in-terleaved. To overcome this problem, this paper developsthe basic EM algorithm into an online (and real-time) algo-rithm. The online property is obtained by limiting the num-ber of times a measurement is considered in EM calculations.A carefully crafted strategy for determining when to considerwhat measurement in the EM procedure leads to an algorithmthat can be executed in real-time on a low-cost PC, as docu-mented in the experimental results section of this paper.Our approach rests on two key assumptions. First, it assumesthat a good estimate of the robot pose is available. The issue ofpose estimation (localization) in mapping has been studied ex-tensively in the robotics literature. In all our experiments, weuse a real-time algorithm described in [12] to estimate pose;thus, our assumption is not unrealistic at all, but it lets us focuson the 3D mapping aspects of our work. Second, we assumethat the environment is largely composed of flat surfaces. Theflat surface assumption leads to a convenient close-form solu-tion of the essential steps of our EM algorithm. Flat surfacesare commonly found in indoor environments, specifically incorridors. We also notice that our algorithm retains measure-ments that cannot be mapped onto any surface and maps theminto finer grained polygonal approximations. Hence, the finalmap may contain non-flat regions in areas that are not suffi-ciently flat in the physical world.Our approach has been applied to building multi-planar tex-tural maps of several indoor environments in real-time. Therobot shown in Figure 1a is equipped with a forward-pointedlaser range finder for localization during mapping, an upward-pointed laser range finder for structural mapping, and apanoramic camera for recording the texture of the environ-ment (see Figure 1b). Our results illustrate that the algorithmis highly robust and effective in generating compact maps inreal-time.p. 1(a) (b)Figure 1: Mobile robot, equipped with two 2D laser range findersand a panoramic camera. The camera uses a panoramicmirror mounted only a few centimeters away from the op-tical axis of the laser range finder.2 Flat Surface ModelMathematically, a map is a finite collection of rectangular flatsurfaces, representing doors, walls, ceilings, plus a set of smallpolygons representing non-flat artifacts in the environment.We will denote the set of rectangular flat surfaces by θ, whereθ = {θ1, . . . , θJ} (1)Here J is the total number of rectangular surfaces θj. Eachθjis described by a total of 9 parameters, arranged in threegroups:θj= hαj, βj, γji (2)Here αjis the three-dimensional surface normal of the rect-angular surface, βjis the one-dimensional offset between thesurface and the origin of the coordinate system, and γjare fiveparameters specifying the size and orientation of the rectan-gular area within the (infinite) planar surface represented byαjand βj. The Euclidean distance of any coordinate z in 3Dspace to any surface θjwill be denotedd(z, θj) (3)In our implementation, we distinguish two cases: The casewhere the orthogonal projection of z falls into the rectangle,and the case where it does not. In the former case, d(z, θj)is given by αj· z − βj; in the latter case, d(z, θj) is the Eu-clidean distance between the bounding box of the rectangleand z, which is either a point-to-line distance or a point-to-point distance.Measurements correspond to points in 3D space. The i-th sen-sor measurement, denotedzi∈ <3(4)is a 3D coordinate of a point detected by a laser range finder.Such point