A tree-based exploration method: utilizing the topology of the map as the basis of goal selection

A tree-based exploration method: utilizing the topology of the map as the basis of goal selection | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A tree-based exploration method: utilizing the topology of the map as the basis of goal selection Barbara Abonyi-Tóth, Ákos Nagy This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5433902/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 02 Dec, 2025 Read the published version in Autonomous Robots → Version 1 posted 9 You are reading this latest preprint version Abstract In this paper, we present a novel method for autonomous robotic exploration using a car-like robot. The proposed method uses the frontiers in the map to build a tree representing the structure of the environment to aid the goal-selection method. An augmentation of the method is also proposed which is able to manage the loops present in the environment. In this case, the environment is represented with a graph structure. A generalization of exploration methods is introduced to simplify the theoretical comparison between exploration methods. Two experiments are described. The first shows, that the success of the Sensor-Based Random Tree method is highly dependent on the dimensions of the environment. In the second experiment, a frontier-based exploration method used with greedy goal selection, the Sensor-Based Random Tree method, and the two proposed exploration methods are compared in three simulated environments. The experiments show, that the proposed methods outperform the existing methods both in the time taken until full exploration and the distance traveled during the exploration. The proposed exploration method was also tested using a real-life robot in an office scenario. Robotic Exploration Frontier-Based Exploration Sensor-Based Random Tree Tree-Based Exploration Full Text Additional Declarations No competing interests reported. Supplementary Files OnlineResource1.mp4 Cite Share Download PDF Status: Published Journal Publication published 02 Dec, 2025 Read the published version in Autonomous Robots → Version 1 posted Editorial decision: Revision requested 17 Mar, 2025 Reviews received at journal 16 Mar, 2025 Reviews received at journal 01 Mar, 2025 Reviewers agreed at journal 16 Feb, 2025 Reviewers agreed at journal 14 Jan, 2025 Reviewers invited by journal 24 Dec, 2024 Editor assigned by journal 16 Dec, 2024 Submission checks completed at journal 12 Nov, 2024 First submitted to journal 11 Nov, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-5433902","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":377463975,"identity":"532a921e-528b-4cf2-9869-ce1086f00f6b","order_by":0,"name":"Barbara Abonyi-Tóth","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABKElEQVRIie3QMUvDQBTA8VcPrsur2eRCSvoVLgQasvhZhMJ1CWiXIgg6FDK1u6V+FIeDwLloXSPt0FLI1KFuFiKaJhHERO0omP8Q3oX8uMsBVFX9wTgAzSaWLwGwtviYyT6EAUXCd9OeBFJC2U/EqT9Ei+3tMWiTgVrhGVxqrZE63/oxOEeBJD2/QNxh17GGUQfYXHVtTA6m+4fiaeRzcCfihIyLhEtBGcrkAKHXNpC/Ma6wHTYSwmceJ40S8hhRPZZX0MoIpKT3mpLTTSkJBTVQBsnwiZB8Fygj7nVUt5vyDq25EvoNB33se7bRnNqY/AsPcFq8MU3Q5VpemOZsoNg6Bk0j99bzum+ajtFZrrBfcs1ZuHsc4Nc38luQV3v57Yuqqqqqf9k7PQNdRe595eIAAAAASUVORK5CYII=","orcid":"","institution":"Budapest University of Technology and Economics","correspondingAuthor":true,"prefix":"","firstName":"Barbara","middleName":"","lastName":"Abonyi-Tóth","suffix":""},{"id":377463977,"identity":"abd69823-11d3-4d8d-a473-85e4f0df6333","order_by":1,"name":"Ákos Nagy","email":"","orcid":"","institution":"Budapest University of Technology and Economics","correspondingAuthor":false,"prefix":"","firstName":"Ákos","middleName":"","lastName":"Nagy","suffix":""}],"badges":[],"createdAt":"2024-11-11 17:38:21","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-5433902/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5433902/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s10514-025-10223-6","type":"published","date":"2025-12-02T15:58:14+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":97724894,"identity":"e4fbeb50-15f0-4238-911d-93a6220bfd34","added_by":"auto","created_at":"2025-12-08 16:13:51","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":8857907,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5433902/v1_covered_7ef4a8dd-dac8-47d4-b723-07e028f85449.pdf"},{"id":70616936,"identity":"ec81b45a-2165-433e-bef6-c2e82d983786","added_by":"auto","created_at":"2024-12-05 02:20:14","extension":"mp4","order_by":0,"title":"","display":"","copyAsset":false,"role":"supplement","size":20300442,"visible":true,"origin":"","legend":"","description":"","filename":"OnlineResource1.mp4","url":"https://assets-eu.researchsquare.com/files/rs-5433902/v1/9247d8cb83a34aa964298ed2.mp4"}],"financialInterests":"No competing interests reported.","formattedTitle":"A tree-based exploration method: utilizing the topology of the map as the basis of goal selection","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"autonomous-robots","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"auro","sideBox":"Learn more about [Autonomous Robots](http://link.springer.com/journal/10514)","snPcode":"10514","submissionUrl":"https://submission.nature.com/new-submission/10514/3","title":"Autonomous Robots","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Robotic Exploration, Frontier-Based Exploration, Sensor-Based Random Tree, Tree-Based Exploration","lastPublishedDoi":"10.21203/rs.3.rs-5433902/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5433902/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eIn this paper, we present a novel method for autonomous robotic exploration using a car-like robot. The proposed method uses the frontiers in the map to build a tree representing the structure of the environment to aid the goal-selection method. An augmentation of the method is also proposed which is able to manage the loops present in the environment. In this case, the environment is represented with a graph structure. A generalization of exploration methods is introduced to simplify the theoretical comparison between exploration methods. Two experiments are described. The first shows, that the success of the Sensor-Based Random Tree method is highly dependent on the dimensions of the environment. In the second experiment, a frontier-based exploration method used with greedy goal selection, the Sensor-Based Random Tree method, and the two proposed exploration methods are compared in three simulated environments. The experiments show, that the proposed methods outperform the existing methods both in the time taken until full exploration and the distance traveled during the exploration. The proposed exploration method was also tested using a real-life robot in an office scenario.\u003c/p\u003e","manuscriptTitle":"A tree-based exploration method: utilizing the topology of the map as the basis of goal selection","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-12-05 02:20:07","doi":"10.21203/rs.3.rs-5433902/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-03-17T21:06:03+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-03-17T03:26:31+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-03-01T21:13:55+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"147265723896133424201038665856917547011","date":"2025-02-16T23:32:08+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"302849740027871138350526977459942687400","date":"2025-01-15T01:37:26+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-12-24T20:20:38+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-12-17T00:31:35+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-11-13T04:45:36+00:00","index":"","fulltext":""},{"type":"submitted","content":"Autonomous Robots","date":"2024-11-11T17:33:29+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"autonomous-robots","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"auro","sideBox":"Learn more about [Autonomous Robots](http://link.springer.com/journal/10514)","snPcode":"10514","submissionUrl":"https://submission.nature.com/new-submission/10514/3","title":"Autonomous Robots","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"2d32c249-9321-483a-b55e-954bba874ca9","owner":[],"postedDate":"December 5th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-12-08T16:12:02+00:00","versionOfRecord":{"articleIdentity":"rs-5433902","link":"https://doi.org/10.1007/s10514-025-10223-6","journal":{"identity":"autonomous-robots","isVorOnly":false,"title":"Autonomous Robots"},"publishedOn":"2025-12-02 15:58:14","publishedOnDateReadable":"December 2nd, 2025"},"versionCreatedAt":"2024-12-05 02:20:07","video":"","vorDoi":"10.1007/s10514-025-10223-6","vorDoiUrl":"https://doi.org/10.1007/s10514-025-10223-6","workflowStages":[]},"version":"v1","identity":"rs-5433902","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5433902","identity":"rs-5433902","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}