树形结构上最优移动的难度
本文通过一个简单框架解决了树形结构上多智能体路径规划（MAPF）的复杂性问题，涵盖距离、最大完工时间和流动时间等标准目标，以及标记和着色变体。证明了在树上标记和2着色MAPF的所有三种目标都是NP难的，并解决了经典的卵石移动问题。所有结果通过堆栈重排问题的NP难性得出。
近日，一篇题为《On the Hardness of Optimal Motion on Trees》的论文在arXiv上发布，作者Tzvika Geft提出了一种简单而强大的框架，彻底解决了树形结构上多智能体路径规划（Multi-Agent Path Finding, MAPF）的复杂性分类问题。该研究涵盖了距离（distance）、最大完工时间（makespan）和流动时间（flowtime）三种标准目标函数，以及标记（labeled）和着色（colored）两种变体。
在MAPF问题中，多个智能体占据图的顶点，需要移动到各自的目标顶点，同时避免碰撞并优化给定的目标。在标记变体中，每个智能体是独特的，并具有指定的目标；而在着色变体中，相同颜色的智能体可以互换目标。尽管许多MAPF变体已被证明是难解的，但树上的一些基本情形长期以来一直是悬而未决的难题。
该论文的核心成果是证明了在树形结构上，标记MAPF和2着色MAPF在所有三种目标下都是NP难的。这一结果不仅解决了几个开放问题，还特别解决了经典的卵石移动问题（Pebble Motion Problem）。在该问题中，一次只能将一颗卵石移动到相邻的空顶点，目标是最小化总移动次数。尽管这是最基本的离散运动模型之一，但其在树上的复杂性在数十年来一直未被解决。此外，对于着色卵石移动问题，该研究首次在任何图类上给出了难度结果，仅用两种颜色就达到了紧界。
所有上述结果都是通过证明堆栈重排问题（Stack Rearrangement）的NP难性而得到的。堆栈重排问题本身是一个开放问题，要求最优地重新排列存储在堆栈中的物品。值得注意的是，与堆栈的联系使得即使在非常简单的树（如细分星形图）上，所有问题也能导出难度结果。
这些发现揭示了一个贯穿多个基本运动模型的共同计算障碍，从而统一并加强了先前的难度结果。该成果对机器人路径规划、物流和自动化等领域具有深远意义，也为未来研究提供了新的方向。