with Rao-Blackwellized Particle Filters Giorgio Grisetti a,b Gian Diego Tipaldi b Cyrill Stachniss c,a

Wolfram Burgard a Daniele Nardi b

a University of Freiburg,Department of Computer Science,D-79110Freiburg,Germany

b Dipartimento Informatica e Sistemistica,Universit´a“La Sapienza”,I-00198Rome,Italy

c Swiss Federal Institute of Technology(ETH)Zurich,CH-8092Zurich,Switzerland

1Introduction

Learning maps is a fundamental task of mobile robots and a lot of researchers focused on this problem.In the literature,the mobile robot mapping problem is often referred to as the simultaneous localization and mapping(SLAM)problem[1, 2,3,4,5,6,7,8].In general,SLAM is a complex problem because for learning a map the robot requires a good pose estimate while at the same time a consistent map is needed to localize the robot.This dependency between the pose and the map estimate makes the SLAM problem hard and requires to search for a solution in a high-dimensional space.

Preprint submitted to Elsevier Science October10,2006Murphy,Doucet,and colleagues[7,9]introduced Rao-Blackwellized particlefil-ters(RBPFs)as an effective means to solve the SLAM problem.The main problem of Rao-Blackwellized particlefilters lies in their complexity,measured in terms of the number of particles required to learn an accurate map.Reducing this quantity is one of the major challenges for this family of algorithms.

The contribution of this paper is a technique that reduces the computational and the memory requirements in the context of mapping with Rao-Blackwellized particle filters.In this way,it becomes feasible to maintain a comparably large set of par-ticles online.This is achieved by enabling a subset of samples to share large parts of the map and to use the same proposal distribution.Our system allows a standard laptop computer to perform all computations necessary to learn accurate maps with more than one thousand samples online.

This paper is organized as follows.After the discussion of related work,we briefly introduce mapping with RBPFs.We then describe our technique for efficiently drawing particles from a proposal distribution.After this,we present our map rep-resentation and the concept of particle clusters.Finally,we show experiments illus-trating the improvements of our approach to map learning with RBPFs.

2Related Work

The estimation techniques for the SLAM problem can be classified according to their underlying basic principle.The most popular approaches are extended Kalman filters(EKFs),maximum likelihood techniques,sparse extended informationfilters (SEIFs),and Rao Blackwellized particlefilters(RBPFs).The effectiveness of the EKF approaches comes from the fact that they estimate a fully correlated posterior over landmark maps and robot poses[10,11].Their weakness lies in the strong assumptions that have to be made on the robot motion model and the sensor noise. Moreover,in the basic framework the landmarks are assumed to be uniquely iden-tifiable.There exist techniques[12]to deal with unknown data association in the SLAM context,however,if certain assumptions are violated,thefilter is likely to diverge[13].

Thrun et al.[8]proposed a SEIF method which is based on the inverse of the co-variance matrix.In this way,measurements can be integrated efficiently.Eustice et al.[14]presented an improved technique to accurately compute the error-bounds within the SEIF framework and thus reduces the risk of becoming overly confident. Paskin[15]presented a solution to the SLAM problem using thin junction trees. This reduces the complexity compared to EKF-based approaches since thinned junction trees provide a linear-timefiltering operation.

An alternative approach is to use a maximum likelihood algorithm that computes a map by constructing a network of relations.The relations represent the spatial

2constraints between the poses of the robot[3,16].The main difference to RBPFs is that the maximum likelihood approach can only track a single mode of the dis-tribution about the trajectory of the robot.It computes the solution by minimizing the least square error introduced by the constraints.

Lisien et al.[17]realized an hierarchical map model in the context of SLAM and reported that this improves loop-closing.Bosse et al.[18]describe a generic frame-work for SLAM in large-scale environments.They use a graph structure of local maps with relative coordinate frames similar to the work described in[19].This approach is able to reduce the complexity of the overall problem and it better deals with the linearizations in the context of EKF-SLAM.Our approach is related to this framework since we also use local maps attached to a graph structure to model the environment.However,our motivation to use such a map representation is to allow multiple particles to share local maps and to compute the proposal distributions in an efficient way.

