Full Text:   <1517>

CLC number: TP242

On-line Access: 2011-07-04

Received: 2010-07-19

Revision Accepted: 2010-12-13

Crosschecked: 2011-05-05

Cited: 0

Clicked: 3388

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.7 P.574-588


Map building for dynamic environments using grid vectors

Author(s):  Wen-fei WANG, Rong XIONG, Jian CHU

Affiliation(s):  State Key Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   rxiong@iipc.zju.edu.cn

Key Words:  Grid vector, Line, Segments, Dynamic, Simultaneous localization and mapping (SLAM), Expectation maximization (EM)

Wen-fei WANG, Rong XIONG, Jian CHU. Map building for dynamic environments using grid vectors[J]. Journal of Zhejiang University Science C, 2011, 12(7): 574-588.

@article{title="Map building for dynamic environments using grid vectors",
author="Wen-fei WANG, Rong XIONG, Jian CHU",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Map building for dynamic environments using grid vectors
%A Wen-fei WANG
%A Jian CHU
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 7
%P 574-588
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1000255

T1 - Map building for dynamic environments using grid vectors
A1 - Wen-fei WANG
A1 - Rong XIONG
A1 - Jian CHU
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 7
SP - 574
EP - 588
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1000255

This paper addresses the problem of creating a geometric map with a mobile robot in a dynamic indoor environment. To form an accurate model of the environment, we present a novel map representation called the ‘grid vector’, which combines each vector that represents a directed line segment with a slender occupancy grid map. A modified expectation maximization (EM) based approach is proposed to evaluate the dynamic objects and simultaneously estimate the robot path and the map of the environment. The probability of each grid vector is evaluated in the expectation step and then used to distinguish the vector into static and dynamic ones. The robot path and map are estimated in the maximization step with a graph-based simultaneous localization and mapping (SLAM) method. The representation we introduce provides advantages on making the SLAM method strictly statistic, reducing memory cost, identifying the dynamic objects, and improving the accuracy of the data associations. The SLAM algorithm we present is efficient in computation and convergence. Experiments on three different kinds of data sets show that our representation and algorithm can generate an accurate static map in a dynamic indoor environment.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Anguelov, D., Biswas, R., Koller, D., Limketkai, B., Sanner, S., Thrun, S., 2002. Learning Hierarchical Object Maps of Non-stationary Environments with Mobile Robots. Proc. Conf. on Uncertainty in Artificial Intelligence, p.10-17.

[2]Arras, K.O., Siegwart, R.Y., 1997. Feature extraction and scene interpretation for map-based navigation and map building. SPIE, 3210:42-53.

[3]Bailey, T., 2002. Mobile Robot Localisation and Mapping in Extensive Outdoor Environments. PhD Thesis, Australian Center for Field Robotics, University of Sydney, Sydney, Australia.

[4]Biswas, R., Limketkai, B., Sanner, S., Thrun, S., 2002. Towards Object Mapping in Non-stationary Environments with Mobile Robots. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 1:1014-1019.

[5]Borges, G.A., Aldon, M.J., 2004. Line extraction in 2D range images for mobile robotics. J. Intell. Robot. Syst., 40(3):267-297.

[6]Brunskill, E., Roy, N., 2005. SLAM Using Incremental Probabilistic PCA and Dimensionality Reduction. Proc. IEEE Int. Conf. on Robotics and Automation, p.342-347.

[7]Connette, C.P., Meister, O., Hägele, M., Trommer, G.F., 2007. Decomposition of Line Segments into Corner and Statistical Grown Line Features in an EKF-SLAM Framework. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, p.3884-3891.

[8]Frese, U., 2006. A discussion of simultaneous localization and mapping. Auton. Robots, 20(1):25-42.

[9]Grisetti, G., Stachniss, C., Grzonka, S., Burgard, W., 2007a. A Tree Parameterization for Efficiently Computing Maximum Likelihood Maps Using Gradient Descent. Proc. Robotics: Science and Systems.

[10]Grisetti, G., Tipaldi, G.D., Stachniss, C., Burgard, W., Nardi, D., 2007b. Fast and accurate SLAM with Rao-Blackwellized particle filters. Robot. Auton. Syst., 55(1):30-38.

[11]Grisetti, G., Lodi Rizzini, D., Stachniss, C., Olson, E., Burgard, W., 2008. Online Constraint Network Optimization for Efficient Maximum Likelihood Map Learning. Proc. IEEE Int. Conf. on Robotics and Automation, 1:1880-1885.

[12]Gutmann, J.S., Konolige, K., 1999. Incremental Mapping of Large Cyclic Environments. Proc. IEEE Int. Symp. on Computational Intelligence in Robotics and Automation, p.318-325.

[13]Hahnel, D., Burgard, W., Fox, D., Thrun, S., 2003. An Efficient Fastslam Algorithm for Generating Maps of Large-Scale Cyclic Environments from Raw Laser Range Measurements. Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 1:206-211.

[14]Lu, F., Milios, E., 1997a. Globally consistent range scan alignment for environment mapping. Auton. Robots, 4(4):333-349.

[15]Lu, F., Milios, E., 1997b. Robot pose estimation in unknown environments by matching 2D range scans. J. Intell. Robot. Syst., 18(3):249-275.

[16]Montesano, L., Minguez, J., Montano, L., 2005. Modeling the Static and the Dynamic Parts of the Environment to Improve Sensor-Based Navigation. Proc. IEEE Int. Conf. on Robotics and Automation, p.4556-4562.

[17]Olson, E., Leonard, J., Teller, S., 2006. Fast Iterative Alignment of Pose Graphs with Poor Initial Estimates. Proc. IEEE Int. Conf. on Robotics and Automation, p.2262-2269.

[18]Siegwart, R., Arras, K.O., Bouabdallah, S., Burnier, D., Froidevaux, G., Greppin, X., Jensen, B., Lorotte, A., Mayor, L., Meisser, M., et~al., 2003. Robox at Expo.02: a large-scale installation of personal robots. Robot. Auton. Syst., 42(3-4):203-222.

[19]Sohn, H.J., Kim, B.K., 2008. An efficient localization algorithm based on vector matching for mobile robots using laser range finders. J. Intell. Robot. Syst., 51(4):461-488.

[20]Sohn, H.J., Kim, B.K., 2009. VecSLAM: an efficient vector-based SLAM algorithm for indoor environments. J. Intell. Robot. Syst., 56(3):301-318.

[21]Thrun, S., 2002. Robotic Mapping: a Survey. In: Lakemeyer, G., Nebel, B. (Eds.), Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann Publishers Inc., San Francisco, p.1-35.

[22]Thrun, S., Burgard, W., Fox, D., 1998. A probabilistic approach to concurrent mapping and localization for mobile robots. Mach. Learn., 31(1/3):29-53.

[23]Thrun, S., Burgard, W., Fox, D., 2005. Probabilistic Robotics. MIT Press, Cambridge, p.153-169.

[24]Walter, M.R., Eustice, R.M., Leonard, J.J., 2007. Exactly sparse extended information filters for feature-based SLAM. Int. J. Robot. Res., 26(4):335-359.

[25]Williams, S., Dissanayake, G., Durrant-Whyte, H., 2001. Towards terrain-aided navigation for underwater robotics. Adv. Robot., 15(5):533-549.

[26]Yamauchi, B., Langley, P., 1997. Place recognition in dynamic environments. J. Robot. Syst., 14(2):107-120.

[27]Zhang, L., Ghosh, B.K., 2000. Line Segment Based Map Building and Localization Using 2D Laser Rangefinder. Proc. IEEE Int. Conf. on Robotics and Automation, 3:2538-2543.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE