# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 3 Improved CBBA
### Bundle Construction
```
procedureBundle Construction(current satellite index \(i\), task index set \(\mathcal{J}=\{1,\ 2,\ \ldots,M\}\), observation availability mask index sets \(\{\mathcal{K}_{11}\), \(K_{22}\),..., \(\mathcal{K}_{id}\}\), \(\mathbf{b}_{i}(T-1)\), \(\mathbf{y}_{i}(T-1)\), \(\mathbf{z}_{i}(T-1)\))  Initialize \(\mathbf{b}_{i}(T)=\mathbf{b}_{i}(T-1)\), \(\mathbf{y}_{i}(T)=\mathbf{y}_{i}(T-1)\), \(\mathbf{z}_{i}(T)=\mathbf{z}_{i}(T-1)\), termination flag \(TF=0\) while\(TF=0\)do/* Execute the procedure if there is still a task that can be added to the bundle */  Initialize \(j^{\text{add}}=-1\), \(DMG_{\text{max}}=0\) for\(j\)in\(\mathcal{J}\setminus\mathbf{b}_{i}\)do  Initialize \(DMG_{ij}=0\), \(st_{ij}^{\text{DMG}}=\text{planning horizon}\)
```  
**Algorithm 2**Bundle Construction for \(sat_{i}\) at iteration \(T\)```
for\(k\)in\(\mathcal{K}_{ij}\)do if\(f_{ijk}=1\wedge st_{ijk}^{\text{QAM}}<sf_{ij}^{\text{DMG}}\)then/* Find the earliest observation availability mask that meets the constraints */ \(k_{ij}^{\text{DMG}}=k\) \(st_{ij}^{\text{DMG}}=st_{ijk_{\text{DMG}}}^{\text{QAM}}\)/* Record the start time of the earliest observation availability mask found so far */ \(DMG_{ij}=op_{j}^{\text{task}}e^{-\lambda st_{ij}^{\text{DMG}}}\)/* Calculate the DMG of the task */ endif endfor \(h_{ij}=1\Big{(}DMG_{ij}>y_{ij}\Big{)}\) if\(h_{ij}=1\wedge DMG_{ij}>DMG_{\text{max}}\)then/* Find the task that meets two sufficient conditions */ \(j^{\text{add}}=j\)/* Record the selected task index */ \(DMG_{\text{max}}=DMG_{ij}\)/* Record the maximum DMG found so far */ endif endfor if\(j^{\text{add}}\
eq-1\)then/* Judge whether there is a task that can be successfully added to the bundle */ \(B_{i}=B_{i}+1\)/* Extend the length of the bundle */ \(b_{ijk}=j^{\text{add}}\)/* Enter the task into the bundle */ \(y_{ij\
eq d}=DMG_{ij^{\text{add}}}\)/* Enter the DMG of the task into the winning bid list */ \(z_{ij\
eq d}=i\)/* Enter the satellite index into the winning satellite list */ for\(j\)in\(\mathcal{J}\setminus\mathbf{b}_{i}\)do/* Check constraints and delete masks that conflict with the task added to bundle this time */ for\(k\)in\(\mathcal{K}_{ij}\)do if\(aam_{ijk}\) conflicts with \(task_{j\
eq d}\)then \(f_{ijk}=1\) else \(f_{ijk}=0\) endif endfor endfor else \(\mathit{TF}=1\) endif endwhile endprocedure
```

**Algorithm 1** The \(\mathcal{K}_{ij}\) algorithm for the \(\mathcal{K}_{ij}\) algorithm. ### Consensus Check

In MSOOP, the time-varying characteristic of the inter-plane ISLs makes the communication network a dynamic network. However, there are no isolated nodes in the whole constellation, which ensures that ICBBA can eventually converge. The global consensus is the condition of algorithm convergence. A consensus check phase ensures that the final planning scheme must meet the consensus constraint described in Formula (5). After receiving the planning information from the neighbor \(sat_{i^{\prime}}\) at time \(t\), the procedure of consensus check for \(sat_{i}\) includes the following steps:

(1) Check whether the consensus between \(sat_{i}\) and \(sat_{i^{\prime}}\) has been reached. If the consensus has been reached, make the consensus flag \(conf_{i}=1\); otherwise, change \(\mathbf{y}_{i}\), \(\mathbf{z}_{i}\) based on the action rule shown in Table 1, and make the consensus flag \(conf_{i}=0\). There are three possible actions \(sat_{i}\) can take on \(task_{j}\):

* Update: \(y_{ij}=y_{fj}\), \(z_{ij}=z_{i^{\prime}j}\);
* Reset: \(y_{ij}=0\), \(z_{ij}=-1\);
* Leave: \(y_{ij}=y_{ij}\), \(z_{ij}=z_{ij}\). (2) Update the time stamp \(\mathbf{s}_{i}\). If \(conf_{i}=1\), end the procedure of this phase; otherwise, continue to the next steps. \[s_{ii^{\prime}}=t \tag{19}\]

\[s_{ii^{\prime\prime}}=\max\{s_{ii^{\prime\prime}},\ s_{i^{\prime}i^{\prime \prime}}\}\text{, }\forall i^{\prime\prime}\in\mathcal{I}\backslash\{i,\ i^{\prime}\}. \tag{20}\]

(3) Release the earliest added task for which \(z_{ij}\
eq i\) and all of the tasks that were added after it.