A Method for Satellite Constellation Collaborative Task Planning Based on Task Clustering and Tabu Search

To address the problems of high computational complexity, large communication overhead, and weak dynamic response in cooperative task planning for LEO remote sensing constellations under dynamic environments, an Improved Contract Net Protocol Based on Task Clustering and Tabu Search (CN-TCTS) is proposed. A hierarchical framework of "single-satellite scheduling and global allocation" is adopted by the algorithm. First, the solution space is effectively reduced as elementary tasks are merged by task clustering. Second, a Dynamic Constraint Tabu Search (DCTS) algorithm is designed, and rapid planning of single-satellite task sequences is achieved by introducing a conflict matrix and a value-oriented neighborhood search strategy. Finally, in the global allocation stage, the traditional Contract Net Protocol is improved by multiple strategies to efficiently allocate tasks and resolve conflicts. Simulation results show that in a large-scale scenario with 400 tasks, a task completion rate of 82.0% is maintained by the proposed CN-TCTS algorithm, and the average number of communication rounds is only 6.6, which is reduced by approximately 98.4% compared to traditional methods. In dynamic scenarios with sudden satellite failures, stronger robustness and a lower benefit loss rate are demonstrated by the algorithm.