浙江大学学报(工学版), 2021, 55(2): 395-401 doi: 10.3785/j.issn.1008-973X.2021.02.020

计算机与控制工程

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

马一凡,, 赵凡宇,, 王鑫, 金仲和

1. 浙江大学 微小卫星研究中心,浙江 杭州 310027

2. 浙江省微纳卫星研究重点实验室,浙江 杭州 310027

Satellite earth observation task planning method based on improved pointer networks

MA Yi-fan,, ZHAO Fan-yu,, WANG Xin, JIN Zhong-he

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

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

通讯作者: 赵凡宇,男,博士后. orcid.org/0000-0002-5239-2531. E-mail: zfybit@zju.edu.cn

收稿日期: 2020-03-11  

基金资助: 国家杰出青年科学基金资助项目(61525403)

Received: 2020-03-11  

Fund supported: 国家杰出青年科学基金资助项目(61525403)

作者简介 About authors

马一凡(1996—),男,硕士生,从事卫星自主任务规划研究.orcid.org/0000-0001-9762-0246.E-mail:21860251@zju.edu.cn , E-mail:21860251@zju.edu.cn

摘要

针对卫星观测任务规划问题约束复杂、求解空间大和输入任务序列长度不固定的特点,使用深度强化学习(DRL)方法对卫星观测任务规划问题进行求解. 综合考虑时间窗口约束、任务间转移机动时间和卫星电量、存储约束,对卫星观测任务规划问题进行建模. 基于指针网络(PN)的运行机制建立序列决策算法模型,使用Mask向量来考虑卫星观测任务规划问题中的各类约束,并通过Actor Critic强化学习算法对模型进行训练,以获得最大的收益率. 借鉴多头注意力(MHA)机制的思想对PN进行改进,提出多头注意力指针网络(MHA-PN)算法. 根据实验结果可以看出,MHA-PN算法显著提高了模型的训练速度和泛化性能,训练好的MHA-PN算法模型可以直接对输入序列进行端到端的推理,避免传统启发式算法迭代求解的过程,具有较高的求解效率.

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

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.

Keywords: satellite observation task planning ; combinatorial optimization problem ; deep reinforcement learning ; pointer networks (PN) ; Actor Critic ; multi-head attention pointer networks (MHA-PN)

