2026-08-14T20:29:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13863 2024-03-06T10:52:54Z ddc:004 open_access

Coordinated Motion Planning Through Randomized k-Opt (CG Challenge) Liu, Paul Spalding-Jamieson, Jack Zhang, Brandon Zheng, Da Wei motion planning randomized local search path finding This paper examines the approach taken by team gitastrophe 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 k-opt local search phase which optimizes this solution. This led to a first place finish in the distance category and a third place finish in the makespan category. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul Liu and Jack Spalding-Jamieson and Brandon Zhang and Da Wei Zheng 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.64 urn:nbn:de:0030-drops-138635 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.64 eng https://creativecommons.org/licenses/by/4.0/legalcode