A two-stage scheduling algorithm based on pointer network with attention mechanism for micro-nano Earth observation satellite constellation

Micro-nano Earth Observation Satellite (MEOS) constellation has the advantages of low construction cost, short revisit cycle, and high functional density, which is considered a promising solution for serving rapidly growing observation demands. The observation Scheduling Problem in the MEOS constellation (MEOSSP) is a challenging issue due to the large number of satellites and tasks, as well as complex observation constraints. To address the large-scale and complicated MEOSSP, we develop a Two-Stage Scheduling Algorithm based on the Pointer Network with Attention mechanism (TSSA-PNA). In TSSA-PNA, the MEOS observation scheduling is decomposed into a task allocation stage and a single-MEOS scheduling stage. In the task allocation stage, an adaptive task allocation algorithm with four problem-specific allocation operators is proposed to reallocate the unscheduled tasks to new MEOSs. Regarding the single-MEOS scheduling stage, we design a pointer network based on the encoder-decoder architecture to learn the optimal single-MEOS scheduling solution and introduce the attention mechanism into the encoder to improve the learning efficiency. The Pointer Network with Attention mechanism (PNA) can generate the single-MEOS scheduling solution quickly in an end-to-end manner. These two decomposed stages are performed iteratively to search for the solution with high profit. A greedy local search algorithm is developed to improve the profits further. The performance of the PNA and TSSA-PNA on single-MEOS and multi-MEOS scheduling problems are evaluated in the experiments. The experimental results demonstrate that PNA can obtain the approximate solution for the single-MEOS scheduling problem in a short time. Besides, the TSSA-PNA can achieve higher observation profits than the existing scheduling algorithms within the acceptable computational time for the large-scale MEOS scheduling problem.