PDF (907KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

马一凡, 赵凡宇, 王鑫, 金仲和. 基于改进指针网络的卫星对地观测任务规划方法. 浙江大学学报(工学版)[J], 2021, 55(2): 395-401 doi:10.3785/j.issn.1008-973X.2021.02.020

MA Yi-fan, ZHAO Fan-yu, WANG Xin, JIN Zhong-he. Satellite earth observation task planning method based on improved pointer networks. Journal of Zhejiang University(Engineering Science)[J], 2021, 55(2): 395-401 doi:10.3785/j.issn.1008-973X.2021.02.020

卫星观测任务规划问题是在考虑时间窗口和资源约束的条件下,对卫星资源加以分配,制定出合理的任务观测序列,从而使有限的卫星资源得以高效利用. 卫星成本高昂,星上资源有限,所以制定出合理的任务观测序列显得尤为重要. 卫星观测任务规划是提高卫星运行效率和降低成本的基础和关键,成为航空航天、计算机、运筹学的研究热点之一[1]. 卫星观测任务规划问题是一类多约束组合优化问题,模型的求解空间大. 目前国内外的研究者对卫星任务观测规划问题进行了研究,并基于智能优化算法对卫星观测任务规划问题进行求解,比如蚁群算法[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 reinforcement 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 = \left\{ {{x_1},{x_2},\cdots,{x_M}} \right\}$$M$为候选任务个数. 将每个候选任务定义为 ${x_i} = \left\{ {{\rm{w}}{{\rm{s}}_i},} \right.$ $\left. {{\rm{po}}{{\rm{s}}_i},{\rm{w}}{{\rm{e}}_i},{d_i},{r_i},{e_i},{m_i}} \right\}$${x_i}$中的元素分别为任务的时间窗口的开始时间、卫星在满足侧摆角度限制条件下进行双向侧摆时,相对于其中一侧边界的位置、时间窗口的结束时间、观测所需的持续时间、观测所获得的收益(执行优先级)、观测的电量消耗和观测的存储量消耗. 规划得到的任务集合为 $Y = \left\{ {{y_1},{y_2},\cdots,{y_N}} \right\}$$N$为规划结果中执行任务的个数.

假设在侧摆过程中消耗的时间为 ${t_{{\rm{sle}}}}$,在卫星姿态调整的机动过程中单位长度消耗的时间为 ${T_{\rm{s}}}$,下一个任务执行的开始时间大于当前任务执行结束时间和卫星侧摆机动时间之和,时间窗口约束的公式为

${\rm{w}}{{\rm{s}}_{i + 1}}{\rm{ > w}}{{\rm{s}}_i} + {d_i} + {t_{{\rm{sle}}}},$

${t_{{\rm{sle}}}} = \left( {{\rm{po}}{{\rm{s}}_{i + 1}} - {\rm{po}}{{\rm{s}}_i}} \right) {T_{\rm{s}}}.$

假设提供的存储总量为 ${M_{{\rm{tot}}}}$,提供的总电量为 ${E_{{\rm{tot}}}}$,卫星在侧摆过程中消耗的电量为 ${e_{{\rm{sle}}}}$,在卫星姿态调整的机动过程中单位长度消耗的电量为 ${e_{\rm{s}}}$,指示函数 $\ell \left( {{y_i}} \right)$表示任务 ${y_i}$被执行,则须满足的存储约束和电量约束为

$\sum\limits_{i = 1}^N \ell \left( {{y_i}} \right){m_{{i}}} \leqslant {M_{{\rm{tot }}}},$

$\sum\limits_{i = 1}^N \ell \left( {{y_i}} \right){e_{{i}}} + {e_{{\rm{sle }}}} \leqslant {E_{{\rm{tot }}}},$

${e_{{\rm{sle}}}} = \sum\limits_{i = 0}^{N - 1} {\left( {{\rm{po}}{{\rm{s}}_{i + 1}} - {\rm{po}}{{\rm{s}}_i}} \right)} {e_{\rm{s}}},$

$\ell \left( {{y_i}} \right) = \left\{ {\begin{array}{*{20}{l}} {1,}&{{\text{任务}}\;{y_{i{\kern 1pt} }}{\kern 1pt} {\text{被执行}}}; \\ {0,}&{\text{其他}} . \end{array}} \right.$

综合考虑各类约束,将收益率 ${R}$作为优化的目标,定义目标函数为

${R} = {{\sum\limits_{j = 1}^N \ell \left( {{y_j}} \right){r_j}} \Bigg/ {\sum\limits_{i = 1}^M \ell \left( {{x_i}} \right){r_i}}}.$

2. 算法模型建立和训练

2.1. 输入任务集合

将输入任务集合 $X = \left\{ {{x_1},{x_2},\cdots,{x_M}} \right\}$中的每个任务 ${x_i}$分为两部分,分别为静态元素集合 ${s_i}$和动态元素集合 $d_i^t$. 在模型的解码阶段的每个解码时间步骤 $t$ 时,静态元素保持不变,动态元素会根据输出节点发生动态变化. 将输入序列中的静态元素集合定义为 ${s_i}\! = \!\left\{ {{\rm{w}}{{\rm{s}}_i},{\rm{po}}{{\rm{s}}_i},{\rm{w}}{{\rm{e}}_i},{d_i},{r_i},{e_i},{m_i}} \right\}$,动态元素集合定义为 $d_i^t = \left\{ {{\rm{win}}_i^t,{\rm{acc}}_i^t,{\rm{mem}}_i^t,{\rm{pow}}_i^t,{\rm{pos}}_i^t} \right\}$$ {\rm{win}}_{i}^{t}{\text{、}}{\rm{acc}}_{i}^{t}{\text{、}}{\rm{mem}}_{i}^{t}{\text{、}} {\rm{pow}}_{i}^{t}{\text{、}}{\rm{pos}}_{i}^{t}$分别为在解码时间步骤 $t$时,任务是否满足时间窗口约束的标记、任务是否已经访问过的标记、卫星剩余的存储量、卫星剩余的电量、卫星侧摆所在的位置. 此时,可以将输入任务集合重新定义为 $X = \left\{ {x_i^t = \left( {{s_i},d_i^t} \right),i = 0,1, \cdots ,M} \right\}$$x_i^t$中的静态元素和动态元素可以看作任务 ${x_i}$的特征,包含任务 ${x_i}$的信息和在时间步骤 $t$时的状态.

2.2. 模型整体结构介绍

提出MHA-PN算法对卫星观测任务规划问题进行求解,算法的模型结构如图1所示. MHA-PN算法整体是基于Seq2Seq[12]的结构,分为编码器和解码器两部分.

图 1

图 1   MHA-PN算法模型结构

Fig.1   Model structure of MHA-PN algorithm


1)编码器部分. 使用一维卷积层作为Embedding Layer将 $X = \left\{ {x_1^t,x_2^t,\cdots,x_5^t} \right\}$输入任务序列中的每个任务映射为一个矩阵,即对于序列中的每个输入任务 $x_i^t,\;\;i \in \left[ {1,5} \right]$,Embedding Layer将其映射为矩阵 $\bar {{x}}_i^t = \left[ {{{\bar {{s}}}_i},\bar {{d}}_i^t} \right],\;\;i \in \left[ {1,5} \right]$

2)解码器部分. 使用GRU保存已解码序列的信息. 在每个解码时间步骤 $t$,根据编码器的输出矩阵 $\bar {{x}}_i^t = \left[ {{{\bar {{s}}}_i},\bar {{d}}_i^t} \right]$、GRU的隐含层状态 ${{{h}}^t}$${\rm{Mask}}$向量,基于MHA-PN机制计算输出节点的概率分布. 最后,选择概率值最大的节点作为输出节点.

2.3. Pointer Networks应用

Pointer Networks机制可以描述为:在每个解码时间步骤 $t$,使用注意力机制和Glimpse机制[17]计算得到的Softmax概率值,指向输入序列中下一个要访问的节点. 具体计算过程[12]如下.

1)通过加法注意力机制(additive attention)计算对齐向量(alignment vector):

