# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 3 Improved CBBA
### Main Procedure of ICBBA  
Before implementing the ICBBA, some pre-work is essential. The ground needs to carry out periodic orbit prediction and communication availability calculation in advance and send it to the constellation before planning. No matter whether the observation tasks are generated on the ground or on the satellite, they need to be broadcast in the constellation in advance. Each satellite calculates the observation availability masks based on satellite information and task information before planning. After all satellites obtain the observation availability masks and the communication availability masks mentioned in Sections 2.2 and 2.3, respectively, ICBBA can be started. ICBBA is a typical market-based task allocation algorithm, which includes two main phases. The first phase is bundle construction, in which all nodes independently add tasks greedily to their bundle. The second phase is consensus check, in which nodes communicate with their neighbors to reduce conflict in the global task allocation based on action rules. On the premise of keeping each satellite clock in sync with the ground, 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. For the decentralized approach, each node cannot perceive the global planning information, and it can only receive the planning information from its neighbors. Therefore, each satellite actually does not know whether the global consensus has been reached (that is, each satellite does not know whether the global algorithm has been terminated) but only whether the consensus between itself and its neighbors has been reached. Although there is no centralized node for unified planning, as long as each decentralized node operates correctly, the global convergence can still be achieved. The convergence of CBBA has been proved in the original work [24]: for dynamic networks in which the communication network topology varies with time, the convergence of CBBA with a conflict resolution phase can still be guaranteed if the union of network topologies for the effective communication of each agent is fully connected. As we introduced in Section 2.3, intra-plane ISLs and inter-plane ISLs allow each satellite node to be fully connected within ICBBA running time, and no node is isolated. * Algorithm-related variables: \(T\) is the iteration time that records the running times of bundle construction. \(\mathbf{b}_{i}\) is the bundle of \(sat_{i}\) with the length of \(B_{i}\), where the element \(b_{in}\) is the \(n\)th entry of \(\mathbf{b}_{i}\). \(\mathbf{y}_{i}\) is the winning bid list of \(sat_{i}\), where the element \(y_{ij}\) is the global winning bid for \(task_{j}\) with the knowledge of \(sat_{i}\). \(\mathbf{z}_{i}\) is the winning satellite list of \(sat_{i}\), where the element \(z_{ij}\) is the global winning satellite index for \(task_{j}\) with the knowledge of \(sat_{i}\). \(\mathbf{s}_{i}\) is the time stamp of the last information update from each of the other satellites, where the element \(s_{ii^{\prime}}\) is the last information-update time stamp of \(sat_{i^{\prime}}\) with the knowledge of \(sat_{i}\). \(DMG_{ij}\), Diminishing Margin Gain, indicates that if \(task_{j}\) is assigned to \(sat_{i}\), the maximum \(fp_{j}^{\text{task}}\) that can be obtained without conflict with the tasks is already added to \(\mathbf{b}_{i}\). The mask index and the task execution start time corresponding to \(DMG_{ij}\) are denoted as \(k_{ij}^{\text{DMG}}\), \(st_{ij}^{\text{DMG}}\), respectively. Each time, the task index added to \(\mathbf{b}_{i}\) is denoted as \(j^{\text{add}}\). With the addition of tasks, some masks belonging to the tasks that have not been added to the bundle may be unavailable due to constraint conflicts. Therefore, a mask enabling flag \(f_{ijk}\) initialized to \(1\) is introduced; \(f_{ijk}=1\) if \(oam_{ijk}\) is available, \(f_{ijk}=0\) otherwise.