{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:32:31Z","timestamp":1756463551538,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French government research program \u201cInvestissements d\u2019Avenir\u201d","award":["16-IDEX-0001 (CAP 20-25)"],"award-info":[{"award-number":["16-IDEX-0001 (CAP 20-25)"]}]},{"name":"French ANR PRC","award":["ANR-19-CE48-0005, ANR-20-CE10-0002, ANR-18-CE39-0019, ANR-18-CE39-0007, ANR-20-CE39-0005, and ANR-18-CE39-0007"],"award-info":[{"award-number":["ANR-19-CE48-0005, ANR-20-CE10-0002, ANR-18-CE39-0019, ANR-18-CE39-0007, ANR-20-CE39-0005, and ANR-18-CE39-0007"]}]},{"name":"ACTIVmap","award":["ANR-19-CE19-0005"],"award-info":[{"award-number":["ANR-19-CE19-0005"]}]},{"name":"French government IDEX-ISITE initiative","award":["16-IDEX-0001 (CAP 20-25)"],"award-info":[{"award-number":["16-IDEX-0001 (CAP 20-25)"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            This article describes the heuristics used by the\n            <jats:monospace>Shadoks<\/jats:monospace>\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            team for the CG:SHOP 2021 challenge. This year\u2019s problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi-agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. Using the heuristics outlined in this article, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions.\n          <\/jats:p>","DOI":"10.1145\/3524133","type":"journal-article","created":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T12:34:21Z","timestamp":1647866061000},"page":"1-17","source":"Crossref","is-referenced-by-count":2,"title":["Shadoks Approach to Low-Makespan Coordinated Motion Planning"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9542-5276","authenticated-orcid":false,"given":"Lo\u00efc","family":"Crombez","sequence":"first","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-028X","authenticated-orcid":false,"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[{"name":"LIS, Aix-Marseille Universit\u00e9, Arles, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2664-0650","authenticated-orcid":false,"given":"Yan","family":"Gerard","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3226-7650","authenticated-orcid":false,"given":"Aldo","family":"Gonzalez-Lorenzo","sequence":"additional","affiliation":[{"name":"LIS, Aix-Marseille Universit\u00e9, Arles, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4459-511X","authenticated-orcid":false,"given":"Pascal","family":"Lafourcade","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9908-4811","authenticated-orcid":false,"given":"Luc","family":"Libralesso","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-61499-419-0-961"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-190621"},{"key":"e_1_3_2_4_2","first-page":"223","volume-title":"8th Annual Symposium on Combinatorial Search (SOCS\u201915","author":"Boyarski Eli","year":"2015","unstructured":"Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, Oded Betzalel, David Tolpin, and Solomon Eyal Shimony. 2015. ICBS: The improved conflict-based search algorithm for multi-agent pathfinding. In 8th Annual Symposium on Combinatorial Search (SOCS\u201915). 223\u2013225. http:\/\/www.aaai.org\/ocs\/index.php\/SOCS\/SOCS15\/paper\/view\/10974."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2017.03.053"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i1a20"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2013.293"},{"issue":"53","key":"e_1_3_2_8_2","first-page":"157","article-title":"V12. 1: User\u2019s manual for CPLEX","volume":"46","author":"CPLEX IBM ILOG","year":"2009","unstructured":"IBM ILOG CPLEX. 2009. V12. 1: User\u2019s manual for CPLEX. International Business Machines Corporation 46, 53 (2009), 157.","journal-title":"International Business Machines Corporation"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1194341"},{"key":"e_1_3_2_10_2","article-title":"Computing coordinated motion plans for robot swarms: The CG: SHOP challenge 2021","volume":"2103","author":"Fekete S\u00e1ndor P.","year":"2021","unstructured":"S\u00e1ndor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. 2021. Computing coordinated motion plans for robot swarms: The CG: SHOP challenge 2021. CoRR abs\/2103.15381 (2021). arXiv:2103.15381.https:\/\/arxiv.org\/abs\/2103.15381.","journal-title":"CoRR"},{"key":"e_1_3_2_11_2","first-page":"83","volume-title":"28th International Conference on Automated Planning and Scheduling (ICAPS\u201918","author":"Felner Ariel","year":"2018","unstructured":"Ariel Felner, Jiaoyang Li, Eli Boyarski, Hang Ma, Liron Cohen, T. K. Satish Kumar, and Sven Koenig. 2018. Adding heuristics to conflict-based search for multi-agent path finding. In 28th International Conference on Automated Planning and Scheduling (ICAPS\u201918). 83\u201387. https:\/\/aaai.org\/ocs\/index.php\/ICAPS\/ICAPS18\/paper\/view\/17735."},{"key":"e_1_3_2_12_2","first-page":"29","volume-title":"T10th International Symposium on Combinatorial Search (SOCS\u201917","author":"Felner Ariel","year":"2017","unstructured":"Ariel Felner, Roni Stern, Solomon Eyal Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan R. Sturtevant, Glenn Wagner, and Pavel Surynek. 2017. Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In T10th International Symposium on Combinatorial Search (SOCS\u201917). 29\u201337. https:\/\/aaai.org\/ocs\/index.php\/SOCS\/SOCS17\/paper\/view\/15781."},{"key":"e_1_3_2_13_2","article-title":"A C++ implementation of a fast hash map and hash set using hopscotch hashing","author":"Goetghebuer-Planchon Thibaut","year":"2020","unstructured":"Thibaut Goetghebuer-Planchon. 2020. A C++ implementation of a fast hash map and hash set using hopscotch hashing. https:\/\/github.com\/Tessil\/hopscotch-map.","journal-title":"https:\/\/github.com\/Tessil\/hopscotch-map"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4171"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.2307\/2369492"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/179"},{"key":"e_1_3_2_17_2","article-title":"Lifelong multi-agent path finding in large-scale warehouses","volume":"2005","author":"Li Jiaoyang","year":"2020","unstructured":"Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar, and Sven Koenig. 2020. Lifelong multi-agent path finding in large-scale warehouses. CoRR abs\/2005.07371 (2020). arXiv:2005.07371.https:\/\/arxiv.org\/abs\/2005.07371.","journal-title":"CoRR"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2021.64"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAR.2019.8813319"},{"key":"e_1_3_2_20_2","article-title":"Overview: Generalizations of multi-agent path finding to real-world scenarios","volume":"1702","author":"Ma Hang","year":"2017","unstructured":"Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang H\u00f6nig, T. K. Satish Kumar, Tansel Uras, Hong Xu, Craig A. Tovey, and Guni Sharon. 2017. Overview: Generalizations of multi-agent path finding to real-world scenarios. CoRR abs\/1702.05515 (2017). arXiv:1702.05515.http:\/\/arxiv.org\/abs\/1702.05515.","journal-title":"CoRR"},{"key":"e_1_3_2_21_2","first-page":"168","volume-title":"5th AAAI National Conference on Artificial Intelligence (AAAI 1986","author":"Ratner Daniel","year":"1986","unstructured":"Daniel Ratner and Manfred Warmuth. 1986. Finding a shortest solution for the N \\( \\times \\) N extension of the 15-puzzle is intractable. In 5th AAAI National Conference on Artificial Intelligence (AAAI 1986). 168\u2013172."},{"key":"e_1_3_2_22_2","article-title":"E-commerce warehousing: Learning a storage policy","volume":"2101","author":"Rim\u00e9l\u00e9 Adrien","year":"2021","unstructured":"Adrien Rim\u00e9l\u00e9, Philippe Grangier, Michel Gamache, Michel Gendreau, and Louis-Martin Rousseau. 2021. E-commerce warehousing: Learning a storage policy. CoRR abs\/2101.08828 (2021). arXiv:2101.08828.https:\/\/arxiv.org\/abs\/2101.08828.","journal-title":"CoRR"},{"key":"e_1_3_2_23_2","article-title":"Supervised learning and tree search for real-time storage allocation in robotic mobile fulfillment systems","volume":"2106","author":"Rim\u00e9l\u00e9 Adrien","year":"2021","unstructured":"Adrien Rim\u00e9l\u00e9, Philippe Grangier, Michel Gamache, Michel Gendreau, and Louis-Martin Rousseau. 2021. Supervised learning and tree search for real-time storage allocation in robotic mobile fulfillment systems. CoRR abs\/2106.02450 (2021). arXiv:2106.02450.https:\/\/arxiv.org\/abs\/2106.02450.","journal-title":"CoRR"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.006"},{"key":"e_1_3_2_25_2","first-page":"117","volume-title":"1 Artificial Intelligence and Interactive Digital Entertainment Conference","author":"Silver David","year":"2005","unstructured":"David Silver. 2005. Cooperative pathfinding. In 1 Artificial Intelligence and Interactive Digital Entertainment Conference. 117\u2013122."},{"key":"e_1_3_2_26_2","first-page":"151","volume-title":"12th International Symposium on Combinatorial Search (SOCS\u201919","author":"Stern Roni","year":"2019","unstructured":"Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Bart\u00e1k, and Eli Boyarski. 2019. Multi-Agent pathfinding: Definitions, variants, and benchmarks. In 12th International Symposium on Combinatorial Search (SOCS\u201919). 151\u2013159. https:\/\/aaai.org\/ocs\/index.php\/SOCS\/SOCS19\/paper\/view\/18341."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/164"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-61499-672-9-810"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5220\/0006184504510458"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105090"},{"key":"e_1_3_2_31_2","article-title":"15 puzzle\u2014Wikipedia, The Free Encyclopedia","year":"2021","unstructured":"Wikipedia. 2021. 15 puzzle\u2014Wikipedia, The Free Encyclopedia. Retrieved December 27, 2021. http:\/\/en.wikipedia.org\/w\/index.php?title=15%20puzz\\le&oldid=1058438932.","journal-title":"http:\/\/en.wikipedia.org\/w\/index.php?title=15%20puzz\\le&oldid=1058438932"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4447"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2021.65"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631084"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524133","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3524133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:05Z","timestamp":1750188665000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":33,"alternative-id":["10.1145\/3524133"],"URL":"https:\/\/doi.org\/10.1145\/3524133","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,7,27]]}}}