{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T13:00:20Z","timestamp":1777208420537,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This paper introduces a negotiation framework to solve the Multi-Agent Path Finding (MAPF) Problem for self-interested agents in a decentralized fashion. The framework aims to achieve a good trade-off between the privacy of the agents and the effectiveness of solutions. Accordingly, a token-based bilateral negotiation protocol and two negotiation strategies are presented. The experimental results over four different settings of the MAPF problem show that the proposed approach could find conflict-free path solutions albeit suboptimally, especially when the search space is large and high-density. In contrast, Explicit Estimation Conflict-Based Search (EECBS) struggles to find optimal solutions. Besides, deploying a sophisticated negotiation strategy that utilizes information about local density for generating alternative paths can yield remarkably better solution performance in this negotiation framework.<\/jats:p>","DOI":"10.1007\/s10458-024-09639-8","type":"journal-article","created":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T04:55:41Z","timestamp":1710305741000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Decentralized multi-agent path finding framework and strategies based on automated negotiation"],"prefix":"10.1007","volume":"38","author":[{"given":"M. Onur","family":"Keskin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Furkan","family":"Cant\u00fcrk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cihan","family":"Eran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reyhan","family":"Aydo\u011fan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"9639_CR1","doi-asserted-by":"crossref","unstructured":"Amir, O., Sharon, G., & Stern, R. (2015). Multi-agent pathfinding as a combinatorial auction. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI\u201915 (pp. 2003\u20132009). AAAI Press.","DOI":"10.1609\/aaai.v29i1.9427"},{"key":"9639_CR2","doi-asserted-by":"publisher","unstructured":"Aydo\u011fan, R., Hindriks, K. V., & Jonker, C. M. (2014). Multilateral mediated negotiation protocols with feedback. In I. Marsa-Maestre, M. Lopez-Carmona, T. Ito, M. Zhang, Q. Bai, & K. Fujita (Eds.), Novel Insights in Agent-based Complex Automated Negotiation (pp. 43\u201359). Studies in Computational Intelligence, Vol. 535. Springer, Tokyo. https:\/\/doi.org\/10.1007\/978-4-431-54758-7_3","DOI":"10.1007\/978-4-431-54758-7_3"},{"key":"9639_CR3","first-page":"153","volume":"674","author":"R Aydo\u011fan","year":"2017","unstructured":"Aydo\u011fan, R., Festen, D., Hindriks, K., & Jonker, C. (2017). Alternating offers protocols for multilateral negotiation. Studies in Computational Intelligence, 674, 153\u2013167.","journal-title":"Studies in Computational Intelligence"},{"key":"9639_CR4","doi-asserted-by":"crossref","unstructured":"Baarslag, T., Gerding, E. H., Aydo\u011fan, R., & Schraefel, M. (2015). Optimal negotiation decision functions in time-sensitive domains. In 2015 IEEE\/WIC\/ACM international joint conferences on web intelligence (WI) and intelligent agent technologies (IAT) (Vol.\u00a02, pp. 190\u2013197).","DOI":"10.1109\/WI-IAT.2015.161"},{"key":"9639_CR5","unstructured":"Bnaya, Z., Stern, R., Felner, A., Zivan, R., & Okamoto, S. (2013). Multi-agent path finding for self interested agents. In Sixth annual symposium on combinatorial search (pp. 39\u201346)."},{"key":"9639_CR6","unstructured":"Bonisoli, A., Gerevini, A., Saetti, A., & Serina, I. (2014). A privacy-preserving model for the multi-agent propositional planning problem. In Proceedings of the Twenty-first European Conference on Artificial Intelligence (ECAI\u201914) (pp. 973\u2013974). IOS Press, NLD."},{"key":"9639_CR7","unstructured":"Brafman, R. I., & Domshlak, C. (2008). From one to many: Planning for loosely coupled multi-agent systems. In ICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling (pp. 28\u201335)."},{"key":"9639_CR8","doi-asserted-by":"crossref","unstructured":"Cole, R. J., Dodis, Y., & Roughgarden, T. (2003). Pricing network edges for heterogeneous selfish users. In STOC \u201903 (pp. 521\u2013530).","DOI":"10.1145\/780615.780618"},{"key":"9639_CR9","unstructured":"de\u00a0Oliveira\u00a0Ramos, G., R\u0103dulescu, R., Now\u00e9, A., & Tavares, A. R. (2020). Toll-based learning for minimising congestion under heterogeneous preferences. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS\u201920) (pp. 1098\u20131106). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC."},{"issue":"4","key":"9639_CR10","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s10514-012-9275-2","volume":"32","author":"VR Desaraju","year":"2012","unstructured":"Desaraju, V. R., & How, J. P. (2012). Decentralized path planning for multi-agent teams with complex constraints. Autonomous Robots, 32(4), 385\u2013403. https:\/\/doi.org\/10.1007\/s10514-012-9275-2","journal-title":"Autonomous Robots"},{"key":"9639_CR11","doi-asserted-by":"crossref","unstructured":"Eran, C., Keskin, M. O., Cant\u00fcrk, F., & Aydo\u011fan, R. (2021). A decentralized token-based negotiation approach for multi-agent path finding. In The 18th European Conference on Multi-Agent Systems (EUMAS) (pp. 264\u2013280).","DOI":"10.1007\/978-3-030-82254-5_16"},{"key":"9639_CR12","doi-asserted-by":"publisher","unstructured":"Erdmann, M., & Lozano-Perez, T. (1986). On multiple moving objects. In Proceedings. 1986 IEEE international conference on robotics and automation (Vol.\u00a03, pp. 1419\u20131424). https:\/\/doi.org\/10.1109\/ROBOT.1986.1087401","DOI":"10.1109\/ROBOT.1986.1087401"},{"key":"9639_CR13","doi-asserted-by":"crossref","unstructured":"Felner, A., Stern, R., Shimony, S. E., Boyarski, E., Goldenberg, M., Sharon, G., Sturtevant, N. R., Wagner, G., & Surynek, P. (2017). Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In SOCS (pp. 29\u201337).","DOI":"10.1609\/socs.v8i1.18423"},{"key":"9639_CR14","unstructured":"Gautier, A., Stephens, A., Lacerda, B., Hawes, N., & Wooldridge, M. (2022). Negotiated path planning for non-cooperative multi-robot systems. In Proceedings of the 21st international conference on autonomous agents and multiagent systems, AAMAS \u201922 (pp. 472\u2013480). International Foundation for Autonomous Agents and Multiagent Systems."},{"issue":"2","key":"9639_CR15","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1109\/TITS.2020.3019397","volume":"23","author":"F Ho","year":"2022","unstructured":"Ho, F., Geraldes, R., Gon\u00e7alves, A., Rigault, B., Sportich, B., Kubo, D., Cavazza, M., & Prendinger, H. (2022). Decentralized multi-agent path finding for UAV traffic management. IEEE Transactions on Intelligent Transportation Systems, 23(2), 997\u20131008. https:\/\/doi.org\/10.1109\/TITS.2020.3019397","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"key":"9639_CR16","doi-asserted-by":"crossref","unstructured":"Inotsume, H., Aggarwal, A., Higa, R., & Nakadai, S. (2020). Path negotiation for self-interested multirobot vehicles in shared space. In Proceedings of the international conference on intelligent robots and systems (pp. 11587\u201311594). IEEE.","DOI":"10.1109\/IROS45743.2020.9341305"},{"key":"9639_CR17","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1109\/MIS.2003.1249167","volume":"18","author":"M Klein","year":"2003","unstructured":"Klein, M., Faratin, P., Sayama, H., & Bar-Yam, Y. (2003). Protocols for negotiating complex contracts. IEEE Intelligent Systems, 18, 32\u201338. https:\/\/doi.org\/10.1109\/MIS.2003.1249167","journal-title":"IEEE Intelligent Systems"},{"key":"9639_CR18","doi-asserted-by":"publisher","first-page":"103574","DOI":"10.1016\/j.artint.2021.103574","volume":"301","author":"J Li","year":"2021","unstructured":"Li, J., Harabor, D., Stuckey, P. J., Ma, H., Gange, G., & Koenig, S. (2021). Pairwise symmetry reasoning for multi-agent path finding search. Artificial Intelligence, 301, 103574. https:\/\/doi.org\/10.1016\/j.artint.2021.103574","journal-title":"Artificial Intelligence"},{"key":"9639_CR19","doi-asserted-by":"crossref","unstructured":"Li, J., Ruml, W., & Koenig, S. (2021). Eecbs: A bounded-suboptimal search for multi-agent path finding. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35(14), pp. 12353\u201312362).","DOI":"10.1609\/aaai.v35i14.17466"},{"key":"9639_CR20","doi-asserted-by":"publisher","unstructured":"Li, Q., Gama, F., Ribeiro, A., & Prorok, A. (2020). Graph neural networks for decentralized multi-robot path planning. In 2020 IEEE\/RSJ international conference on intelligent robots and systems (IROS) (pp. 11785\u201311792). IEEE. https:\/\/doi.org\/10.1109\/iros45743.2020.9341668","DOI":"10.1109\/iros45743.2020.9341668"},{"key":"9639_CR21","doi-asserted-by":"publisher","unstructured":"Parkes, D. C. (1999). Ibundle: An efficient ascending price bundle auction. In: Proceedings of the 1st ACM conference on electronic commerce, EC \u201999 (pp. 148\u2013157). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/336992.337032","DOI":"10.1145\/336992.337032"},{"issue":"2","key":"9639_CR22","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1109\/LRA.2022.3227858","volume":"8","author":"A Patwardhan","year":"2023","unstructured":"Patwardhan, A., Murai, R., & Davison, A. J. (2023). Distributing collaborative multi-robot planning with gaussian belief propagation. IEEE Robotics and Automation Letters, 8(2), 552\u2013559. https:\/\/doi.org\/10.1109\/LRA.2022.3227858","journal-title":"IEEE Robotics and Automation Letters"},{"key":"9639_CR23","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/TITS.2017.2693820","volume":"19","author":"A Pritchett","year":"2018","unstructured":"Pritchett, A., & Genton, A. (2018). Negotiated decentralized aircraft conflict resolution. IEEE Transactions on Intelligent Transportation Systems, 19, 81\u201391.","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"key":"9639_CR24","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/j.robot.2007.09.020","volume":"56","author":"O Purwin","year":"2008","unstructured":"Purwin, O., D\u2019Andrea, R., & Lee, J. (2008). Theory and implementation of path planning by negotiation for decentralized agents. Robotics and Autonomous Systems, 56, 422\u2013436.","journal-title":"Robotics and Autonomous Systems"},{"key":"9639_CR25","volume-title":"Rules of encounter: Designing conventions for automated negotiation among computers","author":"JS Rosenschein","year":"1994","unstructured":"Rosenschein, J. S., & Zlotkin, G. (1994). Rules of encounter: Designing conventions for automated negotiation among computers. MIT Press."},{"key":"9639_CR26","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., & Tardos, \u00c9. (2002). How bad is selfish routing? Journal of ACM, 49, 236\u2013259.","journal-title":"Journal of ACM"},{"key":"9639_CR27","unstructured":"Salzman, O., & Stern, R. (2020). Research challenges and opportunities in multi-agent path finding and multi-agent pickup and delivery problems. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS \u201920 (pp. 1711\u20131715). International Foundation for Autonomous Agents and Multiagent Systems."},{"key":"9639_CR28","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","volume":"219","author":"G Sharon","year":"2012","unstructured":"Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2012). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 40\u201366.","journal-title":"Artificial Intelligence"},{"key":"9639_CR29","doi-asserted-by":"publisher","unstructured":"Stern, R. (2019). Multi-agent path finding\u2014An overview Artificial Intelligence (pp. 96\u2013115). Springer-Verlag, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-030-33274-7_6","DOI":"10.1007\/978-3-030-33274-7_6"},{"key":"9639_CR30","unstructured":"Stern, R., Sturtevant, N. R., Felner, A., Koenig, S., Ma, H., Walker, T. T., Li, J., Atzmon, D., Cohen, L., Kumar, T. K. S., Boyarski, E., & Bart\u00e1k, R. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Symposium on combinatorial search. https:\/\/api.semanticscholar.org\/CorpusID:195218865"},{"key":"9639_CR31","doi-asserted-by":"publisher","unstructured":"Sujit, P.B., Sinha, A., & Ghose, D. (2006). Multiple UAV task allocation using negotiation. In AAMAS \u201906: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, AAMAS \u201906 (pp. 471\u2013478). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/1160633.1160719","DOI":"10.1145\/1160633.1160719"},{"key":"9639_CR32","unstructured":"Thayer, J., & Ruml, W. (2011). Bounded suboptimal search: A direct approach using inadmissible estimates. In The Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (pp. 674-679)."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09639-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-024-09639-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09639-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T19:44:31Z","timestamp":1719863071000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-024-09639-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9639"],"URL":"https:\/\/doi.org\/10.1007\/s10458-024-09639-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3044841\/v1","asserted-by":"object"}]},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"assertion":[{"value":"8 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable to this study.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}],"article-number":"10"}}