Lifelong Multi-Agent Collaborative Path Finding: A Unified Framework for Task Assignment and Path Planning

Lifelong Multi-Agent Collaborative Path Finding: A Unified Framework for Task Assignment and Path Planning | 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 Lifelong Multi-Agent Collaborative Path Finding: A Unified Framework for Task Assignment and Path Planning Yingjie Hua, Zhicheng Ji, Yan Wang, Irfan Ullah, Jawad Khan, Muhammad Asif Khan This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7335719/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 Coordinating lifelong collaboration among multiple agents poses significant challenges, particularly when agents must work together to complete tasks in dynamic environments. Existing methods typically separate task allocation from path planning, resulting in inefficient coordination, idle agents, and frequent deadlocks when collaboration is required. These issues are particularly critical in real-world domains, such as warehouse logistics, where multi-agent cooperation is crucial for handling large or complex tasks. To overcome these limitations, we propose the Lifelong Multi-Agent Collaborative Path Finding (LMACPF) as a unified framework, which tightly integrates task assignment and path planning for lifelong, collaboration-intensive scenarios. LMACPF combines Multi-Level Task Assignment (MLTA) with Collaborative Agent Search (CAS) and Collaborative Revised Prioritized Planning (CRPP) to optimize task allocation and path planning, particularly for cooperative agent behaviors. MLTA hierarchically assigns tasks based on collaboration requirements to ensure that multi-agent tasks are prioritized. CAS and CRPP enable synchronized planning and formation maintenance among agents. In addition, the Evaluation-Based Collaborative Large Neighborhood Search (EBC-LNS) is presented for a task-level evaluation that prioritizes collaborative agent groups and balances the path quality with real-time responsiveness. Experiments show MLTA increases task-ready agents by 45.8% over MAPD. LMACPF improves throughput and task success over state-of-the-art methods, demonstrating its effectiveness in scalable, lifelong multi-agent collaboration. Robust MAPR under fault conditions temporary destination multi-agent path finding MAPF collaborative agent search 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-7335719","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":521280046,"identity":"a78773cc-4457-4d77-bd4f-54a92d28789c","order_by":0,"name":"Yingjie Hua","email":"","orcid":"","institution":"Jiangnan University","correspondingAuthor":false,"prefix":"","firstName":"Yingjie","middleName":"","lastName":"Hua","suffix":""},{"id":521280047,"identity":"b0c95f07-e718-435f-ac4e-013f8c169710","order_by":1,"name":"Zhicheng Ji","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAx0lEQVRIiWNgGAWjYFACxgaGDz/+y4FYBxgYEojTwjizh9mYgYGZgVgtQLU8bMyJDURrMZ+R3PiAh4ctvV8i/8CBDxVpDPzt3fj1ydxIbDaQsODJnTkjmeHgjDM5DBJnzm7Aq0VCOrFNwoBHInfDjWSGw7xtFQwGQDZhLQlsBukGpGk5wJaQANWSQ4QW+YfNho09Bwxn9jw2APoljYewX3iOP3z858cBeX72xIcPPlQky/G39+LXggF4SFM+CkbBKBgFowArAACU3Ue8nUW3pAAAAABJRU5ErkJggg==","orcid":"","institution":"Jiangnan University","correspondingAuthor":true,"prefix":"","firstName":"Zhicheng","middleName":"","lastName":"Ji","suffix":""},{"id":521280048,"identity":"15b2f868-c12b-4f6b-b5d1-fb2e357ca448","order_by":2,"name":"Yan Wang","email":"","orcid":"","institution":"Jiangnan University","correspondingAuthor":false,"prefix":"","firstName":"Yan","middleName":"","lastName":"Wang","suffix":""},{"id":521280049,"identity":"b1e4fd96-6f3e-43e0-93e0-307b0e2546d5","order_by":3,"name":"Irfan Ullah","email":"","orcid":"","institution":"Shaheed Benazir Bhutto University","correspondingAuthor":false,"prefix":"","firstName":"Irfan","middleName":"","lastName":"Ullah","suffix":""},{"id":521280050,"identity":"f6cc50ad-a39d-4854-b7fa-a6788a6ce0a0","order_by":4,"name":"Jawad Khan","email":"","orcid":"","institution":"Gachon University","correspondingAuthor":false,"prefix":"","firstName":"Jawad","middleName":"","lastName":"Khan","suffix":""},{"id":521280051,"identity":"b25e81ad-5399-4199-ae03-b9086fbca10a","order_by":5,"name":"Muhammad Asif Khan","email":"","orcid":"","institution":"Southeast University, China","correspondingAuthor":false,"prefix":"","firstName":"Muhammad","middleName":"Asif","lastName":"Khan","suffix":""}],"badges":[],"createdAt":"2025-08-09 19:53:12","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7335719/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7335719/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":92909797,"identity":"442562e0-0089-40aa-a031-39c0523a82e9","added_by":"auto","created_at":"2025-10-07 02:59:44","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":7583,"visible":true,"origin":"","legend":"","description":"","filename":"402be544e7bc40c383f905b5310bdd83.json","url":"https://assets-eu.researchsquare.com/files/rs-7335719/v1/9a501facb85945d806d8d447.json"},{"id":96927241,"identity":"dc45520b-a033-4d1f-97f8-5281829f6791","added_by":"auto","created_at":"2025-11-27 14:26:47","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1929537,"visible":true,"origin":"","legend":"","description":"","filename":"multiagentspringer.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7335719/v1_covered_fe2f3678-2d43-469e-b211-1362c060488f.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Lifelong Multi-Agent Collaborative Path Finding: A Unified Framework for Task Assignment and Path Planning","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":"Robust MAPR under fault conditions, temporary destination, multi-agent path finding, MAPF, collaborative agent search","lastPublishedDoi":"10.21203/rs.3.rs-7335719/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7335719/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Coordinating lifelong collaboration among multiple agents poses significant challenges, particularly when agents must work together to complete tasks in dynamic environments. Existing methods typically separate task allocation from path planning, resulting in inefficient coordination, idle agents, and frequent deadlocks when collaboration is required. These issues are particularly critical in real-world domains, such as warehouse logistics, where multi-agent cooperation is crucial for handling large or complex tasks. To overcome these limitations, we propose the Lifelong Multi-Agent Collaborative Path Finding (LMACPF) as a unified framework, which tightly integrates task assignment and path planning for lifelong, collaboration-intensive scenarios. LMACPF combines Multi-Level Task Assignment (MLTA) with Collaborative Agent Search (CAS) and Collaborative Revised Prioritized Planning (CRPP) to optimize task allocation and path planning, particularly for cooperative agent behaviors. MLTA hierarchically assigns tasks based on collaboration requirements to ensure that multi-agent tasks are prioritized. CAS and CRPP enable synchronized planning and formation maintenance among agents. In addition, the Evaluation-Based Collaborative Large Neighborhood Search (EBC-LNS) is presented for a task-level evaluation that prioritizes collaborative agent groups and balances the path quality with real-time responsiveness. Experiments show MLTA increases task-ready agents by 45.8% over MAPD. LMACPF improves throughput and task success over state-of-the-art methods, demonstrating its effectiveness in scalable, lifelong multi-agent collaboration.","manuscriptTitle":"Lifelong Multi-Agent Collaborative Path Finding: A Unified Framework for Task Assignment and Path Planning","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-10-07 02:59:39","doi":"10.21203/rs.3.rs-7335719/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":"dc89a36d-dd47-4459-8353-dee34bec87ae","owner":[],"postedDate":"October 7th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-11-27T14:24:47+00:00","versionOfRecord":[],"versionCreatedAt":"2025-10-07 02:59:39","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7335719","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7335719","identity":"rs-7335719","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}