# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 3 Improved CBBA
### Bundle Construction  
In this phase, each satellite iteratively adds tasks to its bundle until all tasks are added to the bundle or cannot be added due to constraint violation. The construction process is sequentially greedy, each time selecting one task to add to the bundle. The selected task needs to meet two sufficient conditions: (1) \(DMG_{ij}>y_{ij}\), i.e., \(h_{ij}=1\); (2) its \(DMG_{ij}\) is the largest among all the tasks that meet condition (1). In each iteration, the procedure of bundle construction for \(sat_{i}\) repeats the following steps until all tasks are added to the bundle or no task can be added because condition (1) is not met:  
(1) Calculate the DMG of each task that have not been added to \(\mathbf{b}_{i}\). The DMG of \(task_{j}\) can be calculated as:  
\[DMG_{ij}=\max\Bigl{(}fp_{j}^{\text{task}}\Bigr{)}=\max\biggl{(}op_{j}^{\text{ task}}e^{-\lambda st_{j}^{\text{task}}}\biggr{)},\forall j\in\mathcal{J}\setminus \mathbf{b}_{i} \tag{11}\]  
where \(fp_{j}^{\text{task}}\) increases with the decrease in \(st_{j}^{\text{task}}\). Therefore, to maximize \(fp_{j}^{\text{task}}\), \(st_{j}^{\text{task}}\) needs to be minimized. Based on Formula (6), \(DMG_{ij}\) can be obtained when \(task_{j}\) is assigned to the earliest observation availability mask and the task execution start time is equal to the mask start time, which is expressed as:  
\[k_{ij}^{\text{DMG}}=\text{argmin}_{k}\Bigl{(}st_{ijk}^{\text{oam}}\Bigr{)},\ \ \forall k\in\mathcal{K}_{ij}\text{ s.t. }f_{ijk}=1 \tag{12}\]  
\[st_{ij}^{\text{DMG}}=st_{ijk_{ij}^{\text{DMG}}}^{\text{oam}}. \tag{13}\]  
(2) Select the task that meets two sufficient conditions. The selected task index \(j^{\text{add}}\) can be expressed as:  
\[j^{\text{add}}=\text{argmax}_{j}\bigl{(}DMG_{ij}\cdot h_{ij}\bigr{)},\,\forall j \in\mathcal{J}\setminus\mathbf{b}_{i}\text{ s.t. }h_{ij}=1. \tag{14}\]  
(3) Update its bundle \(\mathbf{b}_{i}\), the winning satellite list \(\mathbf{z}_{i}\), and the winning bid list \(\mathbf{y}_{i}\). If \(sat_{i}\) selects \(task_{j^{\text{add}}}\), it will enter the task index into its bundle \(\mathbf{b}_{i}\)  
\[B_{i}=B_{i}+1 \tag{15}\]  
\[b_{iB_{i}}=j^{\text{add}} \tag{16}\]  
enter its own index into the winning satellite list \(\mathbf{z}_{i}\)  
\[z_{ij^{\text{add}}}=i \tag{17}\]  
and enter its corresponding DMG into the winning bid list \(\mathbf{y}_{i}\)  
\[y_{ij^{\text{add}}}=DMG_{ij^{\text{add}}}. \tag{18}\]  
(4) Check constraints and delete masks that conflict with the task added to the bundle this time. After a task is successfully added, it is necessary to perform a constraint check on the masks of all tasks outside the bundle. Check whether each mask satisfies the storage, energy and temporary constraints shown in Formulas (3), (4), (6)-(8). If any constraint is not satisfied, change the corresponding mask enable flag \(f_{ijk}=0\). A constraint check makes DMG only calculated for masks with \(f_{ijk}=1\) each time. Because of this, bundle construction can sequentially handle coupled constraints in MSOOP. The pseudo-code of bundle construction is described in Algorithm 2.