# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 3 Improved CBBA
### Bundle Construction
The time-discounted parameter \(\lambda\) in Formula (1) is set to \(10^{-5}\), which means that the final profit \(fp_{j}^{\text{task}}\) of the task completed at the last moment of the planning horizon is about 95% of the original profit \(op_{j}^{\text{task}}\). * Experimental environment: The proposed algorithm was coded in C++ and compiled on an Intel Core i9-11900K processor (3.5 GHz and 64 GB RAM). To reflect the performance of ICBBA under different constraints, experiments are carried out on global targets and regional targets, respectively. For global targets, due to the scattered distribution of targets, the conflicts between different tasks about observation availability masks are not prominent. The storage constraint and the energy constraint become dominant constraints. The DMG calculation can be flexibly adjusted according to the characteristics of different scenes. The most basic calculation that uses task profit to calculate DMG is described in Formula (11), which is denoted as DMG(P). According to the above characteristics of global targets, the estimated consumed storage \(sto_{j}^{\text{task}}\) is introduced into the DMG calculation, which is expressed as:

\[DMG_{ij}=\text{max}\left(\frac{fp_{j}^{\text{task}}}{sto_{j}^{\text{task}}} \right),\;\forall j\in\mathcal{J}\backslash\mathbf{b}_{i}. \tag{25}\]

This DMG calculation is denoted as DMG(P/S). DMG(P/S) focuses on those tasks with higher profit per unit storage, which can be seen as the balance between profit and storage. The comparison results of DMG(P) and DMG(P/S) on global targets are shown in Table 2.

For regional targets, due to the dense distribution of targets, there are more conflicts reflected in the temporary constraints. In order to further highlight the dominance of the temporary constraints, the storage constraint and the energy constraint are not considered. To describe the impact of the execution of one task on other tasks, a new concept \"Loss\" is introduced into the DMG calculation, which is expressed as:

\[DMG_{ij}=\text{max}\Big{(}fp_{j}^{\text{task}}-l_{j}^{\text{task}}\Big{)},\; \forall j\in\mathcal{J}\backslash\mathbf{b}_{i} \tag{26}\] \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Target Type**} & \multirow{2}{*}{**Target**} & \multirow{2}{*}{**Constellation**} & \multirow{2}{*}{**Available**} & \multirow{2}{*}{**Communication**} & \multicolumn{2}{c}{**DMG(P)**} & \multicolumn{2}{c}{**DMG(P)**} \\ \cline{6-11}  & & & & & & **Number** & & **Rate (\%)** & **Profit** & **Number** & **Rate (\%)** & **Total** \\ \hline \multirow{6}{*}{Global targets} & \multirow{3}{*}{500} & 30/3/1 & 282 & 3552 & 261 & 92.55 & 20,134.6 & 263 & **93.26** & **20,201.9** \\  & & 60/3/1 & 299 & 12,434 & 297 & **99.33** & **22,233.5** & 297 & **99.33** & 22,233.4 \\  & & 90/3/1 & 314 & 24,786 & 312 & 99.36 & 23,313.3 & 313 & **99.68** & **23,384.9** \\ \cline{2-11}  & \multirow{3}{*}{1000} & 30/3/1 & 556 & 3241 & 289 & 51.98 & 24,863.2 & 314 & **56.47** & 25,583.5 \\  & & 60/3/1 & 607 & 19,211 & 574 & **94.56** & **43,360.4** & 569 & 93.74 & 42,934.3 \\  & & 90/3/1 & 629 & 37,821 & 621 & **98.73** & **46,406.8** & 621 & **98.73** & 46,361.9 \\ \cline{2-11}  & \multirow{3}{*}{1500} & 30/3/1 & 845 & 3728 & 289 & 34.20 & 26,117.8 & 339 & **40.12** & **28,147.6** \\ \cline{1-1}  & & 60/3/1 & 882 & 16,702 & 582 & 65.99 & 48,043.5 & 609 & **69.05** & **48,573** \\ \cline{1-1}  & & 90/3/1 & 938 & 47,181 & 866 & **92.32** & **65,918.2** & 864 & 92.11 & 65,601 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The comparison results of DMG(P) and DMG(P/S) on global targets. (The highest value of task completion rate and total profit in each instance are marked in bold. )where \(l_{j}^{\text{task}}\) is the expected profit sum of those masks which conflict with the final assigned mask in the temporary constraints. This DMG calculation is denoted as DMG(P-L). Due to the temporary constraints, the execution of one task may lead to the loss caused by the failure of other related tasks.