基于博弈学习的分布式卫星任务规划

基于博弈学习的分布式卫星任务规划

Distributed Satellite Mission Planning via Learning in Games

摘要 对地观测卫星群的任务规划是一个复杂的问题，它提出了重大的理论和技术挑战，尤其是在分布式环境中。为了实现仅依赖于局部信息的高效合作，我们将每个卫星视为一个理性参与者，将问题转化为一个网络化的势博弈，并提出了一种分布式协调和优化算法。通过每个玩家与邻居交互，并按照受限贪婪和基于记忆的规则调整局部规划，证明了稳定的纳什均衡以概率1出现。此外，随机性随着更长的存储器的引入而增加，这也可以保证精确的纳什均衡，这对应于单个卫星之间的更紧密合作和更好的系统级性能。将实验与典型的集中式和分布式方法进行比较，突出了所提出方法的优势。

1. 引言

  随着微机电系统使用的增加和可靠性的提高，航天工业正在经历一个新的范式转变，从单个大型卫星转变为多个较小的个体，作为分布式系统协同工作^[1]。一个典型的例子是地球观测星座，它包括一组卫星，它们位于不同的轨道上，用于收集地面信息^[2]。这种配置有助于更大的表面覆盖率、更高的重新访问频率和更好的系统鲁棒性^[3]。然而，与此同时，出现了一系列新的挑战，其核心是如何协调大量异构卫星的任务计划。
  尽管文献中研究了许多集中式方法，但由于以下限制，分布式卫星任务规划中并未考虑这些方法。首先，尽管诸如动态编程^[4]之类的精确方法保证了最优解，但执行在计算时间上极其昂贵，并且需要较大的内存空间。虽然有一些近似的方法可以在一定程度上克服这些缺点，例如模拟退火^[5]和遗传算法^[6]，但它们不能处理在线异步生成任务请求的动态情况。事实上，每当任务要求在集中规划期间发生变化时，该过程必须完全恢复。最后，由于维护和运行成本高，未来的空间任务旨在尽可能减少地面站的使用，这限制了我们从全局角度进行集中规划。因此，迫切需要使用自适应和自组织机制的新方法，通过这种方法，当每个个体仅依靠本地信息自主和动态地行动时，可以实现系统级合作。
  幸运的是这些问题可以通过博弈论完美解决。博弈论是理性决策者之间冲突与合作的研究^[7]，^[8]。与传统的分布式方法（如合同网协议^[9]）相比，博弈论有其特殊的优势。由于在交互框架和协调规则之间提供了分层分解，因此可以应用博弈中的许多学习技术。更重要的是，令人满意的集体行为将出现，即最著名的纳什均衡概念^[10]。此外，通过利用势博弈，精心制定的学习规则也可以保证收敛到与接近最优系统级性能相关的精炼纳什均衡 {refined Nash equilibrium}，而不是任意均衡点^[11]。
  在过去几年中，在多智能体系统（包括无人机（UAV）集群和传感器网络^[12]，^[13]）的分布式协调和优化中，已经见证了博弈学习的大量应用。例如，Li等人研究了一种博弈论方法，用于多无人机协同搜索和监视^[14]。Yang等人使用雪堆博弈解决了分布式网络系统中的最小顶点覆盖问题，并提供了一种分布式优化方法^[15]。奇怪的是，很少有研究将分布式卫星与博弈中非常相关的学习分支明确联系起来。在本文中，我们将重点放在分布式卫星任务规划上，将星座中的每个卫星视为一个理性的博弈者，并将问题转化为一个网络化的势博弈。为了实现不依赖全局信息的高效协调，我们提出了一种受限贪婪和基于记忆的学习算法，该算法保证收敛到精炼纳什均衡，这意味着降低了运营成本，具有更高的全局性能。据作者所知，这是第一篇通过在博弈中学习来解决分布式卫星任务规划问题并保证接近最佳系统级性能的论文。
  论文组织如下。第二节描述了问题的形成和博弈模型。在第三节中，我们通过博弈学习开发了分布式任务规划算法（DMPA），并对其收敛性进行了理论分析。第四节介绍了DMPA的评估及其与典型算法的比较。最后一节提供了一些结论性意见，并简要介绍了未来的工作。

2. 问题描述

本节展示了分布式卫星任务规划并在势博弈的帮助下建立博弈论模型。