Murphy[7]introduced Rao-Blackwellized particlefilters as an effective means to solve the SLAM problem.Each particle in a RBPF represents a potential trajectory of the robot and a map of the environment.The framework has been subsequently extended by Montemerlo et al.[5,6]for approaching the SLAM problem with landmarks.To learn accurate grid maps,H¨a hnel et al.[4]presented an improved motion model that reduces the number of required particles.A combination of the approach of H¨a hnel et al.and Montemerlo et al.as been presented by Grisetti et al.[2],which extends the ideas of FastSLAM-2[5]to the grid map case.We present in this paper an approximative solution to RBPF-based mapping which describes how to draw particles and how to represent the maps of the particles so that the system can be executed significantly faster and needs less memory resources. There exist other approaches to mapping with RBPFs like DP-SLAM[1]that pro-vide a compact map representation.This approach stores an ancestry tree of parti-cles.Furthermore,each cell of their grid map maintains a tree of poses from which that cell has been observed.This allows the system to store the map hypotheses in an compact manner.Additionally,the resampling can be carried out more ef-ficiently.In contrast to that,our map representation enables us to reuse already computed proposal distributions for multiple samples.This is done by carrying out a coordinate transformation between the reference frames stored in our graph struc-ture.

The contribution of this paper is a computational and memory efficient Rao-Black-wellized particlefilter for SLAM.Our approach allows the robot to efficiently de-termine the proposal distributions to sample the next generation of particles in an approximative manner.Additionally,we present a compact map model in which multiple particles share local maps.This enables us to maintain substantially more samples with less memory and computational requirements compared to state-of-the-art mapping approach using Rao-Blackwellized particlefilters.

33Learning Maps with Rao-Blackwellized Particle Filters

The key idea of the Rao-Blackwellized particlefilter for SLAM is to estimate the joint posterior p(x1:t,m|z1:t,u1:t−1)about the trajectory x1:t=x1,...,x t of the robot and the map m of the environment given the observations z1:t=z1,...,z t and odometry measurements u1:t−1=u1,...,u t−1.It does so by using the following factorization:

p(x1:t,m|z1:t,u1:t−1)=p(x1:t|z1:t,u1:t−1)p(m|x1:t,z1:t)(1) In this equation,the posterior p(x1:t|z1:t,u1:t−1)is similar to the localization prob-lem,since only the trajectory of the vehicle needs to be estimated.This estimation is performed using a particlefilter which incrementally processes the observations and the odometry readings as they are available.The second term p(m|x1:t,z1:t) can be computed efficiently since the poses x1:t of the robot are known when esti-mating the map m.Therefore,a Rao-Blackwellized particlefilter for SLAM main-tains an individual map for each sample and updates this map based on the trajec-tory estimate of the sample upon“mapping with known poses”.

A mapping system that applies a RBPF requires a proposal distribution in order to draw the next generation of samples.The general framework leaves open which proposal should be used and how it should be computed.A proposal distribu-tion typically used in the context of Monte-Carlo localization is the motion model p(x t|x t−1,u t−1).This proposal,however,is sub-optimal since it does not consider the observations of the robot to predict its motion.As pointed out by several au-thors[20,5],problem-specific proposal distributions are needed in order to build an efficient mapping system.The approach presented in this paper,makes use of our previously defined[2]proposal distribution.It transfers the ideas of FastSLAM-2[5]to the grid map case.Under the Markov assumption,the optimal proposal distribution[20]is

p(z t|m(i)t−1,x t)p(x t|x(i)t−1,u t−1) p(x t|m(i)t−1,x(i)t−1,z t,u t−1)={x j}and then evaluate point-wise the observation likelihood.In order to efficiently sample the next generation of particles,one can approximate this distribution by a Gaussian.For each particle i,the parametersµ(i)t andΣ(i)t of the Gaussian are computed as

µ(i)t=

1

η(i)

K

