(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111426199.0 (22)申请日 2021.11.25 (71)申请人 北京航天 飞行控制中心 地址 100094 北京市海淀区北清路26号院 (72)发明人 师明　高宇辉　杨成　张弓　 黄义喆　杨晓晨　 (74)专利代理 机构 中国兵器 工业集团公司专利 中心 11011 专利代理师 王晓娜 (51)Int.Cl. G06F 30/20(2020.01) G06F 30/15(2020.01) G06Q 10/04(2012.01) G06F 111/04(2020.01) (54)发明名称 一种通用的航 天器启发 式时态规划建模、 求 解方法 (57)摘要 本发明提出一种通用的航天器启发式时态 规划建模、 求解方法， 其特征在于： 充分结合航天 工程任务特点和实际需求， 提出一种航天器领域 通用模型及其数学表达， 采用时态网络结构图表 示航天器巡视探测状态转移的时间约束和能源 约束， 采用前向剪枝策略对网络结构图进行约束 传播和问题 求解， 设计实现了一种基于最大时间 跨度的启发 式控制函数进行问题松弛， 以提高求 解效率。 该方法所构建的领域模型表达更加完 整， 采用的时态网络结构图技术降低了规划求解 计算的复杂度， 且极大的简化了算法设计的复杂 度。 权利要求书2页 说明书6页 附图1页 CN 114638082 A 2022.06.17 CN 114638082 A 1.一种通用的航天器启发式时态规划建模、 求解方法， 其特征在于， 该方法包括如下步 骤： 一、 构建领域模型； 二、 根据任务实施方案和定制文件信息， 赋初值完成工程问题实例化处 理； 三、 建立启发式求 解方法； 四、 将领域模型、 实例文件和求 解算法提交规划器， 获得航天器动作序列。 2.如权利要求1所述的航天器启发式时态规划建模、 求解方法， 其特征在于， 所述步骤 一进一步包括： 将航天器的时态规划问题表示为一个三元组P＝(∑， s0， G)， 其中， ∑表示任务活动， 定 义∑＝(S， A， δ )， S为任务状态集合， A为动作集合， δ为状态转移函数； s0为任务初始状态， s ′ 是S中任意一个状态； G为目标状态集合， 其中每个目标命题具有形 式Sg＝{s′∈S|s满足G}； 令状态转移函数δ＝<Ta， exp>， 其中， 动作的时间语义Ta＝<sta， eta>， 将动作a的开始 执行时 刻和结束时刻分别记为sta和eta， exp表示动作执行的代价函数， 是由数值变量和常量组成 表达式， 定义了动作执行与能源消耗的关系； 形式化定义动作集A＝<dura， Ca， Ea>， 其中， dura表示动作的持续 时间； Ca是a的执行条件集合， 简称： 条件集， 描述在开始执行时刻必须 成立的条件、 结束时刻成立的条件和执行过程中保持的条件； Ea是a的执行效果集合， 简称： 效果集， 包含动作a在开始执 行时刻产生的效果和结束时刻产生的效果； 规划问题P的解是动作序列(a1， ...， ak)对应于目标状态转移序列(s0， ...， sk)， 满足s1 ＝ δ(s0， a1)， ...， sk＝ δ(sk‑1， ak)， 并且s1...sk是目标状态集 合G中的子集。 3.如权利要求2所述的航天器启发式时态规划建模、 求解方法， 其特征在于， 所述步骤 三进一步包括： a.根据条件约束， 构建时态网络结构图， 确定各节点和边的数值； b.采用前向剪枝策略对时态网络结构图进行约束传播和问题求 解； c.设计问题 松弛策略提高求 解效率。 4.如权利要求2所述的航天器启发式时态规划建模、 求解方法， 其特征在于， 所述的步 骤三中， 构建时态网络结构图的方法如下： 令时态网络结构图的每个节点表示一个独立的 原子任务∑ ′， 满足∑′＝(S′， A′， δ )， 定义了任务属性和状态； 节点的集合表示一个工程任 务P， 满足三元组P＝(∑ ′， s0， G)； 每条边用状态转移函数δ表示， 满足δ＝<Ta， exp>， 定义了 不同动作之间的时间和能源约束关系； 动 作开始时间sta′、 动作结束时间eta′以及动作代价 exp的常量共同构成加权图的权值； 边的方向定义了原子任务之间的时序关系， 提供了判断 约束传播一致性的依据， 定义节 点数量为M， 有向边的数量为K， 二者的关系符合如下逻辑关 系： 5.如权利要求3所述的航天器启发式时态规划建模、 求解方法， 其特征在于， 所述的步 骤三中， 采用前向剪枝策略对时态网络结构图进行约束传播和问题求 解的过程如下： 构建队列Q， 依次读取步骤a上 所构建的有向加权图的节点， 使其满足Q ＝{∑′}； 按照“先进先出 ”顺序对节点的能源约束和状态属性进行约束判断直到队列为空， 过程权　利　要　求　书 1/2 页 2 CN 114638082 A 2中采用前向剪枝策略移除不符合的约束条件的节点和 边， 完成约束传播； 获得有向加权图 起点到终点的一个可达路径， 即获得了 完成一系列原子任务所需要的动作序列。 6.如权利要求4所述的航天器启发式时态规划建模、 求解方法， 其特征在于， 所述的步 骤三中， 采用前向剪枝策略对时态网络结构 图进行约束传播和问题求解的过程进一步包 括： 1)建立Closed表和Open表， 其中Closed表用于记录搜索算法已经遍历的节点， Open表 用于记录 搜索的边界上的若干状态； 2)读取工程配置文件， 判读节点n的能源剩余量En是否满足完成动作An的最低能耗需 求； 定义E′n为执行当前节点n到下一个节点n+1所消耗的能源， 调用状态转移函数δ中所定 义的动作执 行代价函数exp进行估算， E ′n＝expn+1； 定义能源总量 为E， 当前节点 n的剩余能源为Ea， i节点序号； 设定判断条件En＜E′n； 若结果为真， 继续执 行状态判断， 进入下一 步； 若结果为假， 跳出求 解过程， 提 示能源不满足后续动作执 行要求， 无 可行解； 3)判断节点 n的状态sn是否是目标状态G的子集； 若满足， 则按照问题松弛策略进行约束传播和一致性判断， 计算节点n动作集合An， 形成 可用动作集Ap p＝{An}， n∈N+， 并将结果 放入Open表； 若不满足， 则通过逆向追踪从节点 n的状态sn到初始状态s0的动作序列。 7.如权利要求5所述的航天器启发式时态规划建模、 求解方法， 其特征在于， 所述的步 骤三中， 确定最优解的松弛问题的方法如下： 1)在领域模型中加入动作持续时间dura用以表示时间区间； 2)在时态网络结构图中， 利用节点最早开始时间和动作持续时间， 定义一个基于最大 时间跨度的启发式控制函数： 满足Sn＝{s′∈S|s满足G}， 其中， n∈N+； 3)利用启发式控制函数选择节点， 计算节点之间的有向距离测量出当前状态到目标状 态的所实现的程度； 所选择出的节点是一个满足执行条件下的可行解， 其中， 时间相关的约 束用起始时间表征， 一个原子任务包括最早开始时间、 最晚开始 时间、 最早结束时间、 最晚 结束时间四个参数； 4)使用“目标完成时间 ”度量任务活动的完成情况， 用给定目标状态集合的松弛值， 来 体现当前时态规划问题的求 解程度。权　利　要　求　书 2/2 页 3 CN 114638082 A 3