2.A 分布式卫星任务规划

  考虑一个包含卫星集合 S = { s 1 , s 2 , ⋯   , s n } S=\{s_1,s_2,\cdots,s_n\} S={s1​,s2​,⋯,sn​} 的地球观测系统，每个卫星的参数集包括：环绕轨道 O i O_i Oi​、观测集合 C T i CT_i CTi​（例如光学雷达）、探测范围 S R i SR_i SRi​、存储容量 S C i SC_i SCi​ 和两个相邻任务的最短时间间隔 I T i IT_i ITi​，即 s i = { O i , C T i , S R i , S C i , I T i } s_i=\{O_i,CT_i,SR_i,SC_i,IT_i\} si​={Oi​,CTi​,SRi​,SCi​,ITi​}。将客户端请求按时间排序为 R = { r 1 , r 2 , ⋯   , r m } R=\{r_1,r_2,\cdots,r_m\} R={r1​,r2​,⋯,rm​}。每一个任务 r j r_j rj​ 与一个观测集合 C T j CT_j CTj​、一个网格区域 M j M_j Mj​、和一个优先权重 w j w_j wj​ 相关联。令 A i f r ∈ R A_i^{fr}\in R Aifr​∈R 表示处于 s i s_i si​ 的能视域（field of regard, FOR）内的任务集合，其任务规划空间定义为 A i f r ∈ R A_i^{fr}\in R Aifr​∈R 的子集，即 A i = { a i ∣ a i ∈ A i f r } A_i=\{a_i|a_i\in A_i^{fr}\} Ai​={ai​∣ai​∈Aifr​}，其中 a i = { r i 1 , r i 2 , ⋯   , r i n i } a_i=\{r_{i1},r_{i2},\cdots,r_{in_i}\} ai​={ri1​,ri2​,⋯,rini​​}， r i j ∈ A i f r r_{ij}\in A_i^{fr} rij​∈Aifr​， n i n_i ni​ 表示任务数量。假设当 k > j k>j k>j 时 i k > i j i_k>i_j ik​>ij​，也就是说，每个任务应该根据 R R R上的顺序执行。对于分布式协调，假设任意两个卫星仅当可以观测同一个 M j M_j Mj​ 时可以通过星际链路交换信息。在这种情况下， s i s_i si​ 的邻居定义为 Ω i = { s j ∣ A i f r ⋂ A j f r ≠ ∅ } \Omega_i=\{s_j|A_i^{fr}\bigcap A_j^{fr}\neq\varnothing\} Ωi​={sj​∣Aifr​⋂Ajfr​=∅}，其中 s i ∉ Ω i s_i\notin\Omega_i si​∈/Ωi​。
  一般地， s i s_i si​ 观测 r j r_j rj​ 中的网格的代价为 c i ( r j ) c_i(r_j) ci​(rj​)。进一步地，考虑 s i s_i si​ 绕目标网格旋转的能量消耗，与 r j r_j rj​ 关联的全局代价通常受前一次观测的影响。因此，全局操作代价 f i f_i fi​ 与一个任务规划 a i a_i ai​ 相关，通过将观测代价 O C i OC_i OCi​ 与侧摆代价 R C i RC_i RCi​ 相结合来计算
f i ( a i ) = O C i ( a i ) + S C i ( a i ) = ∑ j = 1 n i c i ( r j ) + ∑ j = 1 n i λ i ∣ θ i j − θ i , j − 1 ∣ ( 1 ) \begin{aligned} f_i(a_i) =& OC_i(a_i)+SC_i(a_i) \\ =& \sum_{j=1}^{n_i}c_i(r_j) +\sum_{j=1}^{n_i}\lambda_i|\theta_{ij}-\theta_{i,j-1}| \qquad(1) \end{aligned} fi​(ai​)==​OCi​(ai​)+SCi​(ai​)j=1∑ni​​ci​(rj​)+j=1∑ni​​λi​∣θij​−θi,j−1​∣(1)​
其中 θ i j \theta_{ij} θij​ 为 s i s_i si​ 执行任务 r j r_j rj​ 时的目标侧摆角， λ i \lambda_i λi​ 表示侧摆代价因子。对每个卫星 s i s_i si​，假设初始侧摆角为 θ i 0 = 0 \theta_{i0}=0 θi0​=0。
  系统规划定义为 a = { a 1 , a 2 , ⋯   , a n } a=\{a_1,a_2,\cdots,a_n\} a={a1​,a2​,⋯,an​}。地球观测卫星的分布式任务规划需要找到最优规划 a ∗ a^* a∗，使得能够以最小的代价完成尽可能多的任务，也就是在观测集合匹配、存储容量限制和最短间隔的硬约束下^[3]，最小化下面的全局目标函数
