{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:59:45Z","timestamp":1757311185749,"version":"3.41.0"},"reference-count":6,"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":"Basic Science Research Program"},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ministry of Education","award":["2017R1D1A1B04036529"],"award-info":[{"award-number":["2017R1D1A1B04036529"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>The third computational geometry challenge was on a coordinated path planning problem in which a collection of square robots need to move on the integer grid, from their given starting points to their target points, and without collision between robots, or between robots and a set of input obstacles. We designed and implemented three algorithms for this problem. First, we computed a feasible solution by placing middle-points outside of the minimum bounding box of the starting positions, the target positions and the obstacles, and moving each robot from its starting point to its target point through a middle-point. Second, we applied a simple local search approach where we repeatedly delete and insert again a random robot through an optimal path. It improves the quality of the solution, as the robots no longer need to go through the middle-points. Finally, we used simulated annealing to further improve this feasible solution. We used two different types of moves: We either tightened the whole trajectory of a robot, or we stretched it between two points by making the robot move through a third intermediate point generated at random.<\/jats:p>","DOI":"10.1145\/3531224","type":"journal-article","created":{"date-parts":[[2022,4,23]],"date-time":"2022-04-23T11:14:14Z","timestamp":1650712454000},"page":"1-14","source":"Crossref","is-referenced-by-count":2,"title":["Coordinated Path Planning through Local Search and Simulated Annealing"],"prefix":"10.1145","volume":"27","author":[{"given":"Hyeyun","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Ulsan National Institute of Science and Technology, Ulsan, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3586-3431","authenticated-orcid":false,"given":"Antoine","family":"Vigneron","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Ulsan National Institute of Science and Technology, Ulsan, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2021.63"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1194341"},{"key":"e_1_3_1_4_2","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. (2021). arxiv:cs.CG\/2103.15381. Retrieved from https:\/\/arxiv.org\/abs\/2103.15381."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2021.64"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/59580"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2021.65"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531224","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:31Z","timestamp":1750188691000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":6,"alternative-id":["10.1145\/3531224"],"URL":"https:\/\/doi.org\/10.1145\/3531224","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]]}}}