# On-Board Decentralized Observation Planning for LEO Satellite Constellations
###### Abstract
However, the computational complexity for both the local module and the global module grows exponentially as the number of satellites increases. [PERSON] et al. exploited a multi-agent evolutionary algorithm to deal with the coordination of CubeSats [16]. Similarly, the complexity of evolutionary computation is uncontrollable in large-scale scenes, and some time constraints are not considered. To sum up, meta-heuristic algorithms usually include some iterative optimization mechanisms, such as local search and population evolution, which makes the computational complexity rise nonlinearly as the number of agents or tasks increases and leads to a poor performance in large-scale scenes. In addition, the computing power of on-board hardware is not enough to support iterative optimization mechanisms. For market-based heuristic algorithms, [PERSON] studied how to optimally manage interdependent satellite clusters under the constraints of energy and communication for heterogeneous small satellite systems, and they introduced a task allocation method based on market mechanism [17]. However, the model is relatively simple, and some coupled constraints such as temporary constraints are not considered. As a representative market-based algorithm, Contract Network Protocol (CNP) was first proposed to deal with distributed problem by [PERSON] [18]. After that, many improved versions have been studied for satellite mission planning [19; 20; 21; 22]. However, the communication cost of CNP and its improved versions cannot be well controlled within an acceptable level. Each task needs to go through the stages of publishing, bidding and winning, which makes the number of communication for task allocation linearly related to the number of agents and the number of tasks. For the whole constellation, a large amount of communication makes the communication cost increase and the robustness decrease. In addition to traditional optimization algorithms, some machine learning algorithms are also emerging to solve decentralized problems. These algorithms are usually based on Game Theory, which achieves global convergence by finding the Nash equilibrium. Multi-Agent Reinforcement Learning (MARL) is widely used in multi-agent systems, such as games (StarCraft II), robot control, and UAV formation. [PERSON] et al. introduced Multi-Agent Deep Deterministic Policy Gradient (MADDPG), a classical MARL algorithm, into MSOOP which was formulated as a fully cooperative Markov Decision Process [23]. However, only the coordination of three satellites is considered in their experiment. It is difficult to guarantee the convergence of machine learning algorithms in large-scale scenes. Therefore, considering the computational complexity, communication cost and convergence, we decide to explore a market-based decentralized algorithm with a low communication cost. In this paper, the Improved Consensus-Based Bundle Algorithm (ICBBA) is proposed to maximize the total profit of the whole constellation at an acceptable communication cost. CBBA is one of the state-of-the-art decentralized market-based algorithms that was developed by [PERSON] et al. in 2009 [24]. CBBA is a polynomial time algorithm with \(O(N\cdot M)\) computational complexity (\(N\) is the number of agents and \(M\) is the number of tasks). It has been proved that CBBA is capable of guaranteeing conflict-free allocation, assuming a strongly connected network, which is one type of coupled constraint. However, it is not able to account for the other types of coupling which are common in MSOOP.