${{{a}}^t} = {\rm{softmax}}\; \left( {{{V}}_{\rm{a}}^{\rm{T}}\tanh\; \left( {{{{W}}_{\rm{a}}}\left[ {\bar {{x}}_i^t;{{{h}}^t}} \right]} \right)} \right).$

式中: ${{{h}}^t}$为解码器GRU在时间步骤 $t$时的输出, ${{{V}}_{\rm{a}}}$${{{W}}_{\rm{a}}}$为训练参数.

2)对输入序列的嵌入矩阵进行加权累加得到背景矩阵(context matrix):

${{{c}}^t} = \sum\limits_{i = 1}^M {{{a}}_i^t} \bar {{x}}_i^t.$

3)通过Glimpse机制得到softmax概率输出:

${{u}}_i^t = \tanh \;\left( {{{{W}}_{\rm{c}}}\left[ {{{\bar x}}_i^t;{{{c}}^t}} \right]} \right),$

${{P}}\left( {{y^{t + 1}}|{Y^t},{X^t}} \right) = {\rm{softmax}}\;\left( {{{V}}_{\rm{c}}^{\rm{T}}{{u}}_i^t + \ln \;({\bf{Mask}})} \right).$

式中:Mask为Mask向量, ${{{V}}_{\rm{c}}}$${{{W}}_{\rm{c}}}$为训练参数.

2.4. MHA-PN算法