F ( a ) = ∑ i = 1 n f i ( a i ) + ∑ j = 1 m [ 1 − b j ( a ) ] ω j ( 2 ) F(a)=\sum_{i=1}^nf_i(a_i) + \sum_{j=1}^m[1-b_j(a)]\omega_j \qquad(2) F(a)=i=1∑n​fi​(ai​)+j=1∑m​[1−bj​(a)]ωj​(2)
值得一提的是 F F F 的第二部分用于施加对任务 r j r_j rj​ 无响应的惩罚项。特别地， b j = 0 b_j=0 bj​=0 指任务 r j r_j rj​ 没有被包含在任何卫星的任务规划中， b j = 1 b_j=1 bj​=1 指包含。

2.B 博弈模型

  对于卫星间高效的系统级协调，考虑一个网络化博弈 G = ( N , { A i } , { U i } ) G=(N,\{A_i\},\{U_i\}) G=(N,{Ai​},{Ui​})，其中 N = S N=S N=S 表示玩家集合。每个卫星看作一个有限理性玩家，其试图从 a i a_i ai​ 中选择行为并与其邻居交换信息来最大化其收益函数 U i : A → R U_i:A\rightarrow\mathbb{R} Ui​:A→R，其中 A = ∏ i ∈ N A i A=\prod_{i\in N}A_i A=∏i∈N​Ai​ 表示系统联合行为集合。将除了 s i s_i si​ 以外的行为曲线简记作 a − i = ( a 1 , ⋯   , a i − 1 , a i + 1 , ⋯   , a n ) a_{-i}=(a_1,\cdots,a_{i-1},a_{i+1},\cdots,a_n) a−i​=(a1​,⋯,ai−1​,ai+1​,⋯,an​)。
  纳什均衡的概念、共识{Convention}和势博弈在分布式系统的博弈论的协调和优化方面扮演了重要角色。下列定义使其更清晰。
定义1（纳什均衡^[7]）对一个博弈 G = ( N , { A i } , { U i } ) G=(N,\{A_i\},\{U_i\}) G=(N,{Ai​},{Ui​})，如果每个玩家 i ∈ N i\in N i∈N 的行为集 a ∗ ∈ A a^*\in A a∗∈A 满足
U i ( a i ∗ , a − i ∗ ) = max ⁡ a i ∈ A i U i ( a i , a − i ∗ ) U_{i}(a_{i}^{*}, a_{-i}^{*})=\max _{a_{i} \in A_{i}} U_{i}(a_{i}, a_{-i}^{*}) Ui​(ai∗​,a−i∗​)=ai​∈Ai​max​Ui​(ai​,a−i∗​)
则 a ∗ a^* a∗ 就是一个纳什均衡。
定义2（共识{Convention}^[16]）将行为集序列从 t + 1 − m t+1-m t+1−m 到 t t t 的迭代记作 h m t = ( a t + 1 − m ， a t + 2 − m ， a t + 1 − m , ⋯   , a t ) h_m^t=(a^{t+1-m}，a^{t+2-m}，a^{t+1-m},\cdots,a^t) hmt​=(at+1−m，at+2−m，at+1−m,⋯,at)。如果每个元素都是相同的纳什均衡 a N E ∈ Φ N E a_{NE}\in\Phi_{NE} aNE​∈ΦNE​，那么 h m ∗ = ( a N E , a N E , ⋯   , a N E ) h_m^*=(a_{NE},a_{NE},\cdots,a_{NE}) hm∗​=(aNE​,aNE​,⋯,aNE​) 称作一个共识。
定义3（势博弈^[11]）一个策略博弈 G = ( N , { A i } , { U i } ) G=(N,\{A_i\},\{U_i\}) G=(N,{Ai​},{Ui​}) 称作一个（严格）势博弈，当存在势函数 ϕ : A → R \phi:A\rightarrow\mathbb{R} ϕ:A→R 使得
U i ( a i ′ , a − i ) − U i ( a i , a − i ) = ϕ ( a i ′ , a − i ) − ϕ ( a i , a − i ) U_{i}(a_{i}^{\prime}, a_{-i})-U_{i}(a_{i}, a_{-i})=\phi(a_{i}^{\prime}, a_{-i})-\phi(a_{i}, a_{-i}) Ui​(ai′​,a−i​)−Ui​(ai​,a−i​)=ϕ(ai′​,a−i​)−ϕ(ai​,a−i​)
对任意 i ∈ N i\in N i∈N， a ∈ A a\in A a∈A，行为 a i ′ ∈ A i a_i'\in A_i ai′​∈Ai​。
  通过上面的定义，我们建立了下面的分布式任务规划博弈模型。
