Online scheduling of distributed Earth observation satellite system under rigid communication constraints

摘要

This paper focused on online scheduling of distributed Earth observation satellite system in a dynamic environment. The objective was to maximize the total profit of the overall system by efficiently coordinating the different satellites with stochastic arrival of urgent tasks, subject to rigid communication and observation time window constraints. We formulated this problem as a single-task, single-robot, time-extended assignment problem with intra-schedule dependency using the multi-robot task assignment taxonomy and formulated the sub-problem after releasing urgent tasks in a mixed-integer linear programming model. We first described the online scheduling algorithm for a single satellite, then we proposed the modified consensus-based bundle algorithm (m-CBBA) and modified asynchronous consensus-based bundle algorithm (m-ACBBA) with synchronous and asynchronous communication, respectively. Compared with initial versions of CBBA and ACBBA, the modified versions added the communication loop prediction phases to efficiently utilize scarce communication opportunities and reduce the communication requirements. Additionally, we introduce two contract net protocol (CNP)-based algorithms for comparison, respectively SingleItem-CNP-based (SI-CNP) algorithm and Batch-CNP-based (BA-CNP) algorithm. Computational experiments indicated that both the total profit and percentage of scheduled urgent tasks achieved by the m-ACBBA and m-CBBA algorithms were much higher than those achieved by both SI-CNP and BA-CNP. Additionally, the number of communications needed by either m-ACBBA or m-CBBA algorithm was lower than that by SI-CNP. When the communication cost in the system is high, the m-CBBA algorithm is preferred because it balances the profit and the required number of communications. When the communication cost is low, the m-ACBBA algorithm is preferred because it achieves high total profit and high percentage of scheduled urgent tasks.