跳转至

第七章：合作决策制定

书籍信息：Decision Making Under Uncertainty: Theory and Application, Christopher Amato, MIT Press, 2015

第一节：本章概述

本章由Christopher Amato撰写，讨论了多智能体协作决策制定问题。在现实世界中，许多应用场景涉及多个智能体（如机器人、传感器、软件代理）需要协同工作以完成复杂任务。随着智能体制造成本的下降，可以部署的智能体数量越来越多，但要让团队发挥全部潜力，每个智能体必须对其他智能体的行为进行推理。本章系统性地介绍了如何建模和求解这类问题。

本章的核心模型是去中心化部分可观测马尔可夫决策过程（Dec-POMDP），这是对MDP和POMDP模型的扩展，适用于分布式执行场景。在Dec-POMDP中，系统动力学和目标函数依赖于所有智能体的动作，但每个智能体必须基于本地信息做出决策。这种设定反映了真实世界中的典型情况：智能体无法获得完整的全局信息，只能根据自己观测到的局部信息来选择行动。

本章的内容安排遵循从理论基础到实际算法的逻辑顺序：首先介绍Dec-POMDP的数学定义和示例问题，然后讨论该模型的基本性质和计算复杂度，接着探讨几个重要的子类（如Dec-MDP、ND-POMDP、MMDP），之后详细阐述精确求解方法和近似求解方法，最后讨论通信在协作决策中的作用。

第二节：关键问题与研究动机

2.1 核心科学问题

多智能体协作决策制定涉及以下几个关键科学问题：

问题一：如何建模多智能体不确定性决策？ 在单智能体场景中，我们可以使用MDP建模完全可观测情况，或使用POMDP建模部分可观测情况。但在多智能体场景中，每个智能体不仅面临环境状态的不确定性，还面临其他智能体行为和观测的不确定性。传统的集中式方法假设所有信息都集中处理，但这在许多实际应用中是不可行的，因为智能体可能分布在不同位置，无法实时共享所有信息。

问题二：如何保证分布式执行的可行性？ 在Dec-POMDP中，每个智能体必须能够独立执行其策略，仅基于本地观测历史做出决策。这要求策略表示必须是去中心化的，每个智能体拥有自己独立的策略树或有限状态控制器，不能依赖全局状态估计。

问题三：如何处理三种不确定性叠加的复杂性？ 本章的机器人导航示例问题说明了这一点：动作结果的不确定性（与MDP相同）、传感器信息的不确定性（与POMDP相同）、以及其他智能体信息的不确定性（多智能体特有）。这三种不确定性叠加使得问题复杂度显著增加。

问题四：如何在计算复杂度和解质量之间取得平衡？ 精确求解Dec-POMDP是NEXP完全问题，在最坏情况下需要双指数时间。研究者需要开发能够在合理时间内产生高质量解的近似算法。

2.2 研究动机与实际意义

多智能体协作系统在现实中有着广泛的应用场景，包括机器人编队控制、传感器网络管理、分布式资源调度、自动驾驶车辆协调等。随着技术发展，实际问题规模越来越大，对算法可扩展性的要求也越来越高。研究Dec-POMDP的理论基础和算法设计对于推动这些应用领域的发展具有重要意义。

第三节：主要公式与推导

3.1 Dec-POMDP的形式化定义