定理1 对任务规划博弈 G = ( N , { A i } , { U i } ) G=(N,\{A_i\},\{U_i\}) G=(N,{Ai​},{Ui​})，下面的势函数 ϕ ( a ) \phi(a) ϕ(a) 和局部收益 U i ( a ) U_i(a) Ui​(a) 定义了一个势博弈
ϕ ( a ) = − F ( a ) \phi(a)=-F(a) ϕ(a)=−F(a)
证明: 。。。。。。证毕。
  由于 ϕ ( a ) \phi(a) ϕ(a) 的最大化值一定是一个纳什均衡点，对多卫星的任务规划问题可通过分布式学习求出精炼纳什均衡点来近似解决。

3. 算法设计和分析

本节通过博弈学习研究DMPA，遵循限制贪婪和有限存储，且通过共识的目标展示其收敛性。

3.A 分布式任务规划算法

  通过引入随机性，我们假设一个长度为 l l l 的有限长度存储器，每个玩家 s i s_i si​ 通过 M i t = ( v 1 , v 2 , ⋯   , v l ) , v j ∈ A i M_i^t=(v_1,v_2,\cdots,v_l),v_j\in A_i Mit​=(v1​,v2​,⋯,vl​),vj​∈Ai​ 定义，它们在初始化时随机生成。当收到一个请求集合 R R R 时，每个玩家计算它的 a i f r a_i^{fr} aifr​ 值来获得行为空间 A i A_i Ai​，并选择一个随机行为 a i t = 1 ∈ A i a_i^{t=1}\in A_i ait=1​∈Ai​ 来开始DMPA。主要的学习过程遵循一个同步行为。对每一个时间步长 t t t，所有的玩家与它们的邻居交换信息并根据式(5)来计算当前收益 U i ( t ) U_i(t) Ui​(t)，以及最佳响应 B R i t BR_i^t BRit​ 和遗忘值 R i t R_i^t Rit​：
B R i t = R i t = \begin{aligned} &BR_i^t= \\ &R_i^t= \end{aligned} ​BRit​=Rit​=​
将 R i t ∗ R_i^{t*} Rit∗​ 定义为邻居 Ω i \Omega_i Ωi​ 中的最大遗忘值， j ∗ = min ⁡ ( arg ⁡ max ⁡ j ∈ Ω i R j t ) j^*=\min(\arg\max_{j\in\Omega_i}R_j^t) j∗=min(argmaxj∈Ωi​​Rjt​) 定义为ID号。仅当(1) s i s_i si​ 有邻居中的严格最大遗忘值或(2) s i s_i si​ 有最大正遗忘值但有相同值的邻居有最大的ID号，限制贪婪行为 a i r a_i^r air​ 与 B R i t BR_i^t BRit​ 相等。否则， a i r = a i t a_i^r=a_i^t air​=ait​。与纯贪婪规则相反，一个DMPA中的玩家采取限制贪婪规则和有限存储。首先， s i s_i si​ 抛弃 M I t M_I^t MIt​ 中的最早元素并记录 a i r a_i^r air​ 来得到 M i t + 1 M_i^{t+1} Mit+1​。接下来，一个第 a i t + 1 a_i^{t+1} ait+1​ 代的 M i t + 1 M_i^{t+1} Mit+1​ 中的随机行为被选中。这一程序继续下去直到一个共识出现。

3.B 收敛性分析

根据共识的概念，我们展示了收敛性的理论分析。
定理2(收敛性) 对于式(2)中给出的多卫星分布式任务规划问题，DMPA一定会从任意初始任务计划收敛到一个共识。
证明:
  证明由接下来的两步展开。首先，我们证明任意初始任务计划都能实现纳什均衡集合。注意从 a t a^t at 到 a t + 1 a^{t+1} at+1 的协调过程{coordination process}。当 l = 1 l=1 l=1 时，将限制贪婪行为 a i r a_i^r air​ 选为 a t + 1 a^{t+1} at+1，在任意邻居中，只有一个个体更新到最佳响应 B R i t BR_i^t BRit​，其余的都保持当前行为，这导致了每个时间步长中 ϕ ( a ) \phi(a) ϕ(a) 的单调增加，因为
