In this paper we present a technique for mapping partially observable features from multiple uncertain vantage points. The problem of concurrent mapping and localization (CML) is stated as follows. Starting from an initial known position, a mobile robot travels through a sequence of positions, obtaining a set of sensor measurements at each position. The goal is to process the sensor data to produce an estimate of the trajectory of the robot while concurrently building a map of the environment. In this paper, we describe a generalized framework for CML that incorporates temporal as well as spatial correlations. The representation is expanded to incorporate past vehicle positions in the state vector. Estimates of the correlations between current and previous vehicle states are explicitly maintained. This enables the consistent initialization of map features using data from multiple time steps. Updates to the map and the vehicle trajectory can also be performed in batches of data acquired from multiple vantage points. The method is illustrated with sonar data from a testing tank and via experiments with a B21 land mobile robot, demonstrating the ability to perform CML with sparse and ambiguous data.
AndersonB. D. O., and MooreJ. B.1979. Optimal Filtering.Englewood Cliffs, NJ: Prentice-Hall.
2.
AuW.1993. The Sonar of Dolphins.New York: Springer-Verlag.
3.
AyacheN., and FaugerasO.1989. Maintaining representations of the environment of a mobile robot. IEEE Trans. Robotics Automation5(6): 804–819.
4.
BallardD., and BrownC.1982. Computer Vision.Engle-wood Cliffs, NJ: Prentice-Hall.
5.
Bar-ShalomY., and FortmannT. E.1988. Tracking and Data Association.New York: Academic.
6.
BosseM., NewmanP., LeonardJ., and TellerS.2002a. An atlas framework for scalable mapping. Technical Report Marine Robotics Laboratory Technical Memorandum 02-04’ Massachusetts Institute of Technology.
7.
BosseM., RikoskiR., LeonardJ., and TellerS. September 2002b. Vanishing points and 3d lines from omnidirectional video. In Int. Conf. on Image Processing, Rochester, NY.
8.
BrooksR. A.1984. Aspects of mobile robot visual map making. In 2nd Int. Symp. Robotics Research, Tokyo, Japan, pp. 287–293. MIT Press.
9.
BucyR. S., and SenneK. D.1971. Digital synthesis of nonlinear filters. Automatica7: 287–298.
10.
CarpenterR. N.2001. Concurrent mapping and localization and map matching on autonomous underwater vehicles. In IEEE Oceans, Hawaii, pp. 380–389.
11.
CastellanosJ. A., and TardósJ.D.2000. Mobile Robot Localization and Map Building: A Multisensor Fusion Approach.Boston: Kluwer Academic Publishers.
12.
ChiusoA., FavaroP., JinH., and SoattoS.2000. 3-d motion and structure from 2-d motion causually integrated over time: Implementation. In 6th European Conference on Computer Vision.
13.
ChongK. S., and KleemanL.1997a. Sonar based map building in large indoor environments. Technical Report MECSE-1997-1, Department of Electrical and Computer Systems Engineering, Monash University.
14.
ChongK. S., and KleemanL.1997b. Sonar feature map building for a mobile robot. In Proc. IEEE Int. Conf. Robotics and Automation.
15.
ChosetH., and NagataniK. April 2001. Topological simultaneous localization and mapping (slam): toward exact localization without explicit localization. IEEE Trans. Robotics Automation17(2): 125–137.
16.
CoxI. J., and LeonardJ. J. April 1994. Modeling a dynamic environment using a Bayesian multiple hypothesis approach. Artificial Intelligence66(2): 311–344.
17.
DavisonA. J.1998. Mobile Robot Navigation Using Active Vision. Ph. D. thesis, University of Oxford.
18.
DeansM. May 2002. Maximally informative statistics for localization and mapping. In Proc. IEEE Int. Conf. Robotics and Automation, pp. 1824–1829.
19.
DeansM., and HebertM. December 2000. Experimental comparison of techniques for localization and mapping using a bearings only sensor. In Proc. ISER ‘00 7th International Symposium on Experimental Robotics.
20.
DissanayakeM. W. M. G., NewmanP., Durrant-WhyteH. F., ClarkS., and CsorbaM. March 1999. An experimental and theoretical investigation into simultaneous localization and map building. In 6th Int. Symposium on Experimental Robotics, pp. 265–274.
21.
DissanayakeM. W. M. G., NewmanP., Durrant-WhyteH. F., ClarkS., and CsorbaM. June 2001. A solution to the simultaneous localization and map building (slam) problem. IEEE Trans. Robotics Automation17(3): 229–241.
22.
DoucetA., de FreitasN., and GordanN. eds. 2001. Sequential Monte Carlo Methods in Practice.Berlin: Springer-Verlag.
23.
Durrant-WhyteH. F., JulierS., and UhlmannJ.A new method for the nonlinear transformation of means and co-variances in filters and estimators. IEEE Translations on Automatic Control45(3): 477–482, March 2000.
24.
FaugerasO.1993. Three-Dimensional Computer Vision: A Geometric Viewpoint.MIT Press.
25.
FaugerasO., LuongQ.-T., and PapadopouloT.2001. The Geometry of Multiple Images.MIT Press.
26.
FederH. J. S.1999. Simultaneous Stochastic Mapping and Localization. Ph. D. thesis, Massachusetts Institute of Technology.
27.
FederH. J. S., LeonardJ. J., and SmithC.M. July 1999. Adaptive mobile robot navigation and mapping. International Journal of Robotics Research18(7): 650–668.
28.
FenwickJ., NewmanP., and LeonardJ. May 2002. Collaborative concurrent mapping and localization. In Proc. IEEE Int. Conf. Robotics and Automation, Washington, DC, pp. 1810–1817.
29.
FischlerM. A., and BollesR. C.1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM24(6): 381–395.
30.
FleischerS. D.2000. Bounded-Error Vision-Based Navigation of Autonomous Underwater Vehicles. Ph. D. thesis, Stanford University.
31.
GrimsonW. E. L.1990. Object Recognition by Computer: The Role of Geometric Constraints.MIT Press. (With contributions from T. Lozano-Perez and D. P. Huttenlocher).
32.
GuivantJ., and NebotE. June 2001. Optimization of the simultaneous localization and map building algorithm for real time implementation. IEEE Trans. Robotics Automation17(3): 242–257.
33.
GutmannJ.-S., and KonoligeK.1999. Incremental mapping of large cyclic environments. In Int. Symposium on Computational Intelligence in Robotics and Automation.
34.
HartleyR. I., and ZissermanA.2001. Multiple View Geometry in Computer Vision.Cambridge: Cambridge University Press.
35.
HealeA., and KleemanL.2001. Fast target classification using sonar. In Proc. IEEE Int. Workshop on Intelligent Robots and Systems, pp. 1446–1451.
36.
JensfeltP.2001. Approaches to Mobile Robot Localization in Indoor Environments. Ph. D. thesis, Royal Institute of Technology, Stockholm, Sweden.
37.
KavrakiL., SvestkaP., LatombeJ.-C., and OvermarsM. August 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans.Robotics Automation12: 566–580.
38.
KleemanL.2001. Advanced sonar sensing. In JarvisR., and ZelinskyA., eds., Robotics Research: The 10th Int. Symposium, Lorne, Australia.Berlin: Springer Verlag.
39.
KleemanL., and KucR.1993. Mobile robot sonar for target localization and classification. Technical Report ISL-9301, Intelligent Sensors Laboratory, Yale University.
40.
KucR.1996. Fusing binaural sonar information for object recognition. In IEEE/SICE/RSJ Int. Conf. on Multisensor Fusion and Integration for Intelligent Systems, pp. 727–735.
41.
KuipersB. J.2000. The spatial semantic hierarchy. Artificial Intelligence.
42.
KurienT.1990. Issues in the design of practical multitarget tracking algorithms. In Bar-ShalomY., ed., Multitarget-Multisensor Tracking: Advanced Applications, pp. 43–83. Boston: Artech House.
43.
LeonardJ. J., CoxI. J., and Durrant-WhyteH. F. August 1992. Dynamic map building for an autonomous mobile robot. International Journal of Robotics Research11(4): 286–298.
44.
LeonardJ. J., and Durrant-WhyteH. F.1992. Directed Sonar Sensing for Mobile Robot Navigation.Boston: Kluwer Academic Publishers.
45.
LeonardJ. J., and FederH. J. S.2001. Decoupled stochastic mapping. IEEE J. Ocean Eng.26(4): 561–571.
46.
LeonardJ. J., NewmanP., RikoskiR., NeiraJ., and TardósJ.2001. Towards robust data association and feature modeling for concurrent mapping and localization. In JarvisR., and ZelinskyA., eds., Robotics Research: The 10th Int. Symposium, Lorne, Australia.Berlin: Springer Verlag.
47.
MacCormickJ. (2000). Probabilistic modelling and stochastic algorithms for visual localisation and tracking. Ph. D. thesis, University of Oxford.
48.
McLauchlanP. F.2000. A batch/recursive algorithm for 3d scene reconstruction. In Int. Conf. Computer Vision and Pattern Recognition, Volume 2, Hilton Head, SC, pp. 738–743.
49.
McLauchlanP. F., and MurrayD. W.1995. A unifying framework for structure and motion recovery from image sequences. In Proc. Int. Conference on Computer Vision, Boston, MA, pp. 314–320.
50.
McLauchlanP. F., and MurrayD. W. January 1996. Active camera calibration for a head-eye platform using the variable state-dimension filter. IEEE Trans. Pattern Anal. Mach. Intell.18(1): 14–22.
51.
MoriS., ChongC., TseE., and WishnerR. May 1986. Tracking and classifying multiple targets without a priori identification. IEEE Trans. Automatic Control31(5).
52.
MoutarlierP., and ChatilaR.1989. Stochastic multi-sensory data fusion for mobile robot location and environment modeling. In 5th Int. Symposium on Robotics Research, pp. 207–216.
53.
NeiraJ., and TardósJ.2001. Data association in stochastic mapping using the joint compatibility test. IEEE Trans. Robotics Automation17(6): 890–897.
54.
NewmanP., BosseM., and LeonardJ.2002. Autonomous feature-based exploration. Technical Report Marine Robotics Laboratory Technical Memorandum 02-03, Massachusetts Institute of Technology.
55.
NewmanP., LeonardJ., NeiraJ., and TardósJ. May 2002. Explore and return: Experimental validation of real time concurrent mapping and localization. In Proc. IEEE Int. Conf. Robotics and Automation, Washington, DC, pp. 1802–1809.
56.
ReidD. B. December 1979. An algorithm for tracking multiple targets. IEEE Trans. Automatic Control24(6):843–854.
57.
SchmidtH.1998. GOATS-98 - AUV network sonar concepts for shallow water mine countermeasures. Technical Report SACLANTCEN SR-302, SACLANT Undersea Research Centre.
58.
SchultzA. C., and AdamsW.1998. Continuous localization using evidence grids. In Proc. IEEE Int. Conf. Robotics and Automation, pp. 2833–2839.
59.
SmithR., SelfM., and CheesemanP.1987. A stochastic map for uncertain spatial relationships. In 4th International Symposium on Robotics Research. MIT Press.
60.
SorensonH. W.1988. Recursive estimation for nonlinear dynamic systems. In SpallJ. C., ed., Bayesian Analysis of Time Series and Dynamic Models, pp. 127–166. New York: Marcel Dekker.
61.
TardósJ., NeiraJ., NewmanP. M., and LeonardJ. J.2001. Robust mapping and localization in indoor environments using sonar data. Technical Report Marine Robotics Laboratory Technical Memorandum 2001-4’ MIT. See http://oe.mit.edu/~jleonard/pubs/tardosetalijrr_2002.pdf
62.
TaylorC. J., and KriegmanD. J. November 1995. Structure and motion from line segments in multiple images. IEEE Trans. Pattern Anal. Mach. Intell.17(11): 1021–1032.
63.
ThrunS. May 2001. A probabilistic online mapping algorithm for teams of mobile robots. International Journal of Robotics Research20(5): 335–363.
64.
TriggsW., McLauchlanP., HartleyR., and FitzgibbonA.2000. Bundle adjustment for structure from motion. In TriggsB., ZissermanA., and SzeliskiR., eds., Vision Algorithms: Theory and Practice, Vol. 1883 of Lecture Notes in Computer Science, pp. 298–372. Berlin: Springer-Verlag.
65.
WijkO., and ChristensenH. December 2000. Triangulation based fusion of sonar data with application in robot pose tracking. IEEE Trans. Robotics Automation16(6):740–752.
66.
WilliamsS.2001. Efficient solutions to autonomous navigation and mapping problems. Ph. D. thesis, University of Sydney.
67.
WilliamsS., DissanayakeG., and Durrant-WhyteH. June 2001. Constrained initialisation of the simultaneous localisation and mapping algorithm. In Field and Service Robot 2001, Finland, pp. 309–314. ISBN 952-5183-13-0.
68.
YagiY., ShouyaK., and YachidaM. May 2000. Environmental map generation and ego-motion estimation in a dynamic environment for an omni-directional image sensor. In Proc. IEEE Int. Conf. Robotics and Automation, pp. 3493–3498.
69.
ZuninoG., and ChristensenH.I. July 2001. SLAM in realistic environments. In M. Devy, ed., Symposium on Intelligent Robotic Systems, Toulouse, France.
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.
