Fast algorithm for centralized multi-agent maze exploration

Fast algorithm for centralized multi-agent maze exploration | 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 Fast algorithm for centralized multi-agent maze exploration Bojan Crnković, Stefan Ivić, Mila Zovko This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8583164/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 4 You are reading this latest preprint version Abstract Recent advances in robotics have paved the way for robots to replace humans in perilous situations, such as searching for victims in burning buildings, in earthquake-damaged structures, in uncharted caves, traversing minefields or patrolling crime-ridden streets. These challenges can be generalized as problems where agents have to explore unknown mazes. We propose a cooperative multi-agent system of automated mobile agents for exploring unknown mazes and localizing stationary targets. The Heat Equation-Driven Area Coverage (HEDAC) algorithm for maze exploration employs a potential field to guide the exploration of the maze and integrates cooperative behaviors of the agents such as collision avoidance, coverage coordination, and path planning. In contrast to previous applications for continuous static domains, we adapt the HEDAC method for mazes on expanding rectilinear grids. The proposed algorithm guarantees the exploration of the entire maze and can ensure the avoidance of collisions and deadlocks. Moreover, this is the first application of the HEDAC algorithm to domains that expand over time. To cope with the dynamically changing domain, succesive over-relaxation (SOR) iterative linear solver has been adapted and implemented, which significantly reduced the computational complexity of the presented algorithm when compared to standard direct and iterative linear solvers. The results highlight significant improvements and show the applicability of the algorithm in different mazes. They confirm its robustness, adaptability, scalability and simplicity, which enables centralized parallel computation to control multiple agents/robots in the maze. cooperative search multi-agent system maze solving maze exploration graph exploration succesive over-relaxation method Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviewers invited by journal 26 Mar, 2026 Editor assigned by journal 13 Jan, 2026 Submission checks completed at journal 13 Jan, 2026 First submitted to journal 12 Jan, 2026 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-8583164","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":612835851,"identity":"43ab8b4a-718b-42a5-a10e-4100184b8b6b","order_by":0,"name":"Bojan Crnković","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA4klEQVRIie3RMQrCMBiG4a8IZol7QbxDxKGI0rMkBLoquDg4FASnunsMN3WLFDKpXYWC1BsoLoKL1Qq6GDs65J3+EB6SEMBm+8MYwIuJ4jF2gQqgnLA8CUoRvAkQFwsT8Uh4vPTh9zwaazcbJWJBakflLA9fSTtSsj6DbK+mk8DlOhWrMWHK2Qy+X2zPeZ1CMZbQFhNhKuZxNX/LhJuIvH2QXSkSFKdso2YmQvWb5G8JOpRJxjZaZFzL1pMIA/FIJFM69HMi1fo68hvzRFdOZwPJ/4N//s4rEwCIMm7bbDabDXfoLlZV1pPzeQAAAABJRU5ErkJggg==","orcid":"","institution":"University of Rijeka","correspondingAuthor":true,"prefix":"","firstName":"Bojan","middleName":"","lastName":"Crnković","suffix":""},{"id":612835852,"identity":"fafe1eff-2d2e-4ef0-a0e5-59d6f2808ba6","order_by":1,"name":"Stefan Ivić","email":"","orcid":"","institution":"University of Rijeka","correspondingAuthor":false,"prefix":"","firstName":"Stefan","middleName":"","lastName":"Ivić","suffix":""},{"id":612835853,"identity":"e79f55a2-e0dc-4456-89b1-35911e84825e","order_by":2,"name":"Mila Zovko","email":"","orcid":"","institution":"University of Mostar","correspondingAuthor":false,"prefix":"","firstName":"Mila","middleName":"","lastName":"Zovko","suffix":""}],"badges":[],"createdAt":"2026-01-12 15:08:15","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8583164/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8583164/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":105701084,"identity":"54e8529b-d5fe-4276-8f5c-59212a86210f","added_by":"auto","created_at":"2026-03-30 05:57:37","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1707301,"visible":true,"origin":"","legend":"","description":"","filename":"mazeExp.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8583164/v1_covered_b639ddbd-a4b6-4d10-a313-2a57a8116b6d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Fast algorithm for centralized multi-agent maze exploration","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"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":"autonomous-agents-and-multi-agent-systems","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"agnt","sideBox":"Learn more about [Autonomous Agents and Multi-Agent Systems](http://link.springer.com/journal/10458)","snPcode":"10458","submissionUrl":"https://submission.nature.com/new-submission/10458/3","title":"Autonomous Agents and Multi-Agent Systems","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"cooperative search, multi-agent system, maze solving, maze exploration, graph exploration, succesive over-relaxation method","lastPublishedDoi":"10.21203/rs.3.rs-8583164/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8583164/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Recent advances in robotics have paved the way for robots to replace humans in perilous situations, such as searching for victims in burning buildings, in earthquake-damaged structures, in uncharted caves, traversing minefields or patrolling crime-ridden streets. These challenges can be generalized as problems where agents have to explore unknown mazes. We propose a cooperative multi-agent system of automated mobile agents for exploring unknown mazes and localizing stationary targets. The Heat Equation-Driven Area Coverage (HEDAC) algorithm for maze exploration employs a potential field to guide the exploration of the maze and integrates cooperative behaviors of the agents such as collision avoidance, coverage coordination, and path planning. In contrast to previous applications for continuous static domains, we adapt the HEDAC method for mazes on expanding rectilinear grids. The proposed algorithm guarantees the exploration of the entire maze and can ensure the avoidance of collisions and deadlocks. Moreover, this is the first application of the HEDAC algorithm to domains that expand over time. To cope with the dynamically changing domain, succesive over-relaxation (SOR) iterative linear solver has been adapted and implemented, which significantly reduced the computational complexity of the presented algorithm when compared to standard direct and iterative linear solvers. The results highlight significant improvements and show the applicability of the algorithm in different mazes. They confirm its robustness, adaptability, scalability and simplicity, which enables centralized parallel computation to control multiple agents/robots in the maze.","manuscriptTitle":"Fast algorithm for centralized multi-agent maze exploration","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-03-30 05:57:26","doi":"10.21203/rs.3.rs-8583164/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"reviewersInvited","content":"","date":"2026-03-26T17:32:44+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-01-13T15:18:50+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-01-13T12:42:39+00:00","index":"","fulltext":""},{"type":"submitted","content":"Autonomous Agents and Multi-Agent Systems","date":"2026-01-12T14:55:44+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"autonomous-agents-and-multi-agent-systems","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"agnt","sideBox":"Learn more about [Autonomous Agents and Multi-Agent Systems](http://link.springer.com/journal/10458)","snPcode":"10458","submissionUrl":"https://submission.nature.com/new-submission/10458/3","title":"Autonomous Agents and Multi-Agent Systems","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"c7125e18-83b1-40c6-bcb5-205364732ef9","owner":[],"postedDate":"March 30th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-03-30T05:57:26+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-30 05:57:26","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8583164","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8583164","identity":"rs-8583164","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}