# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 3 Improved CBBA
### Bundle Construction
```
procedureConsensus Check (planning information receiving time \(t\), current satellite index \(i\), neighbor satellite index \(i^{\prime}\), satellite index set \(\mathcal{I}=\{1,\,2,\,\ldots,N\}\), task index set \(\mathcal{J}=\{1,\,2,\,\ldots,M\}\), observation availability mask index sets \(\{\mathcal{K}_{i1},\,\mathcal{K}_{i2},\,\ldots,\mathcal{K}_{iM}\}\), \(\mathbf{b}_{i}(T),\mathbf{y}_{i}(T)\), \(\mathbf{z}_{i}(T)\), \(\mathbf{s}_{i}\), \(\mathbf{y}_{i^{\prime}}\), \(\mathbf{z}_{i^{\prime}}\), \(\mathbf{s}_{i^{\prime}}\) Initialize \(conf_{i}=1\), \(\overline{n}=-1\) for\(j\)in\(\mathcal{J}\)do if\(y_{ij}\
eq y_{j^{\prime}}\lor z_{ij}\
eq z_{ij}\)then /* Check the consensus between satellite itself and its neighbor */ \(conf_{i}=0\) endif \(y_{ij},\,z_{ij}\leftarrow\) Action Rule(\(y_{ij},\,z_{ij},\,y_{j^{\prime}},\,z_{ij}\)) /* Change the winning bid list and the winning satellite list based on the action rule */ endfor for\(i^{\prime}\)in\(\mathcal{I}\)do/* Update the time stamp */ if\(i^{\prime}=i^{\prime}\)then \(s_{i^{\prime\prime}}=t\) endif if\(i^{\prime}\
eq i\wedge i^{\prime}\
eq i^{\prime}\)then \(s_{i^{\prime\prime}}=\max\{s_{i^{\prime\prime}},\,s_{i^{\prime\prime}}\}\) endif endfor if\(conf_{i}=0\)then for\(n=1\)to\(B_{i}\)do/* Release the earliest added task for which \(z_{ij}\
eq i\) and all of the tasks that were added after it */ if\(\overline{n}=-1\wedge z_{i_{\text{ho}}}\
eq i\)then /* Find the earliest added task for which \(z_{ij}\
eq i\)*/ \(\overline{n}=n\) \(b_{\overline{i}}=\varnothing\)/* Empty the corresponding location of the bundle */ endif if\(\overline{n}\
eq-1\)then \(y_{ij_{\text{ho}}}=0\)/* Reset the corresponding location of the winning bid list */ \(z_{i_{\text{ho}}}=-1\)/* Reset the corresponding location of the winning satellite list */ \(b_{\overline{i}}=\varnothing\)/* Empty the corresponding location of the bundle */ endif endfor \(B_{i}=\overline{n}-1\)/* Shorten the length of the bundle */ for\(j\)in\(\mathcal{J}\backslash\mathbf{b}_{i}\)do/* Recover the masks that have been deleted due to conflict with the released tasks */ for\(k\)in\(K_{ij}\)do if\(aam_{ijk}\) conflicts with any task in \(\mathbf{b}_{i}\)then \(f_{ijk}=1\) else \(f_{ijk}=0\) endif endfor endfor endif endprocedure
```

**Algorithm 3**Consensus Check for \(sat_{i}\) at iteration \(T\)

## 4 Computational Experiments

In this section, we present experimental studies on ICBBA implemented in MSOOP. AGI's STK is used to simulate the experimental scenes and calculate the observation availability masks and communication availability masks. Some details about the experimental instances and environment are as follows:

* Target setting: the targets are divided into two types, global targets and regional targets. The global targets are generated by a random uniform distribution throughout the world, 60\({}^{\circ}\) S-60\({}^{\circ}\) N. The regional targets are generated by a random uniform distribution in the area, 3\({}^{\circ}\) N-53\({}^{\circ}\) N and 73\({}^{\circ}\) E-133\({}^{\circ}\) E. The position of each target is defined by latitude and longitude. For different types of targets, the number of targets includes 500, 1000, and 1500, respectively. * Satellite constellation setting: Walker-\(\delta\) (30/3/1, 600 km, 60\({}^{\circ}\)), Walker-\(\delta\) (60/3/1, 600 km, 60\({}^{\circ}\)), and Walker-\(\delta\) (90/3/1, 600 km, 60\({}^{\circ}\)) are used. * Parameter setting: the planning horizon is set to 1.5 h, from 04:00:00 to 05:30:00 on 30 July 2022. The original profit \(op_{j}^{\text{task}}\) and the estimated consumed storage \(sto_{j}^{\text{task}}\) of each task are generated by a random uniform distribution on \([50,100]\). The maximum available storage \(sto_{i}^{\text{sat}}\) is set to 750, which allows that about 10 tasks can be completed by each satellite in the whole planning horizon.