{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T19:47:47Z","timestamp":1782935267541,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:00:00Z","timestamp":1707868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:00:00Z","timestamp":1707868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["52371275"],"award-info":[{"award-number":["52371275"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Royal Academy of Engineering under the Industrial Fellowships programme","award":["IF2223-199"],"award-info":[{"award-number":["IF2223-199"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Intell Robot Appl"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Exploring large-scale environments autonomously poses a significant challenge. As the size of environments increases, the computational cost becomes a hindrance to real-time operation. Additionally, while frontier-based exploration planning provides convenient access to environment frontiers, it suffers from slow global exploration speed. On the other hand, sampling-based methods can effectively explore individual regions but fail to cover the entire environment. To overcome these limitations, we present a hierarchical exploration approach that integrates frontier-based and sampling-based methods. It assesses the informational gain of sampling points by considering the quantity of frontiers in the vicinity, and effectively enhances exploration efficiency by utilizing a utility function that takes account of the direction of advancement for the purpose of selecting targets. To improve the search speed of global topological graph in large-scale environments, this paper introduces a method for constructing a sparse topological graph. It incrementally constructs a three-dimensional sparse topological graph by dynamically capturing the spatial structure of free space through uniform sampling. In various challenging simulated environments, the proposed approach demonstrates comparable exploration performance in comparison with the state-of-the-art approaches. Notably, in terms of computational efficiency, the single iteration time of our approach is less than one-tenth of that required by the recent advances in autonomous exploration.<\/jats:p>","DOI":"10.1007\/s41315-023-00318-7","type":"journal-article","created":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T13:02:50Z","timestamp":1707915770000},"page":"111-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast autonomous exploration with sparse topological graphs in large-scale environments"],"prefix":"10.1007","volume":"8","author":[{"given":"Changyun","family":"Wei","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianbin","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ze","family":"Ji","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,2,14]]},"reference":[{"issue":"3","key":"318_CR1","doi-asserted-by":"publisher","first-page":"4528","DOI":"10.1109\/LRA.2021.3068923","volume":"6","author":"A Batinovic","year":"2021","unstructured":"Batinovic, A., Petrovic, T., Ivanovic, A., Petric, F., Bogdan, S.: A multi-resolution frontier-based planner for autonomous 3d exploration. IEEE Robot. Autom. Lett. 6(3), 4528\u20134535 (2021)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"318_CR2","doi-asserted-by":"crossref","unstructured":"Bircher, A., Kamel, M., Alexis, K., Oleynikova, H., Siegwart, R.: Receding horizon \u201cnext-best-view\" planner for 3d exploration. In: IEEE International Conference on Robotics and Automation, IEEE, pp. 1462\u20131468 (2016)","DOI":"10.1109\/ICRA.2016.7487281"},{"key":"318_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Zhou, B., Lin, J., Zhang, Y., Zhang, F., Shen, S.: Fast 3d sparse topological skeleton graph generation for mobile robot global planning. In: International Conference on Intelligent Robots and Systems, IEEE, pp. 10283\u201310289 (2022)","DOI":"10.1109\/IROS47612.2022.9981397"},{"key":"318_CR4","doi-asserted-by":"crossref","unstructured":"Cieslewski, T., Kaufmann, E., Scaramuzza, D.: Rapid exploration with multi-rotors: a frontier selection method for high speed flight. In: International Conference on Intelligent Robots and Systems, pp. 2135\u20132142 (2017). IEEE","DOI":"10.1109\/IROS.2017.8206030"},{"key":"318_CR5","doi-asserted-by":"crossref","unstructured":"Dai, A., Papatheodorou, S., Funk, N., Tzoumanikas, D., Leutenegger, S.: Fast frontier-based information-driven autonomous exploration with an mav. In: 2020 IEEE International Conference on Robotics and Automation (ICRA), IEEE, pp. 9570\u20139576 (2020)","DOI":"10.1109\/ICRA40945.2020.9196707"},{"key":"318_CR6","doi-asserted-by":"crossref","unstructured":"Dang, T., Mascarich, F., Khattak, S., Papachristos, C., Alexis, K.: Graph-based path planning for autonomous robotic exploration in subterranean environments. In: International Conference on Intelligent Robots and Systems, IEEE, pp. 3105\u20133112 (2019)","DOI":"10.1109\/IROS40897.2019.8968151"},{"key":"318_CR7","doi-asserted-by":"crossref","unstructured":"Dharmadhikari, M., Dang, T., Solanka, L., Loje, J., Nguyen, H., Khedekar, N., Alexis, K.: Motion primitives-based path planning for fast and agile exploration using aerial robots. In: International Conference on Robotics and Automation, IEEE, pp. 179\u2013185 (2020)","DOI":"10.1109\/ICRA40945.2020.9196964"},{"key":"318_CR8","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10514-012-9321-0","volume":"34","author":"A Hornung","year":"2013","unstructured":"Hornung, A., Wurm, K.M., Bennewitz, M., Stachniss, C., Burgard, W.: Octomap: An efficient probabilistic 3d mapping framework based on octrees. Auton. Robot. 34, 189\u2013206 (2013)","journal-title":"Auton. Robot."},{"issue":"3","key":"318_CR9","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1109\/LRA.2023.3236573","volume":"8","author":"J Huang","year":"2023","unstructured":"Huang, J., Zhou, B., Fan, Z., Zhu, Y., Jie, Y., Li, L., Cheng, H.: Fael: Fast autonomous exploration for large-scale environments with a mobile robot. IEEE Robot. Autom. Lett. 8(3), 1667\u20131674 (2023)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"318_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10514-012-9298-8","volume":"33","author":"M Juli\u00e1","year":"2012","unstructured":"Juli\u00e1, M., Gil, A., Reinoso, O.: A comparison of path planning strategies for autonomous exploration and mapping of unknown environments. Auton. Robot. 33, 427\u2013444 (2012)","journal-title":"Auton. Robot."},{"key":"318_CR11","doi-asserted-by":"crossref","unstructured":"Karaman, S., Frazzoli, E.: Sampling-based motion planning with deterministic $$\\mu$$-calculus specifications. In: The 48h IEEE Conference on Decision and Control, IEEE, pp. 2222\u20132229 (2009)","DOI":"10.1109\/CDC.2009.5400278"},{"issue":"5","key":"318_CR12","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1109\/TRO.2013.2264865","volume":"29","author":"M Kazemi","year":"2013","unstructured":"Kazemi, M., Gupta, K.K., Mehrandezh, M.: Randomized kinodynamic planning for robust visual servoing. IEEE Trans. Rob. 29(5), 1197\u20131211 (2013)","journal-title":"IEEE Trans. Rob."},{"key":"318_CR13","doi-asserted-by":"crossref","unstructured":"Kulkarni, M., Dharmadhikari, M., Tranzatto, M., Zimmermann, S., Reijgwart, V., De\u00a0Petris, P., Nguyen, H., Khedekar, N., Papachristos, C., Ott, L., et al.: Autonomous teamed exploration of subterranean environments using legged and aerial robots. In: 2022 International Conference on Robotics and Automation (ICRA), IEEE, pp. 3306\u20133313 (2022)","DOI":"10.1109\/ICRA46639.2022.9812401"},{"key":"318_CR14","doi-asserted-by":"crossref","unstructured":"Li, S., Xu, X., Zuo, L.: Dynamic path planning of a mobile robot with improved q-learning algorithm. In: IEEE International Conference on Information and Automation, IEEE, pp. 409\u2013414 (2015)","DOI":"10.1109\/ICInfA.2015.7279322"},{"key":"318_CR15","doi-asserted-by":"crossref","unstructured":"Lindemann, S.R., LaValle, S.M.: Current issues in sampling-based motion planning. In: The Eleventh International Symposium, pp. 36\u201354. Springer, Berlin (2005)","DOI":"10.1007\/11008941_5"},{"key":"318_CR16","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.aei.2018.05.005","volume":"37","author":"Z Ma","year":"2018","unstructured":"Ma, Z., Liu, S.: A review of 3d reconstruction techniques in civil engineering and their applications. Adv. Eng. Inform. 37, 163\u2013174 (2018)","journal-title":"Adv. Eng. Inform."},{"issue":"3","key":"318_CR17","doi-asserted-by":"publisher","first-page":"1680","DOI":"10.1109\/LRA.2017.2655144","volume":"2","author":"Z Meng","year":"2017","unstructured":"Meng, Z., Qin, H., Chen, Z., Chen, X., Sun, H., Lin, F., Ang, M.H.: A two-stage optimized next-view planning framework for 3-d unknown environment exploration, and structural reconstruction. IEEE Robot. Autom. Lett. 2(3), 1680\u20131687 (2017)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"2","key":"318_CR18","doi-asserted-by":"publisher","first-page":"1500","DOI":"10.1109\/LRA.2020.2969191","volume":"5","author":"L Schmid","year":"2020","unstructured":"Schmid, L., Pantic, M., Khanna, R., Ott, L., Siegwart, R., Nieto, J.: An efficient sampling-based method for online informative path planning in unknown environments. IEEE Robot. Autom. Lett. 5(2), 1500\u20131507 (2020)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"3","key":"318_CR19","doi-asserted-by":"publisher","first-page":"4504","DOI":"10.1109\/LRA.2021.3068954","volume":"6","author":"L Schmid","year":"2021","unstructured":"Schmid, L., Reijgwart, V., Ott, L., Nieto, J., Siegwart, R., Cadena, C.: A unified approach for autonomous volumetric exploration of large scale environments under severe odometry drift. IEEE Robot. Autom. Lett. 6(3), 4504\u20134511 (2021)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"2","key":"318_CR20","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1109\/LRA.2019.2897343","volume":"4","author":"M Selin","year":"2019","unstructured":"Selin, M., Tiger, M., Duberg, D., Heintz, F., Jensfelt, P.: Efficient autonomous exploration planning of large-scale 3-d environments. IEEE Robot. Autom. Lett. 4(2), 1699\u20131706 (2019)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"318_CR21","doi-asserted-by":"crossref","unstructured":"Sun, Z., Wu, B., Xu, C., Kong, H.: Ada-detector: adaptive frontier detector for rapid exploration. In: 2022 International Conference on Robotics and Automation (ICRA), pp. 3706\u20133712, IEEE (2022)","DOI":"10.1109\/ICRA46639.2022.9811614"},{"key":"318_CR22","doi-asserted-by":"crossref","unstructured":"Yamauchi, B.: Frontier-based exploration using multiple robots. In: The Second International Conference on Autonomous Agents, pp. 47\u201353 (1998)","DOI":"10.1145\/280765.280773"},{"issue":"12","key":"318_CR23","doi-asserted-by":"publisher","first-page":"13131","DOI":"10.1109\/TIE.2021.3137616","volume":"69","author":"X Zhang","year":"2021","unstructured":"Zhang, X., Chu, Y., Liu, Y., Zhang, X., Zhuang, Y.: A novel informative autonomous exploration strategy with uniform sampling for quadrotors. IEEE Trans. Industr. Electron. 69(12), 13131\u201313140 (2021)","journal-title":"IEEE Trans. Industr. Electron."},{"issue":"2","key":"318_CR24","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1109\/LRA.2021.3131754","volume":"7","author":"P Zhong","year":"2021","unstructured":"Zhong, P., Chen, B., Lu, S., Meng, X., Liang, Y.: Information-driven fast marching autonomous exploration with aerial robots. IEEE Robot. Autom. Lett. 7(2), 810\u2013817 (2021)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"318_CR25","doi-asserted-by":"crossref","unstructured":"Zhu, H., Cao, C., Xia, Y., Scherer, S., Zhang, J., Wang, W.: Dsvp: dual-stage viewpoint planner for rapid exploration by dynamic expansion. In: 2021 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, pp. 7623\u20137630 (2021)","DOI":"10.1109\/IROS51168.2021.9636473"},{"key":"318_CR26","doi-asserted-by":"crossref","unstructured":"Zhu, C., Ding, R., Lin, M., Wu, Y.: A 3d frontier-based exploration tool for mavs. In: The 27th International Conference on Tools with Artificial Intelligence, IEEE, pp. 348\u2013352 (2015)","DOI":"10.1109\/ICTAI.2015.60"}],"container-title":["International Journal of Intelligent Robotics and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41315-023-00318-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41315-023-00318-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41315-023-00318-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T05:57:03Z","timestamp":1710741423000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41315-023-00318-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,14]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["318"],"URL":"https:\/\/doi.org\/10.1007\/s41315-023-00318-7","relation":{},"ISSN":["2366-5971","2366-598X"],"issn-type":[{"value":"2366-5971","type":"print"},{"value":"2366-598X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,14]]},"assertion":[{"value":"9 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable. Our manuscript does not report results of studies involving humans or animals.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable. Our manuscript does not report results of studies involving humans or animals.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"All authors have approved and consented to publish the manuscript.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"The authors have no relevant financial or nonfinancial interests to disclose.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}