j=1p(z t|m(i)t−1,x j)·(x j−µ(i)t)(x j−µ(i)t)T.(5)

Hereη= K j=1p(z t|m(i)t−1,x j)is a normalizer.Note thatµ(i)t andΣ(i)t are calcu-lated for each particle individually which is computationally expensive but leads to an informed proposal distribution.This allows us to draw particles in an more accurate manner which seriously reduces the number of required samples.

4Speeding Up the Computation of the Proposal

The problem of the method presented above is the computational complexity of the informed proposal distribution since it has to be done for each sample individually. As a result,such a mapping system runs online only for small particle sets.Fur-thermore,each particle maintains a full grid map which requires to store large grid structures in the memory.To overcome this limitation,we present a way to utilize intermediate results in order to efficiently determine the proposal for the individual samples.Our implementation extends the open-source implementation[21]of the mapping system of Grisetti et al.[2]which originally makes use of the proposal distribution presented in the previous section.

The proposal distribution is needed to model the relative movement of the vehi-cle under uncertainty.In most situations,this uncertainty is similar for all samples within one movement.It therefore makes sense to use the same uncertainty to prop-agate the particles.We derive a way to sample multiple particles from the same proposal.As a result,the time consuming computation of the proposal distribution can be carried out for a few particles that are representatives for groups of similar samples.

Furthermore,we observed that local maps which are represented in a particle-centered coordinate frame look similar for many samples.We therefore present a compact map model in which multiple particles can share their local maps.Instead of storing a full grid map,each sample maintains only a set of reference frames for the different local maps.This substantially reduces the memory requirements of the mapping algorithm.

54.1Different Situations During Mapping

Before we derive our new proposal distributions,we start with a brief analysis of the behavior of a RBPF.One can distinguish three different types of situations during mapping:

•The robot is moving through unknown areas,

•is moving through known areas,or

•is closing a loop.Here,closing a loop means that the robotfirst moves through unknown areas and then reenters known terrain.It can be seen as moving along a so far non traversed shortcut from current pose of the robot to an already known area(see also[22]).

In each of those situations,thefilter behaves differently.Whenever the robot is moving through unknown terrain,the uncertainty about the pose of the robot grows. This is due to the fact that the errors are accumulated along the trajectory.The resulting uncertainty can only be bounded by observations which cover a(partially) known region.

In the second case,a map of the surroundings of the robot is known and in this way the SLAM problem turns into a localization problem which is typically easier to handle.Whenever the robot is closing a loop,the particle cloud is often widely spread.By reentering known areas,thefilter can typically determine which parti-cles are consistent with their own map and which are not.As a result,such a situ-ation leads to an unbalanced distribution of particle weights.The next resampling action then eliminates a series of unlikely hypotheses and the uncertainty decreases. For each of these three situations,we will present a proposal distribution that needs to be computed only for a small set of representatives rather than for all particles. Throughout this paper,we make the following three assumptions.

Assumption1The current situation is known,which means that the robot can determine whether it is moving through unknown terrain,within a known area, or is closing a loop.

Assumption2The corresponding local maps of two samples are similar if con-sidered in a particle-centered reference frame.In the following,we refer to this property as local similarity of the maps.

Assumption3An accurate algorithm for pose tracking is used and the observa-tions are affected by a limited sensor noise.

4.2Computing the Proposal for Unknown Terrain

For proximity sensors like laser rangefinders,the observations of the robot cover only a local area around the robot.As a result,we only need to consider the sur-

6

(a)(b)(c)

(d)

Figure1.Image(a)depicts the pose of a particle,its local map,and the computed proposal which represented by the blue/dashed ellipse.Image(b)illustrates the proposal distribution represented in the ego-centric reference frame of that sample.Image(c)shows a second particle and its map.By carrying out a coordinate transform,the proposal of thefirst particle can be used by the second particle as long as their maps are(locally)similar(d). roundings of the robot when computing the proposal distribution.Let˜m(i)t−1refer to the local map of particle i around its previous pose x(i)t−1.In the surroundings of the robot,we can approximate

