Shadoks Approach to Low-Makespan Coordinated Motion Planning

DOI10.1145/3524133MaRDI QIDQ6163580zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• Branch-and-cut-and-price for multi-agent path finding
• Computing coordinated motion plans for robot swarms: the CG:SHOP challenge 2021
• Conflict-based search for optimal multi-agent pathfinding
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Enhanced partial expansion A\(^*\)
• Migrating techniques from search-based multi-agent path finding solvers to SAT-based approach
• 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
• Two-point \(L_1\) shortest path queries in the plane
• \(L_1\) shortest path queries among polygonal obstacles in the plane

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)