基于改进指针网络的卫星对地观测任务规划方法

第 55 卷第 2 期

2021 年 2 月

浙 江 大 学 学 报

(工学版)

Journal of Zhejiang University (Engineering Science)

Vol.55 No.2

Feb. 2021

DOI: 10.3785/.1008-973X.2021.02.020

基于改进指针网络的卫星对地观测任务规划方法

马一凡

1,2

，赵凡宇

1,2

，王鑫

1,2

，金仲和

1,2

(1. 浙江大学 微小卫星研究中心，浙江 杭州 310027；2. 浙江省微纳卫星研究重点实验室，浙江 杭州 310027)

摘 要：针对卫星观测任务规划问题约束复杂、求解空间大和输入任务序列长度不固定的特点，使用深度强化学

习（DRL）方法对卫星观测任务规划问题进行求解. 综合考虑时间窗口约束、任务间转移机动时间和卫星电量、存

储约束，对卫星观测任务规划问题进行建模. 基于指针网络（PN）的运行机制建立序列决策算法模型，使用Mask

向量来考虑卫星观测任务规划问题中的各类约束，并通过Actor Critic强化学习算法对模型进行训练，以获得最大

的收益率. 借鉴多头注意力（MHA）机制的思想对PN进行改进，提出多头注意力指针网络（MHA-PN）算法. 根据

实验结果可以看出，MHA-PN算法显著提高了模型的训练速度和泛化性能，训练好的MHA-PN算法模型可以直

接对输入序列进行端到端的推理，避免传统启发式算法迭代求解的过程，具有较高的求解效率.

关键词： 卫星观测任务规划；组合优化问题；深度强化学习；指针网络（PN）；Actor Critic；多头注意力指针网络（MHA-PN）

中图分类号： V 474 文献标志码： A 文章编号： 1008−973X（2021）02−0395−07

Satellite earth observation task planning method based on

improved pointer networks

MA Yi-fan

1,2

, ZHAO Fan-yu

1,2

, WANG Xin

1,2

, JIN Zhong-he

1,2

(1. Micro-satellite Research Center, Zhejiang University, Hangzhou 310027, China;

2. Zhejiang Key Laboratory of Micro-nano Satellite Research, Hangzhou 310027, China)

Abstract:

The satellite observation task planning has the characteristics of complex constraints, large solution space,

and unfixed length of input task sequence. The deep reinforcement learning (DRL) method was used to solve the

problems. The satellite observation task planning problem was modeled by taking into account the constraints of

time windows, transfer time between tasks, and satellite power and memory constraints. A sequence decision

algorithm model was established based on the operating mechanism of pointer networks (PN), Mask vector was used

to consider various constraints in the satellite observation task planning problem, and the model was trained by Actor

Critic reinforcement learning algorithm to obtain the maximum reward. The PN was improved by referring to the

multi-head attention (MHA) mechanism, and the multi-head attention pointer networks (MHA-PN) algorithm was

proposed. Experimental results show that the MHA-PN algorithm significantly improves the training speed and the

generalization performance of the model, and the trained MHA-PN algorithm model can carry out end-to-end

reasoning on the input sequence, avoiding the iterative solution process of traditional heuristic algorithm, has a high

efficiency of solution.

Key words: satellite observation task planning; combinatorial optimization problem; deep reinforcement learning;

pointer networks (PN); Actor Critic; multi-head attention pointer networks (MHA-PN)

卫星观测任务规划问题是在考虑时间窗口和

资源约束的条件下，对卫星资源加以分配，制定

出合理的任务观测序列，从而使有限的卫星资源

得以高效利用. 卫星成本高昂，星上资源有限，所

以制定出合理的任务观测序列显得尤为重要. 卫

星观测任务规划是提高卫星运行效率和降低成本

的基础和关键，成为航空航天、计算机、运筹学的

研究热点之一

[1]

. 卫星观测任务规划问题是一类

收稿日期：2020−03−11. 网址：/eng/article/2021/1008-973X/

基金项目：国家杰出青年科学基金资助项目（61525403）.

作者简介：马一凡(1996—)，男，硕士生，从事卫星自主任务规划研究. /0000-0001-9762-0246. E-mail：****************.cn

通信联系人：赵凡宇，男，博士后. /0000-0002-5239-2531. E-mail：**************.cn

396

浙 江 大 学 学 报（工学版）第 55 卷

多约束组合优化问题，模型的求解空间大. 目前

国内外的研究者对卫星任务观测规划问题进行了

研究，并基于智能优化算法对卫星观测任务规划

问题进行求解，比如蚁群算法

[2]

、遗传算法

[3]

、模

拟退火算法

[4]

和禁忌搜索算法

[5]

. 这些算法虽然

合理有效，但是存在着启发式因子设计困难、状态

转移复杂和寻优速度较慢的问题.

近几年来，出现了一些基于深度强化学习求

解组合优化问题的研究. 这些算法的模型整体上

采用了序列到序列（sequence to sequence，Seq2Seq）

的结构，这种结构通常是由2个循环神经网络

（recurrent neural network，RNN），或者其变种如长

短期记忆网络

[6]

（long short-term memory，LSTM）和

门控循环单元

[7]

（gate recurrent unit，GRU）构成，分

别称为编码器和解码器. 这种Seq2Seq结构的问

题在于，输入序列无论长短都会被编码为一个固

定的向量，在解码时受限于该固定的向量表示，

当输入序列较长时会造成信息丢失. 注意力机制

[8]

在解码阶段构建输出状态和输入序列的连接，以

发现输出状态和输入序列各节点之间相关性，解

决Seq2Seq结构长距离依赖的问题.

Vinyals等

[9]

提出指针网络（pointer networks，

PN）求解了一些经典的组合优化问题，比如旅行

商问题（traveling salesman problem，TSP）和背包问

题（knapsack problem，KP），使用注意力机制计算

得到Softmax概率分布，作为指针（pointer）指向输

入序列中的元素，对输入序列进行组合，最后使用

有监督方法对模型进行训练. Bello等

[10]

使用Actor

Critic强化学习算法

[11]

对PN进行训练，在节点长度

为100的TSP问题上获得了近似最优解，解决了有

监督训练中训练数据获取困难、精度不足的问题.

Nazari等

[12]

对Bello等

[10]

所使用算法模型中的

Encoder部分进行改进，用一个嵌入层替换PN的

RNN编码器部分，使得输入序列中的动态元素发

生改变时，可以并行地对Encoder进行更新，减小了

计算的复杂度，最后对交通路线规划问题（vehicle

routing problem，VRP）进行了求解.Dai等

[13]

使用

Structure2Vector的图嵌入

[14]

（graph embedding，GE）

模型依次输出TSP的访问节点，使用DQN算法对

模型进行训练. 这种基于图的结构相比于Seq2Seq

结构能够更好地反映TSP的结构特征.Kool等

[15]

使用图注意力网络（graph attention networks，GAT）

和自注意力机制建立编码器和解码器，并使用

REINFORCE算法对模型进行训练，在训练过程中

采用贪婪策略更新基准，该研究在基于深度强化

学习解决TSP的算法当中实现了最先进的效果.

本研究对上述基于深度强化学习（deep rein-

forcement learning，DRL）解决组合优化问题的方

法进行研究，并应用在卫星观测任务规划问题的

求解上，为解决卫星观测任务规划问题提供了新

的思路. 主要工作包含以下几方面：1）根据卫星

执行观测任务的特点，综合考虑时间窗口和资源

约束，对卫星观测任务规划问题进行建模；2）继

承Nazari等

[12]

所提出的算法结构，基于PN的运

行机制建立序列决策模型，并通过Actor Critic强

化学习算法对模型进行训练，实现对卫星观测任

务规划问题的求解；3）借鉴多头注意力（multi-head

attention，MHA）机制

[16]

的思想，对PN进行改进，

提出MHA-PN算法.

1 卫星观测任务规划问题描述

1.1 卫星观测任务规划问题的约束分析

卫星在执行对地观测任务时，每个地面目标

都有可观测的时间窗口，卫星通过侧摆和在轨运

行完成任务间转移须消耗时间和电量，对每个地

面目标的观测也要消耗电量和存储量. 考虑卫星

在一次过境时可完成的任务数量，在进行卫星观

测任务规划时，须综合考虑以下约束. 1）时间窗

口约束：由于卫星机动能力有限，要同时考虑任

务执行时间和任务转移时间的约束，下一个任务

执行的开始时间必须大于当前任务执行结束时间

和卫星侧摆机动时间之和；2）存储量约束：在执

行观测任务时，须消耗卫星的存储空间. 本研究

仅考虑无数据下传状态下的任务规划，完成所有

规划出的观测任务所需消耗的存储空间不能超过

卫星所提供的存储总容量；3）电量约束：卫星在

执行观测任务及在任务间进行姿态机动转移时，

须消耗卫星的电量，本研究仅考虑无在轨充电的

过程，完成所有规划的观测任务所需消耗的电量

不能超过卫星所提供的总电量.

1.2 卫星观测任务规划的问题描述

假设候选观测任务集合为

X=

{

x

1

,x

2

,···,x

M

}

，

M

为候选任务个数. 将每个候选任务定义为

x

i

=

{

ws

i

,

pos

i

,we

i

,d

i

,r

i

,e

i

,m

i

}

，

x

i

中的元素分别为任务的时间

窗口的开始时间、卫星在满足侧摆角度限制条件

下进行双向侧摆时，相对于其中一侧边界的位

置、时间窗口的结束时间、观测所需的持续时间、

第 2 期

马一凡, 等：基于改进指针网络的卫星对地观测任务规划方法[J]. 浙江大学学报：工学版,

2021, 55(2): 395–401.397

观测所获得的收益（执行优先级）、观测的电量消

耗和观测的存储量消耗. 规划得到的任务集合为

Y=

{

y

1

,y

2

,···,y

N

}

，

N

为规划结果中执行任务的个数.

2 算法模型建立和训练

2.1 输入任务集合

假设在侧摆过程中消耗的时间为

t

sle

，在卫星

姿态调整的机动过程中单位长度消耗的时间为

T

s

，下一个任务执行的开始时间大于当前任务执

将输入任务集合

X=

{

x

1

,x

2

,···,x

M

}

中的每个任

务

x

i

分为两部分，分别为静态元素集合

s

i

和动态元

行结束时间和卫星侧摆机动时间之和，时间窗口

约束的公式为

ws

i+1

>ws

i

+d

i

+t

sle

,

()

t

sle

=

pos

i+1

−pos

i

T

s

.

素集合

d

i

t

. 在模型的解码阶段的每个解码时间步

(1)

(2)

假设提供的存储总量为

M

tot

，提供的总电量为

E

tot

，

卫星在侧摆过程中消耗的电量为

e

sle

，在卫星姿态

骤

t

时，静态元素保持不变，动态元素会根据输出节

点发生动态变化. 将输入序列中的静态元素集合定

{}

义为

s

i

=

ws

i

,pos

i

,we

i

,d

i

,r

i

,e

i

,m

i

，动态元素集合定义

{}

t

ttttt

为

d

i

=

win

i

,acc

i

,mem

i

,pow

i

,pos

i

，

win

t

i

、acc

t

i

、mem

t

i

、

t

pow

t

i

、pos

i

分别为在解码时间步骤

t

时，任务是否

调整的机动过程中单位长度消耗的电量为

e

s

，指

示函数

ℓ

(

y

i

)

表示任务

y

i

被执行，则须满足的存储

约束和电量约束为

N

∑

i=1

N

∑

i=1

满足时间窗口约束的标记、任务是否已经访问过

的标记、卫星剩余的存储量、卫星剩余的电量、卫

星侧摆所在的位置. 此时，可以将输入任务集合重

}{

()

新定义为

X=x

i

t

=

s

i

,d

i

t

,i=0,1,···,M

，

x

i

t

中的静态

ℓ

(

y

i

)

m

i

⩽M

tot

,(3)

元素和动态元素可以看作任务

x

i

的特征，包含任

ℓ

(

y

i

)

e

i

+e

sle

⩽E

tot

,

N−1

∑

i=0

(4)

务

x

i

的信息和在时间步骤

t

时的状态.

2.2 模型整体结构介绍

提出MHA-PN算法对卫星观测任务规划问题

进行求解，算法的模型结构如图1所示. MHA-

PN算法整体是基于Seq2Seq

[12]

的结构，分为编码

器和解码器两部分.

1）编码器部分. 使用一维卷积层作为Embed-

{}

ttt

ding Layer将

X=x

1

,x

2

,···,x

5

输入任务序列中的每

e

sle

=

ℓ

(

y

i

)

=

()

pos

i+1

−pos

i

e

s

,(5)

(6)

{

1,任务y

i

被执行;

0,其他.

综合考虑各类约束，将收益率

R

作为优化的目标，

定义目标函数为

MN

()

/

∑∑

R=

ℓ

y

j

r

j

ℓ

(

x

i

)

r

i

.

j=1

个任务映射为一个矩阵，即对于序列中的每个输

入任务

x

i

t

,i∈

[1

,5]

，Embedding Layer将其映射为矩

[]

t

,i∈

[1

,5]

；

¯

¯¯

t

阵

x

=

s

,

d

i

ii

(7)

2）解码器部分. 使用GRU保存已解码序列的

信息. 在每个解码时间步骤

t

，根据编码器的输出

i=1

MHA+Mask

s

1

d

t

1

P (y

t+1

Y

t

, X

t

)

s

2

d

t

2

s

3

d

t

3

s

4

d

t

4

s

5

d

t

5

h

0

h

1

h

2

h

3

e

0

Embedding layer

e

1

e

2

e

3

Embedding Layer

s

1

d

1

t

s

2

d

2

t

s

3

d

3

t

Encoder

s

4

d

4

t

s

5

d

5

t

y

0

y

1

y

2

y

3

Decoder

图 1 MHA-PN算法模型结构

Fig.1 Model structure of MHA-PN algorithm

398

浙 江 大 学 学 报（工学版）第 55 卷

矩阵

x

¯

t

[

i

=

¯

s

i

,

d

¯

t

]

i

、GRU的隐含层状态

h

t

和

Mask

向

量，基于MHA-PN机制计算输出节点的概率分布.

最后，选择概率值最大的节点作为输出节点.

2.3 Pointer Networks应用

Pointer Networks机制可以描述为：在每个解

码时间步骤

t

[17]

，使用注意力机制和Glimpse机制

计算得到的Softmax概率值，指向输入序列中下

一个要访问的节点. 具体计算过程

[12]

如下.

1）通过加法注意力机制（additive attention）计

算对齐向量（alignment vector

a

t

=softmax

(

）：

V

T

([

a

tanhW

a

x

¯

t

i

;h

t

]))

.(8)

式中：

h

t

为解码器GRU在时间步骤

t

时的输出，

V

a

和

W

a

为训练参数.

2）对输入序列的嵌入矩阵进行加权累加得到

背景矩阵（context matrix）：

c

t

=

∑

M

a

t

i

x

¯

t

i

.(9)

i=1

3）通过Glimpse机制得到softmax

u

t

([

概率输出：

i

=tanh

W

c

x¯

t

])

i

;c

t

,(10)

P

(

y

t+1

|Y

t

,X

t

)

=softmax

(

V

T

c

u

t

)

i

+ln(Mask).(11)

式中：Mask为Mask向量，

V

c

和

W

c

为训练参数.

2.4 MHA-PN算法

借鉴多头注意力机制

[16]

的思想，对PN算法

进行改进，得到MHA-PN算法. 在解码时间步骤

t

时，MHA-PN算法将注意力机制中的

¯

s

i

、

d

¯

t

i

和

h

t

平

均划分为

n

部分. 假设

¯

s

i

、

d

¯

t

i

和

h

t

的维度为

d

mod

，划

分后各部分的维度为

d

n

，则有：

d

mod

=d

n

n.(12)

MHA-PN算法在划分后的

n

部分上分别进行式（8）~

（10）的运算，然后将各部分所得的结果进行合并，

最后经式（11）计算后得到指向输入序列的概率值.

多头注意力机制能够综合不同表示子空间中

模型所学习到的信息，提高模型的学习能力. 由

于整个过程是并行计算的，能提升模型的计算效

率，加快模型的训练.

2.5 Mask向量和解码器

使用Mask向量将约束加入到任务的选择过

程中，其长度和输入序列长度相等，每位的取值为

0或1. 当Mask向量某位的值为0时，经式（11）计

算得到对应位的Softmax概率值为0，可以将对应

的任务排除. 将Mask向量初始化为

[1

,0,0,···,0]

，

保证从第1个理想任务开始执行.

使用GRU

[7]

搭建模型的解码器，在模型解码

的每个时间步骤

t

，解码器中GRU单元的输出为

h

t

，结合Mask向量进行式（11）的运算，计算所得

的Softmax概率指向要输出的节点

y

t+1

. 将节点

y

t+1

对应的静态元素经Embedding Layer后得到

e

¯

t+1

，

作为下一时间步骤

t+1

时GRU单元的输入.

在每个时间步骤

t

得到输出节点

y

t+1

时，根据

卫星任务规划要满足的时间窗口和资源约束，对

输入序列中的动态元素进行更新：1）win，将不满

足时间窗口约束的任务置0；2）acc，将已经访问

过的任务置0；3）mem，对卫星剩余的存储量进行

更新；4）pow，对卫星剩余的电量进行更新；5）pos，

记录卫星执行完任务

i

后的侧摆位置. 最后，根据

动态元素对Mask向量进行更新，将不能访问的

节点对应位置置0. 按照上述过程依次进行解码，

直到满足终止条件：已经执行完所有的任务、没

有满足时间窗口的任务或者存储量和电量耗尽，

此时Mask向量为

[0

,0,0,···,0]

.

模型解码过程的伪代码描述如下.

算法: Decoder Algorithm

1: input: task set

X=

{

x

1

,x

2

,···,x

M

}

2: output:

Y=

{

y

1

,y

2

,···,y

N

}

3: initialize max_steps with n

4: initialize mask vector with

[1

,0,···,0]

5: for t = 1, 2, ···, max_steps do

6: 　if mask all is 0 do

7: 　　break

8: 　end if

9: 　calculate

(

Py

t+1

|Y

t

,X

t

)

by Eq.(11)

10: 　choose

y

t+1

accroding to

P

(

y

t+1

|Y

t

,X

t

)

11: 　calculate

e

¯

t+1

and GRU output

h

t+1

12: 　update dynamic accroding to

y

t+1

13: 　update mask accroding to dynamic

14: end for

2.6 模型的训练

假设最终输出的序列为

Y=

{

y

1

,y

2

,···,y

N

}

，根

据概率的链式法则，产生这个输出序列的概率为

P

(

Y|X

0

)

=

∏

N

P

(

y

t+1

|Y

t

,X

t

)

.(13)

t=0

如果在满足约束条件的情况下，通过策略

π

得

到输出序列

Y

，那么模型训练的目标为找到最优

的策略

π

∗

，使得输出的序列可以获得最大的收益率.

使用Actor Critic算法

[11]

对模型进行训练，其

第 2 期

马一凡, 等：基于改进指针网络的卫星对地观测任务规划方法[J]. 浙江大学学报：工学版,

2021, 55(2): 395–401.399

由2个神经网络构成.

1）Actor：MHA-PN算法模型，对输入序列进

行预测，得到输出序列中各节点的概率. 假设其

参数为

θ

，对参数的梯度为

N

∇≈

())(())

θ

1

∑

(

00

N

R

n

−V

X

n

;φ

∇

θ

lnPY

n

|X

n

.(14)

n=1

式中：

X

0

n

为第

n

个样本序列，

Y

n

为Actor对

0

划输出结果，

R

(

X

n

的规

)

n

为规划得到的收益率，

PY

n

|X

0

n

为

输出序列中每个节点的概率.

2）Critic：计算输入序列可获得收益率的评估

值. 假设其参数为

φ

，对参数的梯度为

∇

∑

N

(())

2

φ

=

1

N

∇

φ

R

n

−V

X

0

n

;φ

.(15)

n

式中：

V

(

=1

0

X

n

;φ

)

为Critic对第

n

个样本序列

X

0

n

可获

得收益率的估计.

训练部分的伪代码如下.

算法: Actor Critic Algorithm

1: initialize actor network with random weights

θ

2: initialize critic network with random weights

φ

3: for iteration = 1, 2, ···, max_iterations do

4: 　reset gradients:

dθ←0,dφ←0

5: 　sample N instances from training data

6: 　for n = 1, 2, ···, N do

7: 　　initialize step counter

t←0

8: 　　repeat

9: 　　　choose

y

t

(

y

t

)

n

+1

accroding to

P

n

+1

|Y

n

t

,X

t

n

10: 　　　observe new state

X

t

n

+1

11: 　　　

t←t+1

12: 　　until termination condition is satisfied

13: 　　compute reward

R

(

n

=R

Y

n

,X

0

)

n

14: 　end for

15: 　

d

1

∑

N

(

θ←

N

R

())

∇

(())

n

−V

X

0

n

;φ

θ

lnPY

n

|X

0

n

n=1

16: 　

d

1

∑

N

(())

2

φ←

N

∇

φ

R

n

−V

X

0

n

;φ

17: 　update

θ

using

n=1

dθ

18: 　update

φ

using

dφ

19: end for

3 训练和测试结果

3.1 实验设置

实验环境设置如下：操作系统为Ubuntu16.04，

CPU为Intel Xeon E5-2

620，GPU为RTX2080Ti，

在GPU上对模型进行训练，实验代码基于Pytorch

深度学习框架编写. 采用MHA-PN模型对卫星观

测任务规划问题进行求解，训练的超参数设定如

下：批样本数量（batch size）为128，训练轮次

（epoch）为1，Actor网络的学习率为

5×10

−4

，Critic

网络的学习率为

5×10

−4

，学习率衰减步长为

2000

，

学习率衰减比例为0.8，Embedding Layer的隐含层

维度为512，GRU的隐含层维度为512，多头注意力

头数为8，Dropout比率为0.1，采用Adam优化器

[18]

.

3.2 数据集介绍

将训练序列样本的数量设定为

10

6

，每个序列

样本的长度设定为50. 观测任务规划的场景假设

为任务时间窗口的范围

[0

s,4000s]

，双向侧摆角

度的范围为

[

−25

◦

,25

◦

]

. 根据实际任务观测规划场

景的特点对各任务元素进行归一化取值. 每个任务

x

i

=

(

s

i

,d

i

)

的元素设定如表1所示，其中

[

a,b

]

表示对

应元素数值随机产生，满足

a

到

b

之间的均匀分布.

3.3 模型的训练

采用3.1节所介绍的超参数设定，采用3.2节

所介绍的数据集，使用Actor Critic算法对MHA-

PN算法模型进行训练，收敛曲线如图2所示. 图

中，s为训练步长，

L

Actor

为训练过程中Actor网络

的损失值，

L

Critic

为Critic网络的损失值.

使用训练好的模型，可以直接对长度为50的

输入样本序列进行端到端的推理，推理结果如图3

所示. 图中，t为时间. 每个横条表示任务执行的时

间窗口，横条上的标号表示对应任务的执行顺

序，时间窗口间的连线表示任务执行的转移过程.

该样本算例的推理结果显示，卫星从位置start开

始依次对规划任务序列进行观测，在任务转移时

进行卫星姿态机动，到达位置end时结束本次过

境的对地目标观测.

采用相同的超参数设定，在相同的硬件平台

表 1 数据集中每个任务的元素设定

Tab.1 Element settings for each task in dataset

元素设定元素设定

ws

[0，4.0]

m

[0, 0.01]

pos

[0，0.5]

win1

we

[ws+0.03，ws+0.08]

acc1

d

[0.01，0.02]

mem0.5

r

[0.1，0.9]

pow0.5

e

[0，0.01]

pos0

400

浙 江 大 学 学 报（工学版）第 55 卷

r

100

o

t

c

A

0

L

−100

02 0004 0006 0008 000

s

(a) Actor 的损失

75

%

50

/

R

25

0

02 0004 0006 0008 000

s

(b) 收益率

10

c

i

t

i

5

r

C

L

−5

0

02 0004 0006 0008 000

s

(c) Critic 的损失

图 2 模型训练的损失和收益曲线

Fig.2 Loss and reward curves for model training

50

40

5

6

30

30

17

22

27

2

结束

)

(

1

3

12

13

18

°

/

s

20

4

14

19

24

o

23

29

p

10

7

8

9

20

26

0

11

15

16

21

25

28

−10

开始

10

01 0002 0003 0004 000

t/s

图 3 模型的推理结果示意图

Fig.3 Schematic diagram of reasoning results of model

上对Nazari等

[12]

所使用的PN模型和MHA-PN模

型进行训练，模型的收益率

R

和训练时间

T

的对比

如表2所示. 表中，

V

rate

为速度提升率. 可以看出，

MHA-PN算法可以获得更高的收益率和更快的训

练速度，速度提升率为

20.0%.

表 2 PN算法和MHA-PN算法收益率和训练时长的对比

Tab.2 Comparison of reward rate and training time between

PN algorithm and MHA-PN algorithm

算法

R /%

T /（s·epoch

−1

）

V

rate

/%

PN69.27 214.7−

MHA-PN

69.65 770.9

20.0

3.4 算法泛化能力对比

在序列长度为50的数据集上训练好的模型，

可以对不同长度的样本序列进行推理. 在实际的

卫星任务规划场景中，要求模型对不同长度的样

本序列具有较好的泛化能力. 对比不同序列长度

下Nazari等

[12]

所使用的PN算法和MHA-PN算法

的表现，为了减小实验的随机性，将每个长度的

样本数设置为100. 不同序列长度下收益率

R

的分

布如图4所示.

80

65

%

60

/

R

70

%

/

55

60

R

50

45

MHA-PNPNMHA-PNPN

(a) 长度为 50

(b) 长度为 100

60

50

%

50

%

40

/

/

R

40

R

30

30

MHA-PNPN

MHA-PNPN

(c) 长度为 125

(d) 长度为 150

50

50

%

40

%

40

/

/

R

30

R

30

20

20

MHA-PNPN

MHA-PNPN

(e) 长度为 175(f) 长度为 200

图 4 不同长度下模型收益率的分布

Fig.4 Distribution of model reward at different lengths

如图4（a）~（f）所示分别对应长度

n

=50、100、

125、150、175、200样本序列的收益率分布. 可以

看出，随着输入序列长度的增加，收益率

R

产生了

明显的下降. 这是由于任务分布的时间跨度是固

定的，当输入序列长度增加时任务分布更加密集，

从而产生更多时间窗口冲突的任务. 对于不同长

度的样本序列，MHA-PN算法所获得的收益率都

要优于Nazari等

[12]

所使用的PN算法. 随着序列

长度的增加，MHA-PN算法收益率的优势也越来

越明显，说明MHA-PN算法可以更好地泛化在密

集对地观测场景下的任务规划求解上. 在不同序

列长度下，模型收益率的均值对比如

表3所示.

表 3 不同长度下模型收益率的均值对比

Tab.3 Mean comparison of model rewards at different lengths

%

算法

n=50n=100n=125n=150n=175n=200

PN68.7553.0544.7232.8827.3825.31

MHA-PN69.4553.3648.9144.4341.6838.11

3.5 MHA-PN算法对比蚁群优化算法

针对同样的卫星观测任务规划问题模型，

赵凡宇

[19]

基于蚁群优化（ant colony optimization，

ACO）算法对多目标卫星观测任务规划问题进行

求解. 将在序列长度为50的数据集上训练所得的

MHA-PN算法模型和ACO算法分别对收益率和

求解时间

T

′

进行对比，输入样本序列的长度分别

设置为50、75和100. 对比结果如表4所示. 可以

看出，对于不同长度的输入序列，MHA-PN算法

获得了更高的收益率和更快的求解速度

.

第 2 期

马一凡, 等：基于改进指针网络的卫星对地观测任务规划方法[J]. 浙江大学学报：工学版,

2021, 55(2): 395–401.401

表 4 MHA-PN算法和ACO算法收益率和求解时间的对比

Tab.4 Comparison of reward rate and solution time between

MHA-PN algorithm and ACO algorithm

n

算法

R /%

T

′

/s

50ACO30.520.904

50MHA-PN59.450.194

75ACO23.311.497

75MHA-PN50.750.221

100ACO19.752.293

100MHA-PN45.730.370

4 结　语

对卫星观测任务规划问题进行建模，并基于深

度强化学习的方法对卫星观测任务规划问题进行

求解. 相比于启发式算法，训练好的模型可以直接

对输入序列进行端到端的推理，避免迭代求解的过

程，极大提高了求解效率. 在Nazari等

[12]

所使用的

PN算法的基础上，借鉴多头注意力机制的思想，提

出MHA-PN算法. 由实验结果可知，MHA-PN算

法相比于改进前的PN算法可以获得更高的收益率

和更快的训练速度. 对于不同长度的输入序列，

MHA-PN算法具有更强的泛化能力，算法在实际卫

星观测任务规划应用场景下具有更高的适用性.

后续工作将会探索更高效的算法模型结构和

训练算法，考虑任务执行开始时间动态变化、多

种任务类型、多圈次观测等更为复杂的观测任务

规划约束，并进一步将深度强化学习的方法应用

在多星联合对地观测任务规划问题上.

参考文献(References):

[1]

刘晓路, 何磊, 陈英武, 等. 面向多颗敏捷卫星协同调度的自适

应大邻域搜索算法[C]//第四届高分辨率对地观测学术年会论

文集. 武汉: 国防科学技术大学信息系统与管理学院, 2017.

LIU Xiao-lu, HE Lei, CHEN Ying-wu, et al. An adaptive large

neighborhood search algorithm for multiple agile satellites [C]//

Proceedings of 4th Annual Conference on High Resolution

Earth Observation. Wuhan: School of Information Systems and

Management, National University of Defense Technology, 2017.

[2]

郭浩, 邱涤珊, 伍国华, 等. 基于改进蚁群算法的敏捷成像卫星

任务调度方法[J]. 系统工程理论与实践, 2012(11): 185–191.

GUO Hao, QIU Di-shan, WU Guo-hua, et al. Agile imaging

satellite task scheduling method based on improved ant colony

algorithm [J]. System Engineering Theory and Practice,

2012(11): 185–191.

[3]

王法瑞. 基于改进遗传算法的微小卫星自主任务规划方法研

究[D]. 哈尔滨: 哈尔滨工业大学, 2017.

WANG Fa-rui. Research on autonomous task planning method of

micro satellite based on improved genetic algorithm [D]. Harbin:

Harbin Institute of Technology, 2017.

[4]

贺仁杰, 高鹏, 白保存, 等. 成像卫星任务规划模型、算法及其

应用[J]. 系统工程理论与实践, 2011(3): 29–40.

HE Ren-jie, GAO Peng, BAI Bao-cun, et al. Imaging satellite

mission planning model, algorithm and application [J]. System

Engineering Theory and Practice, 2011(3): 29–40.

[5]

陈英武, 方炎申, 李菊芳, 等. 卫星任务调度问题的约束规划模

型[J]. 国防科技大学学报, 2006(5): 126–132.

CHEN Ying-wu, FANG Yan-shen, LI Ju-fang, et al. Constrained

programming model for satellite task scheduling problem [J].

Journal of National University of Defense Technology,

2006(5): 126–132.

[6]HOCHREITER S, SCHMIDHUBER J. Long short-term

memory [J]. Neural Computation, 1997, 9(8): 1735–1780.

[7]CHUNG J, GULCEHRE C, CHO K, et al. Empirical evaluation

of gated recurrent neural networks on sequence modeling [J/OL].

[2020-02-29]. /abs/1412.3555.

[8]BAHDANAU D, CHO K, BENGIO Y. Neural machine

translation by jointly learning to align and translate [J/OL]. [2020-

02-29]. /abs/1409.0473.

[9]VINYALS O, FORTUNATO M, JAITLY N. Pointer networks

[C]// International Conference on Neural Information

Processing Systems. Montreal: MIT Press, 2015.

10]BELLO I, PHAM H, LE Q V, et al. Neural combinatorial

optimization with reinforcement learning [J/OL]. [2020-02-29].

/abs/1611.09940.

11]MNIH V, BADIA A P, MIRZA M, et al. Asynchronous methods

