第5期 杨舒，等：一种面向任务的对地观测卫星Aget团队构建方法 ·655. 表1符号定义 Table 1 Symbol definitions 符号 定义 TaskSet={task,i≤M} 对地观测任务集合，共有M个任务 SatSet={Sat,li≤Nl 卫星集合，包含N个卫星的卫星集群 观测任务ak,和TD,表示任务的唯一编号：O,表示观测目标： 专和表示任务的规划起始时间和结束时间：S表示任务对载荷 task;=(TID,O,S,TC,TR,TRC) 类型的要求：TC,表示完成该任务的代价：TR,表示任务的优先级： TRC:表示任务的性价比，TRC=TR,/TC SD,表示卫星Sat,的唯一编号，TW,表示卫星可用的时间窗资源， TW_used,表示卫星上已经被占用的时间窗集合， Sat (SID,TW,TW_used,SC,BTasks,RES) SC,表示Sat,的使用代价，BTasks,表示卫星在团队构建中承担的 任务集合，RES,是卫星的约束条件 卫星Sat的约束条件，△T。表示两次观测活动的最短时间间隔， RES:=(△T,△T,△T) △T.是单圈最长观测时间，△T,是单天最长观测时间 TEAM,1≤i≤M 能够胜任task,到task,的团队集合 w是一条时间窗数据，wD是时间窗的唯一编号， w=(twlD,T",Tg,S,Sat,0,Cir"),tw∈TW,1≤i≤N T和是观测起止时间，S是观测时使用的载荷类型， O,是观测目标，Ci"表示轨道圈号 0Set={0,l1≤i≤k} 观测目标集合 team表示团队，Cost是团队卫星执行ask,到task,的总代价， team =(Cost,StoTSet),team E TEAM StoTSet任务与执行该任务卫星的集合 ST =(Sat,task,),ST E StoTSet 团队中每一个任务与对应执行任务的卫星 1.3约束模型 twn∈TWo,∑(T-T)≥△T 卫星Sat,能够执行任务task,的条件：在卫星拥 式中TW表示TW中所有时间窗起始时间在第 有的时间资源TW:中，找到一组观测时间窗 Q天内的时间窗集合。 TWtasks,胜任Btasks,和task,且与卫星上已经被占 用的时间窗集合TW_used,不产生冲突。考虑卫星 2基于分枝限界的卫星任务团队构建 在执行任务时，受星上电源容量、载荷硬件特性、轨 算法 道参数等限制，将一个时间窗看作一次观测活动， 由上述模型可知，该问题是一个典型的组合优 对TWk和TW_used:组成的时间窗集合TWa进行 化问题，我们拟采用树构建与搜索方法，以初始的 以下约束检测，TW中的TW按照t,排序。 1)两次观测活动不能同时进行。卫星一次只 空团队team。作为根节点，以完成任务为条件向下 能进行一个观测活动，即 分支，形成新的团队，遍历完所有任务，可建构一颗 twm∈TWa,Tm1-Tw≥0 广义的搜索树。 2)两次观测活动最短时间间隔。卫星关机后 算法1TFCA 需要一段时间才能重新开机，即 功能基于分枝限界思想的团队构建算法的 twm∈TWa,Ta1-Tm≥△Td 主算法； 3)单圈最长观测时间约束。卫星单圈累计观 输入TaskSet,SatSet,初始的空团队teamo; 测时间要小于单圈最长开机时间，即 输出最优团队team。 Htw.eTw,∑(T-T)≥△T 1)Begin 式中TW表示TWa中所有圈号为P的时间窗。 2)set team=☑，team=teamo 4)单天最长观测时间约束。卫星单天累计观 3)TFOfEachTask(1,team,team) 测时间限制要小于单天最长观测时间，即 4)Return team表 １ 符号定义 Ｔａｂｌｅ １ Ｓｙｍｂｏｌ ｄｅｆｉｎｉｔｉｏｎｓ 符号 定义 ＴａｓｋＳｅｔ ＝ ｛ｔａｓｋｉ ｉ ≤ Ｍ｝ 对地观测任务集合，共有 Ｍ 个任务 ＳａｔＳｅｔ ＝ ｛Ｓａｔ ｉ ｉ ≤ Ｎ｝ 卫星集合，包含 Ｎ 个卫星的卫星集群 ｔａｓｋｉ ＝ （ＴＩＤｉ，Ｏｋ，ｔ ｉ ｓ，ｔ ｉ ｅ，Ｓ，ＴＣｉ，ＴＲｉ，ＴＲＣｉ） 观测任务 ｔａｓｋｉ和 ＴＩＤｉ表示任务的唯一编号；Ｏｋ表示观测目标； ｔ ｉ ｓ 和 ｔ ｉ ｅ 表示任务的规划起始时间和结束时间；Ｓ 表示任务对载荷 类型的要求；ＴＣｉ表示完成该任务的代价；ＴＲｉ表示任务的优先级； ＴＲＣｉ表示任务的性价比，ＴＲＣｉ ＝ ＴＲｉ ／ ＴＣｉ Ｓａｔ ｉ ＝ ＳＩＤｉ，ＴＷｉ，ＴＷ＿ ｕｓｅｄｉ，ＳＣｉ，ＢＴａｓｋｓｉ，ＲＥＳｉ ( ) ＳＩＤｉ表示卫星 Ｓａｔ ｉ的唯一编号，ＴＷｉ表示卫星可用的时间窗资源， ＴＷ＿ｕｓｅｄｉ表示卫星上已经被占用的时间窗集合， ＳＣｉ表示 Ｓａｔ ｉ的使用代价，ＢＴａｓｋｓｉ表示卫星在团队构建中承担的 任务集合，ＲＥＳｉ是卫星的约束条件 ＲＥＳｉ ＝ （ΔＴ ｉ ｓｄ ，ΔＴ ｉ ｃｉｒ，ΔＴ ｉ ｄａｙ） 卫星 Ｓａｔ ｉ的约束条件， ΔＴ ｉ ｓｄ 表示两次观测活动的最短时间间隔， ΔＴ ｉ ｃｉｒ 是单圈最长观测时间， ΔＴ ｉ ｄａｙ 是单天最长观测时间 ＴＥＡＭｉ，１ ≤ ｉ ≤ Ｍ 能够胜任 ｔａｓｋ１ 到 ｔａｓｋｉ 的团队集合 ｔｗ ＝ （ｔｗＩＤ，Ｔ ｔｗ ｓ ，Ｔ ｔｗ ｅ ，Ｓ，Ｓａｔ ｉ，Ｏｋ，Ｃｉｒ ｔｗ ），ｔｗ ∈ ＴＷｉ，１ ≤ ｉ ≤ Ｎ ｔｗ 是一条时间窗数据，ｔｗＩＤ 是时间窗的唯一编号， Ｔ ｔｗ ｓ 和 Ｔ ｔｗ ｅ 是观测起止时间，Ｓ 是观测时使用的载荷类型， Ｏｋ是观测目标，Ｃｉｒ ｔｗ表示轨道圈号 ＯＳｅｔ ＝ ｛Ｏｉ １ ≤ ｉ ≤ ｋ｝ 观测目标集合 ｔｅａｍ ＝ （Ｃｏｓｔ，ＳｔｏＴＳｅｔ） ， ｔｅａｍ ∈ ＴＥＡＭｉ ｔｅａｍ 表示团队，Ｃｏｓｔ 是团队卫星执行 ｔａｓｋ１ 到 ｔａｓｋｉ的总代价， ＳｔｏＴＳｅｔ 任务与执行该任务卫星的集合 ＳＴ ＝ （Ｓａｔ ｉ，ｔａｓｋｊ），ＳＴ ∈ ＳｔｏＴＳｅｔ 团队中每一个任务与对应执行任务的卫星 １．３ 约束模型 卫星 Ｓａｔ ｉ 能够执行任务 ｔａｓｋｊ 的条件：在卫星拥 有的 时 间 资 源 ＴＷｉ 中， 找 到 一 组 观 测 时 间 窗 ＴＷｔａｓｋｓ，胜任 Ｂｔａｓｋｓｉ 和 ｔａｓｋｊ，且与卫星上已经被占 用的时间窗集合 ＴＷ＿ｕｓｅｄｉ 不产生冲突。 考虑卫星 在执行任务时，受星上电源容量、载荷硬件特性、轨 道参数等限制，将一个时间窗看作一次观测活动， 对 ＴＷｔａｓｋｓ和 ＴＷ＿ｕｓｅｄｉ 组成的时间窗集合 ＴＷｄｅｔ进行 以下约束检测，ＴＷｄｅｔ中的 ＴＷ 按照 ｔ ｓ排序。 １）两次观测活动不能同时进行。 卫星一次只 能进行一个观测活动，即 ∀ ｔｗｍ ∈ ＴＷｄｅｔ，Ｔ ｔｗｍ＋１ ｓ － Ｔ ｔｗｍ ｅ ≥ ０ ２）两次观测活动最短时间间隔。 卫星关机后 需要一段时间才能重新开机，即 ∀ ｔｗｍ ∈ ＴＷｄｅｔ，Ｔ ｔｗｍ＋１ ｓ － Ｔ ｔｗｍ ｅ ≥ ΔＴ ｉ ｓｄ ３）单圈最长观测时间约束。 卫星单圈累计观 测时间要小于单圈最长开机时间，即 ∀ ｔｗｍ ∈ ＴＷｃｉｒＰ ，∑ Ｔ ｔｗｍ ｅ － Ｔ ｔｗｍ ｓ ( ) ≥ ΔＴ ｉ ｃｉｒ 式中 ＴＷｃｉｒＰ表示 ＴＷｄｅｔ中所有圈号为 Ｐ 的时间窗。 ４）单天最长观测时间约束。 卫星单天累计观 测时间限制要小于单天最长观测时间，即 ∀ ｔｗｍ ∈ ＴＷｄａｙＱ，∑ Ｔ ｔｗｍ ｅ － Ｔ ｔｗｍ ｓ ( ) ≥ ΔＴ ｉ ｄａｙ 式中 ＴＷｄａｙＱ表示 ＴＷｄｅｔ中所有时间窗起始时间在第 Ｑ 天内的时间窗集合。 ２ 基于分枝限界的卫星任务团队构建 算法 由上述模型可知，该问题是一个典型的组合优 化问题，我们拟采用树构建与搜索方法，以初始的 空团队 ｔｅａｍ０ 作为根节点，以完成任务为条件向下 分支，形成新的团队，遍历完所有任务，可建构一颗 广义的搜索树。 算法 １ ＴＦＣＡ 功能 基于分枝限界思想的团队构建算法的 主算法； 输入 ＴａｓｋＳｅｔ， ＳａｔＳｅｔ， 初始的空团队 ｔｅａｍ０ ； 输出 最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 。 １） Ｂｅｇｉｎ ２） ｓｅｔ ｔｅａｍ ｂｅｓｔ Ｍ ＝ ⌀，ｔｅａｍ ＝ ｔｅａｍ０ ３） ＴＦＯｆＥａｃｈＴａｓｋ（１，ｔｅａｍ，ｔｅａｍ ｂｅｓｔ Ｍ ） ４） Ｒｅｔｕｒｎ ｔｅａｍ ｂｅｓｔ Ｍ 第 ５ 期 杨舒，等：一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 ·６５５·