借鉴多头注意力机制[16]的思想,对PN算法进行改进,得到MHA-PN算法. 在解码时间步骤 $t$时,MHA-PN算法将注意力机制中的 ${\bar {{s}}_i}$$\bar {{d}}_i^t$${{{h}}^t}$平均划分为 $n$部分. 假设 ${\bar {{s}}_i}$$\bar {{d}}_i^t$${{{h}}^t}$的维度为 ${d_{{\rm{mod}}}}$,划分后各部分的维度为 ${d_n}$,则有:

${d_{{\rm{mod}}}} = {d_n} n.$

MHA-PN算法在划分后的 $n$部分上分别进行式(8)~(10)的运算,然后将各部分所得的结果进行合并,最后经式(11)计算后得到指向输入序列的概率值.

多头注意力机制能够综合不同表示子空间中模型所学习到的信息,提高模型的学习能力. 由于整个过程是并行计算的,能提升模型的计算效率,加快模型的训练.

2.5. Mask向量和解码器

使用Mask向量将约束加入到任务的选择过程中,其长度和输入序列长度相等,每位的取值为0或1. 当Mask向量某位的值为0时,经式(11)计算得到对应位的Softmax概率值为0,可以将对应的任务排除. 将Mask向量初始化为 $\left[ {1,\;0,\;0,\; \cdots ,\;0} \right]$,保证从第1个理想任务开始执行.