ϕ ( a t + 1 ) − ϕ ( a t ) = ∑ i : a i r ≠ a i t { U i [ a i r − a Ω i t ] − U i [ a i t − a Ω i t ] } ≥ 0 \phi(a^{t+1})-\phi(a^t) = \sum_{i:a_i^r\neq a_i^t} \{U_i[a_i^r-a_{\Omega_i}^t]-U_i[a_i^t-a_{\Omega_i}^t]\} \geq 0 ϕ(at+1)−ϕ(at)=i:air​=ait​∑​{Ui​[air​−aΩi​t​]−Ui​[ait​−aΩi​t​]}≥0
由于 ϕ ( a ) \phi(a) ϕ(a) 有上界，DMPA会收敛到纳什均衡。尽管当 l > 1 l>1 l>1 时并不能保证 ϕ ( a ) \phi(a) ϕ(a) 的单调增加，但仍然存在一个 a i r a_i^r air​ 全部被选为 a t + 1 a^{t+1} at+1 的正概率。因此，也存在一个 ϕ ( a ) \phi(a) ϕ(a) 持续增加到纳什均衡的正概率。由于我们考虑一个无限学习的过程，任意的初始任务规划一定可以达到纳什均衡。
  现在我们证明DMPA中的任意纳什均衡都可以通过关注一个构成纳什均衡 a N E a_{NE} aNE​ 的行为集合 a t a^t at 收敛到一个共识。。。。。。证毕。
  尽管保证了共识的收敛性，但解的效率依赖于 l l l。当 l = 1 l=1 l=1 时，DMPA退化至一个确定的过程，其中 ϕ ( a ) \phi(a) ϕ(a) 单调增加并并快速到达第一个纳什均衡点，该均衡点完全依赖于初始行为解集。因为一个势博弈中不止存在一个纳什均衡点，符合要求的系统级性能不一定能完全满足。相对地，当 l > 1 l>1 l>1 时DMPA变成了一个完全的随机过程，打开了一个巨大的协调空间并使得精炼纳什均衡以更高的概率出现。

4. 仿真和结果比较

  为了评估DMPA在分布式卫星任务规划的效果和与现有算法相比的优势，本节使用由 n = 5 n=5 n=5 个在不同轨道上工作的一个卫星星座展示了数值仿真结果。对地面观测来说，每个卫星载有一个光学相机，侧摆角为 ± 2 5 ∘ \pm25^\circ ±25∘，侧摆代价效率 λ i = 10 \lambda_i=10 λi​=10。假设存在一个客户端需求集合，包含了 m = 10 m=10 m=10 个待观测的独立网格区，其中观测代价和目标侧摆角分别由矩阵 C C C 和 Θ \Theta Θ 给定。例如， c 26 = 74 c_{26}=74 c26​=74 和 θ 26 = 15 \theta_{26}=15 θ26​=15 分别表示卫星 s 2 s_2 s2​ 观测第 6 6 6 个网格需要代价 74 74 74 并侧摆 1 5 ∘ 15^\circ 15∘， c 43 = ∞ c_{43}=\infty c43​=∞ 和 θ 43 = ∞ \theta_{43}=\infty θ43​=∞ 表示第 3 3 3 个网格在卫星 s 4 s_4 s4​ 的能视域以外。
  另外可以很容易地验证 s i s_i si​ 执行 r j r_j rj​ 的全局操作代价 O i j O_{ij} Oij​ 也依赖于任务序列 a i a_i ai​ 中之前的任务。当 s 2 s_2 s2​ 在 r 1 r_1 r1​ 之后执行 r 5 r_5 r5​ 时， O 25 = c 25 + λ 2 ∣ θ 21 − θ 25 ∣ = 203 O_{25}=c_{25}+\lambda_2|\theta_{21}-\theta_{25}|=203 O25​=c25​+λ2​∣θ21​−θ25​∣=203，当在 r 2 r_2 r2​ 之后执行 r 5 r_5 r5​ 时， O 25 = 343 O_{25}=343 O25​=343。为了简单地举例，假设所有可行任务的组合按照时间顺序排列，满足观测类别匹配、存储容量要求和最短间隔的硬约束。
