“Multi-robot collaborative dense scene reconstruction” by Dong, Xu, Zhou, Tagliasacchi, Xin, et al. …

  • ©Siyan Dong, Kai Xu, Qiang Zhou, Andrea Tagliasacchi, Shiqing Xin, Matthias Niessner, and Baoquan Chen




    Multi-robot collaborative dense scene reconstruction

Session/Category Title: Scene and Object Reconstruction



    We present an autonomous scanning approach which allows multiple robots to perform collaborative scanning for dense 3D reconstruction of unknown indoor scenes. Our method plans scanning paths for several robots, allowing them to efficiently coordinate with each other such that the collective scanning coverage and reconstruction quality is maximized while the overall scanning effort is minimized. To this end, we define the problem as a dynamic task assignment and introduce a novel formulation based on Optimal Mass Transport (OMT). Given the currently scanned scene, a set of task views are extracted to cover scene regions which are either unknown or uncertain. These task views are assigned to the robots based on the OMT optimization. We then compute for each robot a smooth path over its assigned tasks by solving an approximate traveling salesman problem. In order to showcase our algorithm, we implement a multi-robot auto-scanning system. Since our method is computationally efficient, we can easily run it in real time on commodity hardware, and combine it with online RGB-D reconstruction approaches. In our results, we show several real-world examples of large indoor environments; in addition, we build a benchmark with a series of carefully designed metrics for quantitatively evaluating multi-robot autoscanning. Overall, we are able to demonstrate high-quality scanning results with respect to reconstruction quality and scanning efficiency, which significantly outperforms existing multi-robot exploration systems.


    1. AMCL. 2013. The ROS Package of AMCL. http://wiki.ros.org/amcl.Google Scholar
    2. Omur Arslan and Daniel E Koditschek. 2016. Voronoi-based coverage control of heterogeneous disk-shaped robots. In Proc. ICRA. IEEE, 4259–4266.Google ScholarDigital Library
    3. Nikolay Atanasov, Jerome Le Ny, Kostas Daniilidis, and George J Pappas. 2015. Decentralized active information acquisition: Theory and application to multi-robot SLAM. In Proc. ICRA. IEEE, 4775–4782.Google ScholarCross Ref
    4. Aurenhammer. 1987. Power diagrams: properties, algorithms and applications. Siam Journal on Computing (1987). Google ScholarDigital Library
    5. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-constrained point distributions: a variant of Lloyd’s method. Vol. 28. ACM. Google ScholarDigital Library
    6. T. Bektas. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34, 209–219 (2006).Google ScholarCross Ref
    7. Subhrajit Bhattacharya, Robert Ghrist, and Vijay Kumar. 2014. Multi-robot coverage and exploration on Riemannian manifolds with boundaries. The International Journal of Robotics Research 33, 1 (2014), 113–137. Google ScholarDigital Library
    8. Sofien Bouaziz, Andrea Tagliasacchi, and Mark Pauly. 2013. Sparse iterative closest point. Computer Graphics Forum (SGP) (2013), 113–123. Google ScholarDigital Library
    9. Angel Chang, Angela Dai, Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang. 2017. Matterport3D: Learning from RGB-D Data in Indoor Environments. International Conference on 3D Vision (3DV) (2017).Google ScholarCross Ref
    10. Benjamin Charrow, Gregory Kahn, Sachin Patil, Sikang Liu, Ken Goldberg, Pieter Abbeel, Nathan Michael, and Vijay Kumar. 2015. Information-theoretic planning with trajectory optimization for dense 3D mapping. In Proceedings of Robotics: Science and Systems.Google ScholarCross Ref
    11. Jiawen Chen, Dennis Bautembach, and Shahram Izadi. 2013. Scalable real-time volumetric surface reconstruction. ACM Transactions on Graphics (TOG) 32, 4 (2013), 113. Google ScholarDigital Library
    12. Shengyong Chen, Youfu Li, and Ngai Ming Kwok. 2011. Active vision in robotic systems: A survey of recent developments. International Journal of Robotics Research (2011). Google ScholarDigital Library
    13. Sungjoon Choi, Qian-Yi Zhou, and Vladlen Koltun. 2015. Robust reconstruction of indoor scenes. In Proc. CVPR. 5556–5565.Google Scholar
    14. Nicos Christofides. 1976. Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem. (1976).Google Scholar
    15. Paolo Cignoni, Claudio Rocchini, and Roberto Scopigno. 1998. Metro: Measuring error on simplified surfaces. Computer Graphics Forum (1998).Google Scholar
    16. Jorge Cortés. 2010. Coverage optimization and spatial load balancing by robotic sensor networks. IEEE Trans. Automat. Control 55, 3 (2010), 749–754.Google ScholarCross Ref
    17. Brian Curless and Marc Levoy. 1996. A volumetric method for building complex models from range images. In Proc. of SIGGRAPH. 303–312. Google ScholarDigital Library
    18. Angela Dai, Matthias Nießner, Michael Zollhöfer, Shahram Izadi, and Christian Theobalt. 2017. BundleFusion: Real-time Globally Consistent 3D Reconstruction using On-the-fly Surface Reintegration. ACM Transactions on Graphics (TOG) 36, 3 (2017), 24. Google ScholarDigital Library
    19. Qiang Du, Maria Emelianenko, and Lili Ju. 2006. Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations. SIAM J. Numer. Anal. 44, 1 (2006), 102–119. Google ScholarDigital Library
    20. Jan Faigl, Miroslav Kulich, and Libor Přeučil. 2012. Goal assignment using distance cost in multi-robot exploration. In Proc. IROS. IEEE, 3741–3746.Google ScholarCross Ref
    21. Xinyi Fan, Linguang Zhang, Benedict Brown, and Szymon Rusinkiewicz. 2016. Automated View and Path Planning for Scalable Multi-Object 3D Scanning. ACM Trans. on Graph. (SIGGRAPH Asia) 35, 6 (2016), 239. Google ScholarDigital Library
    22. Sean Ryan Fanello, Christoph Rhemann, Vladimir Tankovich, Adarsh Kowdle, Sergio Orts Escolano, David Kim, and Shahram Izadi. 2016. Hyperdepth: Learning depth from structured light without matching. In Proc. CVPR.Google ScholarCross Ref
    23. Christian Forster, Simon Lynen, Laurent Kneip, and Davide Scaramuzza. 2013. Collaborative monocular slam with multiple micro aerial vehicles. In IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 3962–3970.Google ScholarCross Ref
    24. Saurabh Gupta, James Davidson, Sergey Levine, Rahul Sukthankar, and Jitendra Malik. 2017. Cognitive mapping and planning for visual navigation. arXiv preprint arXiv:1702.03920 3 (2017).Google Scholar
    25. Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent. 2004. Optimal mass transport for registration and warping. International Journal of computer vision 60, 3 (2004), 225–240. Google ScholarDigital Library
    26. Ankur Handa, Thomas Whelan, John McDonald, and Andrew J Davison. 2014. A benchmark for RGB-D visual odometry, 3D reconstruction and SLAM. In Proc. ICRA. IEEE, 1524–1531.Google ScholarCross Ref
    27. Wolfgang Hess, Damon Kohler, Holger Rapp, and Daniel Andor. 2016. Real-time loop closure in 2D LIDAR SLAM. In Proc. ICRA. IEEE, 1271–1278.Google ScholarDigital Library
    28. Armin Hornung, Kai M. Wurm, Maren Bennewitz, Cyrill Stachniss, and Wolfram Burgard. 2013. OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees. Autonomous Robots 34, 3 (2013), 189–206. Google ScholarDigital Library
    29. Chengdu Huang, Gang Zhou, Tarek F Abdelzaher, Sang Hyuk Son, and John A Stankovic. 2005. Load balancing in bounded-latency content distribution. In Proc. of RTSS. IEEE, 12–pp. Google ScholarDigital Library
    30. Shahram Izadi, David Kim, Otmar Hilliges, David Molyneaux, Richard Newcombe, Pushmeet Kohli, Jamie Shotton, Steve Hodges, Dustin Freeman, Andrew Davison, and Andrew Fitzgibbon. 2011. KinectFusion: Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera. In UIST. 559–568. Google ScholarDigital Library
    31. O. Kahler, V. A. Prisacariu, C. Y. Ren, X. Sun, P. H. S Torr, and D. W. Murray. 2015. Very High Frame Rate Volumetric Integration of Depth Images on Mobile Device. IEEE Trans. Vis. & Computer Graphics (ISMAR) 22, 11 (2015). Google ScholarDigital Library
    32. N Koenig and A Howard. 2004. Design and use paradigms for Gazebo, an open-source multi-robot simulator. In International Conference on Intelligent Robots and Systems. 2149–2154 vol. 3.Google ScholarCross Ref
    33. M. Krainin, B. Curless, and D. Fox. 2011. Autonomous Generation of Complete 3D Object Models Using Next Best View Manipulation Planning. In Proc. ICRA.Google Scholar
    34. Simon Kriegel, Christian Rink, Tim Bodenmüller, Alexander Narr, Michael Suppa, and Gerd Hirzinger. 2012. Next-best-scan planning for autonomous 3D modeling. In Proc. IROS. 2850–2856.Google ScholarCross Ref
    35. Ligang Liu, Xi Xia, Han Sun, Qi Shen, Juzhan Xu, Bin Chen, Hui Huang, and Kai Xu. 2018. Object-Aware Guidance for Autonomous Scene Reconstruction. ACM Trans. on Graph. (SIGGRAPH) 37, 4 (2018). Google ScholarDigital Library
    36. Kok-Lim Low and Anselmo Lastra. 2006. An adaptive hierarchical next-best-view algorithm for 3d reconstruction of indoor scenes. In Proceedings of 14th Pacific Conference on Computer Graphics and Applications (Pacific Graphics 2006).Google Scholar
    37. Gajamohan Mohanarajah, Vladyslav Usenko, Mayank Singh, Raffaello D’Andrea, and Markus Waibel. 2015. Cloud-based collaborative 3D mapping in real-time with low-cost robots. IEEE Transactions on Automation Science and Engineering 12, 2 (2015), 423–431.Google ScholarCross Ref
    38. Richard A Newcombe, Andrew J Davison, Shahram Izadi, Pushmeet Kohli, Otmar Hilliges, Jamie Shotton, David Molyneaux, Steve Hodges, David Kim, and Andrew Fitzgibbon. 2011. KinectFusion: Real-time dense surface mapping and tracking. In Proc. IEEE Int. Symp. on Mixed and Augmented Reality. 127–136. Google ScholarDigital Library
    39. M. Nießner, M. Zollhöfer, S. Izadi, and M. Stamminger. 2013. Real-time 3D Reconstruction at Scale using Voxel Hashing. ACM Trans. on Graph. (SIGGRAPH Asia) 32, 6 (2013), 169. Google ScholarDigital Library
    40. Rushabh Patel, Paolo Frasca, and Francesco Bullo. 2014. Centroidal area-constrained partitioning for robotic networks. Journal of Dynamic Systems, Measurement, and Control 136, 3 (2014), 031024.Google ScholarCross Ref
    41. Svetlozar T Rachev and Ludger Rüschendorf. 1998. Mass Transportation Problems: Volume I: Theory. Vol. 1. Springer Science & Business Media.Google Scholar
    42. ROS. 2014. ROS Wiki. http://wiki.ros.org/.Google Scholar
    43. Patrik Schmuck and Margarita Chli. 2017. Multi-UAV collaborative monocular SLAM. In Proc. ICRA. IEEE, 3863–3870.Google ScholarCross Ref
    44. Shuran Song, Fisher Yu, Andy Zeng, Angel X Chang, Manolis Savva, and Thomas Funkhouser. 2017. Semantic Scene Completion from a Single Depth Image. (2017).Google Scholar
    45. S. Song, L. Zhang, and J. Xiao. 2015. Robot In a Room: Toward Perfect Object Recognition in Closed Environments. arXiv preprint arXiv:1507.02703 (2015).Google Scholar
    46. Sebastian Thrun, Wolfram Burgard, and Dieter Fox. 2005. Probabilistic robotics. MIT press.Google ScholarDigital Library
    47. Anastasia Tkach, Mark Pauly, and Andrea Tagliasacchi. 2016. Sphere-Meshes for Real-Time Hand Modeling and Tracking. ACM Transaction on Graphics (Proc. SIGGRAPH Asia) (2016). Google ScholarDigital Library
    48. A Visser, J De Hoog, A Jimenezgonzalez, and J. R Martinezde Dios. 2013. Discussion of Multi-Robot Exploration in Communication-Limited Environments. In 2013 ICRA Workshop on Towards Fully Decentralized Multi-Robot Systems: Hardware, Software and Integration.Google Scholar
    49. Thomas Whelan, Stefan Leutenegger, Renato F Salas-Moreno, Ben Glocker, and Andrew J Davison. 2015. ElasticFusion: Dense SLAM without a pose graph. In Proc. Robotics: Science and Systems.Google ScholarCross Ref
    50. Shihao Wu, Wei Sun, Pinxin Long, Hui Huang, Daniel Cohen-Or, Minglun Gong, Oliver Deussen, and Baoquan Chen. 2014. Quality-driven poisson-guided autoscanning. ACM Trans. on Graph. (SIGGRAPH Asia) 33, 6 (2014), 203. Google ScholarDigital Library
    51. Shi-Qing Xin, Bruno Lévy, Zhonggui Chen, Lei Chu, Yaohui Yu, Changhe Tu, and Wenping Wang. 2016. Centroidal Power Diagrams with Capacity Constraints: Computation, Applications, and Extension. ACM Trans. on Graph. 35, 6 (2016), 244:1–244:12. Google ScholarDigital Library
    52. Kai Xu, Lintao Zheng, Zihao Yan, Guohang Yan, Eugene Zhang, Matthias Nießner, Oliver Deussen, Daniel Cohen-Or, and Hui Huang. 2017. Autonomous Reconstruction of Unknown Indoor Scenes Guided by Time-varying Tensor Fields. ACM Transactions on Graphics 2017 (TOG) (2017). Google ScholarDigital Library
    53. Zhi Yan, Nicolas Jouandeau, and Arab Ali Cherif. 2013. A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems 10, 12 (2013), 399.Google ScholarCross Ref
    54. Yizhong Zhang, Weiwei Xu, Yiying Tong, and Kun Zhou. 2014. Online Structure Analysis for Real-time Indoor Scene Reconstruction. ACM Trans. on Graph. 34, 5 (2014), 159. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: