考虑一个由一组卫星组成的地球观测星座
S
=
{
s
i
∣
i
∈
N
}
S=\{s_i|i\in N\}
S={si∣i∈N}，每个
s
i
s_i
si 通过它的环绕飞行轨道
o
i
o_i
oi、观测类别(例如光学或雷达)、摆动范围、存储容量以及执行两个相邻任务之间的最短时间间隔来定义。定义客户端请求集合
R
=
{
r
j
∣
j
∈
M
}
R=\{r_j|j\in M\}
R={rj∣j∈M}，
M
=
{
1
,
2
,
⋯
,
m
}
M=\{1,2,\cdots,m\}
M={1,2,⋯,m}，每一个
r
j
r_j
rj 是一个与观测类型、需要观测的网格区和最小存储需求相关联的元任务。 对每个
s
i
s_i
si，定义其可行任务集
A
i
f
A_i^f
Aif，该任务集由位于它的关注领域内可分别完成的任务组成。出于执行效率的考虑，一系列给定的
s
i
s_i
si 的可行任务被看作一个特别的任务序列，该序列按与
s
i
s_i
si 相遇的时间顺序执行。如图1所示，
{
r
2
,
r
3
,
r
4
}
\{r_2,r_3,r_4\}
{r2,r3,r4} 表示对于
s
i
s_i
si 的任务序列为
r
4
→
r
2
→
r
3
r_4\rightarrow r_2\rightarrow r_3
r4→r2→r3。当对应的任务序列
r
i
1
→
r
i
2
→
⋯
→
r
i
n
i
r_{i1}\rightarrow r_{i2}\rightarrow\cdots\rightarrow r_{in_i}
ri1→ri2→⋯→rini 没有超出工作约束时，
s
i
s_i
si 的一个可行任务
a
i
a_i
ai 定义为
A
i
f
A_i^f
Aif 的子集，可行分配集定义为
A
i
A_i
Ai。对应地，分配解集{profile}空间定义为
A
=
∏
i
=
1
n
A
i
A=\prod_{i=1}^nA_i
A=∏i=1nAi，其中
a
=
{
a
1
,
a
2
,
⋯
,
a
n
}
∈
A
a=\{a_1,a_2,\cdots,a_n\}\in A
a={a1,a2,⋯,an}∈A 是所有卫星的可行分配的组合。为了简化理论分析，我们假设
A
i
f
A_i^f
Aif 的每个子集由
s
i
s_i
si 的一个可行分配组成。因此
A
A
A 的基数为
2
ϵ
2^\epsilon
2ϵ，
ϵ
=
∑
i
∈
N
∣
A
i
f
∣
\epsilon=\sum_{i\in N}|A_i^f|
ϵ=∑i∈N∣Aif∣。对每个
a
∈
A
a\in A
a∈A，定义
N
(
a
)
=
∣
⋃
i
∈
N
a
i
∣
\mathbb{N}(a)=\left|\bigcup_{i\in N}a_i\right|
N(a)=⋃i∈Nai 为正在执行的任务数量。当最大数量的任务正在处理时，一个分配解集
a
a
a 是一个任务覆盖，也就是说，
N
(
a
)
=
max
a
~
∈
A
N
(
a
~
)
\mathbb{N}(a)=\max_{\tilde{a}\in A}\mathbb{N}(\tilde{a})
N(a)=a~∈AmaxN(a~) 对于分布式协调，假设两个卫星可以通过星间链路交换信息当且仅当它们有相同的可行任务。在这种情况下，
s
i
s_i
si 的邻居定义为
Ω
i
=
{
s
j
∣
A
i
f
∩
A
j
f
≠
∅
}
\Omega_i=\{s_j|A_i^f\cap A_j^f\neq\varnothing\}
Ωi={sj∣Aif∩Ajf=∅}，且
s
i
∉
Ω
i
s_i\notin\Omega_i
si∈/Ωi。 （略）
2.2 等效性分析
对于
a
∈
A
a\in A
a∈A，将未分配任务定义为集合
T
0
(
a
)
=
{
r
j
∣
b
j
(
a
)
=
0
,
j
∈
M
}
T_0(a)=\{r_j|b_j(a)=0,j\in M\}
T0(a)={rj∣bj(a)=0,j∈M}。借此证明
F
(
a
)
F(a)
F(a) 的最优解与最优任务覆盖等价。
定理1： 如果
∀
j
∈
M
,
ω
j
>
max
i
∈
N
f
(
A
i
f
)
\forall j \in M,\omega_j>\max_{i\in N}f(A_i^f)
∀j∈M,ωj>maxi∈Nf(Aif)，式(2)的最优解一定是使得全局代价最小化的最优任务覆盖。 证明： 假设
a
∗
a^*
a∗ 是式(2)的最优解但不是一个任务覆盖。此时一定存在至少一个元任务
r
k
r_k
rk 没有分配给任何一个个体。此时可以构造另一个分配解集
a
^
≠
a
∗
\hat{a}\neq a^*
a^=a∗，这一解集中把
r
k
r_k
rk 分配给了
s
i
s_i
si，并且
r
k
∈
A
i
f
r_k\in A_i^f
rk∈Aif。将除了
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)，并记
a
^
=
(
a
^
i
,
a
−
i
∗
)
\hat{a}=(\hat{a}_i,a_{-i}^*)
a^=(a^i,a−i∗)，其中
a
^
i
=
{
a
i
∗
,
r
k
}
\hat{a}_i=\{a_i^*,r_k\}
a^i={ai∗,rk}。由式(1)(2)得
F
(
a
∗
)
−
F
(
a
^
)
=
∑
j
∈
N
[
f
(
a
j
∗
)
−
f
(
a
^
j
)
]
+
∑
j
∈
T
0
(
a
∗
)
ω
j
−
∑
j
∈
T
0
(
a
^
)
ω
j
=
ω
k
−
f
(
a
^
i
)
+
f
(
a
i
∗
)
=
0
\begin{aligned} F(a^*)-F(\hat{a}) =& \sum_{j\in N}[f(a_j^*)-f(\hat{a}_j)] +\sum_{j\in T_0(a^*)}\omega_j - \sum_{j\in T_0(\hat{a})}\omega_j \\ =& \omega_k - f(\hat{a}_i) + f(a_i^*) \\ =& 0 \end{aligned}
F(a∗)−F(a^)===j∈N∑[f(aj∗)−f(a^j)]+j∈T0(a∗)∑ωj−j∈T0(a^)∑ωjωk−f(a^i)+f(ai∗)0 因为
ω
k
>
max
i
∈
N
f
(
A
i
f
)
≥
f
(
a
^
i
)
\omega_k>\max_{i\in N}f(A_i^f)\geq f(\hat{a}_i)
ωk>maxi∈Nf(Aif)≥f(a^i)。这表明一个没有覆盖所有任务的分配一定不是式(2)的最优解。进一步，由于
f
(
a
∗
)
f(a^*)
f(a∗) 是所有
a
∈
A
a\in A
a∈A 中的最小值，很明显
a
∗
a^*
a∗ 是最优的任务覆盖。证毕。
□
\Box
□ **注1：**需要强调的是，尽管对于
s
i
s_i
si，每个
A
⊆
\mathcal{A}\subseteq
A⊆ 都有效的假设不正确，但
ω
j
>
∑
i
=
1
n
f
i
(
A
i
f
)
,
∀
j
∈
M
\omega_j>\sum_{i=1}^nf_i(A_i^f),\forall j\in M
ωj>∑i=1nfi(Aif),∀j∈M，等效性依然满足，通过
F
(
a
)
<
F
(
b
)
F(a)<F(b)
F(a)<F(b)，if
N
(
a
)
>
N
(
b
)
,
∀
a
,
b
∈
A
\mathbb{N}(a)>\mathbb{N}(b),\forall a,b\in A
N(a)>N(b),∀a,b∈A 来保证。
2.3 网络化势博弈
为了在多卫星任务分配中实现自组织，我们考虑了一个网络博弈
G
=
(
S
,
{
A
i
}
,
{
U
i
}
)
G=(S,\{A_i\},\{U_i\})
G=(S,{Ai},{Ui})，并将每个
S
i
∈
S
S_i\in S
Si∈S 看作一个自主的理性参与者。从博弈论的角度来看，
s
i
s_i
si 的一个可行的任务分配
a
i
∈
A
i
a_i\in A_i
ai∈Ai 被定义为一个行为，而每个分配解集
a
∈
A
a\in A
a∈A 称作行为组合。为了最大化局部效用
U
i
U_i
Ui，每个参与者
s
i
s_i
si 只根据
Ω
i
\Omega_i
Ωi 中的邻居信息迭代地从行为集
A
i
A_i
Ai 中选择它的行为。 对于基于竞争博弈论的分布式协调和优化，纳什均衡、势博弈和共识的概念发挥着重要作用，这些概念通过以下定义得以阐明。 定义1（纳什均衡）（略） 定义2（共识）（略） 定义3（势博弈）（略） 通过使用美好生活效应将系统目标分解到每个个体上，我们建立下面的势博弈。 定理2： 当势函数
ϕ
(
a
)
\phi(a)
ϕ(a) 和局部效用函数
U
i
(
a
)
U_i(a)
Ui(a) 选为
ϕ
(
a
)
=
−
F
(
a
)
U
i
(
a
)
=
−
f
(
a
i
)
−
∑
k
∈
U
i
(
a
)
ω
k
\begin{aligned} \phi(a) &= -F(a) \\ U_i(a) &= -f(a_i)-\sum_{k\in\mathcal{U}_i(a)}\omega_k \end{aligned}
ϕ(a)Ui(a)=−F(a)=−f(ai)−k∈Ui(a)∑ωk 时，任务分配博弈
G
=
(
S
,
A
i
,
U
i
)
G=(S,{A_i},{U_i})
G=(S,Ai,Ui) 是一个势博弈，其中
U
i
(
a
)
=
A
i
f
∩
T
0
(
a
)
\mathcal{U}_i(a)=A_i^f\cap T_0(a)
Ui(a)=Aif∩T0(a) 是
s
i
s_i
si 的可执行但未分配任务的子集。 证明： 根据式(2)把
ϕ
(
a
)
\phi(a)
ϕ(a) 分为无关的两个部分
ϕ
(
a
)
=
−
[
f
(
a
i
)
+
∑
k
∈
U
i
(
a
)
ω
k
]
−
[
∑
j
≠
i
n
f
(
a
j
)
+
∑
k
∉
A
i
f
(
1
−
b
k
)
ω
k
]
\phi(a) = -\left[f(a_i)+\sum_{k\in\mathcal{U}_i(a)}\omega_k\right] -\left[\sum_{j\neq i}^nf(a_j)+\sum_{k\notin A_i^f}(1-b_k)\omega_k\right]
ϕ(a)=−f(ai)+k∈Ui(a)∑ωk−j=i∑nf(aj)+k∈/Aif∑(1−bk)ωk 因此当个体
s
i
s_i
si 将其策略从
a
a
a 中的
a
i
a_i
ai 单方面切换到
a
~
\tilde{a}
a~ 中的
a
~
i
\tilde{a}_i
a~i 时，
ϕ
(
a
)
\phi(a)
ϕ(a) 的变化为
ϕ
(
a
~
)
−
ϕ
(
a
)
=
[
f
(
a
i
)
+
∑
k
∈
U
i
(
a
)
ω
k
]
−
[
f
(
a
~
i
)
+
∑
k
∈
U
i
(
a
~
)
ω
k
]
=
U
i
(
a
~
)
−
U
i
(
a
)
\begin{aligned} \phi(\tilde{a})-\phi(a) =& \left[f(a_i) + \sum_{k\in\mathcal{U}_i(a)}\omega_k\right] -\left[f(\tilde{a}_i) + \sum_{k\in\mathcal{U}_i(\tilde{a})}\omega_k\right] \\ =& U_i(\tilde{a})-U_i(a) \end{aligned}
ϕ(a~)−ϕ(a)==f(ai)+k∈Ui(a)∑ωk−f(a~i)+k∈Ui(a~)∑ωkUi(a~)−Ui(a) 根据定义，这一定是一个势博弈。
□
\Box
□ 通过利用势博弈的优势，势函数的最优解一定是一个纳什均衡，分布式任务分配问题可以近似成得到并尽可能调整纳什均衡直到达到全局最优解。注意到由于
ω
j
\omega_j
ωj 可以设置为任意大的数，所以并不需要全局信息来满足定理1.
定理3： 对于任务分配博弈
G
=
(
S
,
{
A
i
}
,
{
U
i
}
)
G=(S,\{A_i\},\{U_i\})
G=(S,{Ai},{Ui})，每个纳什均衡解
a
∈
A
a\in A
a∈A 一定是一个没有重复分配任务的任务覆盖。 证明： 这一可行性可以根据定理1简单地展示。对任意一个非任务覆盖的纳什均衡
a
a
a 至少有一个个体
s
i
s_i
si 有单独改变自己行为的动力，即添加一个未覆盖任务
r
j
r_j
rj 得到
a
~
i
=
{
a
i
,
r
j
}
\tilde{a}_i=\{a_i,r_j\}
a~i={ai,rj}，其中
r
j
∈
A
i
f
r_j\in A_i^f
rj∈Aif。因为
U
i
(
a
)
−
U
i
(
a
~
i
,
a
−
i
)
<
0
U_i(a)-U_i(\tilde{a}_i,a_{-i})<0
Ui(a)−Ui(a~i,a−i)<0，其中
a
−
i
a_{-i}
a−i 表示
a
a
a 中除了
s
i
s_i
si 以外的所有分配，这与
a
a
a 是一个纳什均衡的假设冲突，证明了
a
a
a 一定是一个任务覆盖。同样的道理，由于一个个体可以通过单独删除一个重复的任务来降低自己的效用函数，所以每个任务一定只分配给了一个卫星。证毕。
□
\Box
□
3. 算法设计
本节提出了一个从势博弈中学习的多卫星分布式任务分配的自组织机制，并借助共识展示了其收敛性。
3.1 分布式任务分配算法(DT2A)
为了能在求解效率和收敛速度之间取得平衡，我们引入了随机性，为每个参与者建立一个长度为
l
l
l 的存储器。特别地，将第
t
t
t 代的存储器向量定义为
M
i
t
=
(
v
1
,
v
2
,
⋯
,
v
l
)
,
v
j
∈
A
i
M_i^t=(v1,v2,\cdots,v_l),v_j\in A_i
Mit=(v1,v2,⋯,vl),vj∈Ai，存储器解集定义为
M
t
=
{
M
1
t
,
M
2
t
,
⋯
,
M
n
t
}
M^t=\{M_1^t,M_2^t,\cdots,M_n^t\}
Mt={M1t,M2t,⋯,Mnt}。对地面发来的请求集合
R
R
R，我们假设一个广播机制，所有卫星都能收到完整的任务集合。基于这一假设，每个
s
i
s_i
si 计算其可行任务集
A
i
f
A_i^f
Aif 并获得可行分配集
A
i
A_i
Ai。 开始分布式任务分配前，每个卫星初始化时在
A
i
A_i
Ai 中随机选择
a
i
t
=
1
a_i^{t=1}
ait=1 和
M
i
t
=
1
M_i^{t=1}
Mit=1。然后同步执行主协调步骤。在每个迭代步
t
t
t 时，每个参与者只与其在
Ω
i
\Omega_i
Ωi 中的邻居交换行为信息
a
i
t
a_i^t
ait。根据式(6)中的局部效用
U
i
t
U_i^t
Uit，最优响应
B
i
t
B_i^t
Bit 和遗憾值
R
i
t
R_i^t
Rit 通过下式计算
B
i
t
=
arg max
a
~
i
t
∈
A
i
U
i
(
a
~
i
t
,
a
−
i
t
)
R
i
t
=
U
i
(
B
i
t
,
a
−
i
t
)
−
U
i
(
a
i
t
,
a
−
i
t
)
\begin{aligned} & B_i^t=\argmax_{\tilde{a}_i^t\in A_i} U_i(\tilde{a}_i^t,a_{-i}^t) \\ & R_i^t=U_i(B_i^t,a_{-i}^t)-U_i(a_i^t,a_{-i}^t) \end{aligned}
Bit=a~it∈AiargmaxUi(a~it,a−it)Rit=Ui(Bit,a−it)−Ui(ait,a−it)
Ω
i
\Omega_i
Ωi 中的最大遗憾值定义为
R
i
t
∗
=
max
j
∈
Ω
i
R
j
t
R_i^{t*}=\max_{j\in\Omega_i}R_j^t
Rit∗=maxj∈ΩiRjt，其ID号定义为
j
∗
=
min
(
arg max
j
∈
Ω
i
R
j
t
)
j^*=\min(\argmax_{j\in\Omega_i}R_j^t)
j∗=min(argmaxj∈ΩiRjt)。当同时满足以下两个条件时，参与者
s
i
s_i
si 定义为“创新者”： (1) 其在
Ω
i
\Omega_i
Ωi 中有最大正遗憾值，即
R
i
t
>
0
,
R
i
t
≥
R
j
t
,
∀
s
j
∈
Ω
i
R_i^t>0,R_i^t\ge R_j^t,\forall s_j\in\Omega_i
Rit>0,Rit≥Rjt,∀sj∈Ωi (2) 任意满足
j
<
i
j<i
j<i 的邻居
s
j
∈
Ω
i
s_j\in\Omega_i
sj∈Ωi 有更小的遗憾值，即
∀
j
<
i
,
R
j
t
<
R
i
t
\forall j<i,R_j^t<R_i^t
∀j<i,Rjt<Rit 否则，
s
i
s_i
si 定义为普通参与者。对于一个创新者，将其受限的最优响应定义为
β
i
t
=
B
i
t
\beta_i^t=B_i^t
βit=Bit，普通参与者为
β
i
t
=
a
i
t
\beta_i^t=a_i^t
βit=ait。很明显在任意邻居集
Ω
i
\Omega_i
Ωi 中最少有一个创新者。 与确定性机制相反，一个 DT2A 中的参与者在有限存储器向量中使用随机协调策略。首先，
s
i
s_i
si 通过丢弃存储器中最早的数据来更新
M
i
t
M_i^t
Mit，并记录
β
i
t
\beta_i^t
βit 来计算
M
i
t
+
1
=
(
v
2
,
v
3
,
⋯
,
v
l
,
β
i
t
)
M_i^{t+1}=(v_2,v_3,\cdots,v_l,\beta_i^t)
Mit+1=(v2,v3,⋯,vl,βit) ，其次，随机地选择
M
i
t
+
1
M_i^{t+1}
Mit+1 中的一个行为来生成
a
i
t
+
1
a_i^{t+1}
ait+1，算法进入下一次迭代。持续这一步骤直到收敛。
3.2 收敛性分析
在给出关于收敛性的主要结论之前，我们首先介绍对推理链至关重要的两个声明。 声明1： 关于DT2A中的随机机制，一个共识是稳定的。 证明： 假设
h
t
=
(
a
t
+
1
−
l
,
a
t
+
2
−
l
,
⋯
,
a
t
)
h^t=(a^{t+1-l},a^{t+2-l},\cdots,a^t)
ht=(at+1−l,at+2−l,⋯,at) 是一个共识，其中每个元素
a
τ
,
t
+
1
−
l
≤
τ
≤
t
a^\tau,t+1-l\le\tau\le t
aτ,t+1−l≤τ≤t 是同一个纳什均衡
a
a
a。对每个个体
s
i
∈
S
s_i\in S
si∈S，更新后的存储器向量
M
i
t
+
1
M_i^{t+1}
Mit+1 仅由构成同一个纳什均衡点
a
a
a 的
a
i
t
a_i^t
ait 组成，那么一定有
∀
τ
>
t
,
a
τ
≡
a
\forall\tau>t,a^\tau\equiv a
∀τ>t,aτ≡a。证毕。 声明2： 考虑一个有限长度的随机过程。如果事件
E
\mathbb{E}
E 在每个时刻
t
t
t 发生的概率为
p
t
(
E
)
>
0
p^t(\mathbb{E})>0
pt(E)>0，那么
E
\mathbb{E}
E 发生的概率为1。 证明： 因为
E
\mathbb{E}
E 永不发生的概率为
p
0
(
E
)
=
lim
t
→
∞
∏
t
=
1
(
1
−
p
t
(
E
)
)
=
0
p_0(\mathbb{E})=\lim_{t\rightarrow\infty}\prod_{t=1}(1-p^t(\mathbb{E}))=0
p0(E)=t→∞limt=1∏(1−pt(E))=0 所以
E
\mathbb{E}
E 发生的概率为
p
1
=
1
−
p
0
(
E
)
=
1
p_1=1-p_0(\mathbb{E})=1
p1=1−p0(E)=1。 从以上事实出发，我们在下面的定理中给出自组织的解决方案。 定理4： 一个给定的多卫星分布式任务分配问题，DT2A算法可以在任意初始分配解集
a
1
a^1
a1 和任意初始存储器解集
M
1
M^1
M1 出发，经过有限次迭代后收敛到一个共识。 证明： 首先考虑从
a
t
a^t
at 到
a
t
+
1
a^{t+1}
at+1 的协调过程，并证明 DT2A 从任意
a
t
a^t
at 和任意
m
t
m^t
mt 出发以概率1达到纳什均衡。 (1) 当
l
=
1
l=1
l=1 时，一个参与者通过确定性地采取唯一的行为来更新其自身行为，也就是在存储器中导致
a
i
t
+
1
=
β
i
t
a_i^{t+1}=\beta_i^t
ait+1=βit 的限制最优响应。已知在任意一个邻居区内最多只有一个使
a
i
t
+
1
=
β
i
t
=
B
i
t
a_i^{t+1}=\beta_i^t=B_i^t
ait+1=βit=Bit 的创新者，其余都是保持当前行为
a
i
t
+
1
=
β
i
t
=
a
i
t
a_i^{t+1}=\beta_i^t=a_i^t
ait+1=βit=ait 的普通个体。已知
ϕ
\phi
ϕ 在每次迭代中都单调增加，因为
ϕ
(
a
t
+
1
)
−
ϕ
(
a
t
)
\phi(a^{t+1})-\phi(a^t)
ϕ(at+1)−ϕ(at) （略） 证毕。
4. 仿真和结结果比较
5.总结
针对多卫星系统的自组织任务分配，我们从博弈论的角度解决了这一问题，并通过博弈论中的学习提出了DT2A，其中每个卫星都被视为一个自主个体，试图仅依靠本地信息来最大化自己的收益。遵循精彩的生活效用{wonderful life utility}，我们将系统级目标分解为个体个体的局部效用，并证明最终博弈是一个势博弈。为了以分布式方式导出接近最优的解，DT2A遵循同步迭代，其中每个卫星与邻居交换信息，并通过遵守有限贪婪和有限记忆的随机规则来更新其分配。借助于约定的概念，我们证明了从任何分配配置文件中，DT2A以有限步数收敛到纳什均衡，纳什均衡必须是构成任务覆盖的分配配置文件。 通过密集的数值实验，我们表明，内存长度在分配效率和协调时间之间提供了有效的折衷，其中，在多次迭代后，大l通常可以获得更好的近似最优解，而小l在更短的时间内产生更昂贵的结果。此外，还证明了DT2A对诸如客户端请求改变或通信断开之类的随机干扰具有鲁棒性。特别是，对于仅在有限时间间隔内发生的偶然通信错误，我们的算法的解决效率实际上可以得到提高，而不是降低。最后，在小规模和大规模场景中进行了对比实验，结果证明了DT2A的优越性。特别是，随着l的增加，可以获得接近或甚至优于典型集中式算法的高效结果。我们未来的工作将集中在分布式卫星任务规划上，该规划包含了更多的约束及其现实应用。
