{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T04:05:10Z","timestamp":1790827510256,"version":"4.1.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030693213","type":"print"},{"value":"9783030693220","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-69322-0_16","type":"book-chapter","created":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T08:44:56Z","timestamp":1613292296000},"page":"248-258","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Mutex Propagation for SAT-based Multi-agent Path Finding"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7200-0542","authenticated-orcid":false,"given":"Pavel","family":"Surynek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaoyang","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Han","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T. K.","family":"Satish Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Koenig","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,2,14]]},"reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-39071-5_23","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2013","author":"G Audemard","year":"2013","unstructured":"Audemard, G., Lagniez, J.-M., Simon, L.: Improving glucose for incremental SAT solving with assumptions: application to MUS extraction. In: J\u00e4rvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 309\u2013317. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39071-5_23"},{"key":"16_CR2","unstructured":"Audemard, G., Simon, L.: Predicting learnt clauses quality in modern SAT solvers. In: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11\u201317, 2009, pp. 399\u2013404 (2009)"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-45193-8_8","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"O Bailleux","year":"2003","unstructured":"Bailleux, O., Boufkhad, Y.: Efficient CNF encoding of boolean cardinality constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 108\u2013122. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45193-8_8"},{"issue":"1\u20132","key":"16_CR4","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0004-3702(96)00047-1","volume":"90","author":"A Blum","year":"1997","unstructured":"Blum, A., Furst, M.L.: Fast planning through planning graph analysis. Artif. Intell. 90(1\u20132), 281\u2013300 (1997)","journal-title":"Artif. Intell."},{"issue":"3","key":"16_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"WF Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Logic Program. 1(3), 267\u2013284 (1984)","journal-title":"J. Logic Program."},{"key":"16_CR6","unstructured":"Felner, A., Li, J., Boyarski, E., Ma, H., Cohen, L., Kumar, T.K.S., Koenig, S.: Adding heuristics to conflict-based search for multi-agent path finding. In: Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft, The Netherlands, 24\u201329 June, 2018, pp. 83\u201387. AAAI Press (2018)"},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1109\/TRO.2018.2853613","volume":"34","author":"W H\u00f6nig","year":"2018","unstructured":"H\u00f6nig, W., Preiss, J.A., Kumar, T.K.S., Sukhatme, G.S., Ayanian, N.: Trajectory planning for quadrotor swarms. IEEE Trans. Robotics 34(4), 856\u2013869 (2018)","journal-title":"IEEE Trans. Robotics"},{"key":"16_CR8","unstructured":"Kautz, H.A., Selman, B.: Pushing the envelope: Planning, propositional logic and stochastic search. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 96, IAAI 96, Portland, Oregon, USA, 4\u20138 August, 1996, vol. 2, pp. 1194\u20131201. AAAI Press\/The MIT Press (1996)"},{"key":"16_CR9","unstructured":"Li, J., Surynek, P., Felner, A., Ma, H., Kumar, T.K.S., Koenig, S.: Multi-agent path finding for large agents. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, 27 January\u20131 February, 2019, pp. 7627\u20137634. AAAI Press (2019)"},{"key":"16_CR10","unstructured":"Nguyen, X., Kambhampati, S.: Extracting effective and admissible state space heuristics from the planning graph. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, 30 July\u20132 August, 2000, Austin, Texas, USA, pp. 798\u2013805. AAAI Press\/The MIT Press (2000)"},{"key":"16_CR11","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."},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.artint.2012.11.006","volume":"195","author":"G Sharon","year":"2013","unstructured":"Sharon, G., Stern, R., Goldenberg, M., Felner, A.: The increasing cost tree search for optimal multi-agent pathfinding. Artif. Intell. 195, 470\u2013495 (2013)","journal-title":"Artif. Intell."},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1007\/11564751_73","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"C Sinz","year":"2005","unstructured":"Sinz, C.: Towards an optimal CNF encoding of boolean cardinality constraints. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 827\u2013831. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11564751_73"},{"key":"16_CR14","unstructured":"Sturtevant, N.R.: Benchmarks for grid-based pathfinding. Trans. Comput. Intell. AI Games 4(2), 144\u2013148 (2012). http:\/\/www.movingai.com"},{"issue":"3\u20134","key":"16_CR15","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10472-017-9560-z","volume":"81","author":"P Surynek","year":"2017","unstructured":"Surynek, P.: Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems. Ann. Math. Artif. Intell. 81(3\u20134), 329\u2013375 (2017)","journal-title":"Ann. Math. Artif. Intell."},{"key":"16_CR16","unstructured":"Surynek, P., Felner, A., Stern, R., Boyarski, E.: Efficient SAT approach to multi-agent path finding under the sum of costs objective. In: ECAI 2016\u201322nd European Conference on Artificial Intelligence, 29 August\u20132 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016). Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 810\u2013818. IOS Press (2016)"},{"issue":"2","key":"16_CR17","first-page":"93","volume":"20","author":"DS Weld","year":"1999","unstructured":"Weld, D.S.: Recent advances in AI planning. AI Mag. 20(2), 93\u2013123 (1999)","journal-title":"AI Mag."},{"issue":"1","key":"16_CR18","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\u201320 (2008)","journal-title":"AI Mag."},{"issue":"1","key":"16_CR19","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1109\/LRA.2015.2503143","volume":"1","author":"J Yu","year":"2016","unstructured":"Yu, J.: Intractability of optimal multirobot path planning on planar graphs. IEEE Robot. Autom. Lett. 1(1), 33\u201340 (2016)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"16_CR20","unstructured":"Zhang, H., Li, J., Surynek, P., Koenig, S., Kumar, T.K.S.: Multi-agent path finding with mutex propagation. In: Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling, Nancy, France, 26\u201330 October, 2020, pp. 323\u2013332. AAAI Press (2020)"}],"container-title":["Lecture Notes in Computer Science","PRIMA 2020: Principles and Practice of Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-69322-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T08:54:08Z","timestamp":1613292848000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-69322-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030693213","9783030693220"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-69322-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"14 February 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PRIMA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Principles and Practice of Multi-Agent Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nagoya","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","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":"18 November 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 November 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"prima2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/uchiya.web.nitech.ac.jp\/prima2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-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":"50","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":"19","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":"13","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":"38% - 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","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":"2","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)"}}]}}