Dec-POMDP由以下要素组成：

  • \(I\)：有限智能体集合
  • \(S\)：有限状态集合，带有指定的初始状态分布 \(b_0\)
  • \(A_i\)：智能体 \(i\) 的有限动作集合
  • \(T\)：转移概率函数 \(T(s'|s,a)\)，表示在状态 \(s\) 下执行联合动作 \(a\) 后转移到状态 \(s'\) 的概率
  • \(R\)：奖励函数 \(R(s,a)\)，表示在状态 \(s\) 执行联合动作 \(a\) 获得的即时奖励
  • \(\Omega_i\)：智能体 \(i\) 的有限观测集合
  • \(O\)：观测模型 \(O(o|s',a)\)，表示在状态 \(s'\) 下执行动作 \(a\) 后获得观测 \(o\) 的概率

3.2 策略树评估的Bellman方程

对于有限视野问题，策略树评估公式为：

\[U(q,s) = R(a_q,s) + \sum_{s',o} P(s'|a_q,s) P(o|a_q,s') U(q_o,s')\]

其中 \(a_q\) 是策略树 \(q\) 根节点定义的联合动作，\(q_o\) 是观测 \(o\) 后访问的子策略树。这个公式本质上是将即时奖励与未来折扣奖励的期望相加，类似于单智能体MDP的Bellman方程，但需要考虑所有可能的联合转移和观测。

3.3 有限状态控制器的评估方程

对于无限视野问题，使用有限状态控制器表示策略。定义 \(P(a_i|q_i)\) 为智能体 \(i\) 在节点 \(q_i\) 选择动作 \(a_i\) 的概率，\(P(q_j'|q_j,a_j,o_j)\) 为控制器在节点 \(q_j\) 执行动作 \(a_j\) 并观测到 \(o_j\) 后转移到节点 \(q_j'\) 的概率。评估方程为：

\[U(q,s) = \sum_{\substack{a}} \prod_i P(a_i|q_i) R(s,a) + \gamma \sum_{\substack{s',o,q'}} P(s'|a,s) O(o|s',a) \prod_j P(q_j'|q_j,a_j,o_j) U(q',s')\]

这个公式比有限视野情况更复杂，因为它涉及对所有可能的联合动作、状态转移、观测和控制器节点转移的积分。

3.4 广义Belief状态

在多智能体情况下，不仅状态有不确定性，其他智能体的策略也有不确定性。广义belief状态定义为：

\[U(p,b_G) = \sum_{q,s} b_G(s,q) U(p,q,s)\]

其中 \(q\) 表示其他智能体的策略分布。如果所有其他智能体的策略已知，则广义belief状态退化为标准的POMDP belief状态，可以将Dec-POMDP简化为POMDP求解。

3.5 Dec-MDP独立性条件

对于因子化的n智能体Dec-MDP，定义状态分解 \(S = S_0 \times S_1 \times ... \times S_n\)，其中 \(S_i\) 是智能体 \(i\) 的本地状态，\(S_0\) 是环境公共状态。三种独立性条件为：

转移独立性： $\(T(s'|s,a) = T_0(s_0'|s_0) \prod_i T_i(s_i'|s_i,a_i)\)$

观测独立性： $\(O(o|s,a) = \prod_i O_i(o_i|s_i,a_i)\)$

奖励独立性： $\(R(s,a) = f(R_1(s_1,a_1), ..., R_n(s_n,a_n))\)$

其中 \(f\) 是单调非递减函数。加性奖励是奖励独立性的一个特例：

\[R(s,a) = R_0(s_0) + \sum_i R_i(s_i,a_i)\]

3.6 线性规划剪枝条件

动态规划算法中判断策略树是否可以被剪枝的线性规划：

最大化 \(\varepsilon\)，满足： $\(\sum_{q_{-i},s} x(q_{-i},s) U(\hat{q}_i, q_{-i}, s) + \varepsilon \leq \sum_{q_{-i},s} x(q_{-i},s) U(q_i, q_{-i}, s) \quad \forall \hat{q}_i\)$

\[\sum_{q_{-i},s} x(q_{-i},s) = 1, \quad x(q_{-i},s) \geq 0 \quad \forall q_{-i}, s\]

这个线性规划判断对于所有可能的广义belief状态，策略树 \(q_i\) 是否被其他策略树严格支配。

第四节：关键算法与建模方法

4.1 精确求解方法

4.1.1 动态规划算法（Algorithm 7.1）

动态规划算法从最后一步向前逐步构建每个智能体的策略树集合 \(\pi\)。算法核心步骤：

  1. 初始化：从单步策略树开始
  2. 穷举备份：对每个智能体，生成所有可能的下一步策略树 \(|A_i|^{|Q_i||\Omega_i|}\) 个
  3. 评估：使用公式(7.1)计算每个策略树的值
  4. 剪枝：对每个智能体，移除被其他策略树支配的策略树
  5. 迭代：重复直到达到指定视野T

剪枝过程使用线性规划（公式7.10-7.11）判断支配关系。只有当策略树在所有可能的广义belief状态下都被其他策略树支配时，才可以安全移除。

4.1.2 多智能体A*算法（Algorithm 7.2）

与自底向上的动态规划不同，MAA*采用自顶向下的搜索方式：

  1. 初始化：将所有可能的联合动作加入开放列表
  2. 选择：从开放列表中选择估计值最高的部分联合策略
  3. 扩展：为选中的部分策略添加下一步动作
  4. 评估：计算完整策略的值，更新下界
  5. 剪枝：移除估计值低于当前下界的部分策略
  6. 迭代：直到开放列表为空

MAA使用启发式估计来指导搜索。好的启发式能显著减少搜索空间。常用的启发式包括VPOMDP（POMDP最优值）和VMDP*（MDP最优值），它们分别是Dec-POMDP最优值的上界。

4.1.3 策略迭代算法（Algorithm 7.3）

策略迭代用于无限视野问题，使用有限状态控制器作为策略表示：

  1. 评估：使用公式(7.2)评估当前控制器
  2. 备份：执行穷举备份添加新节点到控制器
  3. 剪枝：移除被支配的控制器节点
  4. 收敛判断：检查是否满足 \(\frac{\gamma^{t+1}|R_{max}|}{1-\gamma} \leq \varepsilon\)

收敛条件基于折扣因子和最大奖励绝对值，保证剩余步骤的贡献小于 \(\varepsilon\)。

4.2 近似求解方法

4.2.1 记忆有界动态规划（Algorithm 7.4）

MBDP通过限制每步保留的策略树数量来控制内存使用：

  • 使用参数MaxTrees限制每步保留的策略树数量
  • 使用启发式（如MDP策略或随机策略）生成候选belief状态
  • 在这些belief状态上选择值最高的策略树
  • 时间空间复杂度为O(T)，线性于视野

MBDP是精确动态规划和启发式搜索的混合，结合了两者的优点。

4.2.2 联合均衡搜索（Algorithm 7.5）

JESP使用交替最佳响应来寻找局部最优：

  1. 初始化所有智能体的策略
  2. 固定n-1个智能体的策略，优化剩余一个智能体的策略
  3. 轮流进行，直到没有智能体改变策略
  4. 返回的策略是Nash均衡的局部最优

JESP可以看作在合作的Dec-POMDP博弈中寻找Nash均衡。

4.3 通信建模

通信可以是隐式的（通过观测）或显式的（通过消息传递）。Dec-POMDP-Com模型将通信显式建模，每个智能体可以在每步发送消息，奖励是状态、动作和消息的函数。

自由即时通信等价于集中化，因为所有智能体可以获得所有观测。当通信有延迟或成本时，智能体需要决定何时通信以及通信什么内容。

第五节：主要结论

5.1 理论结论

本章建立了多智能体协作决策制定的理论基础。Dec-POMDP能够统一表示三类不确定性：动作结果不确定性、传感器不确定性、以及其他智能体的不确定性。这使得研究者可以用统一的框架分析和比较不同问题设置。

计算复杂度分析表明，即使是有限视野的Dec-POMDP也是NEXP完全的，相比MDP的P完全和POMDP的PSPACE完全，问题复杂度显著增加。这一复杂度结果揭示了为什么近似方法在实际应用中如此重要。

5.2 算法结论

精确算法方面，动态规划、多智能体A和策略迭代三种方法各有特点：动态规划系统性地搜索策略空间但内存消耗大；A利用启发式引导搜索可能更高效；策略迭代适合无限视野问题但只能保证ε最优。

近似算法方面，MBDP通过限制内存使用实现了线性复杂度，JESP通过交替优化找到局部最优。这些算法虽然不能保证全局最优，但能在合理时间内产生可用的解决方案。

5.3 子类分析结论

通过分析Dec-MDP、ND-POMDP和MMDP等子类，可以理解问题结构对复杂度的影响：

  • MMDP完全可观测，P可解
  • Dec-MDP联合完全可观测但分布式执行，NEXP完全
  • 转移独立+观测独立+奖励独立可分解为n个独立MDP，P可解
  • 转移独立+观测独立但奖励依赖，NP完全

这些结果表明，适当的结构化假设可以显著降低问题难度。

第六节：挑战与开放问题

6.1 计算挑战

NEXP完全性带来的根本困难：精确求解Dec-POMDP在最坏情况下需要双指数时间。即使是小规模问题（如少量智能体、有限状态空间），算法也可能无法在合理时间内完成。这推动了近近领域对近似方法和特殊子类的大量研究。

广义belief空间的复杂性：在Dec-POMDP中，无法像POMDP那样维护一个充分的统计量（belief状态）来总结历史信息。广义belief空间包括状态和其他智能体策略的联合分布，但这个空间在计算上几乎是不可处理的。

无限视野问题的未决性：精确求解无限视野Dec-POMDP是不可判定的，因为可能需要无限大的控制器。现有方法只能产生ε最优解，收敛性保证有限但收敛速度可能很慢。

6.2 建模挑战

观测和通信的权衡：如何最佳地平衡显式通信和隐式通信（通过观测传递信息）是一个开放问题。通信有成本但能减少不确定性，如何在特定应用中找到最优权衡需要更多研究。

部分合作vs完全合作：本章主要关注完全合作设置（共享奖励函数），但许多实际场景涉及混合动机或竞争设置。如何扩展Dec-POMDP框架处理这类问题仍在探索中。

动态联盟和联盟形成：当智能体集合不是固定的时候，如智能体可以加入或离开团队，问题变得更加复杂。这类动态联盟场景需要新的建模和求解方法。

6.3 算法挑战

启发式设计的艺术：MAA*等搜索算法的效率高度依赖于启发式质量。设计既能有效引导搜索又容易计算的好启发式是一个持续的研究课题。

大规模问题的可扩展性：现实世界的应用可能涉及数十或数百个智能体，现有算法在这样的大规模问题上几乎完全失效。如何利用问题结构（如稀疏交互、层次化）来实现可扩展性是一个重要方向。

分布式在线执行：大多数现有方法假设离线规划、在线执行。但在一些应用场景中，需要在线规划和执行的集成，需要能够快速响应环境变化的算法。

6.4 开放研究方向

  • 深度强化学习方法在Dec-POMDP中的应用
  • 利用深度学习表示策略或价值函数的可能性
  • 通信协议设计和优化的自动化方法
  • 处理部分可观测环境中长期任务的学习方法
  • 安全关键应用中的鲁棒Dec-POMDP方法

第七节：个人反思与批判性分析

7.1 建模哲学的思考

本章采用的决策论方法（基于概率和优化）与工程实践中的其他方法（如规则基系统、进化算法）形成了鲜明对比。决策论方法的优点在于：理论基础坚实、可以推导理论保证、易于与其他方法比较。但其局限性也很明显：假设理性智能体、要求精确的概率模型、计算复杂度高。

在实际应用中，我倾向于认为Dec-POMDP更适合作为问题分析和算法设计的理论框架，而不是直接用于实时决策系统。例如，可以用Dec-POMDP分析问题结构、确定复杂度下界、设计基准算法，然后针对具体应用的特点开发更高效的专用方法。

7.2 简化假设的得失

Dec-POMDP模型做了许多简化假设：有限状态空间、有限动作空间、有限观测空间、马尔可夫动力学、共享奖励函数等。这些假设使得理论分析和算法设计成为可能，但也限制了模型对现实世界的适用性。

失去的东西：现实问题通常有连续状态空间（如位置、速度）、连续动作空间（如转向角、油门）、非马尔可夫效应（如历史依赖的传感器偏差）、多目标奖励等。将这些问题强行离散化会丢失重要信息或导致维度灾难。

获得的东西：在简化的框架下，我们可以清晰地看到问题结构如何影响复杂度，理解不同算法之间的关系，建立评估基准。这为开发更复杂但可能更实用的方法提供了基础。

7.3 对未来研究方向的看法

我认为以下几个方向最有潜力：

层次化方法：将大规模问题分解为多个层次，在高层做粗粒度规划，在低层做细粒度执行。这种方法可以追溯到元胞自动机和行为树的传统，在多智能体场景中很有前景。

通信作为规划的一部分：与其将通信视为外部约束，不如将其完全纳入规划框架。决定何时通信、通信什么、以及如何响应接收到的信息，是协作智能体的核心能力。

学习与规划的结合：人类和动物展现出惊人的协作能力，但并不是通过明确的决策论计算实现的。理解这些能力如何工作，可能为更高效算法的设计提供启示。强化学习方法，特别是多智能体强化学习，可能是实现这一目标的有效途径。

7.4 实践建议

对于希望在实践中应用这些方法的读者，我的建议是：

  1. 从MMDP或Dec-MDP开始：如果问题结构允许（如全可观测或联合全可观测），优先使用更简单的模型。只有当必要时才引入Dec-POMDP的完整复杂性。

  2. 利用问题结构：许多实际问题有特殊的结构（如稀疏交互、层次化、重复模式）。充分挖掘这些结构可以大幅降低复杂度。

  3. 使用近似和启发式：不要追求全局最优。好的启发式加局部搜索往往能在合理时间内产生足够好的解。

  4. 仿真验证：在将算法部署到真实系统之前，先在仿真环境中充分测试。注意仿真环境可能无法捕捉真实世界的所有复杂性。

7.5 对本书整体的评价

作为决策制定领域的重要著作，本书系统性地介绍了不确定条件下的决策理论。对于第七章而言，作者成功地平衡了理论深度和实用性，既提供了严格的数学分析，也讨论了实际算法的实现细节。

本章的一个特别优点是对复杂度分析和子类结构的详细讨论。通过理解问题复杂度如何随不同假设变化，读者可以更好地选择适合特定应用的方法。

然而，本章也存在一些不足：部分算法的描述过于简洁，对于希望实现的读者来说可能需要参考资料；一些重要的发展（如深度强化学习方法在Dec-POMDP中的应用）没有涉及，这些是活跃的研究领域。

公式汇总

编号 名称 形式 物理意义 类型
(7.1) 策略树评估方程 \(U(q,s) = R(a_q,s) + \sum_{s',o} P(s'\|a_q,s) P(o\|a_q,s') U(q_o,s')\) 有限视野下策略树的期望累积奖励 (T)
(7.2) 控制器评估方程 \(U(q,s) = \sum_{a} \prod_i P(a_i\|q_i) R(s,a) + \gamma \sum_{s',o,q'} P(s'\|a,s) O(o\|s',a) \prod_j P(q_j'\|q_j,a_j,o_j) U(q',s')\) 无限视野下有限状态控制器的期望累积折扣奖励 (T)
(7.3) 广义Belief状态值函数 \(U(p,b_G) = \sum_{q,s} b_G(s,q) U(p,q,s)\) 策略在广义belief状态下的期望值 (T)
(7.4) 转移独立性 \(T(s'\|s,a) = T_0(s_0'\|s_0) \prod_i T_i(s_i'\|s_i,a_i)\) 联合转移概率分解为本地转移的乘积 (T)
(7.5) 观测独立性 \(O(o\|s,a) = \prod_i O_i(o_i\|s_i,a_i)\) 联合观测概率分解为本地观测的乘积 (T)
(7.6) 奖励独立性 \(R(s,a) = f(R_1(s_1,a_1), ..., R_n(s_n,a_n))\) 联合奖励是本地奖励的单调非递减函数 (T)
(7.8) 加性奖励 \(R(s,a) = R_0(s_0) + \sum_i R_i(s_i,a_i)\) 奖励独立性的特例 (T)
(7.10)-(7.11) 剪枝线性规划 见正文 判断策略树是否被支配 (T)
(7.12) 部分策略评估 \(U(\{q^t, \Delta^{T-t}\}, s) = U(q^t, s) + U(\Delta^{T-t}\|q^t, s)\) 有限视野部分策略及其完成策略的值 (T)
(7.13) 启发式估计 \(\hat{U}(q^t, s) = U(q^t, s) + \hat{U}_{q^{T-t},s}^{T-t}\) 部分策略的启发式上界估计 (T)

注：(T)=理论推导，(E)=经验公式

参考文献

[1-63] 见原文第181-182页

本章笔记由科学阅读流程生成