p(x t|m(i)t−1,x(i)t−1,z t,u t−1)≃p(x t|˜m(i)t−1,x(i)t−1,z t,u t−1).(6) Let⊕and⊖be the standard pose compounding operators(see[16]):a⊖b is an operator that translates all the points in the domain of the function a so that the new origin of the domain of a is b and⊕is its inverse.The local similarity between maps(Assumption2)allows us to write˜m(i)t−1⊖x(i)t−1≃˜m(j)t−1⊖x(j)t−1.In this case, the proposal distribution for different particles are similar if transformed to an ego-centric reference frame

p(x t⊖x(j)t−1|˜m(j)t−1,x(j)t−1,z t,u t−1)≃p(x t⊖x(i)t−1|˜m(i)t−1,x(i)t−1,z t,u t−1).(7) As a result,we can determine the proposal for a particle j by computing the pro-posal in the reference frame of particle i and then translating it to the reference frame of particle j

p(x t|˜m(j)t−1,x(j)t−1,z t,u t−1)≃p(x(j)t−1⊕(x t⊖x(i)t−1)|˜m(i)t−1,x(i)t−1,z t,u t−1).(8) This computation is illustrated in Figure1.It shows how to transform a proposal between particles.The complex proposal computation needs to be performed only once and can then be translated to the reference frame of the other particles.

4.3Computing the Proposal for Already Visited Areas

Whenever the robot moves through known areas,each particle stays localized in its own map according to Assumption3.To update the new pose of each particle while the robot moves,we choose the pose x t that maximizes the likelihood of the observation around the pose predicted by odometry

x(i)t=argmax

p(x t|˜m(i)t−1,x(i)t−1,z t,u t−1).(9) x t

7Analog to Eq.(6)-(8),we can express the proposal of particle j using the one of particle i.The only difference is that we do not apply the⊕and⊖operators based on the poses of the samples.Instead,the operators are applied based on the particle dependent reference frames l(i)and l(j)of the local maps.These reference frames were established whenever the robot visits the corresponding area for thefirst time. This results in

p(x t|˜m(j)t−1,x(j)t−1,z t,u t−1)≃p(l(j)⊕(x t⊖l(i))|˜m(i)t−1,x(i)t−1,z t,u t−1).(10) Combining Eq.(9)and Eq.(10)leads to

x(j)t=argmax

x t

p(x t|˜m(j)t−1,x(j)t−1,z t,u t−1)(11)

≃argmax

x t

p(l(j)⊕(x t⊖l(i))|˜m(i)t−1,x(i)t−1,z t,u t−1)=l(j)⊕(x(i)t⊖l(i)).(12)

Under the Assumptions2and3,we can estimate the poses of all samples according to Eq.(12)(while moving through known areas).In this way,the complex compu-tation of an informed proposal needs to be done only once.

4.4Computing the Proposal When Closing a Loop

In contrast to the two situations described before,the computation of the proposal is more complex in case of a loop-closure.This is due to the fact that Assump-tion2(local similarity)is typically violated even for subsets of particles.Let us assume that the particle cloud is widely spread when the loop is closed.Typically, the individual samples reenter the previously mapped terrain at different locations. This results in different hypotheses about the topology of the environment and definitively violates Assumption2.Dealing with such a situation,requires addi-tional effort in the estimation process.

Whenever a particle i closes a loop,we consider that the map˜m(i)t−1of its surround-ings consists of two components.Let m(i)loop refer to the map of the area,the robot seeks to reenter.Then,m(i)local is the map constructed from the most recent measure-ments without the part of the map that overlaps with m(i)loop.Since those two maps are disjoint and under the assumption that the individual grid cells are independent, we can use a factorized form for our likelihood function

p(z t|x t,m(i)local,m(i)loop)∝p(z t|x t,m(i)local)·p(z t|x t,m(i)loop).(13) For efficiency reasons,we use only the local map m(i)local to compute the proposal

and do not consider m(i)

loop .This procedure is valid but requires to adapt the weight