for deep reinforcement learning [J/OL]. [2020-02-29]. arxiv.

org/abs/1602.01783.

12]NAZARI M, OROOJLOOY A, SNYDER L, et al. Reinforcement

learning for solving the vehicle routing problem [J/OL]. [2020-

02-29]. /abs/1802.04240.

13]DAI H, KHALIL E B, ZHANG Y, et al. Learning combinatorial

optimization algorithms over graphs [J/OL]. [2020-02-29].

/abs/1704.01665.

14]DAI H, DAI B, SONG L. Discriminative embeddings of latent

variable models for structured data [J/OL]. [2020-02-29].

/abs/1603.05629.

15]KOOL W, HOOF H V, WELLING M. Attention, learn to solve

routing problems! [J/OL]. [2020-02-29]. /abs/

1803.08475.

16]VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all

you need [J/OL]. [2020-02-29]. /abs/1706.03762v4.

17]VINYALS O, BENGIO S, KUDLUR M. Order matters: sequence

to sequence for sets [J/OL]. [2020-02-29]. /abs/

1511.06391.

18]KINGMA D, BA J. Adam: a method for stochastic optimization

[J/OL]. [2020-02-29]. /abs/1412.6980.

19]

赵凡宇. 航天器多目标观测任务调度与规划方法研究[D]. 北

京: 北京理工大学, 2015.

ZHAO Fan-yu. Research on scheduling and planning methods of

spacecraft multi-object observation mission [D]. Beijing: Beijing

Institute of Technology, 2015.

[

[

[

[

[

[

[

[

[

[