版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、The International Journal of Robotics ResearchFactoring the mapproblem: Mobile robot map-building in the Hybrid Spatial SemHierarachyPatrick Beeson, Joseph Modayil and Benjamin KuipersThe International Journal of Robotics Research published online 19 May 2009 DOI: 10.1177/0278364909100586The online
2、version of this article can be found at:A more recent version of this article was published on - Mar 26, 2010Published by:On behalf of:Multimedia ArchivesAdditional services and information for The International Journal of Robotics Research can be found at:Alerts:Reprints:Permissions:Version of Reco
3、rd - Mar 26, 2010>> OnlineFirst Version of Record - May 19, 2009 What is This?Downloaded from at Tsinghua University on October 23, 2014The International Journal of Robotics Research OnlineFirst, published on May 19, 2009 as doi:10.1177/0278364909100586Factoring the Map Problem: Mobile Robot M
4、ap-building in the Hybrid Spatial Sem HierarchyPatrick BeesonDepartment of Computer Sciences University of Texas at Austin1 University Station C0500 Taylor Hall 2124Austin, TX, USA 78712-0233Joseph ModayilDepartment of Computer Science, University of Rochester,PO Box 270226734 Co
5、mputer Studies Bldg. Rochester, NY, USA, 14627-0226Benjamin KuipersDepartment of Electrical Engineering and Computer Science, University of Michigan,2260 Hayward Street,Ann Arbour, MI 48109-2121, USAAbstractmetrical map from a topological skeleton by connec
6、ting local frames of reference.We propose a factored approach to mobile robot map-building that handles qualitatively different types of uncertainty by combining the strengths of topological and metrical approaches. Our framework is based on a computational m of the human cognitive map thus it allow
7、s robust navigation and communication within several different spatial ontologies. This paper focuses exclusively on the issue of map- building using the framework.KEY WORDSmapcognitive robotics, localization, autonomous agents,1. IntroductionA map is a description of an environment allowing an agen
8、t a human, or in our case a mobile robot to plan and perform effective actions. From a single location, an agents sensors can not observe the whole structure of a complex, large en- vironment. For this reason, the agent must build a map from observations gathered over time and space. We distinguish
9、be- tween large-scale space, with spatial structure larger than the agents sensory horizon, and small-scale space, with structure within the sensory horizon.Most metrical approaches to mobile robot map-building define a single, global frame of reference in which to create the map. Range measurements
10、 are used to perform probabilis- tic inference about the location of features or about the occu- pancy of discretized cells in the map (Thrun et al. 2005). Ex-Our approach factors the mapproblem into natural sub-goals: building a metrical representation for local small-scale spaces finding a topolog
11、ical map that represents the qualitative structure of large-scale space and (when necessary) constructing a metrical representation for large-scale space using the skeleton pro-vided by the topological map. We describe how to abstraym-bolic description of the robots immediate surround from local met
12、ri-cal ms, how to combine these local symbolic ms in order tobuild global symbolic ms, and how to create a globally consistent The International Journal of Robotics ResearchVol. 00, No. 00,xx 2009, pp. 000000DOI: 10.1177/0278364909100586c The Author(s), 2009. Reprints and permissions:isting simultan
13、eous localization and map(SLAM) meth-ods aighly effective for building local metrical ms ofFigures 1, 813, 15, 16 appear in color online:1Downloaded from at Tsinghua University on October 23, 20142THE INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH /xx 2009small-scale space and for providing reliable loc
14、alization in the frame of reference of the local map however, maintaining global consistency over large-scale environments is difficult, particularly when closing large loops in the environment. A popular approach is to use particle filters, where each parti- cle represents a hypothesized exploratio
15、n trajectory. The re- searcher must hope that with enough particles the distributionple serial processing pipeline. In fact, processing of sensory input to build representations of the different kinds is inter- leaved, providing various sorts of synergies. Two are partic- ularly important. First, th
16、e local metrical map of small-scale space is a useful “observer” both for detecting and describ- ing places and for low-level control with obstacle avoidance. Second, it may be useful to order candidate topological mod- els by using the relative displacement of nearby places or even by using the glo
17、bal layout of places within a single frame of reference. Nonetheless, in order to clarify the distinct repre- sentational ontologies, we will describe them in this paper as though they operate independently.The HSSH improves mobile robot capabilities in a vari- ety of ways: efficient and robust map-
18、building and navigation, “natural” humanrobot interaction due to the multiple repre- sentations of space (Beeson et al. 2007), and hierarchical con-will include one thats the loop correctly. Since the spaceof trajectories can be enormous, this hope is often optimistic.The fundamental problem is repr
19、esentational: loop-closinghypotheses are alternative topological structures for the map,not alternative metrical structures. To be able to solve complex, multi-hypothesis loop-closing problems in a tractable manner, the robot must reason with symbolic topological maps. The space of metrical maps in
20、a single frame of reference does not appropriately represent the states of incomplete knowl- edge that arise during exploration and map-building in com- plex, large-scale environments.trol. This paper cannot cover the full bth of benefits ob-tained from using a hybrid topological/metrical framework
21、Our factored mapframework is based on the Spa-thus, this paper focuses solely on the issue of using the HSSH framework for map-building. Here we describe the HSSH the- ory and demonstrate key points of HSSH map-building us- ing a particular implementation that focuses on perception us- ing range sen
22、sors, although other sensory modalities can also be utilized in the HSSH framework the hybrid, hierarchical framework is largely independent of the sensors used to createtial SemHierarchy (SSH) (Kuipers 2000, 2008), whichuses multiple coordinated representations for knowledge oflarge-scale space. Th
23、e Hybrid SSH (HSSH) (Kuipers et al. 2004 Beeson 2008) extends the basic SSH by including rep- resentations for small-scale space and defining the relation- ship between large-scale and small-scale spatial representa-tions. Symbolic topological mapmethods such as the SSHthe local metrical m al. (2006
24、). A moreof small-scale space (cf. Murarka et ed description of the HSSH benefitsprovide a concise representation for the structural alternativesthat arise in investigating loop closures. Topological maps pro- vide the ability to store and access multiple local maps with separate frames of reference
25、 and topological connections an- notated with weak metrical constraints. By separating small- scale from large-scale space, we postpone the problem of co- ordinating the local frames of reference until the global struc- ture of the topological map has been identified. At that point, the global metri
26、cal map can be constructed, efficiently and ac- curately.to control, place detection/description, and humanrobot inter- action are discussed by Beeson (2008).2. Background2.1. Metrical MapPowerful probabilistic methods have been developed for range-sensing mobile robots to perform SLAM within a sin-
27、 gle frame of reference (Thrun et al. 2005). These methods are accurate and reliable for online incremental localization within local neighborhoods. Sensing with sufficiently high frequency relative to local motion guarantees large overlap between suc-Therefore, our approach factors the mapproblem i
28、ntofour natural sub-goals: (1) building a metrical representation for local small-scale spaces (2) detecting places and determin- ing their symbolic descriptions (3) finding a topological map representing the qualitative structure of large-scale space and(4) constructing a metrical representation fo
29、r large-scale space in a single global frame of reference, building on the skeleton provided by the topological map. While the global metrical map is useful for some purposes, it is worth noting that many autonomous planning and navigation goals can be achieved ef- fectively using only the global to
30、pological map and/or the localcessive sensory images. Currensory information can becompared to the current map in order to improve localiza-tion. By analogy with radar signal interpretation, finding thecorrect match between observations and a mis called thedata association problem. After improved lo
31、calization occurs, the sensory information is used to update the map for the next SLAM iteration. In local regions, many data association prob- lems, such as the closing of large loops, can be excluded. The absence of large loops means that the problem of large-scale structural ambiguity does not ar
32、ise in the local metrical map.While metrical SLAM methods work in small spaces, theymetrical maps. Therefore, this approach to hybrid mapismore robust than one that extracts topological relations from a global metrical map that must be built first (Thrun and Bücken 1996).The multiple representa
33、tions of the HSSH are describedindependently, while their semdependencies imply thatdo not extend well to larger environments. Global metrical maps become more expensive to update and access withoutthey build on each other. However, this does not imply a sim-Downloaded from at Tsinghua University on
34、 October 23, 2014Beeson, Modayil, and Kuipers / Factoring the MapProblem3Fig. 1. Closing large loops reveals problems with cumulative errors when attempting to build metrical maps of large-scale environments in a single global frame of reference. (a) This environment and the robots trajectory throug
35、h it are used as an example throughout. (b) The data comes from a Magellan Pro research robot with differential-drive odometry and a SICK-brandlidar device for precise, planar range-sensing. (c) This robot-map of the environment in image (a) shows the effect ofaccumulated raw odometry error. (d) Thi
36、s map shows the improvement in pose estimation over image (c) by using metrical SLAM methods, but it also shows that significant errors still accumulate with respect to the real environment.clever storage schemes. More imports the difficulty thatenvironments. For example, Cummins and(2008)arises whe
37、n closing large loops (Figure 1). Even with local SLAM methods that use perception to improve the accuracy of localization, odometry error accumulates in the relation be- tween the maps global frame of reference and the ground-tdiscuss closing loops over kilometers of travel, where small rotational
38、errors lead to large positional errors, and the correctloop closure may never be considered by odometry-based solu- tions. Additionally, if the environment is subject to perceptual aliasing (different locations look the same), then the matchingreference frame of the real-world environment. This glob
39、al er- ror becomes even more pronounced in environments with long paths that have few distinguishing features. Without proper data association along paths, localization often drifts from theprocess maythe loop incorrectly, distorting the ma whole. Depending on the amount of symmetry in the envi-ronm
40、ent, a single incorrect match can lead the mapagentground-t, both in the robots distance along the path and indown an arbitrarily long “garden path” before the error is dis-the robots heading, causing straight paths to compress, stretch, or curve in the map.covered. It is still unclear how probabili
41、stic methods applied to metrical maps can properly discover an incorrect map and how they might efficiently backtrack to hypothesize a different loop closure (Hähnel et al. 2003b).Some research on map-building avoids loop-closing issuesThere ahoc methods for hypothesizing loop closureswhen the
42、global odometry error is small. When a large loopisd, accumulated error will often result in the robotscurrent observations clashing with older portions of the map.by explicitly assu known (Leonard andthat the correct data association is 2003 Paskin 2003). In someMethods exist that search for a near
43、by pose in the older por- tions of the map where perceptions match the prediction (prop- agating detected global error backwards through the explo- ration trace) (Lu and Milios 1997 Hähnel et al. 2003a) how- ever, these solutions can fail in sufficiently large or complexcases, even without an e
44、xplicit assumption about data associ-ation, impressive feats of large-scale map-making depend on locations in the environment being sufficiently distinguishable based on local cues (Montemerlo et al. 2002 Konolige 2004).Downloaded from at Tsinghua University on October 23, 20144THE INTERNATIONAL JOU
45、RNAL OF ROBOTICS RESEARCH /xx 2009Others accept false negative matches in order to avoid false positives, sometimes improperly hypothesizing that a previ- ously visited location is a new place (Bosse et al. 2003). This can eliminate the possibility of closing a loop correctly and finding the correct
46、 map, which leads to poor planning and nav- igation performance. In a rich environment with noise due to dynamic changes, it could be that every location is in principle distinguishable, but it is difficult or impossible to know which features identify the place, and which are noise. Methods cre- at
47、ed to distinguish between perceptually aliased states can get confused under scenarios of perceptual variability (the same place looks different on separate occasions) (Kuipers and Bee- son 2002) causing a single physical location to be represented multiple times in the same map.Early approaches to
48、probabilistic localization and map used particles to represent a distribution over robot poses for localization, but a single shared map was updated from theum-likelihood pose hypothesis (Thrun et al. 2000b). This could produce an incoherent map due to an incorrectTopological maps are more compact r
49、epresentations than global metrical maps, allowing efficient large-scale planning. Additionally, since the environment is discretized into a graph, movement errors do not accumulate globally. Possibly the most important difference for future robotics research is thattopological maps allow compact, e
50、fficient hierarchical msthat support multi-level symbolic reasoning for robust naviga- tion, planning, and communication.The major hurdle for topological map-building has been the reliable abstraction of useful symbols from continuous, noisy perceptions of the environment, i.e. how to reliably detec
51、t and recognize places and paths. This is an instance of the more general symbol grounding problem (Harnad 1990) that hastroubled the Artificial Intelligence (AI) commu years. Probabilistic approaches are good at overcofor manythekinds of local uncertainty and systematic noise that can hin- der reli
52、able symbol extraction. Incorporating probabilistic data association techniques into the topological map-building par-adigm has sparked interest in hybrid map-building, including the HSSH approach presented in this paper.and premature commitment to aum-likelihood pose hy-pothesis that turned out to
53、be incorrect. A more principledapproach uses Rao-Blackwellized particle filters to explicitly represent the distribution of trajectories and maps by maintain- ing multiple metrical map hypotheses (Montemerlo et al. 2003 Eliazar and Parr 2003 Hähnel et al. 2003a). These methods are run offline (
54、due to computational demands) after exploration is completed, forgoing useful active exploration techniques ca- pable of eliminating some loop-closing hypotheses. Addition- ally, in large, symmetric environments, intractably large num- bers of particles may be required to avoid particle depletion wh
55、en closing large loops. Particle depletion is a failure to have2.3. Hybrid ApproachesMetrical and topological representations for space are very dif- ferent in character, or, more precisely, in ontology. The topo- logical map describes the structure of large-scale space. It abstracts away the specif
56、ic nature of sensory input and the specific methods used for matching sensory images when thetopological map is created. Metrical maptechniques thatrely on local overlap of successive sensations, on the otherhand, precisely capture the structure within the local sensory horizon: small-scale space.Re
57、cently, robotics researchers have begun to look at hybrid topological/metrical representations in order to try to leverage the benefits of both approaches. There are too many hybrid implementations to mention here, many with only very subtle differences, but publications about hybrid metric/topologi
58、cal representations fall into three basic categories, all of whicha particle in the distribution that adequately m map.s the correct2.2. Topological MapTopological mapis the other major paradigm studied inmobile robotics. Cognitive map research supports the creationof topological maps of large, complex environments (Lynchadressed by the work in this paper. We refer theer1960 Siegel and White 197
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年粵教版高三物理下冊(cè)月考試卷
- 2025年新世紀(jì)版八年級(jí)化學(xué)上冊(cè)月考試卷
- 2024微電影演員肖像權(quán)使用及報(bào)酬支付合同3篇
- 2025年浙教版三年級(jí)英語下冊(cè)月考試卷含答案
- 專業(yè)鞋品采購(gòu)協(xié)議模板2024版
- 2025年人教版八年級(jí)地理下冊(cè)階段測(cè)試試卷
- 2024年紅河衛(wèi)生職業(yè)學(xué)院高職單招語文歷年參考題庫(kù)含答案解析
- 2025年蘇教版必修1物理下冊(cè)階段測(cè)試試卷含答案
- 二零二五版寶鋼集團(tuán)勞動(dòng)合同爭(zhēng)議解決機(jī)制3篇
- 2025年人教B版選擇性必修2化學(xué)上冊(cè)階段測(cè)試試卷含答案
- 2025年競(jìng)聘醫(yī)院內(nèi)科醫(yī)生崗位演講稿模版(3篇)
- 虛擬貨幣地址分析技術(shù)的研究-洞察分析
- 綠色供應(yīng)鏈管理制度內(nèi)容
- 心理學(xué)基礎(chǔ)知識(shí)考試參考題庫(kù)500題(含答案)
- 電力智慧檢修安全運(yùn)行三維可視化管理平臺(tái)建設(shè)方案
- 一年級(jí)數(shù)學(xué)(上)計(jì)算題專項(xiàng)練習(xí)集錦
- 消防安全應(yīng)急預(yù)案下載
- 《北航空氣動(dòng)力學(xué)》課件
- 附件:財(cái)政業(yè)務(wù)基礎(chǔ)數(shù)據(jù)規(guī)范(3.0版)
- 電商公司售后服務(wù)管理制度
- 火災(zāi)應(yīng)急處理課件
評(píng)論
0/150
提交評(píng)論