computation.According to the importance sampling principle,this leads to

8p(x(i)t|z t,x(i)t−1,m(i)local,m(i)loop,u t−1)

w(i)t=w(i)t−1·

(15)

η(i)2p(z t|x(i)t,m(i)local)

η(i)1

=w(i)t−1·p(z t|x(i)t,m(i)loop)

original cluster

newly created particle clusters

Figure2.The left image depicts a cluster while the robot is approaching a loop-closure. The shown particle cluster splits up into three different clusters(topology hypotheses)as depicted in the right image.

still possible to represent the posterior in an appropriate way.To achieve local sim-ilarity,we introduce the notion of a particle cluster which describes a subset of particles for which the assumption of local similarity between maps holds.Ambi-guities in the posterior can then be modeled using multiple particle clusters.

In the beginning of the mapping process,we start with a single cluster,but af-ter closing a loop,multiple topology hypotheses typically occur.In this situation, the cluster needs to be split up.Therefore,we determine which particle belongs to which topological hypothesis in order to form new clusters.In our current im-plementation,we group the samples according to their Euclidian distance to the different nodes in their own graph structure of reference frames.For each particle, wefirst determine the list of nodes in thefield of view of that sample.We order this list according to the Euclidian distance from the pose represented by the sample to the corresponding node.Then,a cluster is given by the samples which have the same list of nodes.An example which illustrates how new clusters arise in case of a loop-closure is depicted in Figure2.Note that we currently do not merge clus-ters.Throughout our experiments,we observed that multiple particle clusters are created when closing a loop.The actual number ranges up to50.However,after a few iterations only a small number of clusters(typically up tofive)survive.

In our current implementation,we represent a map as a set of local maps also called patches.A global map for a given particle can be obtained by specifying the location of each patch within a global reference frame.Each sample therefore has to store only a list of reference frames l(i)n for the patches.In this way,the individual patches P1,...,P N need to be stored only once per cluster.The map of particle i can be computed by m(i)= n l(i)n⊕P n.

Within one particle cluster,the local maps of each particle fulfills the assumption of local similarity.Therefore,they can share their patches.This results in a more compact representation compared to storing individual grid maps.In our current mapping system,we used a graph structure where each node is a reference to the corresponding patch.Furthermore,the state vector s(i)t and the clusters C k are rep-

10

Figure 3.Learned map of the MIT Killian Court,the Intel Research lab,and the ACES dataset using our approach.

resented as

s (i )t =

x (i )t robot pose

,k cluster ID ,l (i )1,...,l (i )N k patch locations C k = P 1,...,P N k pointers to patches ,{e l,m } graph edges .

(18)

Note that the number N k of patches does not grow with the length of the trajectory traveled by the robot.It grows with the number of relevant patches which is related to the size of the environment.

To fulfill Assumption 3,we apply an incremental scan alignment technique based on laser range finder data.The experiments presented in this paper indicate that this setup/implementation is sufficient to satisfy the three assumptions.As a result,we obtain a mapping system which provides highly accurate maps in a fast and memory efficient manner.

6Experiments

In this section,we present experiments performed on real robot datasets which are commonly used within the robotics community.In the first experiment,we cor-rected several log files using our approach.The left image of Figure 3depicts the resulting map of the MIT Killian Court.This is a challenging dataset,since the en-vironment is large (it took 2.5h to record this log file)and contains several nested loops which can rise the problem of particle depletion.As shown in the figure,the map does not contain any inconsistencies like for example double walls.Compara-ble results have been obtained using the Intel Research,the Austin ACES dataset,shown in the same figure.

11

Comparison of memory and computational resources for the MIT dataset using a PC with a1.3GHz CPU.

execution time

2,000210MB

1,000180MB

500165MB

RBPF of[21](memory swapping)

RBPF of[21]300min

RBPF of[21]190min

0 100

200 300 400 500

10 20 30 40 50

n u m b e r o f p a t c h e s n u m b e r o f c l u s t e r s time patches clusters Figure 4.This plot depicts the number of patches in the memory and the number of clusters over time for the MIT dataset using 1.500particles.