C = ( 81 ∞ 15 ∞ 65 ∞ 70 82 ∞ ∞ 90 27 ∞ ∞ 3 74 3 69 ∞ ∞ 12 ∞ 95 91 84 ∞ 27 31 76 64 ∞ 95 ∞ 79 93 65 4 ∞ 79 70 63 96 80 ∞ ∞ ∞ ∞ 3 ∞ ∞ ) D = ( 11 ∞ − 12 ∞ − 17 ∞ 7 10 ∞ ∞ − 8 − 22 ∞ ∞ 12 15 − 16 − 12 ∞ ∞ − 7 ∞ − 0.29 18 − 15 ∞ − 4 − 12 − 1 1 ∞ − 4 ∞ 17 12 − 5 − 2 ∞ − 13 24 19 13 − 19 ∞ ∞ ∞ ∞ − 3 ∞ ∞ ) \begin{aligned} C & =\left(\begin{array}{cccccccccc} 81 & \infty & 15 & \infty & 65 & \infty & 70 & 82 & \infty & \infty \\ 90 & 27 & \infty & \infty & 3 & 74 & 3 & 69 & \infty & \infty \\ 12 & \infty & 95 & 91 & 84 & \infty & 27 & 31 & 76 & 64 \\ \infty & 95 & \infty & 79 & 93 & 65 & 4 & \infty & 79 & 70 \\ 63 & 96 & 80 & \infty & \infty & \infty & \infty & 3 & \infty & \infty \end{array}\right) \\ D & =\left(\begin{array}{cccccccccc} 11 & \infty & -12 & \infty & -17 & \infty & 7 & 10 & \infty & \infty \\ -8 & -22 & \infty & \infty & 12 & 15 & -16 & -12 & \infty & \infty \\ -7 & \infty & -0.29 & 18 & -15 & \infty & -4 & -12 & -1 & 1 \\ \infty & -4 & \infty & 17 & 12 & -5 & -2 & \infty & -13 & 24 \\ 19 & 13 & -19 & \infty & \infty & \infty & \infty & -3 & \infty & \infty \end{array}\right) \end{aligned} CD​= ​819012∞63​∞27∞9596​15∞95∞80​∞∞9179∞​6538493∞​∞74∞65∞​703274∞​826931∞3​∞∞7679∞​∞∞6470∞​ ​= ​11−8−7∞19​∞−22∞−413​−12∞−0.29∞−19​∞∞1817∞​−1712−1512∞​∞15∞−5∞​7−16−4−2∞​10−12−12∞−3​∞∞−1−13∞​∞∞124∞​ ​​

4.A l l l 的效果

为了研究存储器长度 l l l 的效果，我们进行蒙特卡洛仿真，独立运行100次取平均。表1展示了 l l l 从1增加到100的结果，其中 F ˉ \bar{F} Fˉ 表示在标准差为 σ \sigma σ 时100次独立运行的平均系统目标， b e s t best best 和 w o r s t worst worst 分别表示 F F F 的最小值和最大值， T T T 是平均计算时间， F ˉ \bar{F} Fˉ 在不同 l l l 下随着代数的变化曲线如图1所示。
  当 l = 1 l=1 l=1 时，DMPA是一个贪婪确定性过程{greedy deterministic process}，可以在0.11s内以最快速度收敛，但是代价最高，达到 F ˉ = 2007 \bar{F}=2007 Fˉ=2007，标准差最大，达到 σ = 279 \sigma=279 σ=279。这一例子表明在 l = 1 l=1 l=1 时，DMPA的计算量更少但达到纳什均衡的结果严重依赖于初始任务规划。当 l l l 增加到100时， F ˉ \bar{F} Fˉ 单调增加至1306， σ \sigma σ 下降至65，同时代价是更长的计算时间 T = 57.79 T=57.79 T=57.79 s。这表明更长的存储器长度可以通过更少的代价得到精炼纳什均衡，并减少对初始行为集合的依赖。与此同时，为了在求解效率和现实应用中的计算代价之间得到令人满意的平衡点， l l l 应根据最优先的需求来选择。如果协调时间被限制，则建议使用更短的 l l l，同时更长的 l l l 可以达到更高的求解效率。
  由于个体自主和分布式计算，DMPA也能动态地适应客户端需求和个体特征的动态变化。图2中，第300次迭代时，客户端要求从初始观测任务中撤回需求 r 5 r_5 r5​，这等价于令 ω 5 = 0 \omega_5=0 ω5​=0。从当前的纳什均衡点 a N E 1 a_{NE}^1 aNE1​ 处有 F ( a N E 1 ) = 1546 F(a_{NE}^1)=1546 F(aNE1​)=1546，所有的卫星按照DMPA重新协调并在20代内收敛于一个新的纳什均衡点 a N E 2 a_{NE}^2 aNE2​，其中 F ( a N E 2 ) = 1546 F(a_{NE}^2)=1546 F(aNE2​)=1546。特别地，我们有
