{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T13:59:32Z","timestamp":1784210372739,"version":"3.55.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030589417","type":"print"},{"value":"9783030589424","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-58942-4_23","type":"book-chapter","created":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T06:03:58Z","timestamp":1600409038000},"page":"347-363","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Template Matching and Decision Diagrams for Multi-agent Path Finding"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2047-7634","authenticated-orcid":false,"given":"Jayanth Krishna","family":"Mogali","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0023-753X","authenticated-orcid":false,"given":"Willem-Jan","family":"van Hoeve","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7053-3166","authenticated-orcid":false,"given":"Stephen F.","family":"Smith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,9,19]]},"reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/S0377-2217(98)00194-5","volume":"117","author":"BM Baker","year":"1999","unstructured":"Baker, B.M., Sheasby, J.: Accelerating the convergence of subgradient optimisation. Eur. J. Oper. Res. 117(1), 136\u2013144 (1999)","journal-title":"Eur. J. Oper. Res."},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/11427186_39","volume-title":"Experimental and Efficient Algorithms","author":"B Becker","year":"2005","unstructured":"Becker, B., Behle, M., Eisenbrand, F., Wimmer, R.: BDDs in a branch and cut framework. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 452\u2013463. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11427186_39"},{"key":"23_CR3","unstructured":"Benoist, T., Laburthe, F., Rottembourg, B.: Lagrange relaxation and constraint programming collaborative schemes for travelling tournament problems. In: CPAIOR, vol. 1, pp. 15\u201326 (2001)"},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-319-23219-5_3","volume-title":"Principles and Practice of Constraint Programming","author":"D Bergman","year":"2015","unstructured":"Bergman, D., Cire, A.A., van Hoeve, W.-J.: Improved constraint propagation via Lagrangian decomposition. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 30\u201338. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23219-5_3"},{"key":"23_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42849-9","volume-title":"Decision Diagrams for Optimization","author":"D Bergman","year":"2016","unstructured":"Bergman, D., Cire, A.A., Van Hoeve, W.J., Hooker, J.: Decision Diagrams for Optimization, vol. 1. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-319-42849-9"},{"key":"23_CR6","unstructured":"Boyarski, E., et al.: ICBS: improved conflict-based search algorithm for multi-agent pathfinding. In: Twenty-Fourth International Joint Conference on Artificial Intelligence (2015)"},{"key":"23_CR7","doi-asserted-by":"publisher","unstructured":"Davarnia, D., van Hoeve, W.-J.: Outer approximation for integer nonlinear programs via decision diagrams. Math. Program., 1\u201340 (2020). https:\/\/doi.org\/10.1007\/s10107-020-01475-4","DOI":"10.1007\/s10107-020-01475-4"},{"issue":"1","key":"23_CR8","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF02085641","volume":"50","author":"LF Escudero","year":"1994","unstructured":"Escudero, L.F., Guignard, M., Malik, K.: A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships. Ann. Oper. Res. 50(1), 219\u2013237 (1994). https:\/\/doi.org\/10.1007\/BF02085641","journal-title":"Ann. Oper. Res."},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Felner, A., et al.: Adding heuristics to conflict-based search for multi-agent path finding. In: Twenty-Eighth International Conference on Automated Planning and Scheduling (2018)","DOI":"10.1609\/icaps.v28i1.13883"},{"key":"23_CR10","series-title":"Mathematical Programming Studies","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BFb0120690","volume-title":"Approaches to integer programming","author":"AM Geoffrion","year":"1974","unstructured":"Geoffrion, A.M.: Lagrangean relaxation for integer programming. In: Balinski, M.L. (ed.) Approaches to integer programming. Mathematical Programming Studies, vol. 2, pp. 82\u2013114. Springer, Heidelberg (1974). https:\/\/doi.org\/10.1007\/BFb0120690"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/11493853_20","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"MOI Khemmoudj","year":"2005","unstructured":"Khemmoudj, M.O.I., Bennaceur, H., Nagih, A.: Combining Arc-consistency and dual Lagrangean relaxation for filtering CSPs. In: Bart\u00e1k, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 258\u2013272. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11493853_20"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Lam, E., Le Bodic, P., Harabor, D., Stuckey, P.J.: Branch-and-cut-and-price for multi-agent pathfinding. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), pp. 1289\u20131296. International Joint Conferences on Artificial Intelligence Organization (2019)","DOI":"10.24963\/ijcai.2019\/179"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Li, J., Boyarski, E., Felner, A., Ma, H., Koenig, S.: Improved heuristics for multi-agent path finding with conflict-based search. In: International Joint Conference on Artificial Intelligence, pp. 442\u2013449 (2019)","DOI":"10.24963\/ijcai.2019\/63"},{"issue":"1","key":"23_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10479-005-3977-1","volume":"140","author":"A Lucena","year":"2005","unstructured":"Lucena, A.: Non delayed relax-and-cut algorithms. Ann. Oper. Res. 140(1), 375\u2013410 (2005). https:\/\/doi.org\/10.1007\/s10479-005-3977-1","journal-title":"Ann. Oper. Res."},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","volume":"219","author":"G Sharon","year":"2015","unstructured":"Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40\u201366 (2015)","journal-title":"Artif. Intell."},{"issue":"2","key":"23_CR16","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1287\/ijoc.2018.0830","volume":"31","author":"C Tjandraatmadja","year":"2019","unstructured":"Tjandraatmadja, C., van Hoeve, W.J.: Target cuts from relaxed decision diagrams. INFORMS J. Comput. 31(2), 285\u2013301 (2019)","journal-title":"INFORMS J. Comput."},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Wagner, G., Choset, H.: M*: a complete multirobot path planning algorithm with performance bounds. In: 2011 IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 3260\u20133267. IEEE (2011)","DOI":"10.1109\/IROS.2011.6095022"},{"key":"23_CR18","unstructured":"Wang, J., Li, J., Ma, H., Koenig, S., Kumar, T.: A new constraint satisfaction perspective on multi-agent path finding: preliminary results. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2253\u20132255. International Foundation for Autonomous Agents and Multiagent Systems (2019)"},{"issue":"1","key":"23_CR19","first-page":"9","volume":"29","author":"PR Wurman","year":"2008","unstructured":"Wurman, P.R., D\u2019Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Mag. 29(1), 9\u20139 (2008)","journal-title":"AI Mag."},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle, S.M.: Planning optimal paths for multiple robots on graphs. In: 2013 IEEE International Conference on Robotics and Automation, pp. 3612\u20133617. IEEE (2013)","DOI":"10.1109\/ICRA.2013.6631084"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle, S.M.: Structure and intractability of optimal multi-robot path planning on graphs. In: Twenty-Seventh AAAI Conference on Artificial Intelligence (2013)","DOI":"10.1609\/aaai.v27i1.8541"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-58942-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T00:57:50Z","timestamp":1668819470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-58942-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030589417","9783030589424"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58942-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"19 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cpaior2020.dbai.tuwien.ac.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"72","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.08","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.08","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}