关 键 词：

步行 机器人 头部 身体 结构 设计

资源描述：

双足步行机器人头部及身体结构的设计,步行,机器人,头部,身体,结构,设计

内容简介：

南京理工大学泰州科技学院毕业设计（论文）任务书系部：机械工程系专 业：机械工程及自动化学 生 姓 名：徐昕晏学 号：05010244设计(论文)题目：两足行走机器人身体及头部结构部分设计起 迄 日 期:2009年 3月09 日 6月14日设计(论文)地点:南京理工大学泰州科技学院指 导 教 师:路建萍 刘艳 专业负责人:龚光容发任务书日期: 2009年 2月 26 日毕 业 设 计（论 文）任 务 书1本毕业设计（论文）课题应达到的目的： 通过本设计，使学生熟悉机械产品开发性设计的一般过程，培养学生综合运用所学基础理论、专业知识和各项技能，着重培养设计、计算、分析和解决问题的能力，进而总结、归纳和获得合理结论，进行较为系统的工程训练，初步锻炼科研能力，提高论文撰写和技术表述能力。为实际工作奠定基础，达到人才培养的目的与要求。2本毕业设计（论文）课题任务的内容和要求（包括原始数据、技术要求、工作要求等）：技术要求：本机器人的总体功能为模拟人体动作。设计两足行走机器人身体及头部结构设计，能够实现摇头功能。工作任务：（1） 查阅资料15篇以上，翻译外文资料3000字，撰写文献综述和开题报告。（2） 完成身体及头部结构总体设计，绘制功能原理图 1 份。（3） 绘制装配图 1 份 （0号图纸）； 部件图 1份；零件图若干。（其中，至少有1张图纸使用计算机绘制）（4） 设计说明书1.5万字左右。(打印)毕 业 设 计（论 文）任 务 书3对本毕业设计（论文）课题成果的要求包括毕业设计论文、图表、实物样品等：(1)开题报告(含文献综述)；(2)外文资料翻译：3,000 汉字以上；(3)总体装配图： 1 张； (4)部件装配图1张；(5)主要零件图：若干张 (总图数约合2张0号图)；(6)毕业设计说明书,字数不少于10,000字,并附有200300汉字的中文摘要及相应的英文摘要。所有设计图表、论文撰写、参考文献标记等均应符合本院的规范化要求。4主要参考文献：1 马香峰.机器人机构学M. 北京: 机械工业出版社, 1991.2 龚振邦等.机器人机械设计M. 北京：电子工业出版社，1995年6月.3 吴瑞祥.机器人技术及应用M. 北京：北京航空航天大学出版社，1994. 4 熊有伦.机器人技术基础M.武汉：华中理工大学出版社，1996.5 王志良.竞赛机器人制作技术M.北京：机械工业出版社，2007.6 马香峰等.工业机器人的操作机设计M. 北京：冶金工业出版社，1996年9月.7 余达太，马香峰. 工业机器人应用工程M. 北京：冶金工业出版社，1999年4月.8 机械设计手册编委会. 机械设计手册M. 北京：机械工业出版社，2007年7月.9 Ernest L. Hall et l. Robotics: A User-Friendly IntroductionM. New York:CBS College Publishing,1985.10 Yoram Koren. Robotics for EngineersM. McGraw-Hill Book Company, 1985.11 成大先.机械设计手册（第4版）.北京：化学工业出版社，2002.12 白井良明著. 王棣棠译. 机器人工程M. 北京：科学出版社，2001年2月.13 秦志强等. 基础机器人制作与编程M. 北京： 电子工业出版社，2007.14 费仁元等.机器人机械设计和分析.北京：北京工业大学出版社，1998.15 陈继荣.智能电子创新制作M. 北京：科技出版社，2007. 毕 业 设 计（论 文）任 务 书5本毕业设计（论文）课题工作进度计划：起 迄 日 期工 作 内 容2009年 3月 9 日 3月15日 3月16日 3月22日3月23日 3月29日3月30日 4月5 日4月6 日 4月12日4月13日 4月26日4月27日 5月3 日5月4 日 5月10日5月11日 5月17 日5月18日 5月24 日5月25日 5月31 日6月1 日 6月7 日6月8 日 6月14 日选题，发放审题表及任务书，熟悉课题完成外文资料翻译完成开题报告(包含文献综述)查阅相关资料，提出几种可行性方案 确定合理方案，进行总体方案论证进行结构部分设计计算相关结构参数，选择标准部件，熟悉相关软件对设计方案进行评价与修改，使之完善绘制总装配图，绘制零件图整理相关资料，撰写并打印设计说明书初步提交设计成果（包括图纸及论文），整改正式提交设计成果和设计说明书准备论文答辩所在专业审查意见：负责人： 年 月 日系部意见：系部主任： 年 月 日FastSLAM: A Factored Solution to the SimultaneousLocalization and Mapping ProblemMichael Montemerlo and Sebastian ThrunSchool of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213mmde, thrunDaphne Koller and Ben WegbreitComputer Science DepartmentStanford UniversityStanford, CA 94305-9010koller, benAbstractThe ability to simultaneously localize a robot and ac-curately map its surroundings is considered by many tobe a key prerequisite of truly autonomous robots. How-ever, few approaches to this problem scale up to handlethe very large number of landmarks present in real envi-ronments. Kalman filter-based algorithms, for example,require time quadratic in the number of landmarks to in-corporate each sensor observation. This paper presentsFastSLAM, an algorithm that recursively estimates thefull posterior distribution over robot pose and landmarklocations, yet scales logarithmically with the number oflandmarks in the map. This algorithm is based on an ex-act factorization of the posterior into a product of con-ditional landmark distributions and a distribution overrobot paths. The algorithm has been run successfullyon as many as 50,000 landmarks, environments far be-yond the reach of previous approaches. Experimentalresults demonstrate the advantages and limitations ofthe FastSLAM algorithm on both simulated and real-world data.IntroductionTheproblemofsimultaneouslocalizationandmapping,alsoknownas SLAM, has attractedimmenseattentionin the mo-bile robotics literature.SLAM addresses the problem ofbuilding a map of an environment from a sequence of land-mark measurements obtained from a moving robot. Sincerobotmotionis subject to error,the mappingproblemneces-sarilyinducesarobotlocalizationproblemhencethenameSLAM. The ability to simultaneously localize a robot andaccurately map its environment is considered by many to bea key prerequisite of truly autonomous robots 3, 7, 16.The dominant approach to the SLAM problem was in-troduced in a seminal paper by Smith, Self, and Cheese-man 15.This paper proposed the use of the extendedKalman filter (EKF) for incrementally estimating the poste-rior distribution over robot pose along with the positions ofthe landmarks. In the last decade, this approach has foundwidespread acceptance in field robotics, as a recent tutorialpaper 2 documents. Recent research has focused on scal-ing this approach to larger environments with more than afew hundred landmarks 6, 8, 9 and to algorithms for han-dling data association problems 17.AkeylimitationofEKF-basedapproachesistheircompu-tational complexity. Sensor updates require time quadraticin the number of landmarks?to compute. This complex-ity stems fromthe fact thatthe covariancematrixmaintainedbytheKalmanfiltershas?elements,all ofwhichmustbe updated even if just a single landmark is observed. Thequadratic complexity limits the number of landmarks thatcan be handled by this approach to only a few hundredwhereasnaturalenvironmentmodelsfrequentlycontainmil-lions of features. This shortcoming has long been recog-nized by the research community 6, 8, 14.In this paper we approach the SLAM problem from aBayesian point of view. Figure 1 illustrates a generativeprobabilistic model (dynamic Bayes network) that underliesthe rich corpus of SLAM literature. In particular, the robotposes, denoted?, evolve over time as a functionof the robot controls, denoted?. Each of the land-mark measurements, denoted?, is a function of thepositionof the landmark measured and of the robot poseat the time the measurementwas taken. From this diagramitis evident that the SLAM problem exhibits important condi-tionalindependences. Inparticular,knowledgeoftherobotspath?rendersthe individuallandmarkmeasure-ments independent. So for example, if an oracle provideduswith the exact path of the robot, the problem of determin-ing the landmark locations could be decoupled into?inde-pendent estimation problems, one for each landmark. Thisobservation was made previously by Murphy 12, who de-veloped an efficient particle filtering algorithm for learninggrid maps.Basedonthisobservation,this paperdescribesanefficientSLAM algorithmcalled FastSLAM. FastSLAM decomposesthe SLAM problem into a robot localization problem, anda collection of landmark estimation problems that are con-ditioned on the robot pose estimate. As remarked in 12,this factored representation is exact, due to the natural con-ditional independences in the SLAM problem. FastSLAMuses a modified particle filter for estimating the posteriorover robot paths. Each particle possesses?Kalman fil-ters that estimate the?landmark locations conditioned onthe path estimate. The resulting algorithm is an instance ofthe Rao-Blackwellized particle filter 5, 13. A naive im-plementation of this idea leads to an algorithm that requires?time, whereis the number of particles in thes1s2stu2ut21z1z2s3u3z3zt.?.?.Figure 1: The SLAM problem: The robot moves from pose?through a sequence of controls,?. As it moves, itobserves nearby landmarks. At time, it observes landmark?out of two landmarks,?. The measurement is denoted?(range and bearing). At time, it observes the other landmark,?, and at time, it observes?again. The SLAM problem isconcerned with estimating the locations of the landmarks and therobots path from the controls?and the measurements. The grayshading illustrates a conditional independence relation.particle filter and?is the number of landmarks. We de-velop a tree-based data structure that reduces the runningtime of FastSLAM to?! #?, making it significantlyfaster than existing EKF-based SLAM algorithms. We alsoextend the FastSLAM algorithm to situations with unknowndata association and unknown number of landmarks, show-ing that our approach can be extended to the full range ofSLAM problems discussed in the literature.Experimental results using a physical robot and a robotsimulator illustrate that the FastSLAM algorithm can han-dle orders of magnitude more landmarks than present dayapproaches. We also find that in certain situations, an in-creased number of landmarks?leads to a mild reductionof the number of particlesneeded to generate accuratemapswhereas in others the number of particles requiredfor accurate mapping may be prohibitively large.SLAM Problem DefinitionThe SLAM problem, as defined in the rich body of litera-ture on SLAM, is best described as a probabilistic Markovchain. The robots pose at time$will be denoted?. Forrobots operating in the planewhichis the case in all of ourexperimentsposes are comprised of a robots%-&coordi-nate in the plane and its heading direction.Poses evolve according to a probabilistic law, often re-ferred to as the motion model:?)(?+*?(1)Thus,?is a probabilistic function of the robot controland the previous pose?+*?. In mobile robotics, the motionmodelisusuallya time-invariantprobabilisticgeneralizationof robot kinematics 1.The robots environment possesses?immobile land-marks. Each landmark is characterized by its location inspace, denotedfor,.-0/?. Without loss of gen-erality, we will think of landmarks as points in the plane, sothat locations are specified by two numerical values.To map its environment, the robot can sense landmarks.For example, it may be able to measure range and bearing toa landmark, relative to its local coordinate frame. The mea-surementat time$will bedenoted?. Whilerobotscanoftensense more than one landmark at a time, we follow com-monplace notation by assuming that sensor measurementscorrespond to exactly one landmark 2. This convention isadopted solely for mathematical convenience. It poses norestriction, as multiple landmark sightings at a single timestep can be processed sequentially.Sensor measurementsare governedby a probabilisticlaw,often referred to as the measurement model:?(?21?(2)Here3-54?76is the set of all landmarks, and198:4;/?6is the index of the landmark perceived attime$. For example, in Figure 1, we have1?,and1AB-C/, since the robot first observes landmark?,thenlandmark?, and finally landmark?fora second time.Many measurement models in the literature assume that therobot can measure range and bearing to landmarks, con-founded by measurement noise. The variable1is oftenreferred to as correspondence. Most theoretical work in theliterature assumes knowledge of the correspondence or, putdifferently, that landmarks are uniquely identifiable. Practi-cal implementationsuse maximum likelihood estimators forestimating the correspondence on-the-fly, which work wellif landmarks are spaced sufficiently far apart. In large partsofthis paperwe will simplyassume that landmarksareiden-tifiable, but we will also discuss an extension that estimatesthe correspondences from data.We are now ready to formulate the SLAM problem. Mostgenerally, SLAM is the problem of determining the locationof all landmarksand robot poses?from measurements-?and controls-?. In probabilis-tic terms, this is expressed by the posterior?D(?,where we use the superscriptto refer to a set of variablesfrom time 1 to time$. If the correspondencesare known, theSLAM problem is simpler:?E(21?(3)As discussed in the introduction,all individual landmark es-timation problems are independent if one knew the robotspath?and the correspondence variables1. This condi-tional independence is the basis of the FastSLAM algorithmdescribed in the next section.FastSLAM with Known CorrespondencesWe begin our consideration with the important case wherethe correspondences1-=1?21are known, and so isthe number of landmarks?observed thus far.Factored RepresentationThe conditional independence property of the SLAM prob-lem implies that the posterior (3) can be factored as follows:?E(21?-?(21?GF?H(?21?(4)Putverbally,theproblemcanbedecomposedinto?JI/esti-mationproblems,oneproblemofestimating a posterioroverrobot paths?, and?problems of estimating the locationsof the?landmarks conditioned on the path estimate. Thisfactorization is exact and always applicable in the SLAMproblem, as previously argued in 12.The FastSLAM algorithm implements the path estimator?(21?using a modified particle filter 4. As weargue further below, this filter can sample efficiently fromthis space, providing a good approximation of the poste-rior even under non-linear motion kinematics. The land-mark pose estimators?(?1?are realized byKalman filters, using separate filters for differentlandmarks.Because the landmark estimates are conditioned on the pathestimate, each particle in the particle filter has its own, lo-cal landmark estimates. Thus, forparticles and?land-marks, there will be a total of?Kalman filters, each ofdimension 2 (for the two landmark coordinates). This repre-sentation will now be discussed in detail.Particle Filter Path EstimationFastSLAM employs a particle filter for estimating the pathposterior?(1?in (4), using a filter that is similar(but not identical) to the Monte Carlo localization (MCL)algorithm 1. MCL is an application of particle filter tothe problem of robot pose estimation (localization). At eachpointin time, both algorithmsmaintain a set of particles rep-resenting the posterior?(21?, denoted?. Eachparticle?8?represents a “guess” of the robots path:?-4?6?-4?6?(5)We use the superscript notation?to refer to the-th par-ticle in the set.The particle set?is calculated incrementally, from theset?+*?at time$D/, a robot control, and a measurement. First, each particle?in?+*?is used to generate aprobabilistic guess of the robots pose at time$:?(?+*?(6)obtained by sampling from the probabilistic motion model.This estimate is then added to a temporary set of parti-cles, along with the path?+*?. Under the assumptionthat the set of particles in?+*?is distributed according to?+*?(+*?+*?1+*?(which is an asymptotically cor-rect approximation), the new particle is distributed accord-ing to?(+*?21+*?. This distribution is commonlyreferred to as the proposal distribution of particle filtering.After generatingparticles in this way, the new set?isobtained by sampling from the temporary particle set. Eachparticle?is drawn(with replacement)witha probabilityproportionalto a so-called importance factor?, which iscalculated as follows 10:?-target distributionproposal distribution-?(21?(+*?21+*?(7)The exact calculation of (7) will be discussed further below.The resultingsampleset?is distributedaccordingto anap-proximation to the desired pose posterior?(21?,an approximationwhichis correctas the numberof particlesgoes to infinity. We also notice that only the most recentrobot pose estimate?+*?is used when generating the parti-cle set?. This will allows us to silently “forget” all otherpose estimates, rendering the size of each particle indepen-dent of the time index$.Landmark Location EstimationFastSLAM represents the conditional landmark estimates?(?1?in (4) by Kalman filters. Since thisestimate is conditioned on the robot pose, the Kalman filtersare attached to individual pose particles in?. More specifi-cally, the full posterior over paths and landmark positions inthe FastSLAM algorithm is represented by the sample setC-4?6?(8)Here?and?are mean and covariance of the Gaus-sian representing the,-th landmark, attached to the-thparticle. In the planar robot navigation scenario, each mean?is a two-element vector, and?is a 2 by 2 matrix.The posterior over the,-th landmarkposeis easily ob-tained. Its computation depends on whether or not1-?,thatis, whetherornotwas observedattime$. For1-,we obtain?(?21?(9)?)(?+*?1?(?+*?1? !#%$#&-?)(?21?(?+*?+*?+*?21+*?For1)(-, we simply leave the Gaussian unchanged:?(?1?-?(?+*?+*?+*?1+*?(10)The FastSLAM algorithm implements the update equation(9) using the extended Kalman filter (EKF). As in existingEKF approaches to SLAM, this filter uses a linearized ver-sion of the perceptual model?(?21?2. Thus,FastSLAMs EKF is similar to the traditional EKF forSLAM 15 in that it approximates the measurement modelusing a linear Gaussian function. We note that, with a lin-ear Gaussian observation model, the resulting distribution?(?1?is exactly a Gaussian, even if the mo-tion model is not linear. This is a consequence of the useof sampling to approximate the distribution over the robotspose.One significant difference between the FastSLAM algo-rithms use of Kalman filters and that of the traditionalSLAM algorithm is that the updates in the FastSLAM algo-rithm involve only a Gaussian of dimensiontwo (for the twolandmark location parameters), whereas in the EKF-basedSLAMapproachaGaussianofsize?I+*hastobeupdated(with?landmarks and 3 robot pose parameters). This cal-culationcanbedoneinconstanttimein FastSLAM,whereasit requires time quadratic in?in standard SLAM.Calculating the Importance WeightsLet us now return to the problem of calculating the impor-tance weights?needed for particle filter resampling, asdefined in (7):?(1?(+*?1+*?-?21)(?+*?1+*?1(+*?1+*?8,87,7k? 7?FT6,65,5k? 5?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm8,87,7k? 7?FT6,65,5k? 5?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmmFigure 2: A tree representing?landmark estimates within asingle particle.?(+*?21?(+*?21?-?21(?+*?21+*?21(+*?21+*?21(?+*?21+*?-?21)(?+*?21+*?E(?+*?21? !$&-?21)(?E(?+*?+*?+*?21+*?-?)(?1?1)(?E(?+*?+*?+*?21+*?(?1?E(?+*?+*?+*?21+*?(?1?(11)Here we assume that the distribution?1=(?isuniforma common assumption in SLAM. In the last line,“EKF” makes explicitthe use ofa linearizedmodelas anap-proximation to the observation model?(?, andthe resulting Gaussian posterior?. The final integra-tion is easily calculated in closed form for a linear Gaussian.Efficient ImplementationTheFastSLAMalgorithm,as describedthusfar,mayrequiretime linear in the number of landmarks?for each updateiteration if implemented naively. This is because of the re-sampling step; every time a particle is added to, its hasto be copied. Since each particle contains?landmark esti-mates, this copyingprocedurerequires?time. How-ever, most of this copying can be avoided.Our approach makes it possible to execute a FastSLAMiteration in?! #?time. The basic idea is that the setofGaussians in eachparticleis representedbya balancedbi-nary tree. Figure 2 shows such a tree for a single particle, inthe case of 8 landmarks. The Gaussian parameters?and8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm3,3k? 3?FTk? 2?FTk? 4?FTmmnew?particleold?particle8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm8,87,7k? 3?FT6,65,5k? 1?FT4,43,3k? 3?FT2,21,1k? 1?FTk? 6?FTk? 2?FTk? 4?FTmmmmmmmmmmmmmmmm3,3k? 3?FTk? 2?FTk? 4?FTmmnew?particleold?particleFigure 3: Generating a new particle from an old one, while modi-fying only a single Gaussian. The new particle receives only a par-tial tree, consisting of a path to the modified Gaussian. All otherpointers are copied from the generating tree.?are located at the leaves of the tree. Clearly, accessingeach Gaussian requires time logarithmic in?.Suppose FastSLAM incorporates a new controland anew measurement. Each new particle inwill differfrom the corresponding one in+*?in two ways: First, itwill possess a different path estimate obtained via (6), andsecond, the Gaussian with index1will be different in ac-cordance with (9). All other Gaussians will be equivalent tothe generating particle.When copying the particle, thus, only a single path hasto be modified in the tree representing all Gaussians. Anexample is shown in Figure 3: Here we assume1-*, thatis, only the Gaussian parameters?and?are updated.Instead of generatingan entirely new tree, only a single pathis created, leading to the Gaussian1-*. This path isan incomplete tree. To complete the tree, for all branchesthat leave this path the corresponding pointers are copiedfrom the tree of the generating particle. Thus, branches thatleave the path will point to the same (unmodified) subtreeas that of the generating tree. Clearly, generating such anincompletetree takesonlytimelogarithmicin?. Moreover,accessing a Gaussian also takes time logarithmicin?, sincethe number of steps required to navigate to a leaf of the treeis equivalent to the length of the path (which is by definitionlogarithmic). Thus, both generating and accessing a partialtree can be done in time?! #?. Since in each updatingstepnew particles are created, an entire update requirestime in?! #?.Data AssociationIn many real-world problems, landmarks are not identifi-able, and the total number of landmarks?cannot be ob-tained triviallyas was the case above. In such situations,the robot has to solve a data association problem betweenmomentary landmarks sightingsand the set of landmarksin the map. It also has to determine if a measurement cor-responds to a new, previously unseen landmark, in which(a)(b)(c)Figure 4: (a) Physical robot mapping rocks, in a testbed developed for Mars Rover research. (b) Raw range and path data. (c) Map generatedusing FastSLAM (dots), and locations of rocks determined manually (circles).case the map should be augmented accordingly.In most existing SLAM solutions based on EKFs, theseproblems are solved via maximum likelihood. More specif-ically, the probability of a data association1is given by?1)(?-?1(?(?1)(? !#%$#&-?1)(?#?(?1?(12)The step labeled “PF” uses the particle filter approxima-tion to the posterior?(?. The final step assumesa uniform prior?1(?, which is commonly used 2.The maximum likelihood data association is simply the in-dex1that maximizes (12).If the maximum value of?1D(?with careful consideration of all constantsin (12)is below a threshold?, the landmark is consideredpreviously unseen and the map is augmented accordingly.In FastSLAM, the data association is estimated on a per-particle basis:1?-?(?21?. As a result,differentparticles mayrely ondifferentvalues of1?. Theymight even possess different numbers of landmarks in theirrespective maps. This constitutes a primary difference toEKF approaches, which determine the data association onlyonce for each sensor measurement. It has been observedfrequently that false data association will make the conven-tional EKF approach fail catastrophically 2. FastSLAM ismore likely to recover, thanks to its ability to pursue multi-ple data associations simultaneously. Particles with wrongdata association are (in expectation) more likely to disap-pear in the resampling process than those that guess the dataassociation correctly.We believe that, under mild assumptions (e.g., minimumspacing between landmarks and bounded sensor error), thedata association search can be implemented in time loga-rithmic in. One possibility is the use of kd-trees as anindexing scheme in the tree structures above, instead of thelandmark number, as proposed in 11.Experimental ResultsThe FastSLAM algorithmwas tested extensivelyundervari-ousconditions. Real-worldexperimentswerecomplimentedby systematic simulation experiments, to investigate thescalingabilities oftheapproach. Overall,theresults indicatefavorably scaling to large number of landmarks and smallparticle sets. A fixed number of particles (e.g.,-/?)appears to work well across a large number of situations.Figure4ashowsthephysicalrobottestbed,whichconsistsof a small arena set up under NASA fundingfor Mars Roverresearch. A Pioneer robot equipped with a SICK laser rangefinder was driven along an approximate straight line, gener-ating the raw data shown in Figure 4b. The resulting mapgenerated with-/samples is depicted in Figure 4c,with manually determined landmark locations marked bycircles. The robots estimates are indicated by xs, illustrat-ing the high accuracy of the resulting maps. FastSLAM re-sulted in an average residual map error of 8.3 centimeters,when compared to the manually generated map.Unfortunately,thephysicaltestbed doesnotallow forsys-tematic experiments regarding the scaling properties of theapproach. In extensive simulations, the number of land-marks was increased up to a total of 50,000, which Fast-SLAM successfully mapped with as few as 100 particles.Here, the number of parameters in FastSLAM is approx-imately 0.3% of that in the conventional EKF. Maps with50,000 landmarks are entirely out of range for conventionalSLAM techniques, due to their enormous computationalcomplexity.Figure 5 shows example maps with smallernumbersof landmarks,fordifferentmaximumsensorrangesas indicated. The ellipses in Figure 5 visualize the residualuncertaintywhenintegratedoverall particlesandGaussians.In a set of experiments specifically aimed to elucidate thescalingpropertiesoftheapproach,weevaluatedthemapandrobot pose errors as a function of the number of landmarks?, and the number of particles, respectively. The resultsare graphically depicted in Figure 6. Figure 6a illustratesthat an increase in the number of landmarks?mildly re-duces the error in the map and the robot pose. This is be-cause the larger the number of landmarks, the smaller therobot pose error at any point in time. Increasing the numberof particlesalso bears a positive effect on the map andpose errors, as illustrated in Figure 6b. In both diagrams, thebars correspond to 95% confidence intervals.(a)(b)Figure 5: Maps and estimated robot path, generated using sensorswith (a) large and (b) small perceptual fields. The correct landmarklocations are shown as dots, and the estimates as ellipses, whosesizes correspond to the residual uncertainty.ConclusionWe presented the FastSLAM algorithm, an efficient new so-lution to the concurrent mapping and localization problem.This algorithm utilizes a Rao-Blackwellized representationof the posterior, integrating particle filter and Kalman filterrepresentations. Similar to Murphys work 12, FastSLAMis based on an inherent conditional independence propertyof the SLAM problem. However, Murphys approach main-tains maps using grid positions with discrete values, andtherefore scales poorly with the size of the map. His ap-proach also did not deal with the data association problem,which does not arise in the grid-based setting.In FastSLAM, landmark estimates are efficiently repre-sented using tree structures. Updating the posterior requires?! #?time, whereis the number of particles and?the number of landmarks.This is in contrast to the?complexity of the common Kalman-filter based ap-proach to SLAM. Experimental results illustrate that Fast-SLAM can build maps with orders of magnitude more land-marks than previous methods. They also demonstrate thatunder certain conditions, a small number of particles workswell regardless of the number of landmarks.AcknowledgmentsWe thank Kevin Murphy and Nando deFreitas for insightful discussions on this topic.This researchwas sponsored by DARPAs MARS Program (Contract numberN66001-01-C-6018) and the National Science Foundation (CA-REER grant number IIS-9876136 and regular grant number IIS-9877033).We thank the Hertz Foundation for their support ofMichael Montemerlos graduate research.Daphne Koller wassupported by the Office of Naval Research, Young Investigator(PECASE) grant N00014-99-1-0464. This work was done whileSebastian T