Robot localization systems typically assume that the environment is static, ignoring the dynamics inherent in most real-world settings. Corresponding scenarios include households, offices, warehouses and parking lots, where the location of certain objects such as goods, furniture or cars can change over time. These changes typically lead to inconsistent observations with respect to previously learned maps and thus decrease the localization accuracy or even prevent the robot from globally localizing itself. In this paper we present a sound probabilistic approach to lifelong localization in changing environments using a combination of a Rao-Blackwellized particle filter with a hidden Markov model. By exploiting several properties of this model, we obtain a highly efficient map management approach for dynamic environments, which makes it feasible to run our algorithm online. Extensive experiments with a real robot in a dynamically changing environment demonstrate that our algorithm reliably adapts to changes in the environment and also outperforms the popular Monte-Carlo localization approach.
AnguelovDBiswasRKollerDLimketkaiBSannerSThrunS (2002) Learning hierarchical object maps of non-stationary environments with mobile robots. In: Proceedings of the conference on uncertainty in AI (UAI).
2.
AvotsDLimEThibauxRThrunS (2002) A probabilistic technique for simultaneous localization and door state estimation with mobile robots in dynamic environments. In: Proceedings of the IEEE/RSJ International conference on intelligent robots and systems (IROS).
3.
BiberPDuckettT (2005) Dynamic maps for long-term operation of mobile service robots. In: Proceedings of robotics: science and systems (RSS).
4.
BlakeAZissermanA (1987) Visual Reconstruction. Cambridge, MA: MIT Press.
5.
BrechtelSGindeleTDillmannR (2010) Recursive importance sampling for efficient grid-based occupancy filtering in dynamic environments. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
6.
ChenCTayCLaugierCMekhnachaK (2006) Dynamic environment modeling with gridmap: A multiple-object tracking application. In: Proceedings of the IEEE International conference on control, automation, robotics and vision (ICARCV).
7.
ChurchillWNewmanP (2012) Practice makes perfect? Managing and leveraging visual experiences for lifelong navigation. In: Proceedings of the IEEE International conference on robotics and automation (ICRA), pp. 4525–4532.
8.
DoucetAde FreitasJMurphyKRusselS (2000) Rao-Blackwellized partcile filtering for dynamic Bayesian networks. In: Proceedings of the conference on uncertainty in artificial intelligence (UAI), Stanford, CA, pp. 176–183.
9.
EliazarAIParrR (2004) DP-SLAM 2.0. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
10.
FoxD (2003) Adapting the sample size in particle filters through KLD-sampling. International Journal of Robotics Research22: 985–1003.
11.
FoxDBurgardWThrunS (1999) Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research11: 391–427.
12.
GallagherGSrinivasaSSBagnellJAFergusonD (2009) GATMO: A generalized approach to tracking movable objects. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
13.
GrisettiGKümmerleRStachnissCBurgardW (2010a) A tutorial on graph-based SLAM. IEEE Transactions on Intelligent Transportation Systems Magazine2: 31–43.
14.
GrisettiGKümmerleRStachnissCFreseUHertzbergC (2010b) Hierarchical optimization on manifolds for online 2D and 3D mapping. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
15.
GrisettiGStachnissCBurgardW (2007) Improved techniques for grid mapping with Rao-Blackwellized particle filters. IEEE Transactions on Robotics23(1): 34–46.
16.
HähnelDTriebelRBurgardWThrunS (2003) Map building with mobile robots in dynamic environments. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
17.
KonoligeKBowmanJ (2009) Towards lifelong visual maps. In: Proceedings of the IEEE/RSJ International conference on intelligent robots and systems (IROS).
18.
KretzschmarHStachnissC (2012) Information-theoretic compression of pose graphs for laser-based slam. International Journal of Robotics Research31: 1219–1230.
19.
LevinDAPeresYWilmerEL (2008) Markov Chains and Mixing Times. American Mathematical Society.
20.
Meyer-DeliusDBeinhoferMBurgardW (2012) Occupancy grid models for robot mapping in changing environments. In: Proceedings of the AAAI conference on artificial intelligence (AAAI), Toronto, Canada.
21.
Meyer-DeliusDHessJGrisettiGBurgardW (2010) Temporary maps for robust localization in semi-static environments. In: Proceedings of the IEEE/RSJ International conference on intelligent robots and systems (IROS), Taipei, Taiwan.
22.
MontemerloMThrunSWhittakerW (2002) Conditional particle filters for simultaneous mobile robot localization and people-tracking. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
23.
MontesanoLMinguezJMontanoL (2005) Modeling the static and the dynamic parts of the environment to improve sensor-based navigation. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
24.
MoravecHElfesA (1985) High resolution maps from wide angle sonar. In: Proceedings of the IEEE International conference on robotics and automation (ICRA).
25.
MurphyK (1999) Bayesian map learning in dynamic environments. In: Proceedings of the conference on neural information processing systems (NIPS), Denver, CO, pp. 1015–1021.
26.
OlsonE (2008) Robust and efficient robotic mapping. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA.
27.
OlsonEWalterMLeonardJTellerS (2005) Single cluster graph partitioning for robotics applications. In: Proceedings of robotics science and systems.
28.
PetrovskayaANgAY (2007) Probabilistic mobile manipulation in dynamic environments, with application to opening doors. In: Proceedings of the International conference on artificial intelligence (IJCAI).
29.
RabinerL (1989) A tutorial on hidden Markov models and selected applications in speech recognition. In: Proceedings of the IEEE77(2), pp. 257–286.
30.
RöwekämperJSprunkCTipaldiGDCyrillSPfaffPBurgardW (2012) On the position accuracy of mobile robot localization based on particle filters combined with scan matching. In: Proceedings of the IEEE/RSJ International conference on intelligent robots and systems (IROS), Villamoura, Protugal.
31.
SaarinenJAndreassonHLilienthalAJ (2012) Independent Markov chain occupancy grid maps for representation of dynamic environments. In: Proceedings of the IEEE/RSJ International conference on intelligent robots and systems (IROS).
32.
SchulzDFoxDHightowerJ (2003) People tracking with anonymous and id-sensors using Rao-Blackwellised particle filters. In: Proceedings of the International conference on artificial intelligence (IJCAI). Available at: http://dl.acm.org/citation.cfm?id=1630659.1630792.
33.
StachnissCBurgardW (2005) Mobile robot mapping and localization in non-static environments. In: Proceedings of the National conference on artificial intelligence (AAAI).
34.
ThrunS (2001) A probabilistic online mapping algorithm for teams of mobile robots. International Journal of Robotics Research20(5): 335–363.
35.
WalcottA (2011) Long-term mobile robot mapping in dynamic environments. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA.
36.
Walcott-BryantAKaessMJohannssonHLeonardJ (2012) Dynamic pose graph SLAM: Long-term mapping in low dynamic environments. In: Proceedings of the IEEE/RSJ International conference on intelligent robots and systems (IROS). Vilamoura, Portugal.
37.
WangCCThorpeCThrunSHebertMDurrant-WhyteH (2007) Simultaneous localization, mapping and moving object tracking. International Journal of Robotics Research26: 889–916.
38.
WolfDFSukhatmeGS (2005) Mobile robot simultaneous localization and mapping in dynamic environments. Autonomous Robots19(1): 53–65.
39.
YangSWWangCC (2011) Feasibility grids for localization and mapping in crowded urban scenes. In: IEEE International conference on robotics and automation (ICRA), Shanghai, China.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
