Single-Pass Imaging Planning with a Hybrid Genetic Tabu Search Algorithm for Agile Earth Observation Satellites

Abstract

Constellations of agile satellites can perform more tasks with fewer resources than can conventional satellites. However, for high-density targets in complex tasks, pairing satellites and targets in each orbit is a challenging optimization problem with complex constraints. This paper proposes a method for optimizing multisatellite task scheduling to minimize energy usage and maximize the number of imaged targets, named the hybrid genetic tabu search algorithm (HGTSA). First, a composite encoding method for target observation schedules was developed. The complex relationships of adjacent imaging targets were described and are enforced using a neighborhood replacement method that is employed to ensure that genetic algorithm (GA) crossover operations do not produce schedules with target conflicts. Moreover, the GA’s solution quality and global search capability are improved by applying a midpoint bidirectional target selection method in the mutation step. Finally, a tabu list and patterns of neighborhood solutions are generated during the GA search, and tabu search is applied in a local search of the neighborhood of high-quality solutions, overcoming the GA’s limited local search capability. Simulation results suggest that the proposed algorithm can considerably increase the number of target observations per orbit and reduce satellite energy usage. The proposed model and algorithm can be applied to scenarios in which multiple agile satellites must perform a high-density and complex task.