Path Planning Optimization in Static Environments with High Time-Cost Traversable Regions: An Approach Based on HTCTR Virtualization and RRT*-Dijkstra Collaborative Decision-Making

Path Planning Optimization in Static Environments with High Time-Cost Traversable Regions: An Approach Based on HTCTR Virtualization and RRT*-Dijkstra Collaborative Decision-Making | 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 Path Planning Optimization in Static Environments with High Time-Cost Traversable Regions: An Approach Based on HTCTR Virtualization and RRT*-Dijkstra Collaborative Decision-Making Yunbo Zhou, Na Yan, Ming Zhang This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7824396/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Static path planning algorithms generate global paths based on completely known environmental information, making them suitable for scenarios with fixed obstacle locations and emphasizing global path optimality. However, in global path planning, besides impassable obstacles, there exists a category of traversable regions that incur a higher time cost compared to continuous roads, termed High Time-Cost Traversable Regions (HTCTRs). RRT, a sampling-based global path planning algorithm, exhibits asymptotic optimality heavily dependent on the number of sampling points. Within HTCTRs, achieving a path with a near-optimal time cost typically requires a large number of samples, significantly increasing computational complexity. To balance path quality and computational efficiency, this paper proposes a method: virtualizing HTCTRs as obstacles and incorporating Dijkstra's algorithm for local path re-planning, thereby optimizing the bypass decision for segments crossing HTCTRs based on an initial path generated by RRT. The core of this method lies in comparing the time cost of the original path segment traversing the HTCTR with that of the bypass path segment planned by Dijkstra, selecting the optimal branch with the goal of minimizing the global time cost. The simulation results demonstrate that, while ensuring path feasibility, the proposed method can achieve path quality comparable to graph-search algorithms within a computational time similar to that of RRT* with a low number of samples. Compared to the low-sampling-point RRT*, our method improves path quality by 47.72% on the 80 \((\times)\) 80 map and by 54.45% on the 500 \((\times)\) 500 map. Furthermore, it shows significant improvements in both computational efficiency and path quality when compared to high-sampling-point RRT* and graph-search methods. HTCTR Path planning RRT -Dijkstra Collaborative Decision-Making Artificial Potential Virtual Force Field Static Grid Map Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted 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-7824396","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":573035112,"identity":"425acb32-88d0-49d1-92ea-6595500d56bf","order_by":0,"name":"Yunbo Zhou","email":"","orcid":"","institution":"Nanjing University of Science and Technology","correspondingAuthor":false,"prefix":"","firstName":"Yunbo","middleName":"","lastName":"Zhou","suffix":""},{"id":573035116,"identity":"6107622a-1c7a-4a33-8156-96460853694d","order_by":1,"name":"Na Yan","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA0UlEQVRIiWNgGAWjYPACNiBmPnDgww+StLCxJR6c2UOaRTzGhznYiFBocPzssQc/d/Alzp/f8+EwAw+DPL/YAQJazuSlG/aeYUvccIx3w+ECCwbDmbMTCGg5kGMmwdsG1MIG1DKDhyHB4DYhLeffmEn+BWqZ38bz4DAPGzFabuSYSYNsaTjGw0CcFskbb8ykZdvYjDccSzMABrIEYb/wnc8xk3zbdkx2fvPhxx8+/LCR55cmoEXhAJg6BuNL4FcOAvINYKqGsMpRMApGwSgYuQAAmchHEe/7kDgAAAAASUVORK5CYII=","orcid":"","institution":"Nanjing University of Science and Technology","correspondingAuthor":true,"prefix":"","firstName":"Na","middleName":"","lastName":"Yan","suffix":""},{"id":573035118,"identity":"605e2fd8-a462-42b1-9a65-c2678c821d35","order_by":2,"name":"Ming Zhang","email":"","orcid":"","institution":"Nanjing University of Science and Technology","correspondingAuthor":false,"prefix":"","firstName":"Ming","middleName":"","lastName":"Zhang","suffix":""}],"badges":[],"createdAt":"2025-10-10 08:23:14","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7824396/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7824396/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":100365821,"identity":"1b412349-a93d-4e21-baa1-685af2a6ef1c","added_by":"auto","created_at":"2026-01-16 07:55:40","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":5333,"visible":true,"origin":"","legend":"","description":"","filename":"20baab1b97e44c8ab78d2f57fdac3c12.json","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/55939c4fcaf44ee10efb66df.json"},{"id":100115591,"identity":"dadc846f-0b36-44c1-9eae-bacba3f0e0f6","added_by":"auto","created_at":"2026-01-13 07:43:41","extension":"xml","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":72506,"visible":true,"origin":"","legend":"","description":"","filename":"20baab1b97e44c8ab78d2f57fdac3c121enriched.xml","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/89cbf128c263ab97a33ceff0.xml"},{"id":100365832,"identity":"0c2d4b69-3d99-49d7-8df2-e9f7880fcb80","added_by":"auto","created_at":"2026-01-16 07:55:40","extension":"aux","order_by":12,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":9218,"visible":true,"origin":"","legend":"","description":"","filename":"paper.aux","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/78d2a791b821f3179c9cfdd8.aux"},{"id":100367192,"identity":"225c45de-1fc8-4cee-91b5-8a2fea7874ac","added_by":"auto","created_at":"2026-01-16 07:56:49","extension":"bbl","order_by":13,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":9680,"visible":true,"origin":"","legend":"","description":"","filename":"paper.bbl","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/18e56c2f19b932de17d28079.bbl"},{"id":100365537,"identity":"417eb779-c81d-408c-b5fc-e57602fd42e4","added_by":"auto","created_at":"2026-01-16 07:55:20","extension":"blg","order_by":14,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":2360,"visible":true,"origin":"","legend":"","description":"","filename":"paper.blg","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/1b1caca41845ce21ccfe4e89.blg"},{"id":100365605,"identity":"e874b9f1-635b-4578-b4bd-71351c2627b2","added_by":"auto","created_at":"2026-01-16 07:55:25","extension":"log","order_by":15,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":36160,"visible":true,"origin":"","legend":"","description":"","filename":"paper.log","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/1fb70cc3ce0c84751a5bec4b.log"},{"id":100367206,"identity":"2fb6de95-1777-403f-9201-f10bcd8201f1","added_by":"auto","created_at":"2026-01-16 07:56:50","extension":"out","order_by":16,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":2786,"visible":true,"origin":"","legend":"","description":"","filename":"paper.out","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/38eed9388a59707e9503ddf2.out"},{"id":100115607,"identity":"ff6570fa-d204-4135-b0d0-60c8c9728101","added_by":"auto","created_at":"2026-01-13 07:43:43","extension":"pdf","order_by":17,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":17046561,"visible":true,"origin":"","legend":"","description":"","filename":"paper.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/cf7d6de106a4bbf80378f542.pdf"},{"id":100367247,"identity":"27ff1e82-45e5-4d98-9a2b-7ec0ecb5f654","added_by":"auto","created_at":"2026-01-16 07:56:52","extension":"bst","order_by":18,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":151345,"visible":true,"origin":"","legend":"","description":"","filename":"snapacite.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/8490f939cc27ce3577cda749.bst"},{"id":100365536,"identity":"f49edae6-375e-4c9d-86d7-139c32e3b56c","added_by":"auto","created_at":"2026-01-16 07:55:20","extension":"bst","order_by":19,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":29828,"visible":true,"origin":"","legend":"","description":"","filename":"snaps.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/58ce1907f18c7bac421dbfba.bst"},{"id":100365465,"identity":"2fd0966e-67bb-4735-8b7b-0bbc2ee3a678","added_by":"auto","created_at":"2026-01-16 07:55:13","extension":"bst","order_by":20,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":35515,"visible":true,"origin":"","legend":"","description":"","filename":"snbasic.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/2dcda8c7817109595560a4de.bst"},{"id":100365296,"identity":"c9371cf8-2218-4435-90cf-60bcd0281be7","added_by":"auto","created_at":"2026-01-16 07:55:00","extension":"bst","order_by":21,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":33968,"visible":true,"origin":"","legend":"","description":"","filename":"snchicago.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/927c313035505365833aa4c9.bst"},{"id":100365678,"identity":"e42358a9-e0b7-4da6-824b-17419194b19c","added_by":"auto","created_at":"2026-01-16 07:55:30","extension":"cls","order_by":22,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":55857,"visible":true,"origin":"","legend":"","description":"","filename":"snjnl.cls","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/f745fd6957ce66b308a1720d.cls"},{"id":100366867,"identity":"47ede358-1ad7-4fc6-8d9e-cea8ec8678f6","added_by":"auto","created_at":"2026-01-16 07:56:36","extension":"bst","order_by":23,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":64023,"visible":true,"origin":"","legend":"","description":"","filename":"snmathphysay.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/04aa7bacb050f39632a6160a.bst"},{"id":100365528,"identity":"9382340d-c9e0-45dd-b15d-409a0aacf595","added_by":"auto","created_at":"2026-01-16 07:55:19","extension":"bst","order_by":24,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":64164,"visible":true,"origin":"","legend":"","description":"","filename":"snmathphysnum.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/fbbc76547d962f23aa44bdf8.bst"},{"id":100365886,"identity":"b2dd456e-04b0-45f2-8a18-f90a9d394a65","added_by":"auto","created_at":"2026-01-16 07:55:43","extension":"bst","order_by":25,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":39056,"visible":true,"origin":"","legend":"","description":"","filename":"snnature.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/1fb1db471359b97e51f68be0.bst"},{"id":100366025,"identity":"75b241d1-57c0-48c2-b376-674e4bb4767c","added_by":"auto","created_at":"2026-01-16 07:55:53","extension":"bst","order_by":26,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":39951,"visible":true,"origin":"","legend":"","description":"","filename":"snvancouveray.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/b8e0f7b33ed31d50c5d1e895.bst"},{"id":100366899,"identity":"2846e578-5e61-458b-b18d-27d766a42d5f","added_by":"auto","created_at":"2026-01-16 07:56:37","extension":"bst","order_by":27,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":40758,"visible":true,"origin":"","legend":"","description":"","filename":"snvancouvernum.bst","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/f888fea4a76821858746f01b.bst"},{"id":100365476,"identity":"3e921e46-6589-4b81-a527-97c8a8d23a75","added_by":"auto","created_at":"2026-01-16 07:55:14","extension":"xml","order_by":28,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":78316,"visible":true,"origin":"","legend":"","description":"","filename":"20baab1b97e44c8ab78d2f57fdac3c121structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/81e84d495ded0b048e94da8b.xml"},{"id":100366827,"identity":"a1153391-b5e8-4ae1-aa5d-e0e73bdf390f","added_by":"auto","created_at":"2026-01-16 07:56:34","extension":"html","order_by":29,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":89645,"visible":true,"origin":"","legend":"","description":"","filename":"earlyproof.html","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1/dac4b0b88e39552b7837a054.html"},{"id":107538101,"identity":"3068ca86-87d3-485c-ba54-3776f123ce27","added_by":"auto","created_at":"2026-04-22 11:43:00","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1539173,"visible":true,"origin":"","legend":"","description":"","filename":"paper.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7824396/v1_covered_03df9b0e-9d19-45f8-8859-c7fc15a25459.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"\u003cp\u003ePath Planning Optimization in Static Environments with High Time-Cost Traversable Regions: An Approach Based on HTCTR Virtualization and RRT*-Dijkstra Collaborative Decision-Making\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"HTCTR, Path planning, RRT, -Dijkstra Collaborative Decision-Making, Artificial Potential Virtual Force Field, Static Grid Map","lastPublishedDoi":"10.21203/rs.3.rs-7824396/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7824396/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eStatic path planning algorithms generate global paths based on completely known environmental information, making them suitable for scenarios with fixed obstacle locations and emphasizing global path optimality. However, in global path planning, besides impassable obstacles, there exists a category of traversable regions that incur a higher time cost compared to continuous roads, termed High Time-Cost Traversable Regions (HTCTRs). RRT, a sampling-based global path planning algorithm, exhibits asymptotic optimality heavily dependent on the number of sampling points. Within HTCTRs, achieving a path with a near-optimal time cost typically requires a large number of samples, significantly increasing computational complexity. To balance path quality and computational efficiency, this paper proposes a method: virtualizing HTCTRs as obstacles and incorporating Dijkstra's algorithm for local path re-planning, thereby optimizing the bypass decision for segments crossing HTCTRs based on an initial path generated by RRT. The core of this method lies in comparing the time cost of the original path segment traversing the HTCTR with that of the bypass path segment planned by Dijkstra, selecting the optimal branch with the goal of minimizing the global time cost. The simulation results demonstrate that, while ensuring path feasibility, the proposed method can achieve path quality comparable to graph-search algorithms within a computational time similar to that of RRT* with a low number of samples. Compared to the low-sampling-point RRT*, our method improves path quality by 47.72% on the 80\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\((\\times)\\)\u003c/span\u003e\u003c/span\u003e80 map and by 54.45% on the 500\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\((\\times)\\)\u003c/span\u003e\u003c/span\u003e500 map. Furthermore, it shows significant improvements in both computational efficiency and path quality when compared to high-sampling-point RRT* and graph-search methods.\u003c/p\u003e","manuscriptTitle":"Path Planning Optimization in Static Environments with High Time-Cost Traversable Regions: An Approach Based on HTCTR Virtualization and RRT*-Dijkstra Collaborative Decision-Making","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-01-13 07:43:36","doi":"10.21203/rs.3.rs-7824396/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"77803604-4e86-4fb3-a342-a2f3c5415da9","owner":[],"postedDate":"January 13th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-04-22T11:42:32+00:00","versionOfRecord":[],"versionCreatedAt":"2026-01-13 07:43:36","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7824396","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7824396","identity":"rs-7824396","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}