0 0.2 0.4 0.6 0.8 1 0 5 10 15 20 25 30

i m p o r t a n c e w e i g h t time approximated exact 0 0.2 0.4 0.6 0.8 1 0 5 10 15 20 25 30time approximated exact 0 0.2 0.4 0.6 0.8 1 0 5 10 15 20 25 30time approximated exact

Figure 5.Difference in the particle weights caused the approximative computation for three different samples during a loop-closure.The left and middle image show typical results,the right one depicts the one of the worst results during our experiments.

Figure 4depicts the number of patches that need to be stored and the number of clusters during the estimation process of the MIT dataset with 1,500particles.As can be seen,the number of clusters is typically small until a loop closure occurs.At this point,the number of clusters increases.However,after a short period of time most of the clusters vanish.

The last experiment evaluates the error introduced by our approximative impor-tance weight computation when closing a loop.As presented in Eq.(17),we ig-nore the normalization factors to achieve a faster estimation.We analyzed the loop-closing actions and in most situations the approximation error was small.Figure 5depicts the differences between the sound computation and our approximation for three different particles during a loop closure.For a more quantitative evaluation between both methods,we computed the KL-divergence (KLD)between the distri-bution of the importance weights in both cases.It turned out,that the average KLD was only 0.02(a KLD of 0means that the distributions are equal and the higher the value the more different are the distributions).Substantiated by the good approxi-mation quality,we ignore the evaluation of η1and η2when computing the particle importance weight.

7Conclusion

In this paper,we presented efficient optimizations for Rao-Blackwellized particle filters applied to solve the SLAM problem on grid maps.We are able to update the complex posterior requiring substantially less computational and memory re-

13

With our optimizations,we are able to maintain more than one order of magni-tude more samples and at the same time require less memory and computational resources compared to other state-of-the-art mapping techniques using Rao-Black-wellized particlefilters.With this comparably high number of particles that we are able to maintain,we can compensate for the errors introduced by our approxi-mations.Our approach has been implemented,tested,and evaluated based on real robots and standard logfiles used within the SLAM community to demonstrate the accuracy and benefits of our system.

Acknowledgment

This work has partly been supported by the German Research Foundation(DFG) under contract number SFB/TR-8(A3),and by the EC under contract number FP6-004250-CoSy and FP6-IST-027140-BACS.The authors would like to acknowledge Mike Bosse and John Leonard for providing us the dataset of the MIT Killian Court, Patrick Beeson for the ACES dataset,and Dirk H¨a hnel for the Intel Research Lab. References

[1] A.Eliazar,R.Parr,DP-SLAM:Fast,robust simultainous localization and mapping

without predetermined landmarks,in:Proc.of the Int.Conf.on Artificial Intelligence (IJCAI),Acapulco,Mexico,2003,pp.1135–1142.

[2]G.Grisetti, C.Stachniss,W.Burgard,Improving grid-based slam with Rao-

Blackwellized particlefilters by adaptive proposals and selective resampling,in: Proc.of the IEEE Int.Conf.on Robotics&Automation(ICRA),Barcelona,Spain, 2005,pp.2443–2448.

[3]J.-S.Gutmann,K.Konolige,Incremental mapping of large cyclic environments,in:

Proc.of the IEEE Int.Symposium on Computational Intelligence in Robotics and Automation(CIRA),Monterey,CA,USA,1999,pp.318–325.

[4] D.H¨a hnel,W.Burgard, D.Fox,S.Thrun,An efficient FastSLAM algorithm

for generating maps of large-scale cyclic environments from raw laser range measurements,in:Proc.of the IEEE/RSJ Int.Conf.on Intelligent Robots and Systems (IROS),Las Vegas,NV,USA,2003,pp.206–211.

14[5]M.Montemerlo,S.T.D.Koller,B.Wegbreit,FastSLAM2.0:An improved particle