使用GRU[7]搭建模型的解码器,在模型解码的每个时间步骤 $t$,解码器中GRU单元的输出为 ${{{h}}^t}$,结合Mask向量进行式(11)的运算,计算所得的Softmax概率指向要输出的节点 ${y^{t + 1}}$. 将节点 ${y^{t + 1}}$对应的静态元素经Embedding Layer后得到 ${\bar {{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向量为 $\left[ {0,\;0,\;0,\; \cdots ,\;0} \right]$.

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

算法: Decoder Algorithm

1: input: task set $X = \left\{ {{x_1},{x_2},\cdots,{x_M}} \right\}$

2: output: $Y = \left\{ {{y_1},{y_2},\cdots,{y_N}} \right\}$

3: initialize max_steps with n

4: initialize mask vector with $\left[ {1,0,\cdots,0} \right]$

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

6:   if mask all is 0 do

7:    break

8:   end if

9:  calculate ${{P}}\left( {{y^{t + 1}}|{Y^t},{X^t}} \right)$ by Eq.(11)

10:  choose ${y^{t + 1}}$ accroding to ${{P}}\left( {{y^{t + 1}}|{Y^t},{X^t}} \right)$

11:  calculate ${{\bar {{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 = \left\{ {{y_1},{y_2}, \cdots ,{y_N}} \right\}$,根据概率的链式法则,产生这个输出序列的概率为

$P\left( {Y|{X^0}} \right) = \prod\limits_{t = 0}^N P \left( {{y^{t + 1}}|{Y^t},{X^t}} \right).$

如果在满足约束条件的情况下,通过策略 ${\text{π}}$得到输出序列 $Y$,那么模型训练的目标为找到最优的策略 ${{\text{π}} ^*}$,使得输出的序列可以获得最大的收益率.

使用Actor Critic算法[11]对模型进行训练,其由2个神经网络构成.

1)Actor:MHA-PN算法模型,对输入序列进行预测,得到输出序列中各节点的概率. 假设其参数为 $\theta $,对参数的梯度为

${\nabla _\theta } \approx \frac{1}{N}\sum\limits_{n = 1}^N {\left( {{R_n} - V\left( {X_n^0;\varphi } \right)} \right)} {\nabla _\theta }\ln \;\left( {P\left( {{Y_n}|X_n^0} \right)} \right).$

式中: $X_n^0$为第 $n$个样本序列, ${Y_n}$为Actor对 $X_n^0$的规划输出结果, ${R_n}$为规划得到的收益率, $P\left( {{Y_n}|X_n^0} \right)$为输出序列中每个节点的概率.

2)Critic:计算输入序列可获得收益率的评估值. 假设其参数为 $\varphi $,对参数的梯度为

${\nabla _\varphi } = \frac{1}{N}\sum\limits_{n = 1}^N {{\nabla _\varphi }} {\left( {{R_n} - V\left( {X_n^0;\varphi } \right)} \right)^2}.$

式中: $V\left( {X_n^0;\varphi } \right)$为Critic对第 $n$个样本序列 $X_n^0$可获得收益率的估计.

训练部分的伪代码如下.

算法: Actor Critic Algorithm

1: initialize actor network with random weights $\theta$

2: initialize critic network with random weights $\varphi$

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

4:  reset gradients: ${\rm{d}}\theta \leftarrow 0,{\rm{d}}\varphi \leftarrow 0$

5:  sample N instances from training data

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

7:   initialize step counter $t \leftarrow 0$

8:    repeat

9:    choose $y_n^{t + 1}$ accroding to $P\left( {y_n^{t + 1}|Y_n^t,X_n^t} \right)$

10:    observe new state $X_n^{t + 1}$

11:     $t \leftarrow t + 1$

12:    until termination condition is satisfied

13:   compute reward ${R_n} = R\left( {{Y_n},X_n^0} \right)$

14:   end for

15:   ${\rm{d}}\theta \leftarrow \dfrac{1}{N}\displaystyle\sum\limits_{n = 1}^N {\left( {{R_n} - V\left( {X_n^0;\varphi } \right)} \right)} {\nabla _\theta }\ln\;\left( { P\left( {{Y_n}|X_n^0} \right)} \right)$

16:   ${\rm{d}}\varphi \leftarrow \dfrac{1}{N}\displaystyle\sum\limits_{n = 1}^N {{\nabla _\varphi }} {{\left( {{R_n} - V\left( {X_n^0;\varphi } \right)} \right)}^2}$

17:  update $\theta$ using ${\rm{d}}\theta$

18:  update $\varphi$ using ${\rm{d}}\varphi$

19: end for

3. 训练和测试结果

3.1. 实验设置

实验环境设置如下:操作系统为Ubuntu16.04,CPU为Intel Xeon E5-2620,GPU为RTX2080Ti,在GPU上对模型进行训练,实验代码基于Pytorch深度学习框架编写. 采用MHA-PN模型对卫星观测任务规划问题进行求解,训练的超参数设定如下:批样本数量(batch size)为128,训练轮次(epoch)为1,Actor网络的学习率为 ${\rm{5}} \times {\rm{1}}{{\rm{0}}^{{\rm{ - 4}}}}$,Critic网络的学习率为 ${\rm{5}} \times {\rm{1}}{{\rm{0}}^{{\rm{ - 4}}}}$,学习率衰减步长为 ${\rm{2}}\,{\rm{000}}$,学习率衰减比例为0.8,Embedding Layer的隐含层维度为512,GRU的隐含层维度为512,多头注意力头数为8,Dropout比率为0.1,采用Adam优化器[18].

3.2. 数据集介绍

将训练序列样本的数量设定为 ${\rm{1}}{{\rm{0}}^6}$,每个序列样本的长度设定为50. 观测任务规划的场景假设为任务时间窗口的范围 $\left[ {0\;{\rm{s}},4\;000\;{\rm{s}}} \right]$,双向侧摆角度的范围为 $\left[ {{\rm{ - }}{{25}^ \circ },{{25}^ \circ }} \right]$. 根据实际任务观测规划场景的特点对各任务元素进行归一化取值. 每个任务 ${x_i} = \left( {{s_i},{d_i}} \right)$的元素设定如表1所示,其中 $\left[ {a,b} \right]$表示对应元素数值随机产生,满足 $a$$b$之间的均匀分布.

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

Tab.1  Element settings for each task in dataset

元素 设定 元素 设定
ws [0,4.0] m [0, 0.01]
pos [0,0.5] win 1
we [ws+0.03,ws+0.08] acc 1
d [0.01,0.02] mem 0.5
r [0.1,0.9] pow 0.5
e [0,0.01] pos 0

新窗口打开| 下载CSV


3.3. 模型的训练

采用3.1节所介绍的超参数设定,采用3.2节所介绍的数据集,使用Actor Critic算法对MHA-PN算法模型进行训练,收敛曲线如图2所示. 图中,s为训练步长, ${L_{{\rm{Actor}}}}$为训练过程中Actor网络的损失值, ${L_{{\rm{Critic}}}}$为Critic网络的损失值.

图 2

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

Fig.2   Loss and reward curves for model training


使用训练好的模型,可以直接对长度为50的输入样本序列进行端到端的推理,推理结果如图3所示. 图中,t为时间. 每个横条表示任务执行的时间窗口,横条上的标号表示对应任务的执行顺序,时间窗口间的连线表示任务执行的转移过程. 该样本算例的推理结果显示,卫星从位置start开始依次对规划任务序列进行观测,在任务转移时进行卫星姿态机动,到达位置end时结束本次过境的对地目标观测.

图 3

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

Fig.3   Schematic diagram of reasoning results of model


采用相同的超参数设定,在相同的硬件平台上对Nazari等[12]所使用的PN模型和MHA-PN模型进行训练,模型的收益率 $R$和训练时间 $T$的对比如表2所示. 表中, ${V_{{\rm{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 Vrate /%
PN 69.2 7 214.7
MHA-PN 69.6 5 770.9 20.0

新窗口打开| 下载CSV


3.4. 算法泛化能力对比

在序列长度为50的数据集上训练好的模型,可以对不同长度的样本序列进行推理. 在实际的卫星任务规划场景中,要求模型对不同长度的样本序列具有较好的泛化能力. 对比不同序列长度下Nazari等[12]所使用的PN算法和MHA-PN算法的表现,为了减小实验的随机性,将每个长度的样本数设置为100. 不同序列长度下收益率 $R$的分布如图4所示.

图 4

图 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=50 n=100 n=125 n=150 n=175 n=200
PN 68.75 53.05 44.72 32.88 27.38 25.31
MHA-PN 69.45 53.36 48.91 44.43 41.68 38.11

新窗口打开| 下载CSV


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

针对同样的卫星观测任务规划问题模型,赵凡宇[19]基于蚁群优化(ant colony optimization,ACO)算法对多目标卫星观测任务规划问题进行求解. 将在序列长度为50的数据集上训练所得的MHA-PN算法模型和ACO算法分别对收益率和求解时间 $T'$进行对比,输入样本序列的长度分别设置为50、75和100. 对比结果如表4所示. 可以看出,对于不同长度的输入序列,MHA-PN算法获得了更高的收益率和更快的求解速度.

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

Tab.4  Comparison of reward rate and solution time between MHA-PN algorithm and ACO algorithm

n 算法 R /% $T' $ /s
50 ACO 30.52 0.904
50 MHA-PN 59.45 0.194
75 ACO 23.31 1.497
75 MHA-PN 50.75 0.221
100 ACO 19.75 2.293
100 MHA-PN 45.73 0.370

新窗口打开| 下载CSV


4. 结 语

对卫星观测任务规划问题进行建模,并基于深度强化学习的方法对卫星观测任务规划问题进行求解. 相比于启发式算法,训练好的模型可以直接对输入序列进行端到端的推理,避免迭代求解的过程,极大提高了求解效率. 在Nazari等[12]所使用的PN算法的基础上,借鉴多头注意力机制的思想,提出MHA-PN算法. 由实验结果可知,MHA-PN算法相比于改进前的PN算法可以获得更高的收益率和更快的训练速度. 对于不同长度的输入序列,MHA-PN算法具有更强的泛化能力,算法在实际卫星观测任务规划应用场景下具有更高的适用性.

后续工作将会探索更高效的算法模型结构和训练算法,考虑任务执行开始时间动态变化、多种任务类型、多圈次观测等更为复杂的观测任务规划约束,并进一步将深度强化学习的方法应用在多星联合对地观测任务规划问题上.

参考文献

刘晓路, 何磊, 陈英武, 等. 面向多颗敏捷卫星协同调度的自适应大邻域搜索算法[C]//第四届高分辨率对地观测学术年会论文集. 武汉: 国防科学技术大学信息系统与管理学院, 2017.

[本文引用: 1]

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.

[本文引用: 1]

郭浩, 邱涤珊, 伍国华, 等

基于改进蚁群算法的敏捷成像卫星任务调度方法

[J]. 系统工程理论与实践, 2012, (11): 185- 191

[本文引用: 1]

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

[本文引用: 1]

王法瑞. 基于改进遗传算法的微小卫星自主任务规划方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2017.

[本文引用: 1]

WANG Fa-rui. Research on autonomous task planning method of micro satellite based on improved genetic algorithm [D]. Harbin: Harbin Institute of Technology, 2017.

[本文引用: 1]

贺仁杰, 高鹏, 白保存, 等

成像卫星任务规划模型、算法及其应用

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

[本文引用: 1]

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

[本文引用: 1]

陈英武, 方炎申, 李菊芳, 等

卫星任务调度问题的约束规划模型

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

DOI:10.3969/j.issn.1001-2486.2006.05.026      [本文引用: 1]

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

DOI:10.3969/j.issn.1001-2486.2006.05.026      [本文引用: 1]

HOCHREITER S, SCHMIDHUBER J

Long short-term memory

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

DOI:10.1162/neco.1997.9.8.1735      [本文引用: 1]

CHUNG J, GULCEHRE C, CHO K, et al. Empirical evaluation of gated recurrent neural networks on sequence modeling [J/OL]. [2020-02-29]. https://arxiv.org/abs/1412.3555.

[本文引用: 2]

BAHDANAU D, CHO K, BENGIO Y. Neural machine translation by jointly learning to align and translate [J/OL]. [2020-02-29]. https://arxiv.org/abs/1409.0473.

[本文引用: 1]

VINYALS O, FORTUNATO M, JAITLY N. Pointer networks [C]// International Conference on Neural Information Processing Systems. Montreal: MIT Press, 2015.

[本文引用: 1]

BELLO I, PHAM H, LE Q V, et al. Neural combinatorial optimization with reinforcement learning [J/OL]. [2020-02-29]. https://arxiv.org/abs/1611.09940.

[本文引用: 2]

MNIH V, BADIA A P, MIRZA M, et al. Asynchronous methods for deep reinforcement learning [J/OL]. [2020-02-29]. https://arxiv.org/abs/1602.01783.

[本文引用: 2]

NAZARI M, OROOJLOOY A, SNYDER L, et al. Reinforcement learning for solving the vehicle routing problem [J/OL]. [2020-02-29]. https://arxiv.org/abs/1802.04240.

[本文引用: 8]

DAI H, KHALIL E B, ZHANG Y, et al. Learning combinatorial optimization algorithms over graphs [J/OL]. [2020-02-29]. https://arxiv.org/abs/1704.01665.

[本文引用: 1]

DAI H, DAI B, SONG L. Discriminative embeddings of latent variable models for structured data [J/OL]. [2020-02-29]. https://arxiv.org/abs/1603.05629.

[本文引用: 1]

KOOL W, HOOF H V, WELLING M. Attention, learn to solve routing problems! [J/OL]. [2020-02-29]. https://arxiv.org/abs/1803.08475.

[本文引用: 1]

VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need [J/OL]. [2020-02-29]. https://arxiv.org/abs/1706.03762v4.

[本文引用: 2]

VINYALS O, BENGIO S, KUDLUR M. Order matters: sequence to sequence for sets [J/OL]. [2020-02-29]. https://arxiv.org/abs/1511.06391.

[本文引用: 1]

KINGMA D, BA J. Adam: a method for stochastic optimization [J/OL]. [2020-02-29]. https://arxiv.org/abs/1412.6980.

[本文引用: 1]

赵凡宇. 航天器多目标观测任务调度与规划方法研究[D]. 北京: 北京理工大学, 2015.

[本文引用: 1]

ZHAO Fan-yu. Research on scheduling and planning methods of spacecraft multi-object observation mission [D]. Beijing: Beijing Institute of Technology, 2015.

[本文引用: 1]

/