# On-Board Decentralized Observation Planning for LEO Satellite Constellations
###### Abstract  
The multi-satellite on-board observation planning (MSOOP) is a variant of the multi-agent task allocation problem (MATAP). MSOOP is used to complete the observation task allocation in a fully cooperative mode to maximize the profits of the whole system. In this paper, MSOOP for LEO satellite constellations is investigated, and the decentralized algorithm is exploited for solving it. The problem description of MSOOP for LEO satellite constellations is detailed. The coupled constraints make MSOOP more complex than other task allocation problems. The improved Consensus-Based Bundle Algorithm (ICBBA), which includes a bundle construction phase and consensus check phase, is proposed. A constraint check and a mask recovery are introduced into bundle construction and consensus check to handle the coupled constraints. The fitness function is adjusted to adapt to the characteristics of different scenes. Experimental results on series instances demonstrate the effectiveness of the proposed algorithm. multi-satellite on-board observation planning; task allocation; decentralized; improved consensus-based bundle algorithm +
Footnote †: journal:  
0000-0002-16, 2000-  
On-board observation planning for LEO satellite constellations belongs to the multi-satellite on-board observation planning (MSOOP) which can be seen as a variant of the multi-agent task allocation problem (MATAP) [8]. In MATAP, there are two typical planning architectures--centralized [9; 10; 11] and decentralized [12; 13; 14; 15]. In a centralized architecture, a central node is required to maximize or minimize user-defined goals by optimizing task-resource allocation, expecting to find the optimal solution. The centralized optimization is built on the premises that the central node knows all the task information and the resource information of the global nodes. This architecture cannot respond to changes on the satellites in real time, which leads to a certain lag in the planning scheme, and it relies heavily on communication links. In addition, the computing power of on-board hardware is poor, so it is difficult to find a node to complete the planning calculation of the whole constellation, especially a large-scale constellation. Thus, it is more feasible to allocate the calculation cost to multiple nodes. Finally, considering the robustness of the whole system, once the central node fails, it will be a devastating blow to the entire constellation. To sum up, a centralized architecture is hard to implement in MSOOP, and a decentralized architecture is chosen. In a decentralized architecture, each satellite claims the task independently and finally generates its own planning scheme. Following that, the consensus problem is difficult to deal with. Assuming that there is no communication between satellites, it cannot be guaranteed that a task will not be claimed repeatedly by multiple satellites, because a satellite does not know the claim results of other nodes. Therefore, we must introduce communication between satellites to ensure consensus. In general, if there is communication so that each satellite knows the claim results of other satellites, consensus can be guaranteed. The communication in LEO satellite constellations is achieved by ISLs. However, as a limited resource, the link cannot be used at will, and there is latency and packet loss in the communication process, which can be seen as the cost of communication. In previous literature, traditional decentralized optimization algorithms mainly include meta-heuristic algorithms and market-based heuristic algorithms. For meta-heuristic algorithms, [PERSON] et al. developed a hybrid distributed Genetic Algorithm including a local constraint satisfaction module and a global distributed optimization module [1]. The local module is performed on each satellite using a local search to provide feasible sub-solutions, and the global module is performed through the inter-satellite communication using a distributed Genetic Algorithm to ensure the satisfaction of coupled global constraints.