## 7 Experimental Evaluation
### Benchmarks
#### 7.1.2 From Requests to DAGs  
In order to encode the problem within the DPAP framework, we first create an agent \(u\) for each user that has an observation request. Then, for each request \(r\) associated with agent \(u\), we first create a graph \(g_{r}\) and define a function \(\mu\) such that \(\mu(g_{r})=u\). In a graph \(g_{r}\) created for request \(r\), the nodes are the orbit slots usable for capturing the POI targeted by \(r\) at some RT, and the edges link two such consecutive orbit slots. We also add a source node that precedes all of the orbit slots of the earliest RT and a sink node that follows all of the orbit slots of the latest RT. Consequently, a path in the graph (i.e., a sequence of consecutive orbit slots) represents a way to satisfy \(r\). Figure 8 represents four requests (a, b, c, and d) from four users (respectively, A, B, C, and D), with three RTs that are time 3, time 9, and time 21. In this example, each RT has at most two possible orbit slots per request. For instance, for request a, there are two orbitslots for RT 3 (a\({}_{1}\) and a\({}_{3}\)), one orbit slot for RT 9 (a\({}_{2}\)), and two orbit slots for RT 21 (a\({}_{4}\) and a\({}_{5}\)). Requests c and d do not have any orbit slot for RTs 3 and 9 but two each for RT 21.  
For simplicity, even if the incoming arcs in the graphs of a DPAP for a given slot can have different weights, we only consider in our experiments utilities attached to the slots and not to the transitions between slots. As illustrated in Figure 9, for each candidate orbit slot for a given RT, we consider a utility function that is piecewise linear in the distance between the middle \(\tau\) of the slot and that RT. The utility linearly decreases from 1 when \(\tau\) is exactly on the RT to 0.25 when \(\tau\) reaches the bounds of the tolerance window, i.e., RT \(+\Delta\) and RT \(-\Delta\). We normalize each utility with respect to the maximum utility that can be achieved for each user individually along by using its best paths. Therefore, each user's set of best paths has a utility equal to 1.  
In order to limit the number of edges in graphs, we add a virtual node between all slots of one RT and all slots of the next RT. If there are \(n\) orbit slots for an RT \(t\) and \(m\) slots for the next RT \(t^{\prime}\), this allows there to be \(n+m\) edges (\(n\) edges with utility 0 going into the virtual node and \(m\) edges weighted by the utility of orbit slots going out of the virtual node) instead of \(n\cdot m\) edges (all \(n\) nodes connected to all \(m\) nodes).  
Last, we consider two variants of the problem depending on whether requests can be partially satisfied.  
* In the _full satisfaction_ variant, each path goes through one orbit slot for each RT, except for a specific direct source-to-sink path that allows us to guarantee that there exists at least one feasible path for each request. In other words, it is not possible to skip one RT for an observation request, unless this request is not served at all.
* In the _partial satisfaction_ variant, it is possible to skip some RTs for a request. In terms of generated graphs, it simply consists in adding edges with a null utility between successive virtual nodes, between the source and the first virtual node and between the last virtual node and the sink.  
Figure 10 illustrates the request \(a\) of Figure 8 in a full configuration (only black edges) and in a partial configuration (black and thick blue edges).  
Figure 10: Graph for request a of Figure 8 with virtual nodes between successive RTs. The graph with only black edges represents the problem in full satisfaction mode. The graph with both black and thick blue edges represents the problem in partial request satisfaction mode.  
Figure 9: Utility function used to compute the utility of an orbit slot with respect to some RT and a tolerance \(\Delta\).