Simultaneous localization, mapping and moving object tracking (SLAMMOT) involves both simultaneous localization and mapping (SLAM) in dynamic environments and detecting and tracking these dynamic objects. In this paper, a mathematical framework is established to integrate SLAM and moving object tracking. Two solutions are described: SLAM with generalized objects, and SLAM with detection and tracking of moving objects (DATMO). SLAM with generalized objects calculates a joint posterior over all generalized objects and the robot. Such an approach is similar to existing SLAM algorithms, but with additional structure to allow for motion modeling of generalized objects. Unfortunately, it is computationally demanding and generally infeasible. SLAM with DATMO decomposes the estimation problem into two separate estimators. By maintaining separate posteriors for stationary objects and moving objects, the resulting estimation problems are much lower dimensional than SLAM with generalized objects. Both SLAM and moving object tracking from a moving vehicle in crowded urban areas are daunting tasks. Based on the SLAM with DATMO framework, practical algorithms are proposed which deal with issues of perception modeling, data association, and moving object detection. The implementation of SLAM with DATMO was demonstrated using data collected from the CMU Navlab11 vehicle at high speeds in crowded urban environments. Ample experimental results shows the feasibility of the proposed theory and algorithms.
Anguelov, D., Biswas, R., Koller, D., Limketkai, B., Sanner, S., and Thrun, S. (2002). Learning hierarchical object maps of non-stationary environments with mobile robots. In Proceedings of the 17th Annual Conference on Uncertainty in AI (UAI).
2.
Anguelov, D., Koller, D., Parker, E., and Thrun, S. (2004). Detecting and modeling doors with mobile robots . In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
3.
Arnold, J., Shaw, S., and Pasternack, H. (1993). Efficient target tracking using dynamic programming . IEEE Transactions on Aerospace and Electronic Systems, 29(1): 44—56.
4.
Bar-Shalom, Y. and Li, X.-R. (1988). Estimation and Tracking: Principles, Techniques, and Software. YBS, Danvers, MA.
5.
Bar-Shalom, Y. and Li, X.-R. (1995). Multitarget-Multisensor Tracking: Principles andTechniques . YBS, Danvers, MA.
6.
Biswas, R., Limketkai, B., Sanner, S., and Thrun, S. (2002). Towards object mapping in dynamic environments with mobile robots. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland.
7.
Blackman, S. and Popoli, R. (1999). Design and Analysis of Modern Tracking Systems . Artech House, Norwood, MA.
8.
Blom, H.A.P. and Bar-Shalom, Y. (1988). The interacting multiple model algorithm for systems with Markovian switching coefficients. IEEE Transactions On Automatic Control, 33(8): 780—783.
9.
Bosse, M., Newman, P., Leonard, J., Soika, M., Feiten, W., and Teller, S. (2003). An atlas framework for scalavle mapping. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan.
10.
Brand, M. (2001). Morphable 3d models from video. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
11.
Bregler, C., Hertzmann, A., and Biermann, H. (2000). Recovering non-rigid 3d shape from image streams . In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
12.
Choset, H. and Nagatani, K. (2001). Topological simultaneous localization and mapping (slam): Toward exact localization without explicit localization. IEEE Transactions onRobotics and Automation, 17(2): 125—136.
13.
Christensen, H. I. (ed.) (2002). Lecture Notes: SLAM Summer School 2002.
14.
Coraluppi, S. and Carthel, C. (2001). Multiple-hypothesis IMM (MH-IMM) filter for moving and stationary targets. In Proceedings of the International Conference on InformationFusion, Montreal, QC, Canada, pp. TuB1.
15.
Coraluppi, S., Luettgen, M., and Carthel, C. (2000). A hybrid-state estimation algorithm for multi-sensor target tracking. In Proceedings of the International Conference on Information Fusion, Paris, France, pp. TuB118—23.
16.
Cox, I.J. and Hingorani, S.L. (1996). An efficient implemenation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking. IEEE Transactions on Pattern Analysis and Machine intelligence, 18(2): 138—150.
17.
Deans, M.C. (2005). Bearings-Only Localization and Mapping. PhD thesis , The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
18.
Dellaert, F., Burgard, W., Fox, D., and Thrun, S. (1999). Using the condensation algorithm for robust, vision-based mobile robot localization. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'99).
19.
Demirdjian, D. and Horaud, R. (2000). Motion-egomotion discrimination and motion segmentation from image-pair streams. Computer Vision and Image Understanding , 78(1), pp. 53—68.
20.
Durrant-Whyte, H., Majumder, S., Thrun, S., de Battista, M., and Scheding, S. (2003). A bayesian algorithm for simultaneous localization and map building. In 10th International Symposium on Robotics Research, Volume 6, pp. 44—66.
21.
Elfes, A. (1988). Occupancy Grids as a Spatial Representation for Mobile Robot Mapping and Navigation. PhD thesis, Electrical and Computer Engineering/Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
22.
Elfes, A. (1990). Sonar-based real-world mapping and Navigation, in Autonomous Robot Vehicles, Springer, Berlin.
23.
Fortmann, T., Bar-Shalom, Y., and Scheffe, M. (1983). Sonar tracking of multiple targets using joint probabilistic data association. IEEE Journal of Oceanic Engineering , OE-8: 173—184.
24.
Fox, D., Burgard, W., Dellaert, F., and Thrun, S. (1999). Monte carlo localization: Efficient position estimation for mobile robots. In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI'99).
25.
Gish, H. and Mucci, R. (1987). Target state estimation in a multi-target environments . IEEE Transactions on Aerospace and Electronic Systems, 23: 60—73.
26.
Guivant, J.E. and Nebot, E.M. (2001). Optimization of the simultaneous localization and map building algorithm for real-time implementation. IEEE Transaction on Robotics and Automation, 17: 242—257.
27.
Hähnel, D., Burgard, W., Wegbreit, B., and Thrun, S. (2003). Towards lazy data association in SLAM. In Proceedings of the 11th International Symposium of Robotics Research, Siena, Italy.
28.
Hähnel, D., Schulz, D., and Burgard, W. (2002). Map building with mobile robots in populated environments . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne , Switzerland.
29.
Hähnel, D., Triebel, R., Burgard, W., and Thrun, S. (2003). Map building with mobile robots in dynamic environments . In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan.
30.
Hoover, A., Jean-Baptiste, G., Jiang, X., Flynn, P.J., Bunke, H., Goldgof, D., Bowyer, K., Eggert, D., Fitzgibbon, A., and Fisher, R. (1996). An experimental comparison of range image segmentation algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(7): 673— 689.
31.
Kantor, G.A. and Singh, S. (2002). Preliminary results in range-only localization and mapping. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
32.
Kirubarajan, T. and Bar-Shalom, Y. (2000). Tracking evasive move-stop-move targets with an MTI radar using a VS-IMM estimator. In Proceedings of the SPIE Signal and Data Processing of Small Targets, Volume 4048, pp. 236— 246.
33.
Leonard, J. and Durrant-Whyte, H. (1991). Simultaneous map building and localization for an autonomous mobile robot. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Volume 3, pp. 1442— 1447.
34.
Leonard, J.J. and Feder, H.J.S. (1999). A computationally efficient method for large-scale concurrent mapping and localization. In Proceedings of the Ninth International Symposium on Robotics Research.
35.
Lu, F. and Milios, E. (1994). Robot pose estimation in unknown environments by matching 2d range scans. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Seattle, WA, pp. 935— 938.
36.
Lu, F. and Milios, E. (1997). Robot pose estimation in unknown environments by matching 2D range scans. Journal of Intelligent and Robotic Systems, 18(3): 249— 275.
37.
Mazor, E., Averbuch, A., Bar-Shalom, Y., and Dayan, J. (1998). Interacting multiple model methods in target tracking: A survey. IEEE Transactions on Aerospace and Electronic Systems , 34(1): 103—123.
38.
Montemerlo, M. (2003). FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem with Unknown Data Association. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
39.
Montesano, L., Minguez, J., and Montano, L. (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).
40.
Newman, P.M. and Leonard, J.J. (2003). Pure range-only subsea slam. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
41.
Olson, C.F. (2000). Probabilistic self-localization for mobile robots . IEEE Transactions on Robotics and Automation, 16(1): 55—66.
42.
Paskin, M.A. (2003). Thin junction tree filters for simultaneous localization and mapping. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI) (eds Gottlob, G. and Walsh, T. ), pp. 1157— 1164.
43.
Reid, D.B. (1979). An algorithm for tracking multiple targets. IEEE Trans. On Automatic Control, 24(6): 843— 854.
44.
Rogers, S. (1988). Tracking mulitple targets with correlated measurements and maneuvers. IEEE Transactions on Aerospace and Electronic Systems, AES-24(3): 313—315.
45.
Rusinkiewicz, S. and Levoy, M. (2001). Efficient variants of the icp algorithms. In Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, pp. 145—152.
46.
Shea, P.J., Zadra, T., Klamer, D., Frangione, E., and Brouillard, R. (2000). Percision tracking of ground targets. In Proceedings of the IEEE Aerospace Conference, Volume 3, pp. 473—482.
47.
Smith, R.C. and Cheeseman, P. (1986). On the representation and estimation of spatial uncertainty. International Journal of Robotics Research, 5(4): 56—58.
48.
Smith, R.C., Self, M., and Cheeseman, P. (1990). Estimating uncertain spatial relationships in robotics. In Autonomous Robot Vehicles, Springer, Berlin.
49.
Stewart, B., Ko, J., Fox, D., and Konolige, K. (2003). The revisiting problem in mobile robot map building: A hierarchical bayesian approach. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), Siena, Italy.
50.
Thorpe, C. and Durrant-Whyte, H. (2001). Field robots. In 10th International Symposium of Robotics Research, Lorne, Victoria, Australia. Springer-Verlag.
51.
Thrun, S. (2002). Robotic mapping: A survey. Technical Report CMU-CS-02-111, School of Computer Science, Carnegie Mellon University , Pittsburgh.
52.
Thrun, S., Fox, D., and Burgard, W. (1998). A probabilistic approach to concurrent mapping and localization for mobile robots. Machine Learning, 31(1—3): 29—53.
53.
Thrun, S., Koller, D., Ghahramani, Z., Durrant-Whyte, H., and Ng, A. (2002). Simultaneous mapping and localization with sparse extended information filters: theory and initial results. Technical Report CMU-CS-02-112, Carnegie Mellon University, Computer Science Department, Pittsburgh, PA.
54.
Thrun, S. and Liu, Y. (2003). Multi-robot SLAM with sparse extended information filers. In Proceedings of the 11th International Symposium of Robotics Research, Siena, Italy (eds Chatila, R. and Dario, P.).
55.
Torresani, L., Yang, D., Alexander, G., and Bregler, C. (2001). Tracking and modeling non-rigid objects with rank constraints. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
56.
Tugnait, J.K. (1982). Detection and estimation for abruptly changing systems. Automatica, 18: 607—615.
57.
Wang, C.-C. (2004). Simultaneous Localization, Mapping and Moving Object Tracking. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
58.
Wang, C.-C., Duggins, D., Gowdy, J., Kozar, J., MacLachlan, R., Mertz, C., Suppe, A., and Thorpe, C. (2004). Navlab SLAMMOT datasets. www.cs.cmu.edu/∼bobwang/datasets.html. Carnegie Mellon University.
59.
Wang, C.-C., Lo, T.-C., and Yang, S.-W. (2007). Interacting object tracking in crowded urban areas . In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
60.
Wang, C.-C. and Thorpe, C. (2002). Simultaneous localization and mapping with detection and tracking of moving objects. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC.
61.
Wang, C.-C. and Thorpe, C. (2004). A Hierarchical Object based Representation for Simultaneous Localization and Mapping. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sendai, Japan.
62.
Wang, C.-C., Thorpe, C., and Suppe, A. (2003a). Ladar-based detection and tracking of moving objects from a ground vehicle at high speeds. In Proceedings of the IEEE Intelligent Vehicles Symposium, Columbus, OH.
63.
Wang, C.-C., Thorpe, C., and Thrun, S. (2003b). Online simultaneous localization and mapping with detection and tracking of moving objects: Theory and results from a ground vehicle in crowded urban areas. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan.
64.
Wolf, D.F. and Sukhatme, G.S. (2005). Mobile robot simultaneous localization and mapping in dynamic environments. Autonomous Robots, 19(1): 53—65.
65.
Xiao, J., Chai, J., and Kanade, T. (2004). A closed-form solution to non-rigid shape and motion recovery. In The 8th European Conference on Computer Vision (ECCV 2004).
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.
