Shadoks Approach to Low-Makespan Coordinated Motion Planning

DOI10.1145/3524133zbMATH Open1521.68224arXiv2103.13956OpenAlexW4220830180MaRDI QIDQ6163580FDOQ6163580

Authors: Loïc Crombez, Guilherme D. Da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso 

Publication date: 26 June 2023

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Abstract: This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. 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. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions.

Full work available at URL: https://arxiv.org/abs/2103.13956

Recommendations

• Coordinated Motion Planning Through Randomized k -Opt
• Computing coordinated motion plans for robot swarms: the CG:SHOP challenge 2021
• scientific article; zbMATH DE number 1882044
• Coordinated motion planning: the video (multimedia exposition)
• Coordinated Path Planning through Local Search and Simulated Annealing

zbMATH Keywords

heuristicsshortest pathmotion planningmulti-agent path finding

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

Cites Work

• Branch-and-cut-and-price for multi-agent path finding
• Conflict-based search for optimal multi-agent pathfinding
• \(L_1\) shortest path queries among polygonal obstacles in the plane
• Enhanced partial expansion A\(^*\)
• Order allocation, rack allocation and rack sequencing for pickers in a mobile rack environment
• Parts-to-picker based order processing in a rack-moving mobile robots environment
• Push and rotate: a complete multi-agent pathfinding algorithm
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Two-point \(L_1\) shortest path queries in the plane
• Migrating techniques from search-based multi-agent path finding solvers to SAT-based approach
• Computing coordinated motion plans for robot swarms: the CG:SHOP challenge 2021

Cited In (4)

• Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• Coordinated Motion Planning Through Randomized k -Opt
• Computing coordinated motion plans for robot swarms: the CG:SHOP challenge 2021

This page was built for publication: Shadoks Approach to Low-Makespan Coordinated Motion Planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163580)