{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T02:13:19Z","timestamp":1773108799731,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T00:00:00Z","timestamp":1729814400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T00:00:00Z","timestamp":1729814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Lulea University of Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Intell Robot Syst"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article introduces a novel approach to constructing a topometric map that allows for efficient navigation and decision-making in mobile robotics applications. The method generates the topometric map from a 2D grid-based map. The topometric map segments areas of the input map into different structural-semantic classes: intersections, pathways, dead ends, and pathways leading to unexplored areas. This method is grounded in a new technique for intersection detection that identifies the area and the openings of intersections in a semantically meaningful way. The framework introduces two levels of pre-filtering with minimal computational cost to eliminate small openings and objects from the map which are unimportant in the context of high-level map segmentation and decision making. The topological map generated by GRID-FAST enables fast navigation in large-scale environments, and the structural semantics can aid in mission planning, autonomous exploration, and human-to-robot cooperation. The efficacy of the proposed method is demonstrated through validation on real maps gathered from robotic experiments: 1) a structured indoor environment, 2) an unstructured cave-like subterranean environment, and 3) a large-scale outdoor environment, which comprises pathways, buildings, and scattered objects. Additionally, the proposed framework has been compared with state-of-the-art topological mapping solutions and is able to produce a topometric and topological map with up to 92% fewer nodes than the next best solution. The method proposed in this article has been implemented in the robotics framework ROS and is open-sourced. The code is available at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/LTU-RAI\/GRID-FAST\">https:\/\/github.com\/LTU-RAI\/GRID-FAST<\/jats:ext-link>.<\/jats:p>","DOI":"10.1007\/s10846-024-02180-6","type":"journal-article","created":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T10:02:20Z","timestamp":1729850540000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["GRID-FAST: A Grid-based Intersection Detection for Fast Semantic Topometric Mapping"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0889-8780","authenticated-orcid":false,"given":"Scott","family":"Fredriksson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akshit","family":"Saradagi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Nikolakopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,25]]},"reference":[{"key":"2180_CR1","doi-asserted-by":"crossref","unstructured":"Patel, A., Lindqvist, B., Kanellakis, C., Agha-mohammadi, A., Nikolakopoulos, G.: REF: a rapid exploration framework for deploying autonomous MAVs in unknown environments. J. Intell. Robot. Syst. 108(3), 35 1573\u20130409 (2023)","DOI":"10.1007\/s10846-023-01836-z"},{"issue":"2","key":"2180_CR2","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/s10846-023-01961-9","volume":"109","author":"VK Viswanathan","year":"2023","unstructured":"Viswanathan, V.K., Lindqvist, B., Satpute, S.G., Kanellakis, C., Nikolakopoulos, G.: Towards visual inspection of distributed and irregular structures: a unified autonomy approach. J. Intell. Robot. Syst. 109(2), 32 (2023)","journal-title":"J. Intell. Robot. Syst."},{"issue":"3","key":"2180_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10846-022-01665-6","volume":"105","author":"B Lindqvist","year":"2022","unstructured":"Lindqvist, B., Kanellakis, C., Mansouri, S.S., Agha-mohammadi, A., Nikolakopoulos, G.: COMPRA: A compact reactive autonomy framework for subterranean MAV based search-and-rescue operations. J. Intell. Robot. Syst. 105(3), 49 (2022)","journal-title":"J. Intell. Robot. Syst."},{"key":"2180_CR4","unstructured":"Ferguson, D., Likhachev, M., Stentz, A.: A guide to heuristic-based path planning. In: Proceedings of the International Workshop on Planning Under Uncertainty for Autonomous systems, International Conference on Automated Planning and Scheduling (ICAPS), pp. 9\u201318 (2005)"},{"issue":"1","key":"2180_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0004-3702(03)00114-0","volume":"152","author":"E Remolina","year":"2004","unstructured":"Remolina, E., Kuipers, B.: Towards a general theory of topological maps. Artif. Intell. 152(1), 47\u2013104 (2004)","journal-title":"Artif. Intell."},{"key":"2180_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.robot.2014.12.006","volume":"66","author":"I Kostavelis","year":"2015","unstructured":"Kostavelis, I., Gasteratos, A.: Semantic mapping for mobile robotics tasks: a survey. Robot. Auton. Syst. 66, 86\u2013103 (2015)","journal-title":"Robot. Auton. Syst."},{"key":"2180_CR7","doi-asserted-by":"crossref","unstructured":"Bormann, R., Jordan, F., Li, W., Hampp, J., H\u00e4gele, M.: Room segmentation: Survey, implementation, and analysis. In: 2016 IEEE International Conference on Robotics and Automation (ICRA). pp. 1019\u20131026 (2016)","DOI":"10.1109\/ICRA.2016.7487234"},{"issue":"3","key":"2180_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams-a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"key":"2180_CR9","doi-asserted-by":"crossref","unstructured":"Mielle, M., Magnusson, M., Lilienthal, A.J.: A method to segment maps from different modalities using free space layout maoris: map of ripples segmentation. In: Proceedings - IEEE International Conference on Robotics and Automation, 4993\u20134999 (2018)","DOI":"10.1109\/ICRA.2018.8461128"},{"key":"2180_CR10","doi-asserted-by":"crossref","unstructured":"Hou, J., Yuan, Y., Schwertfeger, S.: Area graph: generation of topological maps using the voronoi diagram. 2019 19th International Conference on Advanced Robotics, ICAR 2019, 509\u2013515 (2019)","DOI":"10.1109\/ICAR46387.2019.8981588"},{"key":"2180_CR11","doi-asserted-by":"crossref","unstructured":"Hiller, M., Qiu, C., Particke, F., Hofmann, C., Thielecke, J.: Learning topometric semantic maps from occupancy grids. In: 2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4190\u20134197 (2019)","DOI":"10.1109\/IROS40897.2019.8968111"},{"issue":"5","key":"2180_CR12","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/s10514-021-09991-8","volume":"45","author":"Z He","year":"2021","unstructured":"He, Z., Sun, H., Hou, J., Ha, Y., Schwertfeger, S.: Hierarchical topometric representation of 3D robotic maps. Auton. Robot. 45(5), 755\u2013771 (2021)","journal-title":"Auton. Robot."},{"issue":"3","key":"2180_CR13","doi-asserted-by":"publisher","first-page":"7974","DOI":"10.1109\/LRA.2022.3186495","volume":"7","author":"M Luperto","year":"2022","unstructured":"Luperto, M., Kucner, T.P., Tassi, A., Magnusson, M., Amigoni, F.: Robust structure identification and room segmentation of cluttered indoor environments from occupancy grid maps. IEEE Robot. Autom. Lett. 7(3), 7974\u20137981 (2022)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"2180_CR14","doi-asserted-by":"crossref","unstructured":"Blochliger, F., Fehr, M., Dymczyk, M., Schneider, T., Siegwart, R.: Topomap: topological mapping and navigation based on visual SLAM maps. In: Proceedings - IEEE International Conference on Robotics and Automation. 3818\u20133825 (2018)","DOI":"10.1109\/ICRA.2018.8460641"},{"issue":"4","key":"2180_CR15","doi-asserted-by":"publisher","first-page":"458","DOI":"10.4218\/etrij.2018-0041","volume":"40","author":"B Park","year":"2018","unstructured":"Park, B., Choi, J., Chung, W.K.: Incremental hierarchical roadmap construction for efficient path planning. ETRI J. 40(4), 458\u2013470 (2018)","journal-title":"ETRI J."},{"issue":"3","key":"2180_CR16","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s11370-008-0015-6","volume":"1","author":"TB Kwon","year":"2008","unstructured":"Kwon, T.B., Song, J.B.: Real-time building of a thinning-based topological map. Intel. Serv. Robot. 1(3), 211\u2013220 (2008)","journal-title":"Intel. Serv. Robot."},{"key":"2180_CR17","doi-asserted-by":"crossref","unstructured":"Lau, B., Sprunk, C., Burgard, W.: Improved updating of Euclidean distance maps and Voronoi diagrams. In: 2010 IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 281\u2013286 (2010)","DOI":"10.1109\/IROS.2010.5650794"},{"key":"2180_CR18","doi-asserted-by":"crossref","unstructured":"Choset, Howie and Burdick, Joel.: Sensor-based exploration: the hierarchical generalized voronoi graph. Int. J. Robot. Res. 19(2), 96\u2013125 (2000)","DOI":"10.1177\/02783640022066770"},{"issue":"2","key":"2180_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1109\/70.928558","volume":"17","author":"H Choset","year":"2001","unstructured":"Choset, H., Nagatani, K.: Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Trans. Robot. Autom. 17(2), 125\u2013137 (2001)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"2180_CR20","doi-asserted-by":"crossref","unstructured":"Beeson, P., Jong, N.K., Kuipers, B.: Towards autonomous topological place detection using the extended voronoi graph. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, pp. 4373\u20134379 (2005)","DOI":"10.1109\/ROBOT.2005.1570793"},{"key":"2180_CR21","doi-asserted-by":"crossref","unstructured":"Hou, Q.: Zhang, S., Chen, S., Nan, Z., Zheng, N.: Straight skeleton based automatic generation of hierarchical topological map in indoor environment. In: 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pp. 2229\u20132236 (2021)","DOI":"10.1109\/ITSC48978.2021.9564514"},{"issue":"2","key":"2180_CR22","doi-asserted-by":"publisher","first-page":"9251","DOI":"10.1016\/j.ifacol.2023.10.007","volume":"56","author":"S Fredriksson","year":"2023","unstructured":"Fredriksson, S., Saradagi, A., Nikolakopoulos, G.: Semantic and Topological Mapping using Intersection Identification. IFAC-PapersOnLine. 56(2), 9251\u20139256 (2023)","journal-title":"IFAC-PapersOnLine."},{"issue":"4","key":"2180_CR23","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/245.248","volume":"2","author":"MR Dunlavey","year":"1983","unstructured":"Dunlavey, M.R.: Efficient polygon-filling algorithms for raster displays. ACM Trans. Graph. 2(4), 264\u2013273 (1983)","journal-title":"ACM Trans. Graph."},{"issue":"3","key":"2180_CR24","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/357994.358023","volume":"27","author":"TY Zhang","year":"1984","unstructured":"Zhang, T.Y., Suen, C.Y.: A fast parallel algorithm for thinning digital patterns. Commun. ACM 27(3), 236\u2013239 (1984)","journal-title":"Commun. ACM"},{"key":"2180_CR25","unstructured":"Beeson, P.: EVG-Thin: A Thinning Approximation to the Extended Voronoi Graph (2006)"},{"key":"2180_CR26","doi-asserted-by":"publisher","first-page":"104168","DOI":"10.1016\/j.robot.2022.104168","volume":"155","author":"A Koval","year":"2022","unstructured":"Koval, A., Karlsson, S., Mansouri, S.S., Kanellakis, C., Tevetzidis, I., Haluska, J., Agha-mohammadi, A., Nikolakopoulos, G.: Dataset collection from a SubT environment. Robot. Auton. Syst. 155, 104168 (2022)","journal-title":"Robot. Auton. Syst."},{"issue":"2","key":"2180_CR27","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"2180_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.proeng.2014.12.098","volume":"96","author":"F Ducho\u0148","year":"2014","unstructured":"Ducho\u0148, F., Babinec, A., Kajan, M., Be\u0148o, P., Florek, M., Fico, T., Juri\u0161ica, L.: Path Planning with Modified a Star Algorithm for a Mobile Robot. Procedia Eng. 96, 59\u201369 (2014)","journal-title":"Procedia Eng."},{"key":"2180_CR29","doi-asserted-by":"crossref","unstructured":"Armeni, I., He, Z., Zamir, A., Gwak, J., Malik, J., Fischer, M., Savarese, S.: 3D scene graph: a structure for unified semantics, 3D space, and camera. In: 2019 IEEE\/CVF International Conference on Computer Vision (ICCV), pp. 5663\u20135672 (2019)","DOI":"10.1109\/ICCV.2019.00576"},{"issue":"1","key":"2180_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TPAMI.2021.3137605","volume":"45","author":"X Chang","year":"2023","unstructured":"Chang, X., Ren, P., Xu, P., Li, Z., Chen, X., Hauptmann, A.: A comprehensive survey of scene graphs: generation and application. IEEE Trans. Pattern Anal. Mach. Intell. 45(1), 1\u201326 (2023)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."}],"container-title":["Journal of Intelligent &amp; Robotic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-024-02180-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10846-024-02180-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-024-02180-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T03:13:41Z","timestamp":1736306021000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10846-024-02180-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,25]]},"references-count":30,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["2180"],"URL":"https:\/\/doi.org\/10.1007\/s10846-024-02180-6","relation":{},"ISSN":["1573-0409"],"issn-type":[{"value":"1573-0409","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,25]]},"assertion":[{"value":"7 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 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.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Publish"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"154"}}