技术摘要：Tensor-Coord

问题陈述

大语言模型（LLMs）在多智能体规划方面存在根本性的局限性，这主要是由于生成流畅性与结构化推理之间的差距所致。虽然 LLMs 可以生成看似合理的单个计划，但它们缺乏协调行动所需的确定性状态跟踪和系统性搜索能力。当多个智能体独立进行规划时，它们的计划往往会导致集体性的不一致，例如空间碰撞、资源争夺和时间死锁。

现有的协调方法未能有效解决这一问题：

• 联合提示（Joint Prompting）： 将所有智能体的上下文拼接在一起会超出实际的上下文窗口限制，因为联合动作空间呈指数级增长（$|A|^N$）。
• 顺序规划（Sequential Planning）： 会引入排序偏差，且无法解决循环依赖问题。
• 经典算法（如基于冲突的搜索，Conflict-Based Search）： 需要形式化的领域规范（PDDP），这抵消了自然语言的灵活性。

核心挑战在于：如何在不依赖特定领域规则或形式化状态空间模型的情况下，检测并解决 LLM 生成的联合计划中的协调失败问题。

方法论：Tensor-Coord 框架

本文介绍了 Tensor-Coord，该框架将 $N$ 个智能体的联合计划编码为一个三阶张量 $\mathbf{T} \in \mathbb{R}^{N \times T \times A}$（智能体 $\times$ 时间步 $\times$ 动作），并应用多线性代数来发现潜在的协调结构。

1. 软张量表示（Soft Tensor Representation）

为了确保数值稳定性并实现全多线性秩，该框架避免了硬性的二进制编码。相反，它使用了一个软计划张量（Soft Plan Tensor）：
$$\mathcal{T}(i, t, k) = \gamma \cdot \mathbb{1}[a_i^t = a_k] + \frac{1-\gamma}{K-1} \cdot \mathbb{1}[a_i^t \neq a_k]$$
其中 $\gamma$ 是置信度参数（例如 0.8）。这为选定的动作分配高概率，并将剩余概率分布在其他动作中，在保留主导结构的同时防止秩亏（rank deficiency）。

2. 典型张量分解（CP Decomposition）与复杂度度量

框架应用 CP 分解将张量分解为若干个秩一分量的和：
$$\mathcal{T} \approx \sum_{r=1}^{R} \lambda_r \cdot \mathbf{u}_r \otimes \mathbf{v}_r \otimes \mathbf{w}_r$$

• 理论洞察： 如果智能体是相互独立的，则张量秩 $R^*$ 等于智能体数量 $N$。如果 $R^* > N$，则多出的秩代表了智能体间的依赖关系（耦合）。
• *协调复杂度度量（Coordination Complexity Metric, $CC$）：** 定义为$CC(\Pi) = \frac{R^ - N}{N}$。
  • $CC(\Pi) = 0$ 意味着相互独立（不存在冲突可能）。
  • $CC(\Pi) > 0$ 意味着统计学上的相关性以及协调的必要性。

3. 基于残差的冲突检测

分解残差 $\mathbf{E} = \mathcal{T} - \mathcal{T}_{R^*}$ 捕捉了无法由独立线程解释的行为。

• 冲突评分： $CS(i, j, t) = \rho(i, t) \cdot \rho(j, t)$，其中 $\rho(i, t) = \|\mathbf{E}(i, t, :)\|_2$。
• 机制： 在同一时间步 $t$ 下，智能体 $i$ 和 $j$ 出现的高残差表明存在协调失败（例如碰撞），这种失败是独立模型无法解释的。这使得在无需领域特定规则的情况下，通过代数方式实现冲突定位。

4. 用于可解释性的 Tucker 分解

为了指导重新规划，框架使用 Tucker 分解（$\mathcal{T} \approx \mathcal{G} \times_1 \mathbf{U} \times_2 \mathbf{V} \times_3 \mathbf{W}$）来提取可解释的因子：

• $\mathbf{U}$（智能体角色）： 对具有相似协调角色的智能体进行聚类。
• $\mathbf{V}$（时间阶段）： 识别关键的协调窗口。
• $\mathbf{W}$（动作类型）： 将功能等效的动作进行分组。
  这些因子被转化为自然语言约束（例如，“在时间步 $t$ 避开位置 $(x,y)$” 或 “在阶段边界处同步”），以指导迭代式的 LLM 重新规划。

5. 迭代算法

系统按以下循环运行：

1. LLMs 生成初始计划。
2. 将计划编码为软张量。
3. 通过 CP 分解计算 $R^*$ 和残差 $\mathbf{E}$。
4. 通过残差评分定位冲突。
5. 利用 Tucker 因子生成具体的自然语言约束。
6. 将约束反馈给 LLMs 进行重新规划。
7. 重复该循环直至收敛或达到最大迭代次数。

核心贡献

1. 张量化表述： 一种软编码的联合计划表示法，实现了稳定的多线性分解。
2. 代数复杂度度量： 首个可计算的、具有代数基础的协调复杂度度量（$CC$），证明了$R^*=N$ 是计划独立的充要条件。
3. 领域无关的冲突检测： 一种基于残差的方法，能够在智能体 $\times$ 时间步 $\times$ 动作空间中通过代数方式定位冲突，而无需显式的碰撞规则。
4. 可解释结构提取： 利用 Tucker 分解推导出智能体角色、时间阶段和动作簇，从而生成可操作的约束。
5. 迭代优化算法： 一个在多机器人递送任务中实现了高收敛率的框架。

实验结果

实验在包含 2 到 5 个智能体的网格世界（5x5 和 6x6）中进行的多机器人递送任务上展开。

• 收敛率：
  • 简单（2 个智能体）： 100% 收敛（平均 1.4 次迭代）。
  • 中等（3 个智能体）： 80% 收敛（平均 3.2 次迭代）。
  • 困难（4 个智能体）： 60% 收敛（平均 4.0 次迭代）。
  • 极难（5 个智能体）： 20% 收敛（高拥堵限制了解决能力）。
• 缩放法则： 最小 CP 秩随智能体数量线性扩展：$R^*(N) \approx 3.9 \cdot N + 0.5$（$R^2 = 0.94$），证实了该度量作为复杂度预测器的可靠性。
• 基准对比： Tensor-Coord 显著优于独立规划（Independent Planning）、轮询顺序规划（Round-Robin sequential planning）以及单 LLM 联合提示（Single-LLM Joint prompting）。它是唯一能够通过迭代优化达到零冲突的方法，尤其是在中等复杂度场景下。

意义与主张

本文声称 Tensor-Coord 弥合了 LLM 的自然语言灵活性与多智能体协调的严苛要求之间的鸿沟。通过将协调视为一个张量秩的代数问题，该框架：

• 提供了一个可量化的难度度量（$CC$），这在以往的 LLM 多智能体系统中是缺失的。
• 提供了一种原则性的冲突检测机制，不依赖于手工设计的领域规则，使其适用于多种环境。
• 证明了代数分解可以有效地引导 LLM 解决标准提示策略无法处理的复杂协调失败问题。

作者指出，虽然该方法在可处理的问题上取得了很高的成功率，但在高度拥挤的环境中（例如 6x6 网格中的 5 个智能体）面临挑战，因为约束之间的相互作用可能导致非单调收敛。未来的工作拟针对更大规模的智能体数量提出层次化分解以及最小冲突解决约束集。