# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 3 Improved CBBA
### Bundle Construction
(2) Optimization performance analysis: It has been proved that CBBA is equivalent to the centralized sequential greedy algorithm in terms of optimization performance [24], and the rules for greedy can be controlled by designing the DMG calculation function. For global targets, DMG(P/S) has a better performance in MSOOP than DMG(P); similarly, for regional targets, DMG(P-L) has a better performance than DMG(P). In comparison, DMG(P-L) (all better than DMG(P)) has a more significant effect on regional targets than DMG(P/S) (five out of nine better than DMG(P)) on global targets. For global targets, when the storage constraint is not tight, the completion rate is close to 100%; when the storage constraint is tight, the storage can also be effectively used to maximize the completion of tasks. (3) Convergence performance analysis: From Table 4, it can be seen that ICBBA can effectively handle dynamically arrived tasks and improve the completion rate and the total profit. For \"global targets-1500-90/3/1\" in Figure 3a, ICBBA iterates 56 times to achieve the \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Target Type**} & \multirow{2}{*}{**Target**} & \multirow{2}{*}{**Constellation**} & **Available** & \multirow{2}{*}{**Communication**} & \multicolumn{2}{c}{**DMG(P)**} \\  & & & **Target** & & & **Number** & **Completion** & **Completion** \\  & & & & & & **Number** & **Rate (\%)** & **Total Profit** \\ \hline Global & 1500 & 90/3/1 & 938 & 47,181 & 866 & 92.32 & 65,918.2 \\ targets & 1500 + 100 & 90/3/1 & 994 & 49,785 & 870 & 87.53 & 67,426.7 \\ \cline{2-8} Regional & 1500 & 90/3/1 & 864 & 55,574 & 770 & 89.12 & 57,981.3 \\ targets & 1500 + 100 & 90/3/1 & 916 & 58,520 & 813 & 88.76 & 61,280.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The results of DMG(P) on global targets and regional targets with tasks arriving dynamically. Figure 4: The number of repeated claims for the whole constellation after bundle construction varies according to iteration times, with 100 tasks arriving dynamically at the 30 th iteration: (**a**) Global targets-1500-90/3/1; (**b**) Regional targets-1500-90/3/1. global consensus; for \"regional targets-1500-90/3/1\" in Figure 3b, ICBBA iterates 68 times to achieve the global consensus. The number of repeated claims decreases with the number of iterations in the whole constellation. The decline speed is faster in the early stage. From Figure 4a,b, it can be seen that when 100 tasks arrive dynamically at the 30 th iteration, the number of repeated claims rises sharply and then continues to decline until convergence at the 58 th and 71 st iteration, respectively. ## 5 Conclusions

In this paper, we investigate the multi-satellite on-board observation planning (MSOOP) with the case study of LEO satellite constellations. MSOOP, as a variant of multi-agent task allocation problem (MATAP), should complete the task allocation in a fully cooperative mode to maximize the profits of the whole constellation. We give a detailed description of MSOOP to discover its unique characteristics compared with the task allocation model in the original work of CBBA. In this case, not only the commonalities of MSOOP but also some coupled constraints should be taken into consideration, such as the storage constraint, the energy constraint, the consensus constraint and the special temporary constraints, which increases the difficulty of planning. Adapted to the characteristics of the problem, the improved Consensus-Based Bundle Algorithm (ICBBA) is exploited. ICBBA includes two main phases: bundle construction and consensus check. Each satellite runs the above two phases iteratively in parallel until the global consensus is reached and receives its own final planning scheme to perform observation. A constraint check and a mask recovery are introduced into bundle construction and consensus check to handle the coupled constraints. In addition, the DMG calculation is adjusted to adapt to the characteristics of different scenes.