# A Distributed Autonomous Mission Planning Method for the Low-Orbit Imaging Constellation
## 4 c-Cbba
### Task Preemption Strategy  
Based on the analysis of the implicit drawbacks of CBBA algorithm, the Task Preemption Strategy (TPS) is introduced to accelerate the convergence of the algorithm. In TPS, single satellite can autonomously preempt tasks. If the satellite continues to believe that it has the highest bid after aggregating the auction messages sent by its neighbors for a certain number of communications, it can preempt the task and inform the other satellites of this message. Then, other satellites will no longer add the preempted task to their own task bundle. At the global level, TPS overcomes the drawbacks of the task masking phenomenon. It is not necessary to wait for a high-bid task to identify the winning satellite before a lower-bid task can be efficiently scheduled, thus accelerating the process of global consistency. During the distributed operation of the algorithm, there may be a situation where multiple satellites are preempting the same task. Therefore, it is necessary to record the timestamp of the satellite's preemption of the task, and stipulate that the satellite that first preempts the task acquires the task.  
Each satellite requires additional maintenance of the following information:  
* \(u_{i}=\left\{u_{i1},\ u_{i2},\ldots,\ u_{ij},\ldots,\ u_{i|T|}\right\}\), the list of task preemption markers under the cognition of satellite \(s_{i}\), its length is the number of tasks \(\left\lvert T\right\rvert\). \(u_{ij}\) represents the preemptive marker of task \(t_{j}\). If \(t_{j}\) has already been preempted, then \(u_{ij}=1\); otherwise, \(u_{ij}=\)0.
* \(v_{i}=\left\{v_{i1},\ v_{i2},\ldots,\ v_{ij},\ldots,\ v_{i|T|}\right\}\), the task preemption timestamp list under the cognition of satellite \(s_{i}\), its length is \(\left\lvert S\right\rvert\). \(v_{ij}\) represents the timestamp of the earliest time when task \(t_{j}\) was preempted under the cognition of satellite \(s_{i}\).
* \(q_{i}=\left\{q_{i1},\ q_{i2},\ldots,\ q_{ij},\ldots,\ q_{i|T|}\right\}\), recording the number of communications made by the satellite that consistently considers itself to be the highest bidder. Its length is \(\left\lvert T\right\rvert\).
* \(\alpha\), the parameter of TPS. When \(q_{ij}\) reaches \(\alpha\) times, satellite \(s_{i}\) preempts task \(t_{j}\).  
1.1. 4.1.  
that meet the requirements. Note that the tasks in the task bundle need to be arranged in the order of addition. The selected task \(t_{j}\) must meet three conditions simultaneously:  
* The task bundle \(b_{i}\) needs to be able to satisfy the constraints of the model after joining task \(t_{j}\).
* Satellite \(s_{i}\)'s bid for task \(t_{j}\) needs to be higher than the highest bid recorded for \(t_{j}\) in the list \(y_{i}\) it maintains.
* Task \(t_{j}\) is currently not preempted, i.e., \(u_{ij}=0\).  
As task \(t_{j}\) is added to \(b_{i}\), the corresponding task information in \(y_{i}\) and \(z_{i}\) should be updated at the same time.  
Equation (9) defines the bidding function for the time window \(w_{ijk}\).  
\[g_{ijk}=\frac{r_{j}-\sum_{w_{ij}\
eq cConf_{ijk}}r_{j^{\prime}}/|S|}{m_{j}}, \tag{9}\]  
where \(Conf_{ijk}\) denotes the set of O-UTWs that have constraint conflicts (Equation (6)) with the time window \(w_{ijk}\). The bidding function aims to select tasks with high profit, less storage usage, and low conflict with other tasks.  
When tasks are executed on the same satellite, there are many coupling constraints, such as the constraints on the satellite attitude transition time represented in Equation (6). Therefore, during the bundle construction phase, constraint checking is required for every task added.