Improved Techniques for Grid Mapping with Rao ...

1 1. Improved Techniques for Grid Mapping with Rao-Blackwellized particle filters Giorgio Grisetti Cyrill Stachniss Wolfram Burgard . University of Freiburg, Dept. of Computer Science, Georges-Ko hler-Allee 79, D-79110 Freiburg, Germany Dipartimento Informatica e Sistemistica, Universita La Sapienza , Via Salaria 113, I-00198 Rome, Italy Eidgeno ssische Technische Hochschule Zurich (ETH), IRIS, ASL, 8092 Zurich, Switzerland Abstract Recently, Rao-Blackwellized particle filters have An adaptive resampling technique which maintains a been introduced as an effective means to solve the simultaneous reasonable variety of particles and in this way enables localization and Mapping problem.

2 This approach uses a particle the algorithm to learn an accurate map while reducing filter in which each particle carries an individual map of the environment. Accordingly, a key question is how to reduce the the risk of particle depletion. number of particles . In this paper, we present adaptive Techniques The proposal distribution is computed by evaluating the like- for reducing this number in a Rao-Blackwellized particle filter lihood around a particle-dependent most likely pose obtained for learning grid maps. We propose an approach to compute by a scan-matching procedure combined with odometry in- an accurate proposal distribution taking into account not only the movement of the robot but also the most recent observation.

3 Formation. In this way, the most recent sensor observation is This drastically decreases the uncertainty about the robot's pose taken into account for creating the next generation of particles . in the prediction step of the filter . Furthermore, we present an This allows us to estimate the state of the robot according to approach to selectively carry out resampling operations which a more informed (and thus more accurate) model than the seriously reduces the problem of particle depletion. Experimental one obtained based only on the odometry information. The results carried out with real mobile robots in large-scale indoor as well as in outdoor environments illustrate the advantages of use of this refined model has two effects.

4 The map is more our methods over previous approaches. accurate since the current observation is incorporated into the Index Terms SLAM, Rao-Blackwellized particle filter , adap- individual maps after considering its effect on the pose of tive resampling, motion-model, Improved proposal the robot. This significantly reduces the estimation error so that less particles are required to represent the posterior. The second approach, the adaptive resampling strategy, allows us I. I NTRODUCTION. to perform a resampling step only when needed and in this Building maps is one of the fundamental tasks of mobile way keeping a reasonable particle diversity. This results in a robots.

5 In the literature, the mobile robot Mapping problem is significantly reduced risk of particle depletion. often referred to as the simultaneous localization and Mapping The work presented in this paper is an extension of our (SLAM) problem [4, 6, 9, 15, 16, 26, 29, 32, 39]. It is previous work [14] as it further optimizes the proposal dis- considered to be a complex problem, because for localization tribution to even more accurately draw the next generation a robot needs a consistent map and for acquiring a map a of particles . Furthermore, we added a complexity analysis, a robot requires a good estimate of its location. This mutual formal description of the used Techniques , and provide more dependency between the pose and the map estimates makes detailed experiments in this paper.

6 Our approach has been the SLAM problem hard and requires searching for a solution validated by a set of systematic experiments in large-scale in a high-dimensional space. indoor and outdoor environments. In all experiments, our Murphy, Doucet, and colleagues [6, 32] introduced Rao- approach generated highly accurate metric maps. Additionally, Blackwellized particle filters as an effective means to solve the number of the required particles is one order of magnitude the simultaneous localization and Mapping problem. The main lower than with previous approaches. problem of the Rao-Blackwellized approaches is their com- This paper is organized as follows.

7 After explaining how a plexity measured in terms of the number of particles required Rao-Blackwellized filter can be used in general to solve the to build an accurate map. Therefore, reducing this quantity SLAM problem, we describe our approach in Section III. We is one of the major challenges for this family of algorithms. then provide implementation details in Section IV. Experi- Additionally, the resampling step can potentially eliminate ments carried out on real robots are presented in Section VI. the correct particle. This effect is also known as the particle Finally, Section VII discusses related approaches. depletion problem or as particle impoverishment [44].

8 In this work, we present two approaches to substantially increase the performance of Rao-Blackwellized particle filters II. M APPING WITH R AO -B LACKWELLIZED PARTICLE. applied to solve the SLAM problem with grid maps: F ILTERS. A proposal distribution that considers the accuracy of the According to Murphy [32], the key idea of the Rao- robot's sensors and allows us to draw particles in a highly Blackwellized particle filter for SLAM is to estimate the joint accurate manner. posterior p(x1:t , m | z1:t , u1:t 1 ) about the map m and the 2. trajectory x1:t = x1 , .. , xt of the robot. This estimation is increases over time, this procedure would lead to an obviously performed given the observations z1:t = z1.

9 , zt and the inefficient algorithm. According to Doucet et al. [7], we obtain odometry measurements u1:t 1 = u1 , .. , ut 1 obtained by a recursive formulation to compute the importance weights by the mobile robot. The Rao-Blackwellized particle filter for restricting the proposal to fulfill the following assumption SLAM makes use of the following factorization (x1:t | z1:t , u1:t 1 ) = (xt | x1:t 1 , z1:t , u1:t 1 ). p(x1:t , m | z1:t , u1:t 1 ) = (x1:t 1 | z1:t 1 , u1:t 2 ). (3). p(m | x1:t , z1:t ) p(x1:t | z1:t , u1:t 1 ). (1). Based on Eq. (2) and (3), the weights are computed as This factorization allows us to first estimate only the trajectory (i).

10 Of the robot and then to compute the map given that trajectory. (i) p(x1:t | z1:t , u1:t 1 ). wt = (i). (4). Since the map strongly depends on the pose estimate of (x1:t | z1:t , u1:t 1 ). the robot, this approach offers an efficient computation. This (i) (i) (i). p(zt | x1:t , z1:t 1 )p(xt | xt 1 , ut 1 ). technique is often referred to as Rao-Blackwellization. = (i) (i). Typically, Eq. (1) can be calculated efficiently since the pos- (xt | x1:t 1 , z1:t , u1:t 1 ). terior over maps p(m | x1:t , z1:t ) can be computed analytically (i). p(x1:t 1 | z1:t 1 , u1:t 2 ). using Mapping with known poses [31] since x1:t and z1:t (i). (5). are known. (x1:t 1 | z1:t 1 , u1:t 2 ).