敏捷卫星调度的时间约束推理方法

敏捷卫星机动能力的增强带来观测机会的增多和观测时间窗口的增长，具有很大的应用潜能。但管控中由于观测开始时间是一个具有连续值域的变量，传统非敏捷卫星调度问题的组合优化建模方法不再适用。本文介绍了敏捷卫星的时间依赖、可控与不可控事件混合、资源过度受限等特性；给出了时间约束网络概念及敏捷卫星调度中的时间约束推理问题描述；分析时间约束网络与距离图的等价性，借鉴Johnson 算法对稀疏网络的特殊处理，采用重赋权技术，提出针对敏捷卫星调度的改进循环检测算法检查时间约束；建立了分支剪枝搜索算法，以约束规划方式获得时间一致解。最后通过实例验证本文方法的有效性，实验结果表明本文方法能够较好地实现敏捷卫星调度的时间约束的一致性检验和搜索求解。

Temporal reasoning technology for AEOS scheduling

Agile earth observation satellite (AEOS) is a new type of satellite with high application potential, for its added observation opportunities and flexible time window from enhanced maneuverability. However, start time of observations is a continuous variable, so combination optimization modeling methods for non-agile satellites are not usable for it. This paper introduces characteristics of temporal dependence, hybrid of controllable and uncontrollable events, and resource’s over-subscribed. Temporal constraint network concept and temporal reasoning problem of AEOS has been presented. Equivalence of temporal constraint network and distance graph and Johnson algorithm for sparse networks has been analyzed. Then, an improved cycle checking algorithm for AEOS scheduling based on re-evaluating has been proposed, and a branch-prune algorithm based on constraint programming way was applied to get a consist solution. Finally some experiments were presented to prove the validity of the method. The results showed the efficiency and validity of the method in consist checking and searching of temporal constraints in AEOS scheduling.