# On-Board Decentralized Observation Planning for LEO Satellite Constellations
## 2 Problem Description
### Mathematical Formulation
Based on the above variable definitions, the mathematical model of MSOOP is formulated as follows:  
\[\max\sum_{i=1}^{N}\left(\sum_{j=1}^{M}\left(\sum_{k=1}^{O_{ij}}x_{ijk}fp_{j}^{ \text{task}}\right)\right) \tag{2}\]  
subject to  
\[\sum_{j=1}^{M}\left(\sum_{k=1}^{O_{ij}}x_{ijk}st_{j}^{\text{task}}\right)\leq st _{i}^{\text{sat}},\ \forall i\in\mathcal{I} \tag{3}\]  
\[\sum_{j=1}^{M}\left(\sum_{k=1}^{O_{ij}}x_{ijk}ene_{j}^{\text{task}}\right)\leq en _{i}^{\text{sat}},\ \forall i\in\mathcal{I} \tag{4}\]  
\[\sum_{i=1}^{N}\left(\sum_{k=1}^{O_{ij}}x_{ijk}\right)\leq 1,\ \forall j\in \mathcal{J} \tag{5}\]  
\[st_{ijk}^{\text{oam}}\leq st_{j}^{\text{task}}<et_{j}^{\text{task}}\leq et_{ ijk}^{\text{oam}},\ \text{ if }x_{ijk}=1 \tag{6}\]  
\[et_{j}^{\text{task}}+amt_{ij}^{\text{task}}\leq st_{f}^{\text{task}},\ \text{ if }et_{j}^{\text{task}}<st_{f}^{\text{task}} \tag{7}\]  
\[st_{j}^{\text{task}}+dur_{j}^{\text{task}}=et_{j}^{\text{task}},\ \text{ if }\sum_{i=1}^{N}\left(\sum_{k=1}^{O_{ij}}x_{ijk}\right)=1 \tag{8}\]  
\[x_{ijk}\in\left\{0,\,1\right\},\ \forall(i,j,k)\in\mathcal{I}\times\mathcal{J} \times\mathcal{K}_{ij} \tag{9}\]  
where Formula (2) represents that the objective function is to maximize the total profit; Formulas (3) and (4), respectively, use the storage constraint and the energy constraint to restrict the number of tasks completed by each satellite; Formula (5) describes the consensus constraint; Formulas (6)-(8) describe the special temporary constraints in MSOOP, Formula (6) means the observation action of each planned task must be within the observation availability mask; Formula (7) means any two observation actions do not overlap and the attitude maneuver time between them should be reserved; Formula (8) means there must be a duration needed for each planned task to receive a complete observation action; Formula (9) guarantees that once an observation action starts, it cannot be preempted. According to attitude maneuver capability, Earth Observation Satellites are divided into non-agile satellites and agile satellites. Non-agile satellites have one axe of the single direction (roll), which means the target can only be imaged when the satellite is just on the top of target point. In Formula (6), if \(task_{j}\) is assigned to \(oam_{ijk}\), the execution start time \(st_{j}^{\text{task}}\) should be equal to \(s_{ijk}^{o\text{am}}\) and the execution end time \(et_{j}^{\text{task}}\) should be equal to \(et_{ijk}^{o\text{am}}\). Agile satellites are mobile along three axes (roll, pitch and yaw). This mobility makes the target also can be imaged even if the satellite flies over or does not reach the target point. Agile satellites have the longer observation availability mask for a task than non-agile satellites. So, we need to determine not only \(x_{ijk}\) but also \(st_{j}^{\text{task}}\) and \(et_{f}^{\text{task}}\) of each task. Observation planning for single agile satellite has been proved to be NP-hard [25]. \(st_{j}^{\text{task}}\) and \(et_{f}^{\text{task}}\) are continuous variables, so it is difficult to use discrete algorithms to determine. In this paper, we use heuristic strategies such as forward arrangement and central arrangement to determine the execution time of each task. The above constraints are divided into coupled constraints and uncoupled constraints. Coupled constraints include any situation where the decisions regarding one task or agent affect the options available regarding other tasks or agents. The constraints described in Formulas (3)-(5) and (7) are coupled constraints. The observation action of each task may cause other observation masks to be disabled due to insufficient storage or energy, avoidance of re-assignment, or lack of attitude maneuver time. These coupled constraints make MSOOP more complex than other task allocation problems.