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.

翻译：本文描述沙多克团队在 CG:SHOP 2021 挑战中使用的逻辑论。 今年的问题是协调多个机器人的运动, 以便不发生碰撞地达到目标, 并尽可能减少黑板。 这是一个典型的多剂路径, 其特殊性是, 这些事件在无边界的网格中非常密集。 使用本文概述的逻辑论, 我们的团队首先赢得了202个案例中的202个最佳解决方案, 至少105个最佳解决方案。 主要元素包括数种不同的战略, 来计算初步解决方案, 加上一种叫作“ 冲突最佳化” 的黑板, 以减少现有解决方案的构成。