filtering algorithm for simultaneous localization and mapping that provably converges, in:Proc.of the Int.Conf.on Artificial Intelligence(IJCAI),Acapulco,Mexico,2003, pp.1151–1156.

[6]M.Montemerlo,S.Thrun,D.Koller,B.Wegbreit,FastSLAM:A factored solution

to simultaneous localization and mapping,in:Proc.of the National Conference on Artificial Intelligence(AAAI),Edmonton,Canada,2002,pp.593–598.

[7]K.Murphy,Bayesian map learning in dynamic environments,in:Proc.of the Conf.on

Neural Information Processing Systems(NIPS),Denver,CO,USA,1999,pp.1015–1021.

[8]S.Thrun,Y.Liu,D.Koller,A.Ng,Z.Ghahramani,H.Durrant-Whyte,Simultaneous

localization and mapping with sparse extended informationfilters,Int.Journal of Robotics Research23(7/8).

[9] A.Doucet,J.de Freitas,K.Murphy,S.Russel,Rao-Blackwellized partcilefiltering

for dynamic bayesian networks,in:Proc.of the Conf.on Uncertainty in Artificial Intelligence(UAI),Stanford,CA,USA,2000,pp.176–183.

[10]J.Leonard,H.Durrant-Whyte,Mobile robot localization by tracking geometric

beacons,IEEE Transactions on Robotics and Automation7(4)(1991)376–382. [11]R.Smith,M.Self,P.Cheeseman,Estimating uncertain spatial realtionships in

robotics,in:I.Cox,G.Wilfong(Eds.),Autonomous Robot Vehicles,Springer Verlag, 1990,pp.167–193.

[12]J.Neira,J.Tard´o s,Data association in stochastic mapping using the joint compatibility

test,IEEE Transactions on Robotics and Automation17(6)(2001)0–7. [13]U.Frese,G.Hirzinger,Simultaneous localization and mapping-a discussion,in:

Proc.of the IJCAI Workshop on Reasoning with Uncertainty in Robotics,Seattle, WA,USA,2001,pp.17–26.

[14]R.Eustice,M.Walter,J.Leonard,Sparse extended informationfilters:Insights into

sparsification,in:Proc.of the IEEE/RSJ Int.Conf.on Intelligent Robots and Systems (IROS),Edmonton,Cananda,2005,pp.1–8.

[15]M.Paskin,Thin junction treefilters for simultaneous localization and mapping,in:

Proc.of the Int.Conf.on Artificial Intelligence(IJCAI),Acapulco,Mexico,2003,pp.

1157–11.

[16]F.Lu,E.Milios,Globally consistent range scan alignment for environment mapping,

Journal of Autonomous Robots4(1997)333–349.

[17]B.Lisien, D.S. D.Morales,G.Kantor,I.Rekleitis,H.Choset,Hierarchical

simultaneous localization and mapping,in:Proc.of the IEEE/RSJ Int.Conf.on Intelligent Robots and Systems(IROS),Las Vegas,NV,USA,2003,pp.448–453. [18]M.Bosse,P.Newman,J.Leonard,S.Teller,An ALTAS framework for scalable

mapping,in:Proc.of the IEEE Int.Conf.on Robotics&Automation(ICRA),Taipei, Taiwan,2003,pp.19–1906.

15[19]C.Estrada,J.Neira,J.Tard´o s,Hierachical slam:Real-time accurate mapping of large

environments,IEEE Transactions on Robotics21(4)(2005)588–596.

[20]A.Doucet,On sequential simulation-based methods for bayesianfiltering,Tech.rep.,

Signal Processing Group,Dept.of Engeneering,University of Cambridge(1998). [21]C.Stachniss,G.Grisetti,Mapping results obtained with Rao-Blackwellized particle

filters,http://www.informatik.uni-freiburg.de/∼stachnis/research/rbpfmapper/(2004).

[22]C.Stachniss,D.H¨a hnel,W.Burgard,G.Grisetti,On actively closing loops in grid-

based fastslam,Advanced Robotics19(10)(2005)1059–1080.

16下载本文