(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210625202.X (22)申请日 2022.06.02 (71)申请人 北京理工大 学 地址 100081 北京市海淀区中关村南大街5 号 (72)发明人 卢少兆　张尧　叶吉　李新刚　 张昆鹏　 (74)专利代理 机构 北京正阳理工知识产权代理 事务所(普通 合伙) 11639 专利代理师 邬晓楠 (51)Int.Cl. G06F 30/20(2020.01) G06F 16/21(2019.01) G06F 16/245(2019.01) G06F 16/2453(2019.01)G06F 111/04(2020.01) G06F 111/06(2020.01) (54)发明名称 一种基于并行架构的空间大规模目标飞越 的序列规划方法 (57)摘要 本发明公开的一种基于并行架构的最优飞 越序列获取方法， 属于轨道设计与优化领域。 本 发明实现方法如下： 构建并行集束搜索算法， 将 兰伯特问题 求解并行化； 在任务时间窗口的起始 时刻确定航天器此时的状态， 进行并行集束搜索 得到目标访问的子序列； 然后将 子序列保存至数 据库中， 提取数据库中每个子序列末端的状态及 时刻， 从此状态出发再次进行并行集束搜索； 将 上述过程反复迭代， 生成子序列数据库； 对子序 列进行拼接， 生成一条完整的目标访问飞越序列 轨迹； 通过调整目标间转移时间以及优化飞越速 度进一步降低飞越序列的总速度增量。 本发明能 够显著提高飞越序列规划效率， 有效保证大规模 目标问题序列生成的最优性， 获取高精度低能耗 的航天器飞越序列。 权利要求书4页 说明书9页 附图4页 CN 115169075 A 2022.10.11 CN 115169075 A 1.一种基于并行架构的空间大规模目标飞越的序列规划方法， 其特征在于： 包括如下 步骤， 步骤一： 针对空间大规模目标飞越序列规划存在的优化效率低、 规划结果最优性难保 证的难题， 基于并行架构将兰伯特问题求解并行化， 针对不同的输入量， 同步计算得到各自 相应的结果； 得到兰伯特问题计算结果后， 并行计算出不同输入量对应的速度增量， 构建以 速度增量为指标的并行集束搜索算法， 该算法支持以更小的搜索步长来提高子序列获取的 最优性， 并提高空间大规模目标兰伯特问题的求 解效率； 步骤二： 给定飞越任务所需的飞越目标数量及飞越时间窗口， 对目标间的转移时间离 散化， 从时间窗口的起始时刻开始， 基于并行集束搜索算法生成子序列， 通过提取子序列终 端状态和时刻， 利用算法继续生成子序列， 反复迭代直至出发时刻大于飞越时间窗口的末 端值， 基于并行集束搜索算法能快速建立 飞越子序列数据库， 离线生成数据库， 并能够指导 多个飞越序列的生成； 步骤三： 通过在集束搜索算法中通过设置集束宽度， 使步骤二构建的数据库中子序列 在足够宽的集束宽度下进行拼接， 有效避免飞越序列拼接过程中提前落入局部最优解， 提 高整个序列获取的最优性， 待拼接 完成后， 挑选得到序列总速度增量 最小的序列S1； 步骤四： 通过构建双层优化策略， 对 步骤三得到的完整序列S1中每个目标与目标之间的 转移时间进 行调整及 优化， 以降低完整序列的总速度增量， 进一步提高整个序列的最优性， 得到总速度增量更低的飞越序列S2； 步骤五： 以每个目标的飞越速度作为待优化变量， 序列的总速度增量作为优化目标， 以 飞越的相 对速度条件作为约束条件， 建立优化问题模型， 通过非线性规划算法SQP， 优化步 骤四得到 的序列S2中每个目标的飞越速度， 进一步降低整个飞越过程的总速度增量， 提高 整个序列的最优性， 得到 速度增量更小的飞越序列S3。 2.如权利要求1所述的一种基于并行架构的空间大规模目标飞越的序列规划方法， 其 特征在于： 还包括步骤六， 根据步骤 五得到的优化后的速度增量更小的飞越序列S3， 对航天 器在对应时刻下施加相 应速度增量， 在给定的飞越窗口和飞越时刻的速度约束下， 实现高 精度低能耗的航天器飞越 任务。 3.如权利要求1或2所述的一种基于并行架构的空间大规模目标飞越的序列规划方法， 其特征在于： 步骤一实现方法为， 基于图形处理器GPU强大的并行计算能力， 首先将兰伯特问题 的求解建立并行架构的 核函数中， 即将兰伯特问题建立在GPU的每一个线程上进 行求解； 每个线程 都能针对不同的 输入， 求解对应的兰伯特问题， 输出相应的结果， 计算过程同步进行； 针对每个线程中的兰 伯特问题， 其输入量包括转移时间tf、 初始位置R0、 终端期望位置Ra， 输出量包括初始 位置所 对需的速度 终端期望位置所需的速度 对于从一个目标出发， 到另一个目标的单步 飞越问题， 起始位置所对应的速度为V0； 因此， 在起始位置应施加的速度增量矢量为 该速度增量大小为 记终端目标的速度为Va， 飞越任务最低的 相对速度限制为Δvl， 则到达的速度增量矢量Δvf由分段函数式(1)进行计算：权　利　要　求　书 1/4 页 2 CN 115169075 A 2到达速度增量大小为Δvf＝||Δvf||； 因此， 对于单步飞越问题， 总的速度增量大小Δv 为： Δv＝Δv0+Δvf              (2) 基于上述建立的并行兰伯特问题， 将其应用于子序列数据库生成的并行集束搜索算 法， 并行集束搜索算法通过求解不同输入条件下 的并行兰伯特问题， 得到转移轨迹的起始 速度和末端速度， 通过式(2)计算每个输入条件 下的总速度增量， 设置集束搜索宽度来筛选 相应的子序列； 所述并行集束搜索算法需要根据待求解兰伯特问题的数量给并行求解框架分配相应 的网格数Gs和块数Bs； 当有N个待求 解的兰伯特问题时， Bs和Gs的关系由以下式子获得： 与贪心算法不同， 所述 的并行集束搜索算法能通过设置超参数Bw来保留前Bw个较优的 结点， 有效避免过早陷入局部最优解， 同时也能减少搜索所占用的空间和时间， 提高空间大 规模目标兰伯特问题的求 解效率。 4.如权利要求3所述的一种基于并行架构的空间大规模目标飞越的序列规划方法， 其 特征在于： 步骤二实现方法为， 所述子序列的要素包括目标编号、 飞越时刻、 飞越速度、 从上一个目标到当前目标的速 度增量大小； 针对包含Nt个可选目标的序列规划问题， 给定任务的起始时刻， 得到对应的位置及速 度， 航天器从此时刻出发， 待选的目标有Nt个， 待选定目标完成飞越后， 下一个 的待选目标 将是Nt‑1个； 因此， 对于要求飞越Nflyby个的飞越任务而言， 当目标间的转移时间为固定值 时， 其备选的序列总数P为： 式中， 指Nt个可选目标中取 出Nflyby个元素进行排序； 对于Nt较小的小 规模目标的飞越序列规划问题， 能通过穷举方法得到最优的访问序列； 但对于Nt较大的问题， 穷举方法的序列总数超出计算机可求解范围； 并且， 每个目标之间的 转移时间也是待优化变量， 无法事先获取； 因此， 当前步骤二将建立子序列数据库生成方 法， 能有效提高最优序列的生成效率； 定义序列飞越的时间 窗口为[T0,Tf]， 其中T0为飞越任 务的起始时刻， Tf为飞越任务的终 端时刻， 即航天器需要在Tf‑T0的时间内完成对Nflyby个目标进行飞越； 定义目标与目标之间 的转移时间的最大值为 应小于Tf‑T0， 转移时间的最小值记 为 则目标间的转移 时间 对于目标间的转移， 需给定离散间隔进行穷举遍历以获得最优解， 记离权　利　要　求　书 2/4 页 3 CN 115169075 A 3