Earth Observation Satellite Scheduling with Graph Neural Networks and Monte Carlo Tree Search
作者: Antoine Jacquet, Guillaume Infantes, Emmanuel Benazera, Vincent Baudoui, Jonathan Guerra, Stéphanie Roussel
分类: cs.AI, cs.LG, eess.SY
发布日期: 2024-08-27 (更新: 2025-11-26)
备注: Accepted at International Workshop on Planning & Scheduling for Space (IWPSS 2025)
💡 一句话要点
提出基于图神经网络和蒙特卡洛树搜索的地球观测卫星调度方法
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 地球观测卫星调度 图神经网络 深度强化学习 蒙特卡洛树搜索 任务规划
📋 核心要点
- 地球观测卫星规划问题复杂，传统方法如启发式搜索难以应对大规模、高约束的实际场景。
- 利用图神经网络提取观测任务之间的关系特征，结合深度强化学习进行调度决策，提升搜索效率。
- 引入蒙特卡洛树搜索进行后优化，进一步提升调度方案的质量，并在真实数据集上验证了有效性。
📝 摘要（中文）
地球观测卫星规划（EOSP）是一个具有重要实际意义的困难优化问题。需要在敏捷地球观测卫星上调度一组请求的观测任务，同时满足其可见窗口约束以及在连续观测之间施加不同延迟的机动约束。此外，该问题在很大程度上是超额订阅的：候选观测任务远远多于可能完成的任务。因此，必须选择将要执行的观测任务集合，同时最大化其累积收益，并为这些观测任务提出可行的调度方案。鉴于先前的工作主要集中在启发式和迭代搜索算法上，本文提出了一种基于图神经网络（GNN）和深度强化学习（DRL）的选择和调度观测任务的新技术。GNN用于从表示EOSP实例的图中提取相关信息，DRL驱动搜索最优调度方案。添加了一个基于蒙特卡洛树搜索（MCTS）的后学习搜索步骤，能够找到更好的解决方案。实验表明，该方法能够在小型问题实例上学习并推广到更大的真实世界实例，与传统方法相比具有非常强的竞争力。
🔬 方法详解
问题定义：地球观测卫星规划（EOSP）问题旨在选择一组观测任务并在卫星上安排它们的执行顺序，以最大化累积收益，同时满足可见窗口、机动约束等多种约束条件。现有方法，如启发式搜索和迭代算法，在处理大规模、高约束的实际问题时效率较低，难以找到全局最优解。
核心思路：论文的核心思路是将EOSP问题建模为图结构，利用图神经网络（GNN）学习观测任务之间的复杂关系，并结合深度强化学习（DRL）来指导搜索过程，从而更有效地选择和调度观测任务。GNN负责提取特征，DRL负责决策，两者协同工作。
技术框架：整体框架包含三个主要阶段：1) 图神经网络特征提取：使用GNN从EOSP问题的图表示中提取每个观测任务的特征向量，这些特征向量包含了任务的收益、时间窗口、与其他任务的依赖关系等信息。2) 深度强化学习调度：使用DRL智能体根据GNN提取的特征选择要执行的观测任务，并确定它们的执行顺序。DRL智能体通过与环境交互学习，目标是最大化累积收益。3) 蒙特卡洛树搜索后优化：在DRL得到初步调度方案后，使用MCTS进行进一步的优化，以找到更好的解决方案。
关键创新：该论文的关键创新在于将图神经网络和深度强化学习相结合，用于解决地球观测卫星调度问题。与传统方法相比，该方法能够更好地利用观测任务之间的关系信息，并能够通过学习自动优化调度策略。此外，引入MCTS进行后优化，进一步提升了调度方案的质量。
关键设计：GNN的具体结构未知，但其目标是学习每个观测任务的嵌入表示。DRL部分，智能体的状态空间由当前已调度任务和剩余任务的特征向量组成，动作空间为选择下一个要调度的任务。奖励函数设计为累积收益，目标是最大化总收益。MCTS的搜索策略和模拟策略未知。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该方法能够在小型问题实例上学习，并推广到更大的真实世界实例。与传统方法相比，该方法具有非常强的竞争力，能够找到更高质量的调度方案，但具体的性能提升数据未知。
🎯 应用场景
该研究成果可应用于实际的地球观测卫星任务规划，提高卫星资源的利用率，最大化观测收益。此外，该方法也可推广到其他具有类似约束和优化目标的调度问题，例如无人机任务规划、机器人路径规划等。
📄 摘要（原文）
Earth Observation Satellite Planning (EOSP) is a difficult optimization problem with considerable practical interest. A set of requested observations must be scheduled on an agile Earth observation satellite while respecting constraints on their visibility window, as well as maneuver constraints that impose varying delays between successive observations. In addition, the problem is largely oversubscribed: there are much more candidate observations than can possibly be achieved. Therefore, one must select the set of observations that will be performed while maximizing their cumulative benefit and propose a feasible schedule for these observations. As previous work mostly focused on heuristic and iterative search algorithms, this paper presents a new technique for selecting and scheduling observations based on Graph Neural Networks (GNNs) and Deep Reinforcement Learning (DRL). GNNs are used to extract relevant information from the graphs representing instances of the EOSP, and DRL drives the search for optimal schedules. A post-learning search step based on Monte Carlo Tree Search (MCTS) is added that is able to find even better solutions. Experiments show that it is able to learn on small problem instances and generalize to larger real-world instances, with very competitive performance compared to traditional approaches.