{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:51Z","timestamp":1750220271326,"version":"3.41.0"},"reference-count":9,"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"}],"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 examines the approach taken by team\n            <jats:monospace>gitastrophe<\/jats:monospace>\n            in the CG:SHOP 2021 challenge. The challenge was to find a sequence of simultaneous moves of square robots between two given configurations that minimized either total distance travelled or makespan (total time). Our winning approach has two main components: an initialization phase that finds a good initial solution and a\n            <jats:italic>k<\/jats:italic>\n            -opt local search phase that seeks to optimize this solution. This led to a first-place finish in the distance category and a third-place finish in the makespan category.\n          <\/jats:p>","DOI":"10.1145\/3524134","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T12:54:06Z","timestamp":1648212846000},"page":"1-9","source":"Crossref","is-referenced-by-count":0,"title":["Coordinated Motion Planning Through Randomized\n            <i>k<\/i>\n            -Opt"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9386-6609","authenticated-orcid":false,"given":"Paul","family":"Liu","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}]},{"given":"Jack","family":"Spalding-Jamieson","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Brandon","family":"Zhang","sequence":"additional","affiliation":[{"name":"No institution, Canada"}]},{"given":"Da Wei","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_3_1_2_2","volume-title":"Proceedings of the 37th International Symposium on Computational Geometry (SoCG\u201921) (LIPIcs)","volume":"189","author":"Crombez Lo\u00efc","year":"2021","unstructured":"Lo\u00efc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. 2021. Shadoks approach to low-makespan coordinated motion planning. In Proceedings of the 37th International Symposium on Computational Geometry (SoCG\u201921) (LIPIcs), Vol. 189."},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"S\u00e1ndor Fekete Phillip Keldenich Dominik Krupke and Joseph S. B. Mitchell. 2021. Computing coordinated motion plans for robot swarms: The CG:SHOP challenge 2021. Retrieved from https:\/\/arxiv.org\/abs\/2103.15381.","DOI":"10.1145\/3532773"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2894217"},{"key":"e_1_3_1_5_2","first-page":"270","volume-title":"Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE\u201917)","author":"Ma Hang","year":"2017","unstructured":"Hang Ma, Jingxing Yang, Liron Cohen, T. K. Satish Kumar, and Sven Koenig. 2017. Feasibility study: Moving non-homogeneous teams in congested video game environments. In Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE\u201917), Brian Magerko and Jonathan P. Rowe (Eds.). AAAI Press, 270\u2013272. Retrieved from https:\/\/aaai.org\/ocs\/index.php\/AIIDE\/AIIDE17\/paper\/view\/15845."},{"key":"e_1_3_1_6_2","volume-title":"Proceedings of the AAAI Workshop on Artificial Intelligence for Transportation: Advice, Interactivity, and Actor Modeling (AAAI Workshops\u201915)","volume":"15","author":"Morris Robert","year":"2015","unstructured":"Robert Morris, Mai Lee Chang, Ronald Archer, Ernest Vincent Cross II, Shelby Thompson, Jerry L. Franke, Robert Christopher Garrett, Waqar Malik, Kerry McGuire, and Garrett Hemann. 2015. Self-driving aircraft towing vehicles: A preliminary report. In Proceedings of the AAAI Workshop on Artificial Intelligence for Transportation: Advice, Interactivity, and Actor Modeling (AAAI Workshops\u201915), Adi Botea and Sebastiaan A. Meijer (Eds.), Vol. WS-15-05. AAAI Press. Retrieved from http:\/\/aaai.org\/ocs\/index.php\/WS\/AAAIW15\/paper\/view\/10075."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.006"},{"key":"e_1_3_1_8_2","volume-title":"Proceedings of the 37th International Symposium on Computational Geometry (SoCG\u201921) (LIPIcs)","volume":"189","author":"Yang Hyeyun","year":"2021","unstructured":"Hyeyun Yang and Antoine Vigneron. 2021. A simulated annealing approach to coordinated motion planning. In Proceedings of the 37th International Symposium on Computational Geometry (SoCG\u201921) (LIPIcs), Vol. 189."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631084"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2593448"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524134","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3524134","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\/3524134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":9,"alternative-id":["10.1145\/3524134"],"URL":"https:\/\/doi.org\/10.1145\/3524134","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]]}}}