LIPIcs.SoCG.2021.64.pdf
- Filesize: 0.88 MB
- 8 pages
Document
Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)
Authors
Paul Liu 
,
Da Wei Zheng
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
Cite As Get BibTex
Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Coordinated Motion Planning Through Randomized k-Opt (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 64:1-64:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.64
Abstract
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.
Subject Classification
ACM Subject Classification
- Computing methodologies → Motion path planning
- Theory of computation → Computational geometry
Keywords
- motion planning
- randomized local search
- path finding
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
Supplementary Materials
-
Software (Source Code)
https://github.com/jacketsj/cgshop2021-gitastrophe
browse
archived version
References
- Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning. In 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of LIPIcs, pages 63:1-63:9, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.63.
- Sándor Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021. CoRR, abs/2103.15381, 2021. URL: http://arxiv.org/abs/2103.15381.
- Hyeyun Yang and Antoine Vigneron. A Simulated Annealing Approach to Coordinated Motion Planning. In 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of LIPIcs, pages 65:1-65:9, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.65.