王桢朗,何慧群,周 军,金云飞
(1.上海卫星工程研究所,上海 201109;2.上海航天技术研究院,上海 201109)
由于卫星数量大量增加,导致卫星观测任务需求也井喷式发展[1]。传统集成大量功能的大型卫星被分解为多个单一功能的小型卫星,这些小型卫星具备较高的灵活性,并组成星群,可快速根据空间环境及任务变化调整自身情况,适应灵活任务需求[2-3]。这种情况下,会面临集中式决策模式信息传递难度大、时间复杂度过高等问题。随着边缘计算的发展,带来新的分布式决策模式,边缘节点具有一定的算力,并有自主决策能力[4-5]。该模式更适应未来的复杂环境及多变的任务需求,更适合多星观测任务分配。
可将上述问题理解为一个全局最优化问题,面对小规模问题时,采用确定性的精确算法,其问题规模变大后,会带来更复杂的时空条件约束,增大求解难度,甚至无法求解[6]。
强化学习算法是一种不断根据环境调整学习并受启发的算法,智能体通过不断地“试错”与环境进行交互,获得反馈并优化自身。随着深度强化学习技术的发展应用,该算法在动态路由、通信链路分配、边缘计算节点数据管理等领域取得了较为成功的应用[7-9]。在多星观测系统中,将卫星看作决策智能体,并将观测任务分配转化为一个多智能体强化学习任务。
当前由于暂未有多智能体深度强化学习算法在多星观测任务分配中的实际应用,因此本文做出以下工作[10]。
1)对多星观测场景建模。
2)提出一个基于多智能体深度强化学习的多星观测任务分配算法,在上述场景中解决分配问题。
3)设置对比算法,对比证明上述算法的优越性。
集中式决策与分布式决策是当前2 种主要决策方式[11],在集中式决策场景中,存在一个中心决策节点来处理全局的信息,将决策好的序列分配给卫星执行。而分布式决策系统中不存在为系统统一进行决策的中心决策节点,各卫星的调度方案均由自身结合获取的信息独立决策集中式决策方案,往往由于系统复杂度高、信息过多导致决策时效性和质量下降。同时面对通信受限的场景时,由于信息传递不到位,造成信息获取不全,可能会导致决策错误。
在多星观测任务分配中,由于卫星数量多,响应时间要求高,且可能面对通信受限的场景,集中式决策难以得出最优解,因此采用分布式决策系统解决该问题。分布式系统的各个子模块能按照自身获取的信息及预先确定的内置规则自行决策,但这些系统不能实时更新决策规则,在多星观测任务分配问题中,由于环境的动态性、任务的多样性、约束的多样性等原因,决策方案需要不断进行自我调整,人为更新速度跟不上应用环境的变化。
作为一种端到端的人工智能方法,强化学习不需要频繁地为新环境制定策略,其决策方案随着智能体与环境的动态交互制定并不断优化,且已被成功地应用于多个领域[12]。
强化学习是近年发展起来的机器学习方法,通过让智能体(Agent)与环境不断交互,进而在获得回报奖励的过程中不断学习并优化策略,达到获得最大累积奖励的目标。这一交互过程不断重复,最终智能体通过收集的数据,达到最优的策略。与监督学习和无监督学习不同的是,强化学习的智能体在学习与交互过程中,没有标准答案或事先制定的标签,而是尝试采取不同的行动来学习如何在给定的场景下获得最大的奖励。强化学习的框架如图1所示。
图1 强化学习的框架Fig.1 Frame of reinforcement learning
深度强化学习结合深度学习及强化学习的优点,其数学基础和建模工具是马尔可夫决策过程[13](Markov Decision Process,MDP)。这使得其算法能够更好地适应复杂、大规模、连续、离散、高维、时变、不准确、不确定等真实世界中的各种问题。
当环境中存在多个智能体交互时,即是一个多智能体系统[14](Multi-Agent System,MAS)。每个智能体都各自遵循强化学习的目标,且彼此竞争或协作,以最大化回报奖励。由于在系统中,智能体之间彼此互相作用影响,因此需要考虑联合动作对环境和策略制定的影响。与单智能体强化学习问题相比,其问题难度较高,两者之间主要存在以下区别。
1)环境的不稳定性:智能体在做决策的同时,由于其他智能体也在采取动作,环境状态会随着每个智能体采取动作而做出相应改变。
2)智能体获取信息的局限性:不一定能够获得全局的信息,智能体仅能获取局部的观测信息,但无法得知其他智能体的观测信息、动作、奖励等信息。
3)个体的目标一致性:各智能体的目标可能是最优的全局回报,也可能是各自局部回报的最优。
4)可拓展性:在大规模的多智能体系统中,会涉及高维度的状态空间和动作空间,对模型表达能力和真实场景中的硬件算力有一定的要求。
近年来,较多研究均将训练与执行过程拆分开来,采用策略-评论家算法(Actor-Critic,AC)来训练模型,训练阶段通过价值网络(Critic)获取全局信息来训练策略网络(Actor),执行阶段只留下Actor 网络独立根据自身获取的信息选取动作执行。
多星观测任务分配问题的模型构建是通过抽象多星观测任务分配问题中的各要素,使其成为马尔科夫决策过程中的状态、动作、回报等,进而构建马尔科夫决策模型,并在此基础上进一步设计深度强化学习算法框架。
大部分强化学习算法均可解释为马尔科夫决策过程在场景中,智能体会根据当前时刻的环境状态,通过内置策略,选取一个对应当前状态的动作,执行动作后,改变当前环境并获得回报奖励,得到序 列:s0,a0,r1,s1,a1,r2,s2,a2,r3,…,sn-1,an-1,rn,sn,此序列t时刻的数据元组st,at,rt+1,st+1即是一个马尔科夫决策过程。
马尔科夫决策过程其下一个时刻的状态只与当前时刻的状态有关,可表示为
式中:Pr为状态转移函数;h为在时间t之前的任意时间;s为当前的观测状态空间;s′为下一时刻状态。
在马尔科夫决策过程中,动作执行后一定会造成当前状态以一定概率向下一个状态转移,如图2所示。
图2 马尔科夫决策过程Fig.2 Diagram of the MDP
用元组(s,a,r,p)表示一个卡尔科夫决策过程,a为策略中可以执行的动作空间;为在状态s下执行决策动作a,并使过程从s状态转移到s′的状态转移概率为,并获得回报。表达式为
状态值函数表示在遵循某一策略情况下,转移状态与目标状态相似程度的函数,可以反映当前策略的好坏。在策略π下的状态值函数为
式中:V为状态价值函数;γ为折扣函数;π为当前策略。
当马尔科夫决策过程进行到一定程度转移状态非常接近目标状态时,即可得出最优状态值函数或最优动作值函数,并通过最优值函数推导获得最优策略π*,最优策略π*的推导公式如下:
最优状态值函数的一般形式如下:
式中:Rt为回报奖励总和;rt+k为在状态st+k时采用动作at+k后的回报奖励值,并通过最大化回报奖励求解最优策略π*和状态值函数Vπ(s)。
提取对多星任务的资源、任务、约束进行数学化抽象后的要素[15],再用马尔科夫决策过程对其描述,得出以下过程:智能体在当前环境中获取状态s,依据自身制定的策略π选择下一步要执行的动作a,执行过动作a后,动作影响会使环境状态转变至s′,并获得奖励回报r。多星观测任务分配的MDP模型如图3 所示。
图3 多星观测任务分配的MDP 模型Fig.3 MDP model for multi-satellite observation task allocation
根据之前建立的MDP 模型,假设在时间t下,给定当前智能体i的输入环境状态为Sit,智能体根据自身策略输出动作Ait,整个环境的环境状态空间为St={S1t,S2t,…,Sit},多智能体的联合动作集合为Ait={A1t,A2t,…,Ait},执行完当前动作获得奖励Rt,在多星观测任务分配方法中,星群之间是完全合作关系,所以共享奖励,可促进星群之间的合作,尽可能让全局收益最大化。同时执行完动作后,智能体i所处的状态Sit会以Pit(Sit|Sit+1,Ait)转移到下一时刻t+1 的状态Sit+1。
资源集中的智能体i在t时刻的状态信息可用元组表示,其中(xi,yi,zi,vxi,vyi,vzi)为当前智能体的位置坐标以及速度矢量,(pi1,pi2,…,pin)为智能体各项能力数值的集合。
任务集中的子任务j在t时刻的状态信息可用元组表示,其中(xj,yj,zj,vxj,vyj,vzj)为当前任务的位置坐标及速度矢量,为任务完成需要的各项指标数值的集合。
当智能体i与任务j的元组计算满足可见性约束dij,如式(7)~式(12),以及卫星各项能力值pin与任务各项能力需求的比值Pbij时,如式(13),在满足约束集要求时,Pbij越大说明该智能体i与任务j的匹配效果越好,在满足可见性约束dij=1 时,可以进行任务分配。
式中:heij为Pbij的调节系数,如智能体i的能力系数都大于任务j对应的能力系数时,则认为当前分配效果好,将赋值为2,否则赋值为1/2。
本文将多星观测任务的资源分配设计归结为对目标观测的离散控制问题,其取值范围为{a1,a2,…,an},n为目标数量,智能体i的动作决策表示:Ait=πi(·|Sit)。
对智能体的回报奖励函数进行以下设计:R为回报奖励函数,式(15)中第1 项为任务与智能体两者的能力匹配情况和的倒数,作为观测执行质量的体现,其中ai为智能体i的决策结果,第2 项为未分配任务的惩罚值,其中k为固定参数,用于调整回报奖励函数中的未分配任务对系统的影响程度,n0为未分配任务数。
在上述多星观测任务分配场景中,因为智能体之间是完全协作的,因此共享一个回报奖励值。
在多智能体深度确定性策略梯度算法(Multi-Agent Deep Deterministic Policy Gradient,MADDPG)[16]中,每个智能体都有一组Actor和Critic,其根据观测状态si,输出动作ai使智能体整体获得最大回报奖励;Critic 仅在进行中心化训练阶段使用,在训练阶段,Critic 根据Actor 输出的动作,对动作进行评价分析,并反馈给Actor,实现Actor 的调优。
模型训练的框图如图4 所示,图中MADDPG 算法是由多个智能体分别实现一个深度确定性策略梯度算法[17](Deep Deterministic Policy Gradient,DDPG)组成,所有智能体i从环境获取当前的观测数据si后,其在线策略网络(Online Actor,OA)根据si决策出动作ai,将其作为智能体i的动作输出,多个智能体决策过后组成动作集合a,环境受到动作集合a的影响,更新当前状态至s′,并反馈回报奖励r={r1,r2,…,ri},之后将获得的四元组(si,ai,ri,si′)存储到经验回放池[18](Experience Relay Pool,ERP)中,供下一步训练需要。
图4 MADDPG 模型训练的框Fig.4 Block diagram of MADDPG model training
在模型训练的过程中,从经验回放池中抽取小批量样本(Sample Mini-Batch,SMB)训练[19]。在线价值网络(Online Critic,OC)会把当前的(s,a)={s1,s2,…,si|a1,a2,…,ai}作为输入用于自身训练,输出一维的Q值Q(s,a),同时结合回放样本的Q′(s,a)以时序差分误差构建两者的MSE 损失函数,并结合奖励r利用梯度下降更新Online Critic 网络的参数,再通过软更新(Soft Update,SU)算法更新目标价值网络(Target Critic,TC)的参数,进而实现对网络参数的更新。在计算自身Actor 的前向传播时,Online Actor 只将自身局部观测到的s={s1,s2,…,si}作为其输入,输出一个确定的动作ai,同时计算时序差分误差的MSE损失函数,并结合Q(s,a) 利用随机梯度下降(Stochastic Gradient Descent,SGD)更新参数,再通过软更新算法更新目标策略网络(Target Actor,TA)的参数。
智能体的Actor 网络结构如图5 所示,其包括输入层、隐含层、Softmax 层、输出层,以及激活函数。将智能体观测到的自身与其他智能体和任务的信息作为观测状态si输入,状态si经神经网络的处理后获得的一维向量为对应每个动作选择[20],并使用Gumbel-softmax 方法激活函数,得到选择每个动作对应的概率pi,依此制定策略π,对应pi_max的动作ai作为智能体i在状态si时的输出结果。
图5 Actor 网络结构Fig.5 Diagram of the Actor network structure
智能体的Critic 网络结构如图6 所示,Critic 网络分为输入层、隐含层、输出层及激活函数,将所有智能体的状态信息s={s1,s2,…,si}和动作决策a={a1,a2,…,ai}作为输入,经神经网络处理后获得一个一维向量,再通过这个向量计算所有智能体共享的回报奖励值r={r1,r2,…,ri}。
图6 Critic 网络结构Fig.6 Diagram of the Critic network structure
根据以下算法完成模型训练后,各智能体根据制定的策略,独立地在不同观测状态下选择合适动作。
输入初始化策略网络参数θ={θ1,θ2,…,θM}和价值网络参数ϕ={ϕ1,ϕ2,…,ϕM}。
输出训练后的最优参数θ*,ϕ*。
为了证明基于上述设计的算法在建立的场景下具有有效性,选取DDPG 算法以及传统随机策略(Random)算法[21]作为对比算法。
本文设计了一个多星观测任务分配场景,在该场景中,有一定数量的通信受到限制的卫星和任务节点,各卫星处于固定运行的轨道上,观测任务目标节点随机生成在WGS84 坐标下地面或近地空间的位置[22],此外每个卫星均拥有3 种类型能力,如分辨率、能源、最大可视距离等,能力数值根据正态分布随机生成;对任务节点,也相应设置对这3 种能力的需求值,其大小根据正态分布随机生成[23]。各卫星节点没有中心决策节点对系统进行统一决策,各个卫星需自行根据观测情况并结合自身策略选择动作。由于该分配任务场景是完全协作的,所以各个卫星的动作回报奖励将作为各智能体的奖励,使得在协作的情况下,达到回报奖励的全局最大化,并以此回报奖励作为对算法性能的评估指标[24]。
本文算法采用Python 实现,硬件配置为1 台Geforce RTX 4080 显 卡、Intel-Corei7-12700KCPU的计算机,MADDPG 与DDPG 的网络参数设定采用相同的配置,见表1。
表1 网络超参数Tab.1 Hyperparameters of the network
采用MADDPG 算法时的回报奖励曲线如图7所示,横纵坐标分别表示训练回合数Epoch 及回报奖励Reward。由图7 可知,智能体获得的回报奖励值阶梯式变化,最终稳定收敛在88 左右。在模型开始训练阶段,智能体获得的回报奖励波动较大,因为该阶段智能体之间还未学会协同任务分配,导致其互相抢占相同任务,造成资源浪费。但由于不断“试错”,智能体在没有中心决策节点的情况下,也逐渐分阶段地学会了仅根据自身状态和观测信息的分布式协同任务分配策略。
图7 采用MADDPG 算法训练的智能体平均奖励曲线Fig.7 Average reward curve of agents trained by the MADDPG algorithm
采用DDPG 算法解决多星观测任务分配问题的训练曲线如图8 所示。由图8 可知,采用该方法时,从训练开始到结束回报奖励的波动起伏较大。由于智能体之间不共享回报奖励,导致其不是完全协作关系,并将彼此视为影响环境的因素,使得环境状态难以稳定下来,最终造成算法难以收敛。
图8 采用DDPG 算法训练的智能体平均奖励曲线Fig.8 Average reward curve of agents trained by the DDPG algorithm
采用Random 算法解决多星观测任务分配问题的训练曲线如图9 所示。由图9 可知,其大致收敛在65 左右,但比采用MADDPG 算法时收敛的回报奖励低,采用MADDPG 算法解决多星观测任务分配问题的效果更佳。
图9 采用Random 算法训练的平均奖励曲线Fig.9 Average reward curve trained by the Random algorithm
在天基星座快速发展的当下,卫星及任务需求大量增加,空间环境复杂,传统观测任务分配方案难以适应未来需求,因此要求卫星有更强大的自主决策能力。
本文设计的基于MADDPG 算法的多星观测任务分配算法,对动作空间的离散化改进动作空间选择[25],设计了合适的回报奖励函数优化决策方案,采用集中式训练、分布式执行的模式,赋予卫星一定的自主决策能力[26]。在训练阶段,综合全局信息开展训练;在执行阶段,卫星只需通过自身的观测情况,即可做出决策,使其在通信受限的场景下也能进行观测任务分配。实验结果显示,采用DDPG算法与Random 算法相比,采用MADDPG 训练出来的各智能体收敛更稳定,且能获得更高的回报奖励,说明其具备更好的协同能力,其多星观测任务分配方案效果更好。