The discrete version of the agile Earth Observation Satellite Scheduling (EOSS) Problem is an NP-complete combinatorial optimization problem with a binary decision variable representing each imaging possibility of fitting customer requests along a discrete satellite path. A set of customer's requests have to be acquired on Earth, determined by different priority and acquisition constraints. In addition, when it comes to agile very high resolution satellites, the number of requests is way more important than the satellite acquisition capability. The optimization problem itself is equivalent to the maximum weighted clique problem and the generalized knapsack problem. The decision space is constrained by a the complex maneuverability check, which requires the execution of non linear models to be verified, a maximum amount of images per request and per time unit, as well as a strip request constraint allowing for the imaging of customer requests that are larger than the swath of the considered Earth Observation (EO) satellite. In addition, this mission plan has to be computed from the ground and uploaded to the satellite before each pass over a ground station. In order to include last minute requests, it is therefore important that the optimization algorithm used does not require more than a few minutes.

In this competition, we consider a Large-scale problem scenario consisting of a 12 hour planning horizon with a time resolution (discretization) of 5 seconds. We have a fleet of high-resolution and highly agile EO satellites consisting of the Pleiades NEO 3, NEO 4 satellites, as well as the Spot 6 satellites. Agility for a satellite means that it can rotate around its 3 axis. Therefore, the mission schedule does not only consist in choosing the area on Earth to image but the exact date and satellite attitude at the moment the satellite acquires it. We consider spot and strip imaging capabilities (that is, single shot and multi-shot images of requests) to be allowed in the customer database consisting of 1000 customer requests spread around the globe.

As previously said, the satellites agility is modeled by non linear simulators. However, the maneuver feasibility between two image acquisitions can be precomputed and we can therefore transform it into a linear constraint, and consequently we can write the EOSS problem as a linear programming problem in the following form:
Max_x∈X F(x)
s.t.
x ∈ {0, 1}^D
where D is the number of attempts considered. The decision variable is consequently representing all the feasible imaging attempts considered in the time horizon. Before a pre-processing step removes attempts that violate off-nadir angle, sun elevation, and cloud cover forecasts, D is equal to the number of requests times the number of time steps considered in the discretized time horizon.
Fx ≤ f
This is the maneuverability infeasibility constraint. It comes from the pairwise infeasibility matrix H in which only consecutive images that follow the satellites maneuverability capabilities are allowed. H has dimensions D times D and is binary with Hi, j = 0 if attempts x(i) and x( j) are possible in the same tasking schedule, if Hi, j = 1 then the pair of attempts are not feasible to execute consecutively due to the acquisition duration of attempt x(i) and maneuverability time between attempts i and j is too much to meet the acquisition time of x(j). Note in H only the infeasible attempts forward in time from attempt i is considered, thus having ones only in the upper triangular elements of H. We convert H to the matrix F by having pairs of attempts that acquired together are infeasible or complete sets attempts that are infeasible. One of these infeasible sets are then represented by ones in a row of the matrix F. That is, to ensure we do not over-constrain the solution space. Consequently, F has dimensions equal to the number of infeasible sets/pairs of attempts times D. Here f equals 1 for each row there is in F, thus ensuring that when acquiring attempts only two attempts that are not infeasible together per F can be acquired. Lastly, the infeasibility is naturally only considered for set of attempt performed by the same satellite.
Ax ≤ a
Thereby a maximum of a(t) images per time unit. Here, a(t) is equal to one for all t since the satellite cannot image two acquisitions at the same time. The matrix A has dimension T times D, where T is the number of time instances in which attempts can be acquired for each satellite, that is, we have removed all the time instances in which no attempts are considered. A is binary and represents for each time instance and each satellite all the attempts that occur in that time instance and is performed by the same satellite.
Bx ≤ b
This constraint states that a maximum of b(r) images per request can be acquired. Note, for larger image requests than the swath of the satellite, we assume the acquisitions can be completed by acquiring the same request b(r) amount of times, where that corresponds to the width of the image request divided by the swath capabilities of the satellite. Here the B is a binary matrix with dimensions R times D, where R is the number of requests that are reachable by any other satellites and thus considered in the EOSS.

PHASES
The competition consists of two phases:
In the first phase, we consider a single objective version of the above EOSS problem. That is the objective function is:

F(X) := maximize the number of acquisitions during the planning horizon.

In the second phase, we consider a multi-objective version of the EOSS problem. That is, the
objective function set F(X) := {f1, f2, f3}, where:

f1 : = maximize number of acquisitions,
f2 : = maximize number of prioritized (emergency) acquisitions, and
f3 : = minimize the average cloud coverage.

Thus we seek to get the solution set, that best represents the Pareto front of the stated problem. We therefore evaluate based on number of non-dominated solutions, the hyper volume of the solution set, and the average diversity between neighboring solutions.

Since both phases are evaluated in a single-shot manner, we will evaluate the evolutionary algorithm that performs the best after a run time of 100 seconds. In the second phase only a population of 100 solutions should be returned. The algorithms are run on the same computer with specifications of that of a regular laptop. We encourage participants to submit their algorithm in Python, but it is not necessary.

We encourage participants to share their algorithm with the organizers through GitHub (see the judging segment!).

The large scale and highly constrained nature of the provided problem scenarios should yield participants good means for developing novel operators to efficiently search the solution space and comply with the constraints in an intuitive and evolutionary manner. Especially the infeasibility constraint is expected to challenge participants!

We look very much forward to seeing your contributions!