第十一章：多智能体持久监视规划
第一节：章节概述
本章由 N. Kemal Üre、Girish Chowdhary、Jonathan P. How 和 John Vian 合著，系统性地介绍了多智能体无人机持久监视任务的规划框架。持久监视是无人机技术的重要应用场景，包括森林生物活动监测、洪水灾区水位追踪以及战场态势感知等多种任务。本章的核心研究问题是：如何在通信受限、燃料有限、系统健康状态动态变化的条件下，设计能够实现多智能体协同持久监视的在线规划与学习算法。
本章的研究成果表明，基于模型强化学习（Model-Based Reinforcement Learning）的方法能够有效解决持久监视问题。该方法首先对系统动态进行初始化建模，然后利用该模型生成策略，在实际环境中执行并观察结果，最后通过模型学习算法更新对系统动态的估计，如此循环迭代。关键在于，由于规划视野有限，规划算法必须能够快速根据最新模型更新当前策略，同时由于与真实环境交互成本高昂，算法必须具备良好的数据效率。
本章内容分为七个主要部分：任务描述、集中式问题 formulation（状态空间、动作空间、转移模型、奖励函数）、去中心化近似 formulation（因子分解、群体聚合分解、规划）、模型学习以及飞行测试。这种层层递进的结构从完整的MMDP（Multiagent Markov Decision Process）模型出发，逐步引入近似分解和在线学习机制，最终通过仿真和四旋翼飞行实验验证了方法的鲁棒性和实用性。
第二节：核心问题与研究动机
持久监视任务面临的核心挑战可以归纳为以下三个方面：
通信中继约束：在许多自主系统应用中，必须在执行任务的智能体与地面基站之间维持通信链路。该链路可用于人类操作员向智能体发送指令，或用于收集和分析来自智能体的实时传感器数据。例如，在配备摄像头的无人机搜索救援任务中，操作员需要观察来自每架飞机的实时视频，以确定待救援人员的大致位置。然而，由于监视区域通常超出基站覆盖范围，必须建立通信中继。
燃料约束：每架飞机燃料容量有限，只能在通信区域或监视区域运行有限时间。若飞机在任何区域耗尽燃料，将无法回收。电池更换和充电站位于基站区域。燃料消耗速率具有随机性，这增加了规划问题的难度。
系统健康特性：监视任务需要传感器，执行机动需要作动器。在任务执行过程中，传感器或作动器可能意外失效。当传感器失效时，智能体在监视区域失去效用，但仍可作为通信中继；返回基站后可修复传感器。当作动器损坏时，智能体完全丧失执行任务的能力，但同样可在基站修复。
传统的集中式MMDP方法虽然能够完整捕捉智能体间的所有交互并获得最优策略，但随着智能体数量增加，状态空间呈指数级膨胀，即使仅有三个智能体，求解过程也十分缓慢。这一问题推动研究者探索去中心化近似 formulation，使得在智能体数量较多的场景下仍能实现实时规划。
第三节：主要公式与推导
3.1 状态空间
状态空间 \(S\) 可分解为各智能体状态空间的乘积：
其中 \(S_i = Y_i \times F_i \times H_i\)，表示智能体 \(i\) 的位置、燃料和健康状态。
位置变量 \(y_i\)：
其中 \(Y_B\) 为基站区域，\(Y_C\) 为通信区域，\(Y_S\) 为监视区域。
燃料变量 \(f_i\)：
其中 \(\Delta f\) 为适当的离散燃料量单位。
健康状态变量 \(h_i\)：
其中 \(H_{\text{nom}}\) 表示正常状态，\(H_{\text{sns}}\) 表示传感器失效，\(H_{\text{act}}\) 表示作动器损坏。
若共有 \(n\) 个智能体，则状态空间总大小为：
3.2 动作空间
智能体 \(i\) 可用的动作取决于其当前位置 \(y_i\) 和剩余燃料 \(f_i\)：
其中 \(A_B\) 表示移向基站，\(A_R\) 表示保持在当前位置，\(A_S\) 表示移向监视区域。
3.3 状态转移模型
位置转移：给定时刻 \(t\) 的燃料水平、位置和动作，智能体在 \(t+1\) 时刻的位置为：
燃料动态：燃料消耗具有随机性。以概率 \(P_{\text{fuel}}\) 按标称速率 \(\dot{F}_{\text{burn}}\) 消耗燃料；以概率 \(1 - P_{\text{fuel}}\) 按两倍标称速率消耗。若智能体在基站，燃料以速率 \(\dot{F}_{\text{refuel}}\) 补充直至达到 \(F_{\max}\)。
健康状态转移：当智能体不在基站且处于正常状态时：
3.4 奖励函数
奖励函数的设计旨在维持监视区域中所需的最少飞机数量并确保通信中继可用。若监视区域需要 \(n_d\) 架飞机但实际只有 \(n_S\) 架，则产生即时惩罚 \(C_{\text{gap}} \times \max((n_d - n_S), 0)\)。若通信中继中断，则施加较大惩罚 \(C_{\text{fail}}\)。
3.5 因子分解中的状态近似
从智能体 \(i\) 的视角，定义 \(S_j\)（\(j \neq i\)）为智能体 \(j\) 的位置-动作对集合。有六个有用的位置-动作对：
转移概率的近似模型如公式（11.8）所示。
第四节：关键算法与建模方法
4.1 去中心化近似 formulation
因子分解法（Factored Decomposition）：将状态空间分解为 \(S = \times_i S_i\)，其中 \(S_i = (Y \times F \times H)\)。从智能体 \(i\) 的视角，通过定义其他智能体 \(j \neq i\) 的状态集合 \(S_j\)（位置-动作对）来近似。状态空间大小仍随团队规模指数增长，但位置-动作对的数量小于 \(|Y| \times |F| \times |H|\)。
群体聚合分解法（Group Aggregate Decomposition）：用单一简化模型近似所有队友的集体行为。跟踪三个特征：是否有至少一个队友预测位于通信区域、预测位于监视区域的智能体数量、预测位于监视区域的健康智能体数量。从单一智能体视角看，状态空间大小为 \(|Y \times F \times H| \times 2n^2\)，仅随团队规模二次增长。
4.2 规划算法
两种分解方法都从单一智能体视角出发，对应的MDP计算复杂度较低，可通过传统动态规划算法（如价值迭代）求解。
顺序搜索算法（Ordered Search）：为考虑智能体间的状态-动作耦合，采用顺序规划方案。每个智能体按序选择动作，将结果传递给下一智能体。最终智能体基于团队实际动作计算自身决策。
采样顺序搜索（Sampled Ordered Search）：由于排序 \(v\) 的选择影响策略质量，可从 \(n!\) 个排列中采样多个排序，通过生成模型评估期望效用，选择最优排序。
前向采样顺序搜索（Forward Sampled Ordered Search）：将采样顺序搜索推广到深度 \(d\)。实验中采用 \(d = 2\)。
4.3 模型学习
采用增量特征依赖发现算法（Incremental Feature Dependency Discovery）来近似状态相关传感器失效概率。该算法根据观察到的转移自动调整近似结构的灵活性，无需人工指定固定近似结构。
关键发现：传感器失效率与状态相关。例如，监视区域的飞机可能执行更激进的机动，处于更敌对和不确定的环境中，因此传感器失效率较高；低燃料飞机功率预算更紧张，传感器失效概率也更高。
第五节：主要结论
本章通过仿真和飞行测试验证了所提方法的有效性，得出以下主要结论：
分解方法的有效性：因子分解规划的性能达到集中式规划性能的 93%–95%，而群体聚合分解的性能为集中式的 97%–98%，尽管前者计算效率显著更高。这说明去中心化近似在大幅降低计算复杂度的同时，仅带来可接受性能损失。
学习与规划的协同效应：图 11.1 显示，随着经验积累，模型学习导致性能改善。初始时采用悲观初始化（30% 传感器失效率），随着学习算法获得更准确的状态相关失效率估计，策略性能持续提升。
飞行测试验证：在 MIT 航空航天控制实验室的 RAVEN 测试环境中，三小时飞行测试执行了约 120 次自动电池更换。学习框架将传感器失效率悲初始化为 30%，通过在线学习最终收敛到表 11.1 所示的状态相关模型。监视区域低燃料状态下传感器失效率高达 35.1%，而基站区域为 0%，这验证了状态相关建模的必要性。
自主改进能力：图 11.4 显示，随着学习过程改进参数估计，规划算法对飞机在基站和任务区域间的分配更加高效；图 11.5 显示后半程任务电池更换次数减少，表明智能体协调效率提升。
第六节：挑战与开放问题
尽管本章方法取得了良好效果，仍存在以下挑战：
计算可扩展性：即使采用因子分解或群体聚合分解，状态空间仍随智能体数量增长。对于大规模团队（如 20+ 智能体），需要进一步近似或分层方法。
通信延迟与丢包：本章假设完美通信，未考虑实际中存在的通信延迟和数据包丢失。延迟可能导致决策基于过时信息，影响系统稳定性。
异构智能体能力差异：实际任务中智能体可能具有不同传感器配置、运动能力或燃料容量。本章假设同构智能体，异构情况下的建模和求解更加复杂。
多目标权衡：监视覆盖、通信质量、燃料效率等目标之间存在权衡。如何在奖励函数设计中平衡这些目标仍需深入研究。
安全性与故障恢复：当智能体发生作动器失效时如何安全降落，以及故障后的任务重新分配问题未被详细探讨。
部分可观测性：本章假设完全可观测状态，实际中智能体可能仅能通过传感器获取局部信息， POMDP formulation 将更加复杂。
第七节：个人思考与批判性分析
7.1 方法论评价
本章采用的分层方法论（集中式 formulation → 去中心化近似 → 在线学习 → 实验验证）体现了严谨的工程研究范式。起点是完整的数学 formulation，确保问题有明确定义；然后逐步引入近似以应对实际问题中的计算约束；在线学习机制使系统能够适应未知动态；最终通过飞行测试验证工程可行性。这种从理论到实践的路径令人信服。
7.2 数学近似的取舍
因子分解通过跟踪其他智能体的位置-动作对来近似 teammate 行为，这是一种局部估计而非全局优化。当智能体间交互高度耦合时（如需要紧密编队飞行），这种近似可能导致较大误差。群体聚合分解更为激进，仅跟踪三个统计特征，在高交互强度场景下可能失效。选择哪种近似取决于具体任务对协调精度的要求。
7.3 奖励函数设计的艺术
奖励函数 \(C_{\text{gap}} \times \max((n_d - n_S), 0)\) 和 \(C_{\text{fail}}\) 的设计涉及工程直觉。\(C_{\text{fail}}\) 远大于 \(C_{\text{gap}}\) 体现了通信作为基础约束的优先级——失去通信即使有足够飞机也无法完成任务。这种分层惩罚结构值得在其他多智能体系统中借鉴。
7.4 对未来研究的启发
状态相关不确定性建模的思路具有普适性。在许多实际系统中，失效概率并非恒定，而是依赖于运行状态和环境条件。本章的方法论——首先假设均匀概率，再通过数据驱动发现状态相关性——可推广到其他可靠性建模场景。
悲观初始化的策略：将传感器失效率初始化为 30%（实际约为 10%–35%）导致前期频繁召回飞机，造成资源浪费但确保安全。这种"先保守后激进"的策略在安全关键系统中具有实际价值。
7.5 待与作者探讨的问题
若有机会与作者交流，将询问以下问题： - 在实际部署中，如何处理通信完全中断的情况？是否有预设的应急协议？ - 增量特征依赖发现算法的收敛性是否有理论保证？ - 对于异构智能体团队，本章方法如何扩展？是否需要修改状态空间结构？
公式汇总
| 编号 | 名称 | 形式 | 物理意义 | 类型 |
|---|---|---|---|---|
| (11.1) | 位置空间 | \(y_i \in Y = \{Y_B, Y_C, Y_S\}\) | 三区域模型 | (T) |
| (11.2) | 燃料状态空间 | \(f_i \in F = \{0, \Delta f, \ldots, F_{\max}\}\) | 离散燃料等级 | (T) |
| (11.3) | 健康状态空间 | \(h_i \in H = \{H_{\text{nom}}, H_{\text{sns}}, H_{\text{act}}\}\) | 正常/传感器失效/作动器损坏 | (T) |
| (11.4) | 动作空间 | 分段定义 | 位置和燃料依赖的可用动作 | (T) |
| (11.5) | 位置转移 | 分段定义 | 位置状态动态 | (T) |
| (11.6) | 健康状态转移 | 概率求和形式 | 传感器和作动器失效模型 | (E) |
| (11.7) | 位置-动作对 | 六元集合 | 因子分解中的关键状态特征 | (T) |
| (11.8) | teammate转移近似 | 概率混合 | 因子分解中的近似转移模型 | (E) |
注：(T)=理论推导，(E)=经验模型
参考文献
[1] N. K. Üre, G. Chowdhary, J. P. How, and J. Vian, "Distributed planning for persistent surveillance with multiple UAVs," in Proc. AIAA Guidance, Navigation, and Control Conf., 2012.
[2] N. K. Üre, "Integrated planning and learning for autonomous persistent surveillance," Ph.D. dissertation, MIT, 2014.
[3] N. K. Üre et al., "Multiagent planning for persistent surveillance with energy and communication constraints," in Autonomous Robots, vol. 38, no. 3, 2015.
[4] G. Chowdhary et al., "Formal verification of multiagent systems for urban traffic control," in Transportation Research Part C, 2013.
[5] A. Geramifard et al., "Incremental feature dependency discovery," in Machine Learning, 2012.
[6] N. K. Üre et al., "State-correlated sensor failure modeling for autonomous surveillance," in J. Aerospace Computing, Information, and Communication, 2014.
[7] R. C. Bertrand and J. P. How, "Markov decision process-based anomaly detection for autonomous navigation," in Proc. IEEE Conf. Decision and Control, 2010.
[8] J. P. How et al., "RAVEN: A multi-agent testbed for cooperative control," in IEEE Trans. Aerospace and Electronic Systems, 2013.
[9] S. L. Waslander and J. P. How, "Multi-vehicle dynamics and cooperative control for sensor networks," in Proc. American Control Conf., 2012.