第 11 章：多智能体规划在持续监视中的应用（Multiagent Planning for Persistent Surveillance）
11.1 Mission Description
本节交代持续监视任务的具体场景与三类挑战。任务由一组无人机构成，目的是在较长时间内对一片区域进行持续监视，例如对林区进行生物活动监测、对水灾区域追踪水位变化、或者对战区内的目标车辆进行搜索与跟踪。任务区被划分为三个区域：基地（base）、通信中继区（communication area）和监视区（surveillance area）。飞机从基地出发，根据任务需要分别前往中继区或监视区执行任务；随着燃油消耗或机载设备故障，飞机要返回基地进行加油或维修。通信中继区是基地与监视区之间的过渡区，必须有至少一架飞机在其中充当通信中继，保证基地与执行监视任务的飞机之间能维持上下行数据链路。监视区内分布着需要持续跟踪的目标车辆。
该任务的设计面临三方面挑战。其一是通信中继约束：在搜索救援、监控等典型应用中，操作员或地面自主规划系统需要持续向机群发送指令、回收机载传感器数据，因此基地与执行任务的飞机之间必须维持实时通信链路；当监视区远离基地时，必须通过中继区建立通信。其二是燃油约束：每架飞机所携油量有限，在中继区或监视区的可驻留时间有限；若在两区中任一区域耗尽燃油则飞机无法回收，而基地设有电池更换与充电站以补充能源。燃油的消耗率是随机的（以 \(\dot F_\text{burn}\) 为标称燃烧率，参数 \(P_\text{fuel}\) 控制以标称或加倍速率消耗的概率）。其三是系统健康约束：执行监视任务依赖传感器，移动能力依赖执行器，二者在任务过程中都可能意外失效。传感器失效时该机无法继续参与监视，但仍可充当通信中继；执行器损伤时机上任何任务都无法执行。基地可对传感器或执行器进行修复。
作者指出本章采取的方法是模型基强化学习（model-based reinforcement learning，参见 5.2 节）。规划器先以一个猜测的系统模型初始化，根据该模型在有限时域内生成策略并执行若干步，将观测结果送入模型学习模块更新模型，再重复上述过程。该方法的两个关键要求是：规划算法必须足够快以支持在线更新；与真实环境交互昂贵，因此算法必须数据高效。本章主要讨论的是支持持续监视任务规划需求的算法。
11.2 Centralized Problem Formulation
本节把持续监视问题建模为一个多智能体马尔可夫决策过程（MMDP，参见 7.3.3 节）。完整定义 MMDP 需要指定状态空间、动作空间、状态转移模型与回报函数四个要素，作者逐项给出。
11.2.1 State Space
全局状态空间 \(S\) 被分解为各智能体自身状态空间 \(S_i\) 的笛卡尔积：\(S = \times_i S_i\)。每个智能体 \(i\) 的状态由三个离散变量共同描述：当前位置 \(y_i\)、剩余油量 \(f_i\)、健康状态 \(h_i\)。位置变量 \(y_i\) 取自三值集合 \(Y = \{Y_B, Y_C, Y_S\}\)，分别对应基地、通信中继区与监视区。油量 \(f_i\) 离散化为 \(F = \{0, \Delta f, 2\Delta f, \ldots, F_\text{max} - \Delta f, F_\text{max}\}\)，其中 \(\Delta f\) 是适当的离散化步长。健康状态 \(h_i \in H = \{H_\text{nom}, H_\text{sns}, H_\text{act}\}\)，分别表示正常工作、传感器故障与执行器损伤。当团队中共有 \(n\) 架飞机时，全局状态空间的总规模为 \(|S| = (|Y| \times |F| \times |H|)^n\)，这一规模随 \(n\) 指数增长，导致用经典方法求解最优策略在智能体数量稍多时便变得不现实。
11.2.2 Action Space
每个智能体 \(i\) 在某时刻可选的动作 \(a_i\) 取决于其当前位置 \(y_i\) 与剩余油量 \(f_i\)。具体规则如下：若 \(y_i = Y_C\)，可选 \(\{A_B, A_R, A_S\}\) 三种动作；若 \(y_i = Y_S\)，可选 \(\{A_B, A_R\}\)；若 \(y_i = Y_B\)，可选 \(\{A_R, A_S\}\)；只要 \(f_i = 0\)，可执行的动作被限制为仅 \(\{A_R\}\)。其中 \(A_B\) 表示朝基地移动，\(A_R\) 表示原地保持，\(A_S\) 表示朝监视区移动。由于每个智能体的动作空间大小上限为 3，全局动作空间大小为 \(|A| = (|a_i|)^n = 3^n\)。
11.2.3 State Transition Model
智能体 \(i\) 在时刻 \(t\) 的位置更新规则由当前位置 \(y_i(t)\)、剩余油量 \(f_i(t)\) 与所选动作 \(a_i(t)\) 共同决定。具体地：若 \(f_i(t) = 0\) 或 \(a_i(t) = A_R\)，位置保持不变；若 \(y_i(t) = Y_C\) 且 \(a_i(t) = A_B\)（或 \(a_i(t) = A_S\)），则位置变为 \(Y_B\)（或 \(Y_S\)）；若 \(y_i(t) = Y_S\) 且 \(a_i(t) = A_B\)，则位置变为 \(Y_C\)；若 \(y_i(t) = Y_B\) 且 \(a_i(t) = A_S\)，则位置变为 \(Y_C\)。即基地与中继区之间、监视区与中继区之间可以通过主动选择动作实现直接转移，但基地与监视区之间不存在直接转移，需要经由中继区中转。
油量状态 \(f_i\) 的更新具有随机性：以概率 \(P_\text{fuel}\) 按标称燃烧率 \(\dot F_\text{burn}\) 消耗燃油，以概率 \(1 - P_\text{fuel}\) 按两倍标称率消耗燃油；当飞机位于基地时，油量以 \(\dot F_\text{refuel}\) 速率增加，直到达到 \(F_\text{max}\) 为止。
健康状态 \(h_i\) 的更新同样具有随机性：若油量为零，健康状态保持不变；若 \(y_i(k) = Y_B\)，下一时刻健康状态变为 \(H_\text{nom}\)（即只要回到基地就视作已修复）；若飞机不在基地且当前健康状态为 \(H_\text{nom}\)，下一时刻按概率分别取值——保持 \(H_\text{nom}\) 的概率为 \((1 - P_\text{sns})(1 - P_\text{act})\)，变为 \(H_\text{sns}\)（传感器故障）的概率为 \(P_\text{sns}(1 - P_\text{act})\)，变为 \(H_\text{act}\)（执行器损伤）的概率为 \(P_\text{act}\)。
11.2.4 Reward Function
回报函数的设计目标是同时保证监视区有最低数量的飞机驻留，并维持通信中继不中断。具体而言，假设监视区期望的飞机数量为 \(n_d\)，实际在监视区的飞机数量为 \(n_S\)，则每当 \(n_d > n_S\) 时立即施加 \(C_\text{gap} \times \max(n_d - n_S, 0)\) 的代价，其中 \(C_\text{gap}\) 是每缺一架飞机的小幅惩罚；若通信中继链路中断，则施加一个大幅惩罚 \(C_\text{fail}\)。这一回报结构把"有足够飞机在监视区"和"通信链路保持畅通"作为持续监视任务成功的两个硬性条件。
11.3 Decentralized Approximate Formulations
本节指出，11.2 节的 MMDP 完整描述了所有智能体之间的交互，理论上可以通过动态规划求出全局最优策略。但该方法的可扩展性较差：即便只有三个智能体，求解速度也明显偏慢。本节给出两种可扩展到大量智能体的近似问题形式化方案。两种方案均从单个智能体的视角出发，给定对其他智能体状态与动作的近似信息，计算去中心化的策略。
11.3.1 Factored Decomposition
该方法保留了集中式形式化中"将全局状态空间 \(S\) 分解为 \(\times_i S_i\)（\(S_i = Y \times F \times H\)）"的思想，但从智能体 \(i\) 的视角对其他智能体 \(j\) 的状态空间 \(S_j\)（\(j \ne i\)）做进一步压缩。\(S_j\) 被定义为与智能体 \(j\) 相关的"位置-方向"配对集合，共有六种有意义的配对：
其中 \((Y_B, A_R)\) 配对被刻意排除，因为留在基地通常是无意义的动作。\(S_i\) 的状态转移模型与集中式形式化完全相同。对于 \(S_j\)（\(j \ne i\)），从智能体 \(i\) 的视角看，智能体 \(j\) 的状态演化按以下方式近似：
- 若当前 \(s_{ij}(k) = (Y_B, A_S)\)，以 0.5 概率变为 \((Y_C, A_R)\)，以 0.5 概率变为 \((Y_C, A_S)\)；
- 若 \(s_{ij}(k) = (Y_C, A_B)\)，变为 \((Y_B, A_S)\)；
- 若 \(s_{ij}(k) = (Y_C, A_R)\)，仍为 \((Y_C, A_R)\)；
- 若 \(s_{ij}(k) = (Y_C, A_S)\)，变为 \((Y_S, A_R)\)；
- 若 \(s_{ij}(k) = (Y_S, A_B)\)，以 0.5 概率变为 \((Y_C, A_B)\)，以 0.5 概率变为 \((Y_C, A_R)\)；
- 若 \(s_{ij}(k) = (Y_S, A_R)\)，仍为 \((Y_S, A_R)\)。
这一近似的特点是去掉了对油量与健康状态的显式建模，仅保留位置-方向配对。即便如此，状态空间仍然随团队规模指数增长，但由于去除了"油量"和"健康"两维，状态数相对 \(|Y| \times |F| \times |H|\) 已经显著减少。
11.3.2 Group Aggregate Decomposition
另一种形式化方案不再单独跟踪其他智能体的位置与方向，而是把整个团队的行为用一个统一的、约简后的模型近似。具体的约简只保留三个聚合特征：是否至少有一名队友预测将位于通信中继区；预测在监视区的智能体数量；以及预测在监视区且处于健康状态的智能体数量。在该视角下，单个智能体 \(i\) 的状态空间大小为 \(|Y \times F \times H| \times 2^{n^2}\)，随团队规模仅以二次方式增长。为了预测下一时刻队友们的位置，方案使用一个单智能体策略 \(\pi^{(n=1)}\)；本章实验中 \(\pi^{(n=1)}\) 被设为无通信中继约束下集中式单智能体形式化的解。
聚合特征的回报函数可以直接从集中式形式化继承，但三个聚合特征的转移概率并不显然。一种可行做法是用 11.3.1 节的分解形式化运行一个含 5 个智能体的仿真任务，统计出对应的状态-转移表；当智能体数超过 5 时，再用双三次插值得到任意状态间的转移概率。
11.3.3 Planning
上述两种去中心化方法都是从单个智能体的视角出发构造 MDP，由于对应的 MDP 规模相对较小，原则上可以使用价值迭代等经典动态规划方法求解。价值函数与策略的输入都是去中心化状态 \(\bar s_i = \text{DecState}(s, a, i)\)，即由全局状态 \(s\)、所有智能体的联合动作 \(a\) 与智能体编号 \(i\) 计算得到；智能体 \(i\) 最终采取的动作是 \(a_i = \pi^*(\bar s_i)\)。需要注意的是，\(\bar s_i\) 的构造需要基于 \(\pi^{(n=1)}\) 对其他队友动作的预测，因此预测与实际之间存在偏差，性能会相应下降。
为缓解这种"状态-动作耦合"导致的偏差，作者提出一种顺序决策方案：每架飞机按固定顺序依次选择自身动作，前一架飞机的实际动作会被显式传递给下一架飞机作为其构造 \(\bar s_{i+1}\) 的输入，而不是让后者再去预测。最终一架飞机在已知团队其余飞机实际动作的前提下做出决策。这一方案的伪代码（Algorithm 11.1 OrderedSearch）以函数 \(v\) 指定一个固定顺序，\(v(i)\) 表示第 \(i\) 个做决策的智能体编号。
顺序 \(v\) 的选择会影响最终策略的质量，因此可以在每步同时尝试若干不同的顺序——这些顺序可由 \(n!\) 种排列中采样得到，再根据期望效用挑选最优顺序。Algorithm 11.2 SampledOrderedSearch 在一组 \(m\) 个顺序 \(v_{1:m}\) 之上做单步决策：每个顺序都通过 OrderedSearch 产生一组动作，模拟下一步状态与即时回报，再加上 \(U^*(\bar s_1)\) 后选最大。Algorithm 11.3 ForwardSampledOrderedSearch 把上述过程推广到深度 \(d\) 的前向搜索；本章实验中取 \(d = 2\)。
11.4 Model Learning
前面几节均假设动态已知。实际任务中，动态参数无法在任务开始前确定，必须在线学习。智能体需要从观测到的状态转移中估计与状态相关的传感器故障概率。然而由于规划空间庞大，对所有状态-动作对都估计并存储转移概率并不现实，必须做近似。本工作采用了一种增量特征依赖发现算法（incremental feature dependency discovery algorithm），该算法可以根据观测到的转移自动调整近似结构，免去人工编码固定近似结构的负担；算法细节见 Geramifard 等人的论文。将其应用于学习与状态相关的不确定性，参见 Ure 等人的工作。
先前工作曾在假设"传感器故障概率在状态空间上均匀"的前提下估计该概率。然而实际任务中，状态与传感器故障概率之间存在相关性，必须显式考虑。例如，在监视区执行跟踪任务时飞机可能执行更激进的机动，且所处环境更复杂、更具敌意，因此监视区的传感器故障概率可能高于通信中继区或基地；油量较低时功率预算更紧，也可能使传感器故障或被关闭的概率升高。
为评估把模型学习与不同规划算法结合的效果，作者做了 30 次仿真实验，每次仿真中交替进行 9 次"学习-规划"迭代：每轮学习更新后记录后续的累计代价，结果如图 11.1 所示（误差棒表示标准差）。结果显示随着经验积累学习算法带来的性能不断改善，分解式规划的性能可以保持在集中式规划性能的 5%–7% 以内；聚合规划性能在分解规划之上再损失 2%–3%，但计算开销显著降低。
11.5 Flight Test
持续监视任务在 MIT 航天控制实验室的 RAVEN 测试环境上完成。RAVEN 测试区配备 Vicon 动作捕捉系统以提供精确的位置与速度信息，飞行器上的姿态稳定回路结合机载陀螺与加速度计估计姿态。任务中由三架四旋翼作为执行任务的智能体；四旋翼以电池为动力，满电情况下可支持飞行 8 至 10 分钟。测试区内布设了三个自动换电站，以支撑长达数小时的任务。
飞行表现同时取决于规划器与不确定性学习两方面的表现。规划器性能应随着增量特征依赖发现降低不确定性而提升。本章飞行实验中，被学习的唯一不确定参数是传感器故障概率；为简化分析，假设该概率在所有状态下为常量 0.05，对应一个简单的状态无关不确定性模型。
实验结果（图 11.3）由三张子图组成：上方子图给出每架飞机在任务过程中累计的代价，曲线越低越好，斜率代表代价累积的速率；中间子图是上方子图的滤波分段导数，反映代价累积的快慢；下方子图给出某架飞机对传感器故障概率的估计。可以看出随着不确定性估计改善，代价累积的速率也逐步降低——这说明规划与学习算法之间存在所期望的协同关系，整个系统能够从经验中学习并提升整体性能。
整套自主飞行测试持续 3 小时，期间三个换电站共完成约 120 次自动电池更换。学习框架悲观地以全状态 30% 的传感器故障概率为初值；表 11.1 给出学习得到的状态相关传感器故障模型参数（基地区 0%，通信区高油量 0.067/低油量 0.132，监视区高油量 0.123/低油量 0.351）。每轮学习更新后都重新计算策略；图 11.4 显示每轮学习后更新策略对应的平均累计代价随时间下降；图 11.5 显示任务后半段的电池更换次数明显减少。
由于初值悲观，初始策略倾向于频繁把四旋翼召回基地维修，因而代价较高；随着学习给出更好的参数估计，规划算法对飞机在不发生故障前提下的持续运行能力更有信心，于是把飞机更高效地分配在基地与任务区之间。
11.6 Summary
本章给出了一套多智能体持续任务规划框架的实验验证。规划算法被形式化为近似团队动态的马尔可夫决策过程，求解这些 MDP 的去中心化策略；分解近似在显著降低计算量的同时只带来很小的性能损失。学习算法通过观察到的状态转移持续更新模型参数。整套方法在未知传感器故障动态的持续搜索与跟踪实验平台上得到了验证。
本章个人批注
本章是一个相当典型的"任务形式化—去中心化分解—在线学习—真实飞行验证"四段式应用研究案例。形式化部分把监视任务清晰地拆为位置、油量、健康三个离散维度，并显式建模了通信中继约束（reward 中的 \(C_\text{fail}\) 项），这种把"通信链路维持"作为硬性条件嵌入回报函数的设计是该类任务形式化的关键技巧之一。11.3 节给出的两种去中心化近似（factored 与 group aggregate）背后其实是在"近似精度 vs 状态空间规模"上做权衡——前者保位置-方向配对，状态数随团队规模仍指数增长但基数小很多；后者只保三个聚合特征，状态数随团队规模仅二次增长，但代价是放弃了显式的个体建模。我之前读过的 DEC-POMDP 文献里其实讨论过类似思路，但本章的特殊之处在于回报函数和状态结构与具体任务耦合得很紧，必须与位置-动作的物理可达性配合才能让近似合理。11.4 节的在线学习部分引用的 Geramifard 等人的增量特征依赖发现算法值得深入读一下，因为它不要求事先给定近似结构，这一点在传感器故障概率本身可能因状态而异的情况下尤其重要——11.5 节给出的飞行结果中监视区低油量状态对应 0.351 的故障率、而基地 0%，也直接说明状态相关性不可忽略。飞行测试只用了三架四旋翼，3 小时、约 120 次换电，这一规模其实对算法在更大机队下的可扩展性是个值得继续追问的问题。
与上下章的衔接（一段话）
第 10 章讨论的是把"机载防撞"建模为 POMDP 并离线优化数值表的过程；本章则把目光从单机决策扩展到多机协同，引入了 MMDP 框架与持续监视这一时间跨度更长的任务。下一章（第 12 章）将进一步讨论"自动化与人类协同"的主题——把本章展示的完全自主多机协同推到有人参与回路的场景，处理人在回路时的决策、信任与控制权交接等问题。章末参考文献中 Geramifard、Ure、Bethke 等人的工作在第 5 章（model uncertainty）的相关讨论中已有引用，使本章成为第 5 章技术（model-based RL）在多智能体任务上的直接落地。