a N E 1 = { ( ∅ ) , ( ∅ ) , ( r 3 , r 9 , r 10 ) , ( r 4 , r 5 , r 6 , r 7 , ) , ( r 1 , r 2 , r 8 ) } a N E 2 = { ( ∅ ) , ( ∅ ) , ( r 3 , r 9 , r 10 ) , ( r 4 , r 6 , r 7 , ) , ( r 1 , r 2 , r 8 ) } \begin{aligned} & a_{NE}^1=\{(\varnothing),(\varnothing),(r_{3}, r_{9}, r_{10}),(r_{4}, r_{5}, r_{6}, r_{7},),(r_{1}, r_{2}, r_{8})\} \\ & a_{NE}^2=\{(\varnothing),(\varnothing),(r_{3}, r_{9}, r_{10}),(r_{4}, r_{6}, r_{7},),(r_{1}, r_{2}, r_{8})\} \end{aligned} ​aNE1​={(∅),(∅),(r3​,r9​,r10​),(r4​,r5​,r6​,r7​,),(r1​,r2​,r8​)}aNE2​={(∅),(∅),(r3​,r9​,r10​),(r4​,r6​,r7​,),(r1​,r2​,r8​)}​

4.B 与经典方法的比较

为了显示DMPA的优势，我们将其与分布式卫星任务规划的典型方法进行了比较：
  (1)BRR（最佳响应规则^[12]）：这是一种贪婪的分布式学习算法，其中一个玩家被随机选择并更新到其最佳响应，而其他所有玩家都保持当前的动作。
  (2)简单：这是一种分布式和确定性的规划算法，其中每个卫星只与邻居进行通信，只有观测代价最小的一颗卫星被分配给mesh=j中的任务。该算法保证了可行的任务计划，但效率取决于两个连续任务之间的侧摆代价。
  (3)SAP（空间自适应播放^[13]）：这是一种以异步方式执行的分布式学习算法。具体来说，选择一个随机玩家按照波尔兹曼分布进行更新。当Boltzman系数β接近无穷大时，该算法在理论上保证了全局最优性。
  (4)PSO（粒子群优化^[17]）：这是一种典型的基于群体智能的集中优化算法，它通过模拟鸟群或鱼群中的生物运动，使用候选解决方案群体来解决问题。在模拟中，我们采用了大小为100、迭代长度为2000的总体。
  表2显示，在4个分布式算法中，我们的DMPA对于 l = 50 l=50 l=50（ F ˉ = 1340 \bar{F}=1340 Fˉ=1340）和 l = 100 l=100 l=100（ F ˉ = 1306 \bar{F}=1306 Fˉ=1306）都有最小系统代价，而BRRR、simple和SAP的平均代价分别为2154、1962和1829。

5. 总结

  为了实现分布式卫星系统的高效任务规划，本文从博弈学习的角度解决了这个问题。每一颗卫星都被视为一个理性的参与者，与邻居互动以最大限度地提高收益。通过使用奇妙的生命效用，我们为每个博弈设计了局部效用函数，并表明它一定是一个势博弈。为了仅使用局部信息来逼近最优解，我们提出了DMPA，其中所有卫星都按照受限贪婪和有限内存的规则同步更新其任务计划。借助于惯例，我们证明了DMPA从随机生成的任何初始系统计划以概率1收敛到纳什均衡。通过数值模拟结果，我们还表明增加存储器长度有助于提高系统级性能。特别是，当l增加到100时，我们的DMPA在所有性能指标方面领先于PSO等集中式方法。我们未来的工作将侧重于非理想通信环境下的分布式任务规划及其现实应用。