LIPIcs.SoCG.2021.63.pdf
- Filesize: 0.98 MB
- 9 pages
Document
Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)
Authors
Loïc Crombez 
,
Guilherme D. da Fonseca ,
Yan Gerard ,
Aldo Gonzalez-Lorenzo ,
Pascal Lafourcade ,
Luc Libralesso
-
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
Acknowledgements
We would like to thank Hélène Toussaint, Raphaël Amato, Boris Lonjon, and William Guyot-Lénat from LIMOS, as well as the Qarma and TALEP teams and Manuel Bertrand from LIS, who continue to make the computational resources of the LIMOS and LIS clusters available to our research. We would also like to thank the challenge organizers and other competitors for their time, feedback, and making this whole event possible.
Cite As Get BibTex
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 (CG Challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.63
Abstract
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Computing methodologies → Motion path planning
Keywords
- heuristics
- motion planning
- digital geometry
- shortest path
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
Supplementary Materials
- Audiovisual https://vimeo.com/515040997
-
Software (Source Code)
https://github.com/gfonsecabr/shadoks-robots
browse
archived version
References
-
IBM ILOG Cplex. V12. 1: User’s manual for CPLEX. International Business Machines Corporation, 46(53):157, 2009.
- Sándor P. Demaine, Erik D .and Fekete, Phillip Keldenich, Henk Meijer, and Christian Scheffer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM Journal on Computing, 48(6):1727-1762, 2019. URL: http://dx.doi.org/10.1137/18M1194341.
- Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Computing coordinated motion plans for robot swarms: The cg:shop challenge 2021, 2021. URL: http://arxiv.org/abs/2103.15381.
-
Ariel Felner, Roni Stern, Solomon Eyal Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan Sturtevant, Glenn Wagner, and Pavel Surynek. Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In Tenth Annual Symposium on Combinatorial Search, 2017.
- Guni Sharon, Roni Stern, Ariel Felner, and Nathan R Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40-66, 2015. URL: http://dx.doi.org/10.1016/j.artint.2014.11.006.
- Jack Spalding-Jamieson, Paul Liu, Brandon Zhang, and Da Wei Zheng. Coordinated motion through randomized k-opt. In 37th International Symposium on Computational Geometry, SoCG 2021, volume 189 of LIPIcs, pages 64:1-64:8, 2021. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2021.64.
- Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.08291.
-
Pavel Surynek. Unifying search-based and compilation-based approaches to multi-agent path finding through satisfiability modulo theories. In International Joint Conferences on Artificial Intelligence, pages 1177-1183, 2019.
- Pavel Surynek, Ariel Felner, Roni Stern, and Eli Boyarski. Efficient SAT approach to multi-agent path finding under the sum of costs objective. In 22nd European Conference on Artificial Intelligence, ECAI 2016, volume 285 of Frontiers in Artificial Intelligence and Applications, pages 810-818, 2016. URL: http://dx.doi.org/10.3233/978-1-61499-672-9-810.
- 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: http://dx.doi.org/10.4230/LIPIcs.SoCG.2021.65.