Gauthier Picard
email: gauthier.picard@onera.fr

Trajectory Coordination based on Distributed Constraint Optimization Techniques in Unmanned Air Traffic Management

Keywords: Unmanned Air Traffic Management, Coordination, Distributed Optimization, DCOP, 4D Contracts

In this paper, we explore a multiagent-based deconfliction strategy in Unmanned Air Traffic Management (UTM). We equip autonomous unmanned aerial vehicles (UAV) with decision capabilities to update their trajectories (4D contracts) when facing unpredictable events or when priority trajectories are added to the airspace. Current initiatives for UTM envision a multi-layered management system where the lowest one is composed of either autonomous UAV or human-operated one, that may have to react to incidents and emergencies, while sticking to the contracted 4D trajectories. We propose an agent-based approach, where UAVs, being aware of close potential conflicts provided by the UTM communication layer, can coordinate directly, without central UTM control, to update trajectories and solve resulting conflicts in a decentralized manner. This reduces the access to a central decision bottleneck and permits reactive deconfliction. We propose both uncoordinated and DCOP-based coordinated behaviors, that we experimentally evaluate on dense scenarios within a limited area with numerous 4D contracts, potential incidents and emergency procedures.

INTRODUCTION

In 2018, the NextGen office of the US Federal Aviation Administration (FAA) published a first global concept of operations (ConOps) for unmanned aircraft system traffic management (UTM) that presents a vision and describes the associated operational and technical requirements for developing a supporting architecture and operating in a UTM ecosystem [START_REF]UTM concept of operations version 2.0[END_REF], depicted in Figure 1. This is a community-based traffic management system in which operators and entities providing operations support services are responsible for the coordination, execution, and management of operations, with rules of conduct established by the FAA. This federated set of services enables cooperative operations management among UAS (unmanned aircraft systems) operators, facilitated by thirdparty service providers (USSP) through networked information exchanges. UTM is designed to support the demand and expectations for a broad spectrum of operations with ever-increasing complexity and risk through an innovative and competitive open market of service providers. The services provided by USSP are interoperable to enable the UTM ecosystem to meet the needs of the UAS operator community. This working document also proposes a set of scenarios raising strong coordination issues, whose resolution proves to be real scientific challenges as illustrated in [START_REF] Hamadi | Optimization for Urban Air Mobility[END_REF], and which also allow to define scenarios for the evaluation of candidate solutions. On the European side, the operational model envisioned by the Single European Sky Air Traffic Management Research (SESAR), called U-Space, also identifies the needs for coordination between actors, and the distribution of decisions [START_REF]European ATM Master Plan: Roadmap for the safe integration of drones into all classes of airspace[END_REF], and supported by the CORUS concept of operations [START_REF][END_REF]. This service-oriented vision is also promoted by manufacturers and companies as Airbus and Boeing [START_REF] Airbus | A New Digital Era of Aviation: The Path Forward for Airspace and Traffic Management[END_REF], and opens doors for various implementations, as in [START_REF] Capitán | Unmanned Aerial Traffic Management System Architecture for U-Space In-Flight Services[END_REF] for instance. Although they display notable differences (classification of UAVs, sectorization of airspace, level of security, responsibilities of the USS) as identified in [START_REF] Lieb | Unmanned Aircraft Systems Traffic Management: A comparsion on the FAA UTM and the European CORUS ConOps based on U-space[END_REF][START_REF] Mccarthy | Fundamental Elements of an Urban UTM[END_REF], these ConOps converge on many points (service orientation, modularity, confidentiality, highlevel actors, separation into strategic, tactical and reactive levels), particularly concerning the coordination of USSPs and UAS.

In this paper, we propose an adaptive coordination mechanism enabling unmanned aircraft systems (autonomous or operated) evolving in a urban free route airspace to handle trajectory conflicts due to delays, incidents (e.g. the UAV has to stay in position for capturing some image of a monitored area) or the appearance of new high priority trajectories (e.g. emergency helicopter evacuation). While there exist some adaptation strategies (postponing trajectories or elevating trajectories) to avoid future trajectory conflicts, we propose here to make UAVs coordinate using a direct messaging service (either direct vehicle-to-vehicle or using platform-wide communication) to solve conflicts, and to choose the best actions wrt. multiple objectives. The coordination mechanism is based on distributed constraint optimization, as to ensure UAVs will collectively choose deconfliction actions, while minimizing some operational indicators. The subject of our study being the interaction between UAVs and USSPs, the proposed results aim be generic enough to be applicable to the different UTM and U-Space concepts of operations. Our approach addresses the online 4D contract repair in a distributed fashion. Multi-agent-wise, as far as we know, there is no multi-agent approach to this problem, which is a novel topic following these new concepts of operation in urban air spaces.

This paper is structured as follows. In Section 2, we present an illustrative scenario emphasizing the need for coordination in multi-UAV settings. Section 3 expounds the operational model we use, based on recent concepts of operation [START_REF]UTM concept of operations version 2.0[END_REF][START_REF][END_REF], and particularly focus on the 4D trajectory model the UAV will commit to. It also presents three uncoordinated deconfliction behaviors (namely, postpone, elevate, and skip), while Section 4 details the coordinated and adaptive approach based on distributed constraint optimization. We experimentally evaluate these behaviors, and multiple DCOP solution methods, on scenarios with randomly generated trajectories, incidents and emergency trajectories. Section 6 finally concludes the paper with some perspectives.

ILLUSTRATIVE SCENARIO

Let's use an illustrative scenario to highlight the needs for coordination and adaptation in unmanned Urban Air Traffic settings, depicted in Figure 2. We mainly reuse the scenario proposed in [START_REF]UTM concept of operations version 2.0[END_REF], focused on a free route airspace. We consider a 2km by 2km urban area where several UAVs operators have requested some 4D trajectories to perform different tasks, as delivery, surveillance or ground image capturing. These trajectories have been requested to the UTM, which in return sends the 4D way-points (3D space and time) the UAVs have to follow to perform their tasks. UTM also provides some tolerance margins to diverge from the initial trajectory, represented as safety tubes encapsulating the trajectories. The trajectories (and their respective safety tubes) provided by the UTM are ensured to be spatio-temporally conflict-free but require to be requested some hours before the operations. In short, as to flight in this free route area, operators have to inform UTM in advance. The resulting 4D trajectories are thus contracted (and then called 4D contracts), and UAVs commit to these contracts.

However, in some cases, UAVs may not be able to stick to their trajectory. For instance, unpredictable wind may drastically change the trajectories, especially on small and light UAVs [START_REF] Perozzi | Trajectory tracking for a quadrotor under wind perturbations: sliding mode control with state-dependent gains[END_REF]. Moreover, some tasks may require an UAV to stay in position to implement some surveillance routine (e.g. a monitoring UAV detecting a hazard on its surveillance area has to capture the scene on different angles). Finally, some high priority trajectories may be added to the airspace, due to emergency reasons. For instance, following a road accident, Figure 2: A sample scenario with 3 UAVs following their trajectories (green, blue and yellow) handling some incidents (orange stars), a Medevac helicopter on its emergency trajectory (red), and some identified conflicts (red circles).

a Medevac Helicopter may fly to the accident destination, evacuate the injured people, and then fly back to the hospital, thus potentially generating several conflicts with current trajectories. 4D contracts do not handle such conditional and non deterministic trajectories, and thus must be updated when such events occur.

In our scenario and experiments, we will consider UAVs having some surveillance trajectories, and that may have to implement some incident surveillance routine (with stationary flight), thus suspending their current trajectory. The occurrence of such incidents is not known in advance, and is assumed fully random. We will also consider some emergency events, with destination not known in advance too, that are high priority and cannot be negotiated. In Figure 2, 3 UAVs are following their trajectories (green, blue and yellow) and handling some incidents (orange stars), which will delay their planned trajectories, and thus generate a conflict (red circle at yellow-green crossing) at a position that was spatio-temporally safe before. Even more conflicting, a Medevac helicopter has to cross the airspace in emergency, thus leading so two other conflicts (red circles at green-red and blue-red crossings).

We position the work at the UAS level of Figure 1, where UAVs can directly exchange information via V2V communication, they can receive commands and orders from operators, and obtain some real-time info (e.g. about trajectories, conflicts, emergency procedures) from some USSPs. We envision the proposed tactical and reactive coordination mechanisms to take place between several (semi-)autonomous UAS or between several UAS operators, depending on the autonomy of the vehicles. We notably focus on small UAVs able to perform stationary flight and operating at low altitude (between 0m and 300m).

4D Trajectories

A trajectory is a set 𝑊 ⊂ R 4 of 4D points 𝑤 = (𝑥, 𝑦, 𝑧, 𝑡) where 𝑥 and 𝑦 are coordinates on the 2D plane (or GPS coordinates), 𝑧 is the altitude, and 𝑡 the time. These points define way-points UAVs have to flight over. We call a segment 𝑙 = (𝑤 𝑠 , 𝑤 𝑒 ) a line between two timely consecutive points. We will only consider horizontal and vertical segments. UAVs evolves on planes or move to another plane using a vertical segment. Thus the airspace is divided into several planes separated by a constant height, noted 𝑍 sep . On each plane, the routes are free, which means there is no predefined flight network. A trajectory is also defined by safety margins, as to prevent UAVs from collision, letting time and space for reactive avoidance routines to subsume navigation orders. Classically, these safety tubes are defined horizontally (for 𝑥 and 𝑦 dimensions), vertically (for 𝑧) and timely (for 𝑡). So a safety tube is defined by 𝜏 = (ℎ, 𝑣, 𝑡). A UAV is diverging when outside of the safety tube of its current flight segment. A UAV is violating a trajectory if its position is inside the safety tube of another UAV. Formally, A point 𝑤 0 is inside a safety tube (ℎ, 𝑣, 𝑡) for segment 𝑙 = (𝑤 1 , 𝑤 2 ) if it satisfies all three conditions (1) and ( 2) and (3):

|(𝑥 2 -𝑥 1 )(𝑦 1 -𝑦 0 ) -(𝑥 1 -𝑥 0 )(𝑦 2 -𝑦 1 )| 𝑑 𝑥 𝑦 (𝑤 1 , 𝑤 2 ) ≤ ℎ (1) min(𝑧 1 , 𝑧 2 ) -𝑣 ≤ 𝑧 0 ≤ max(𝑧 1 , 𝑧 2 ) + 𝑣 (2)
|𝑡 0 -(𝑡 1 + 𝑑 𝑥 𝑦 (𝑤 1 , 𝑝 𝑥 𝑦 (𝑤 0 , 𝑙)) 𝑑 𝑥 𝑦 (𝑤 1 , 𝑤 2 ) 𝑑 𝑡 (𝑤 1 , 𝑤 2 ))| ≤ 𝑡 (3)
with 𝑑 𝑥 𝑦 the 2D Euclidean distance, 𝑑 𝑡 the 1D time distance, and 𝑝 𝑥 𝑦 (𝑤, 𝑙) the 2D projection of 𝑤 on 𝑙. Two segments are in conflict if they are on the same plane (either horizontally or vertically) and they intersect at the same time (at the tolerance 𝑡). Building 4D trajectory is a classical operational problem with an extensive literature. It has been very well studied in the context of aircraft traffic management [START_REF] Delahaye | Front Matter[END_REF][START_REF] Delahaye | Mathematical Models for Aircraft Trajectory Design: A Survey[END_REF]. Building conflict-free trajectories is a hard optimization problem, often solved using metaheuristics as simulated annealing [START_REF] Islami | Large-Scale 4D Trajectory Planning[END_REF] or evolutionary algorithms [START_REF] Su | A multi-objective multi-memetic algorithm for network-wide conflict-free 4D flight trajectories planning[END_REF]. In the presence of small UAVs able to change direction and speed in a more flexible way than classical aircrafts, the problem remains a hard one, but other techniques as PSO [START_REF] Alejo | Particle Swarm Optimization for collision-free 4D trajectory planning in Unmanned Aerial Vehicles[END_REF] or even multi-agent based ones [START_REF] Zhao | Four-Dimensional Trajectory Generation for UAVs Based on Multi-Agent Q Learning[END_REF] have been considered. We study here unstructured, free route airspace, i.e. there is no predefined air traffic route network the trajectories are constrained to, contrary to usual ATM operational concepts [START_REF] Nava-Gaxiola | Study of a Full Implementation of Free Route in the European Airspace*[END_REF]. In our case, we will consider the initial trajectories to be conflict-free, obtained from any trajectory generator (incremental in our experiments).

We focus on the repair procedure; not the generation of the initial set of trajectories. We aim at optimizing some criteria related to the quality of the repair. We consider here: (i) minimizing the number of conflicts generated by the trajectory adaptation, as to ensure flight safety; (ii) minimizing the number of missed way-points, as to ensure the quality of the trajectories, especially in urban context, where trajectories are defined to fulfill some missions between and at these way-points; (iii) minimizing the overall delay induced by the adaptation. Such a problem is non-trivial and may require some trade-off; e.g. skipping a conflicting segments improves safety but reduces quality of service.

UAVs

Our scenario considers a set 𝑈 of UAVs, 𝑢 = (𝑝, 𝑠, 𝑑,𝑇 ), where 𝑝 = (𝑥, 𝑦, 𝑧, 𝑡) ∈ R 4 is its position, 𝑠 = (ℎ, 𝑣, 𝑎) ≤ (ℎ 𝑚𝑎𝑥 , 𝑣 𝑚𝑎𝑥 , 𝑎 𝑚𝑎𝑥 ) ∈ R 3 represents its current horizontal (in m.𝑠 -1 ), vertical (in m.𝑠 -1 ) and angular (rad.𝑠 -1 ) speeds. 𝑑 ∈ [0, 2Π] defines its current direction, and 𝑇 is its 4D trajectory/contract. Note that these speed values can be equal to zero (e.g. no motion). In nominal conditions, UAVs change their speed and direction as to reach their next waypoint on time, or to enter back into their safety tubes if they have been forced to exit (e.g. due to strong wind or obstacle avoidance).

In case, there is an incident close to its position, a UAV will stay at the same position (they keep a way-point at their current position) to observe the situation for a given time. Then it will switch back to its nominal trajectory. We model this target-following behavior as a simple motion model. When 𝑢 is at position 𝑝, aiming to reach position 𝑜 at angle ∠(𝑝, 𝑜) ∈ [-Π, Π], it will apply the following variations to its three degrees of freedom:

Δℎ = min( 𝑑 𝑥 𝑦 (𝑝, 𝑜) 𝑑 𝑡 (𝑝, 𝑜) , Δℎ 𝑚𝑎𝑥 ) (4)
Δ𝑣 = min( 𝑑 𝑧 (𝑝, 𝑜) 𝑑 𝑡 (𝑝, 𝑜) , Δ𝑣 𝑚𝑎𝑥 ) (5)
Δ𝑎 = sgn(∠(𝑝, 𝑜)) • (min(∠(𝑝, 𝑜), Δ𝑎 𝑚𝑎𝑥 ) (6)
leading to the following position variation:

Δ𝑝 = (ℎ cos(𝑑), ℎ sin(𝑑), 𝑣, 𝑎) (7)
UAV nominal behavior depicted in Figure 3 consists first in perceiving the environment and checking incoming messages. Then if no conflict, nor close obstacle is detected, the UAV chooses a target position (either a way-point, an incident location, or its contracted position if it diverged), and then move by adjusting its speeds using (4), ( 5) and ( 6) to reach a new position 𝑝 + Δ𝑝 bringing it closer to its target position. UAVs communicate with UTM services (e.g. geolocalization, conflict detection) and with their neighboring UAVs (either directly or via USSP). Such communication may warn about conflicts. In such case, the UAV will deconflict by possibly updating its trajectory. UAVs are also equipped with reactive collision avoidance routine if they detect a mobile too close to their position. In such case the UAV will perform a "sense and avoid" behavior [START_REF] Zeitlin | Sense amp; Avoid capability development challenges[END_REF], we do not detail in this paper.

UTM Services

UAV operators subscribe to services as to obtain information and provide information about their ongoing missions. Real-time information (about positions, conflicts or new inserted trajectories) are send by the services to the subscribed UAVs, while trajectory update requests and incident report are sent by the UAVs to the USSPs. We consider at least the following services:

• A direct messaging service (DMS), which enables UAVs to communicate in a P2P manner. UAVs will make use of this service to send coordination messages (related to the DCOP solution method, see Section 4). • A conflict detection service (CDS), which sends to subscribers the conflicts to occur in the next few minutes, following a trajectory update or a new trajectory addition. A conflict information contains the intersecting segments, the respective UAVs, and the intersection point. We note 𝐶 (𝑢) the set of conflicts in which 𝑢 is involved. As to keep it reactive enough, the conflict detection is performed at a limited horizon: it only checks the 𝑘 next segments for each trajectory, starting a the current time. • A trajectory update service (TUS), that UAVs request to postpone their current trajectory or to add new way-points (e.g. to bypass an obstacle outside the safety tubes). In return, the service sends back the new trajectory and the new conflicts (if any). Indeed, if a UAV has to postpone its trajectory, it may produce conflicts on future segments. • A trajectory assessment service (TAS) which is queried for evaluating the replacement of a trajectory by another. This service returns the new trajectory and some evaluation metrics (e.g. the number of generated conflicts and the resulting delay compared to the replaced trajectory).

Deconfliction Actions and Behaviors

After the conflict-free system starts, non predicted events (as incidents or emergencies) will eventually require the contracts to be broken. Because conflicts mostly consist in intersections on the same plan, and since the considered UAVs are able to perform stationary flight, three main options are opened for updating the contracts: postpone, elevate and skip.

Postpone. The principle of this update is simple: delaying all the way-points of the contract after a given date for a given time, as to be able to avoid a conflict or to have enough time to observe an incident. Postpone is automatically called when a UAV detect an incident close to its position. It will then request to the contract update service a delay for a time depending on the incident. All the way-points after its current spatio-temporal position are delayed by this amount of time. Postpone can also be called by UAVs as to avoid a future potential conflicts identified by the conflict detection service. In such a case, the UAVs will add a new way-point before the intersection and delay its route for an amount of time equals to the time required to extract from a safety tube. We will call postpone UAVs, UAVs only performing postpone deconfliction actions.

Elevate. Another approach to deconfliction with UAVs able of vertical flight if make the UAVs change their plane (either down or up), to bypass the conflict location, and then to flight back to is previous plane. This action is performed as to avoid obstacles or to prevent a future potential conflict. When requesting an elevate update, a UAV provides the conflict or the position to avoid, and the trajectory update service will send back an updated trajectory with a "bridge" over the position to avoid, i.e. the addition of 4 way-points to create a vertical segment, followed by an horizontal one, and finally another vertical one. A bridge is either upward or downward (depending on the altitude). We will call elevate UAVs, UAVs only performing elevate deconfliction actions.

Skip. Finally, one may just skip a conflicting segment, by removing its starting way-point. This the UAV will bypass the conflict by moving directly to the way-point after the conflicting segment. When requesting a skip, the UAV just provides the conflicts to the trajectory update service that will remove the related way-point, and send back the new trajectory. We will call skip UAVs, UAVs only performing skip deconfliction actions.

DCOP-BASED COORDINATION

This section defines a cooperative coordination between UAVs, so that they jointly decide which UAVs will trigger a specific deconfliction action for a given conflict. We model this collective decision problem as a DCOP.

DCOP Framework

Distributed Constraint Optimization Problem (DCOP) is the distributed variant of constrained optimization [START_REF] Modi | ADOPT: Asynchronous distributed constraint optimization with quality guarantees[END_REF]. Here a group of agents must choose values for a set of variables in a decentralized way in order to minimize a cost function or to maximize a utility function. Formally, A DCOP is a tuple ⟨A, X, D, C, 𝜇, 𝑓 ⟩, where: A = {𝑎 1 , . . . , 𝑎 |𝐴| } is a set of agents; X = {𝑥 1 , . . . , 𝑥 𝑛 } are variables owned by the agents; D = {D 𝑥 1 , . . . , D 𝑥 𝑛 } is a set of finite domains, such that variable 𝑥 𝑖 takes values in D 𝑥 𝑖 = {𝑣 1 , . . . , 𝑣 𝑘 }; C = {𝑓 1 , . . . , 𝑓 𝑚 } is a set of soft constraints, where each 𝑓 𝑖 defines a cost ∈ R + ∪ {+∞} for each combination of assignments to a subset of variables (a constraint is initially known only to the agents involved); 𝛼 : X → A maps variables to their associated agent; 𝑓 : D 𝑥 𝑖 → R is an objective function, representing the global cost of a complete variable assignment. The optimization objective is represented by function 𝑓 , which, in general, is considered as the sum of costs: 𝑓 = 𝑖 𝑓 𝑖 . A solution to a DCOP 𝑃 is a complete assignment to all variables. A solution is optimal if it minimizes 𝑓 .

DCOP have been widely studied and applied to many areas [START_REF] Fioretto | Distributed Constraint Optimization Problems and Applications: A Survey[END_REF], because: (i) they focus on decentralized approaches where agents coordinate a joint solution through local message exchanges; (ii) they exploit the domain structure (by encoding it in constraints) to address hard computational problems; (iii) there exists wide variety of solution methods ranging from exact methods to heuristic and approximate techniques. We refer the reader to Fioretto et al.'s survey for a recent catalog of algorithms [START_REF] Fioretto | Distributed Constraint Optimization Problems and Applications: A Survey[END_REF]. DCOP solution methods implement direct message passing, which, in the context our UTM, are send via a DMS.

Solving Conflicts with DCOP

Let's now model our coordination problem into a DCOP to be instantiated each time some UAVs are aware of some conflict. The idea is twofold: (i) let UAVs choose between several deconfliction actions when a conflict is detected; and (ii) make UAVs involved in the same conflict coordinate to choose which one is the best for performing the deconfliction.

The set of agents A ⊆ 𝑈 is the set of UAVs that have been alerted by the conflict detection service for being part of some conflict. Each such UAV 𝑢 is aware of its conflicts 𝐶 (𝑢) and the other UAVs it is in conflict with, 𝑈 (𝐶 (𝑢)) = {𝑣 ∈ 𝑈 | 𝑣 ≠ 𝑢, 𝐶 (𝑢) ∩ 𝐶 (𝑣) ≠ ∅}. For a given conflict 𝑐, a UAVs is able to perform some deconfliction actions; e.g. postpone(𝑐, 20), elevate(𝑐, -15), elevate(𝑐, +15) and skip(c). We note I this set of actions.

The decisions consist in choosing the deconfliction action to trigger for each known conflict. Let's note 𝑥 𝑢,𝑐,𝑖 ∈ {0, 1} the decision variable stating whether UAV 𝑢 decides to solve conflict 𝑐 using action 𝑖. Actions are either postpone, elevate or skip. Thus, X = {𝑥 𝑢,𝑐,𝑖 | 𝑢 ∈ A, 𝑐 ∈ 𝐶 (𝑢), 𝑖 ∈ I}, D = {𝑑 𝑥 𝑢,𝑐,𝑖 = {0, 1} | 𝑢 ∈ A, 𝑐 ∈ 𝐶 (𝑢), 𝑖 ∈ I}, and 𝛼 : 𝑥 𝑢,𝑐,𝑖 ↦ → 𝑢.

Constraints fall into two categories: unary costs (preferences for actions), and coordination ones preventing the same conflict to be solved more than once. Concerning unary costs, we model preferences for actions generating less conflicts without decreasing the quality of service (i.e. increasing the number of missed way-points), and delaying the mission. Agents should be able to valuate the actions using the trajectory assessment service. We note 𝑣 conflict (𝑖, 𝑐) (resp. 𝑣 missed (𝑖, 𝑐) and 𝑣 delay (𝑖, 𝑐)) the number of conflicts (resp. the number of missed way-points and the delay) of the trajectory when performing action 𝑖 to solve conflict 𝑐. We aggregate these multiple local objective valuation by linearization and prioritization, as follows, for all 𝑢 ∈ 𝑈 , 𝑐 ∈ 𝐶 (𝑢) and 𝑖 ∈ I: 𝑓 pref (𝑥 𝑢,𝑐,𝑖 ) = 𝜔 2 • 𝑣 conflict (𝑖, 𝑐) + 𝜔 • 𝑣 missed (𝑖, 𝑐) + 𝑣 delay (𝑖, 𝑐) [START_REF] Farinelli | Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm[END_REF] with 𝜔 a sufficiently large number to assign preference to conflict resolution against missed way-points and delay reduction. This aggregated valuations model the multiple objectives discussed in Section 3. Concerning coordination constraints, we must ensure exactly one 𝑥 𝑖,𝑐,𝑢 variable is set to 1 for the same conflict. Thus, for each such conflict 𝑐:

∑ 𝑢 ∈𝑈 ∑ 𝑖 ∈ I 𝑥 𝑖,𝑐,𝑢 = 1 (9)
In order to fit into the DCOP framework, this hard constraint is encoded into a soft constraint as follows:

𝑓 exo (𝑥 𝑢 1 ,𝑐,𝑖 1 , . . . , 𝑥 𝑢 |𝑈 | ,𝑐,𝑖 |I| ) = 0, if (9) +∞, otherwise (10)
Therefore, C is the set of constraints from ( 8) and ( 9). The objective function is the sum of all these constraints, thus aiming first at solving existing conflicts and then reducing the overall delay.

This DCOP can be distributively solved by the involved agents, using any DCOP solution method from the literature, each time agents require to coordinate. In the case an agent detects a conflict with a non-negotiable trajectory (e.g. an emergency), it will still try to solve the same mono-agent problem, thus deciding which alternative between skip, elevate and postpone is the better.

EXPERIMENTAL EVALUATION

We now evaluate the performance of the coordinated and adaptive behaviors on synthetic dense scenarios, where multiple UAVs adapt their trajectories following the occurrence of incidents and emergency trajectories.

Experimental Setup

We will analyze the performances of the investigated deconfliction behaviors with a growing number of UAVs (and trajectories). They are coded in Java and executed on 20-core Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz, 62GB RAM, Ubuntu 18.04.5 LTS, with an OpenJDK 11.0.9.1 JVM. We ran 30 instances of randomly generated sets of trajectories and incidents for each fleet size, and plot the average values, with [0.05, 0.95] confidence interval. The DCOP algorithms used here are the implementations from FRODO Library [START_REF] Léauté | FRODO 2.0: An Open-Source Framework for Distributed Constraint Optimization[END_REF]. Randomly generated values are uniformly chosen within provided intervals. The reported computation time is the mono-CPU 20-core simulation time.

We consider an area of 2km by 2km, illustrated in Figure 4, with vertical airspace planes at 20m, 40m and 60m. We consider UAVs with the following characteristics: ℎ 𝑚𝑎𝑥 = 18𝑚.𝑠 -1 , 𝑣 𝑚𝑎𝑥 = 6𝑚.𝑠 -1 , 𝑎 𝑚𝑎𝑥 = Π/2rad.𝑠 -1 , Δℎ max = Δ𝑣 max = 6𝑚.𝑠 -2 , Δ𝑎 max = Π/2rad.𝑠 -2 . Initial speed is set to (0, 0, 0). Initial UAV trajectories are randomly and incrementally generated as follows. The starting point is randomly positioned in the airspace, at altitude 𝑧 = 0 and at time 𝑡 = 0. The next points are randomly chosen within a distance between 200m and 1000m, so that there is no conflict with existing segments, by possibly increasing or decreasing the altitude. The time for the next point is also set using a default cruise speed, equals to (12, 3, 0) (equiv. to 40km/h horizontally). UAvs ave initially 60 way-points to their destination, then a last segment back to their origin, leading to a dense set of crossing trajectories. Safety tubes are defined by (ℎ, 𝑣, 𝑡) = (30, 15, 1), which means that UAVs must be separated by at least 30m horizontally, 15m vertically, with 1s temporal tolerance. To add unpredictable events, we generate 3 emergency trajectories, consisting in starting from a random position at the border of the area, moving to a random point at at least 1km distance from the initial point, then a waiting point for 360s (to simulate an emergency response), and finally a way back to the initial point. These emergency trajectories are not editable. Each simulated second there is also a 1% chance an incident occurs close to a randomly chosen UAV, thus having to capture the scene for a random duration between 30s and 120s.

We evaluate the following behaviors: (i) postpone characterizes UAVs that only perform a postpone(𝑐, 20) action when a conflict is identified (subscribing to CDS and TUS services); (ii) elevate characterizes UAVs that only perform elevate(𝑐, ±15) actions, depending on their current plane, when a conflict is identified (subscribing to CDS and TUS services); (iii) skip represents UAVs that only perform skip(𝑐) action when a conflict is detected (subscribing to CDS and TUS services); (iv) afb [START_REF] Amir Gershman | Asynchronous Forward-Bounding for Distributed Constraints Optimization[END_REF], dpop [START_REF] Petcu | A scalable method for multiagent constraint optimization[END_REF], dsa (variant C) [START_REF] Zhang | Distributed Stochastic Search and Distributed Breakout: Properties, Comparison and Applications to Constraint Optimization Problems in Sensor Networks[END_REF], mgm2 [START_REF] Maheswaran | Distributed Algorithms for DCOP: A Graphical-Game-Based Approach[END_REF] represent UAVs which perform a coordinated and adaptive decision using a DCOP algorithm 1 to deconflict, that opt between postpone(𝑐, 𝑑) with 𝑑 ∈ {20, 40, 60}, elevate(𝑐, ±15) and skip(𝑐) (subscribing to DMS, CDS, TAS and TUS services); and finally, (v) centralized is a tree-search based deconfliction algorithm computing the optimal sequence of repair actions (from the same set than DCOPs) to fully repair a conflicting set of trajectories, by optimizing objective derived from equation [START_REF] Farinelli | Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm[END_REF]. All UAVs are equipped with collision avoidance routine and equipment. CDS Service is configured with an horizon 𝑘 = 10, which in our case represents approx. 10min in the future.

Figure 5 presents performance metrics obtained by simulation, with an increasing number of UAVs (and trajectories); and Figure 6 shows the evolution of some metrics, with time, for a specific instance with 25 UAVs, 3 emergency procedures and 25 incidents.

Conflicts and Contracts

The first row in Figure 5 (5a-5d) focuses on conflicts and trajectories. While in classical ATM, with structured airspace, postponing at departure is used to reduce conflicts [START_REF] Barnier | Trajectory deconfliction with constraint programming[END_REF], in our free route scenario, postpone is generating numerous conflicts due to the accumulated delays over crossing trajectories, which are not structured as flow networks, as shown in Figure 5a. All the other behaviors still generate conflicts (around 200 on larger instances), since almost 70 trajectories are added to the airspace on larger instances.

Facing conflicts, UAVs update their contracts, which are no more guaranteed to be conflict-free compared to the initial ones. Thus, UAVs tend to request numerous contract updates, as illustrated in Figure 5b. This is especially true for postpone and elevate, which delays trajectories for some duration, which most of the time is not sufficient for breaking the conflicts, or which generates other conflicts. On larger instances, a trajectory update is requested every second, on average. These dynamics of trajectory updates make some UAVs violate some others' safety tubes, and often trigger the anti-collision routines, as illustrated in Figures 5c and5d. Indeed, when a UAV requests for a contract update with a new segment very close to its current position (in space and time) and to another UAV's position, this may lead to such situations, before any of the 2 UAVs is able to update again its contract. Notably, elevate makes UAVs violate 4 times more safety tubes than the other behaviors. These numbers of contract updates and violations is high because we choose here to generate very dense trajectories, which represents some sort of worst scenario, where even safety margins are not enough to prevent collisions.

Looking to our single instance (Figure 6), we can see how much dynamic this setting is, letting no rest for the UAVs to repair the trajectories and fulfilling their missions, which last for approx. 1h. There is only a "calm" window between time 𝑡 = 291 and 𝑡 = 744. We can observe how the addition of incidents immediately triggers postpone action (that all agents implement to handle incidents). In particular, postpone and elevate generate numerous conflicts just after the addition of a first emergency trajectory, as shown in Figure 6a. Facing such conflicts, UAVs constantly attempt to repair the trajectories, until there is no more incidents and emergency in the airspace, as illustrated by Figure 6b, after 𝑡 = 2290. Even when contracts are stable, UAVs may still continue violating some safety tubes, as shown in Figure 6c, since they have been computed using some time projection, that may not be very precise.

Trajectory Conservation and Delays

The second row of Figure 5 presents metrics related to the second and third optimization criteria we look at, namely trajectory conservation and delays. In Figure 5e, which reports the average percentage of conserved initial way-points in the final trajectories, skip is the less conservative behavior (up to 12.5% of way-points are skipped), since it automatically bypasses way-points when facing a conflict, which also results in lower time to terminate all the trajectories (reported in Figure 5f). Both elevate and postpone add delay for solving conflicts (either by changing altitude, thus spending time in elevation, or by postponing next way-points), as reinforced in Figures 5g and5h showing the total accumulated delay and the average delay per UAV. Note that every behavior adds delay: this is due to the fact that UAVs handle numerous incidents (around 35 in larger instances) forcing them to stay in position for a while, thus accumulating delay. Centralized solver loses performances on larger instances since it first consider minimizing conflicts and missed way-points, and thus postpone more frequently than DCOP-based solvers. The DCOP-based approaches locally co-optimize conflicts, trajectory conservation, and delays, which makes them an efficient compromise.

Looking at our isolated instance, we can observe how skip constantly skips way-points to answer to conflicts, as shown in Figures 6d and 6e. skip deleted 3 times more points than DCOP-based behaviors. The adaptations to incidents continuously add delays to trajectories, due to the postpone action triggered in such cases.

DCOP Operation

The third row of Figure 5 area, the DCOP procedures between several UAVs is constantly but not so frequently triggered, as seen in Figure 5i. This is explained by the fact that DCOP-based coordinated decisions manage to solve conflicts for the given horizon, and then do not require other coordination for some time, expect when other disturbances occur. Interestingly, incomplete solvers (dsa, mgm2) require more coordination than complete solvers (afb and dpop). In fact, since the decisions made by these incomplete solvers are non optimal, they may result on conflicting decisions requiring further deconfliction coordination. During coordination, conflicts are concerning one third of the total fleet on average, as shown in Figure 5k. Coordination can theoretically regroup many agents, but in our setting, restricted DCOP sizes allow the use of complete solution methods as afb and dpop, which does not strongly impact the individual UAV decision runtime as reported in Figure 5l. Looking at the communication load in Figure 5j, dpop requires exchanging few but large messages since the DCOPs to solve are cyclic and thus require exchanging exponential size messages. mgm2, due to its 2-coordination settings, exchanges numerous small messages.

DCOP-based behaviors are triggered when facing some of the disturbances, as shown in Figure 6f, and apply the most valued actions, namely elevate (to conserve way-points) and skip (to limit delays), as shown in Figures 6h and6i. The postpone action is not used in such conditions, as observed in the "calm" period in Fig- ure 6g. This explains how DCOPs achieve good results as trade-offs between contract conservation and delays. afb is the best competitor, with good deconfliction requiring low communication load. However, afb is not robust to message loss, contrary dsa. Further experiments should be done to assess the impact of communication unreliability on DCOP performances.

Summary

These results highlight how the setting is a very extreme dynamic configuration, where UAVs have to constantly update that trajectories. Clearly, the postpone behavior is bad on two dimensions: delays and conflicts (therefore safety). The elevate behavior is a good candidate for trajectory conservation, but with extra delays and numerous safety violations, while skip generates few conflicts, at the expense of some missed way-points. DCOP-based behavior is positioned as a good compromise between elevate and skip, thus meeting our objective of minimizing generated conflicts, maximizing the trajectory conservation and minimizing the delays, as good as a centralized deconfliction. In other settings, with many crossroads on structured airspace, these results may not hold. In fact, many of the performances depends on the fact that UAVs can freely change altitude or bypass some way-points. In more structured airspace, UAVs would normally change altitude in some limited vertical corridors, and cannot fly outside horizontal corridors, as defined in [START_REF] Capitán | Unmanned Aerial Traffic Management System Architecture for U-Space In-Flight Services[END_REF] for instance. In such cases, postpone would probably behaves better, while DCOPs would form larger groups of conflicting trajectories, flowing through some limited number of crossroads. We keep this investigation and analysis for future works.

CONCLUSION

In this paper we promoted and implemented a multi-agent coordination mechanisms to help UAVs evolving in a dynamic free route airspace to adapt their trajectories. Coordination is built upon a distributed constraint solving protocol, which aims at minimizing the future conflicts, maximizing the conservation of the initial trajectories, and reducing the overall delay implied by deconfliction actions. On the simulated scenario we developed, forming a dense airspace with random events to handle, we show that using a coordinated and adaptive deconfliction, provides solutions with reduced conflicts, missed way-points and accumulated delay, compared to uncoordinated and fixed ones. Still, this coordination requires some extra in all, the DCOP-based approach is a promising candidate for installing autonomous deconfliction in UAVs collective, and paves the way for future research.

Since UTM and U-Space visions are evolving, especially towards more structured airspace [START_REF] Bauranov | Designing airspace for urban air mobility: A review of concepts and approaches[END_REF][START_REF] Capitán | Unmanned Aerial Traffic Management System Architecture for U-Space In-Flight Services[END_REF], we envision to extend our framework and services to such settings, which promise to be harder to solve due to the lack of trajectory freedom to deconflict and the larger size of deconfliction groups. We particularly aim to adapt the DCOP solution method to use to the trajectory deconfliction settings. In fact, we used here a straightforward linear aggregation of three criteria, which still generates non-conflict-free trajectories. Multiobjective DCOPs could be a relevant approach for future developments [START_REF] Matsui | Distributed Search Method with Bounded Cost Vectors on Multiple Objective DCOPs[END_REF]. Moreover, devising less communication intensive coordination algorithms appears to be a requirement to deploy such protocol and services on real devices and UTM. This could be achieved by either limiting the size of the deconfliction DCOPs or by relying on lightweight and robust solution methods as A-DSA, as proposed in the Internet-of-Things context [START_REF] Rust | Resilient Distributed Constraint Optimization in Physical Multi-Agent Systems[END_REF], at the expense of completeness.

Figure 1 :

 1 Figure 1: Candidate architecture for Unmanned Traffic Management, as proposed by FAA [9]

Figure 3 :

 3 Figure 3: The UAV generic behavior.

Figure 4 :

 4 Figure 4: A sample dense scenario with 20 UAVs flying over a 2km x 2km urban area. UAVs are represented as circles (with their current speed vector). 4D contracts (and their respective safety tubes) are represented in green. Current segments are represented in blue.

Figure 5 :

 5 Figure 5: Average values over 30 instances for several performance metrics with increasing number of UAVs.

Figure 6 :

 6 Figure 6: Evolution of performance metrics during one simulation with 25 UAVs and 3 emergency procedures (gray dashed lines) and 25 incidents (gray dotted lines).

This section presents the core models used in this study, namely the 4D trajectories, the UAVs and the UTM services required to implement deconfliction actions between the UAVs.

We do not include MaxSum algorithm[START_REF] Farinelli | Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm[END_REF], since it cannot converge in most of our instances, thus providing low quality results while requiring numerous messages.


Gauthier Picard
email: gauthier.picard@onera.fr

Auction-based and Distributed Optimization Approaches for Scheduling Observations in Satellite Constellations with Exclusive Orbit Portions

Keywords: Satellite Constellations, Scheduling, Resource Allocation, Distributed Optimization, Auctions ACM Reference Format:

We investigate the use of cooperative multi-agent allocation techniques on problems related to Earth observation scenarios with multiple users and satellites. We focus on the problem of coordinating users having reserved exclusive orbit portions and one central planner having several requests that may use some intervals of these exclusives. We define this problem as Earth Observation Satellite Constellation Scheduling Problem (EOSCSP) and map it to a Mixed Integer Linear Program. As to solve EOSCSP, we propose market-based techniques and a distributed problem solving technique based on Distributed Constraint Optimization (DCOP), where agents cooperate to allocate requests without sharing their own schedules. These contributions are experimentally evaluated on randomly generated EOSCSP instances based on real large-scale or highly conflicting observation order books.

INTRODUCTION

Recent years have shown a large increase in the development of satellite constellations. Instead of considering individual satellites, they take advantage of a group of satellites, some of them often sharing the same orbital planes, to provide richer services like positioning, telecommunication or Earth observation [START_REF] Walker | Satellite Constellations[END_REF]. With few satellites in a constellation (e.g. two in the PLEIADES project [START_REF] Michel Lemaître | Selecting and scheduling observations of agile satellites[END_REF]), and in low or medium Earth orbits (altitude inferior to 35,000km), no region on Earth is permanently covered by the constellation at any time. So, the main motivation to increase the size of these constellations is to allow to capture with a high reactivity any point on Earth, as the Planet company is doing with more than 150 Earth Observation Satellites (EOS) [START_REF] Shah | Scheduling the World's Largest Earth-Observing Fleet of Medium-Resolution Imaging Satellites[END_REF]. But, operating numerous EOS requires improving cooperation between the assets and onboard autonomy in order to make the best use of the system, which becomes a highly combinatorial task. Besides their growing number, constellations' composition is evolving too. Recent technological advances allow the production and deployment of agile EOS able to change their orientation, and to provide multiple types of image shooting with multiple sensors. While providing richer services to multiple users, this adds many degrees of freedom and decision variables to schedule EOS activity, and opens many challenges [START_REF] Wang | Agile Earth observation satellite scheduling over 20 years: formulations, methods and future directions[END_REF], especially from a multi-agent perspective [START_REF] Gauthier Picard | Autonomous Agents and Multiagent Systems Challenges in Earth Observation Satellite Constellations[END_REF]. Among these challenges, we focus on the collective scheduling of observations on a set of satellites on which some users have exclusive access to some orbit portions, using distributed techniques, as to spread decisions among the different users of the constellation. This anwers to strong user expectations to benefit on the one hand from the advantages of a system shared between several stakeholders (reduction of costs compared to a very expensive global system) and on the other hand from the advantages of a proprietary system (ability to do what one wants with the satellite and potentially without disclosing it to others). While the literature about multi-satellite scheduling is rich, as confirmed by a recent review paper [START_REF] Wang | Agile Earth observation satellite scheduling over 20 years: formulations, methods and future directions[END_REF], considering satellite constellations as shared resources requiring multiple users to coordinate as to allocate observation tasks within exclusive orbit portions is a completely novel problem, we address in this paper, as illustrated in Figure 1.

In [START_REF] Phillips | A Case Study on Auction-Based Task Allocation Algorithms in Multi-Satellite Systems[END_REF], auction-based approaches are proposed to allocate observation tasks to a set of satellites, where each satellite is managed by a different mission center. Mission centers coordinate their allocation using auctions, by bidding on the open observations depending on the impact on the on-board plan and its reward (valued using the incidence angle of the scheduled observations). Contrary to this approach, in this study, the distribution is related to some exclusive users having full control on some orbit portions (using full direct tasking1 operation) or having bought some orbit portions outside direct communication, on which they have full priority to schedule observations. In such setting, some user can request relatively cheap observations to a satellite by the way of a central planner, thereby also disclosing her intentions. Alternatively, users may purchase exclusive time slots, and privately use the satellite during these times. Here, the fact that schedules cannot be performed by a single authority, for privacy reason in exclusive windows, is a strong requirement. This is the reason to provide distributed scheduler where agents coordinate without disclosing their plans, while meeting coupling constraints like satellite capacity or interobservation configuration time, that could not be guaranteed by non-coordinated schemes where users make their plans in parallel.

We will investigate here two different distributed resource allocation and coordination schemes: auctions and distributed constraint optimization (DCOP). Section 2 illustrates and defines Earth Observation Satellite Constellation Scheduling Problem (EOSCSP). Section 3 focuses on centralized solution methods Mixed-Integer Linear Program (MILP) and greedy approach to EOSCSP, we will use as our centralized benchmark. Section 4 expounds some auction-based approaches to solve EOSCSP, using different auction schemes (PSI, SSI and CBBA), while Section 5 proposes another approach to coordination between exclusive users using DCOPs. We experimentally evaluate these different algorithms using randomly generated order books on a constellation to be deployed, in Section 6. Finally, Section 7 concludes the paper with some perspectives.

EOSCSP MODEL

This section illustrates the problem we investigate using a sample scenario, and then provides some core definitions.

Sample Scenario

Figure 2 illustrates a scenario, where we consider: 3 satellites, each having a given planning period (e.g. planning on the next orbit, or on horizons depending on the communication windows between the satellite and ground stations); one user 𝑢 0 without exclusive orbit portion; two users having exclusive orbit portions such that user 𝑢 1 owns exclusives on satellite 𝑠 0 and on satellite 𝑠 1 (hashed red), user 𝑢 2 owns exclusives on satellite 𝑠 0 and on satellite 𝑠 2 (hashed blue); several requests to be performed before a due date, denoted 𝑟 𝑖,𝑗 for the 𝑗th request for user 𝑖; several observation opportunities (simply observations) per request, denoted 𝑜 𝑖,𝑗,𝑘 for the 𝑘th observation for the 𝑗th request of the 𝑖th user. Only one observation should be planned to fulfill the request on temporal slots depending on the satellites' orbits and the position of zones of interest (slots are represented as transparent areas). More precisely, we consider 2 observation opportunities per request, such that opportunities 𝑜 1,0,0 and 𝑜 1,0,1 are private for user 𝑢 1 (in red), opportunities 𝑜 2,0,0 , 𝑜 2,0,1 , 𝑜 2,1,0 , and 𝑜 2,1,1 are private for user 𝑢 2 (in blue), opportunities 𝑜 0,𝑗,𝑘 's (in green) which are directly requested to the central scheduler 𝑢 0 by other clients without exclusives. The proposed solution fulfills all requests, by allowing non exclusive user 𝑢 0 to position observation on exclusive orbit portions (e.g. 𝑜 0,0,0 in on 𝑢 1 's exclusive on satellite 𝑠 0 ). A simplified energy constraint states that a satellite cannot perform more than 𝑛 max observations on its scheduling period (here, 𝑛 max = 4), and there are minimal transition times between two observations 𝑜 and 𝑝, depending on 𝑜 and 𝑝 and the date at which the transition is triggered on a given satellite. At the global level, each exclusive user (𝑢 1 or 𝑢 2 ) could have its own scheduling system to manage its exclusive periods, and a central scheduling system (𝑢 0 ) manages observations 𝑜 0,𝑗,𝑘 's. In the end, every user and the central scheduler have a local scheduling problem to solve. Solving them in a separate manner may lead the central scheduler not to be able to book slots on exclusive orbit portions, while it may improve the solution. Without coordination, and with a non-cooperative management of exclusive slots, the overall schedule might not be optimal, wrt the number of possible scheduled observations. Moreover, exclusive users may gain from this cooperation by making profits from observation scheduled on their orbit portions. Thus, we propose here to coordinate the scheduling processes between users.

Definitions and Notations

Let's provide the core concepts of this scheduling problem. Definition 1 (EOSCSP). An Earth Observation Satellite Constellation Scheduling with Exclusives Problem (or EOSCSP) is defined by a tuple 𝑃 = ⟨S, U, R, O⟩, such that S is a set of satellites, U is a set of users, R is a set of requests, and O is a set of observations to schedule to fulfill requests in R. 𝑠 ])} ⊂ (S × (R × R)), and a priority 𝑝 𝑢 ∈ N + (the lower the better, used in case of conflict). We note U ex (resp. U nex ) the set of users owning (resp. not owning) exclusives.

Definition 2 (Satellite

We assume here that only one user has no exclusive orbit portion, the central planner, denoted 𝑢 0 , i.e. U nex = {𝑢 0 }, and there is no overlapping exclusive portions.

∈ R, a duration Δ 𝑟 ∈ R, a reward 𝜌 𝑟 ∈ R if 𝑟 is fulfilled, a latitude-longitude-altitude position (LLA) to observe 𝑝 𝑟 , a requester 𝑢 𝑟 ∈ U and a list 𝜃 𝑟 ∈ 2 O of observation opportunities to fulfill the request.
𝜃 𝑟 is dynamically computed on current constellation configuration and requested LLA position 𝑝 𝑟 , since several agile satellites, by changing their orientation may acquire the same position, thus generating several observation opportunities. Definition 5 (Observation). An observation opportunity (or observation) is defined as a tuple 𝑜 = ⟨𝑡 start 𝑜 , 𝑡 end 𝑜 , Δ 𝑜 , 𝑟 𝑜 , 𝜌 𝑜 , 𝑠 𝑜 , 𝑢 𝑜 , 𝑝 𝑜 ⟩, with a validity time window defined by 𝑡 start 𝑜 ∈ R and 𝑡 end 𝑜 ∈ R, a request 𝑟 𝑜 to which it contributes, a duration Δ 𝑜 ∈ R (Δ 𝑜 = Δ 𝑟 𝑜 ), a reward 𝜌 𝑜 ∈ R (combined from 𝑟 𝑜 and information about the weather), a satellite 𝑠 𝑜 on which this observation can be scheduled, an owner 𝑢 𝑜 ∈ U (𝑢 𝑜 = 𝑢 𝑟 𝑜 ), and a priority 𝑝 𝑜 ∈ N + (𝑝 𝑜 = 𝑝 𝑟 𝑜 ).

The difference between request reward and observation reward comes from the fact that, in practice, weather conditions or incidence angle of an observation may increase or decrease the basic reward for a given request. So, our model can consider different rewards, but in this study we only focus on cases where observation rewards are directly inherited from the requests.

Definition 6 (Solution

). A solution to an EOSCSP is a map- ping M = {(𝑜, 𝑡) | 𝑜 ∈ O, 𝑡 ∈ [𝑡 start 𝑜 , 𝑡 end 𝑜 ]
} assigning a start time to at most one observation per request such that exclusive users have their observations scheduled on their respective exclusive windows. An optimal solution is a solution where the overall reward is maximized (sum of the rewards of the scheduled observations):

arg max M (𝑜,𝑡 ) ∈ M 𝜌 𝑜 . Definition 7. An EOSCSP for user 𝑢, denoted 𝑃 [𝑢] = ⟨S, U, R [𝑢], O [𝑢]⟩ (or EOSCSP[𝑢]), is an EOSCSP, sub-problem of another EOSCSP 𝑃 = ⟨S, U, R, O⟩ restricted to requests and observations from 𝑢, where R [𝑢] = {𝑟 | 𝑟 ∈ R, 𝑢 𝑟 = 𝑢} ⊆ R and O [𝑢] = {𝑜 | 𝑜 ∈ O, 𝑢 𝑜 = 𝑢} ⊆ O.
More generally, we note 𝑃 [𝑥] (resp. 𝑃 [𝑥]) the problem 𝑃 limited to the only components related to 𝑥, 𝑥 being a request, an observation or a satellite. Later on, we will also use the notations 𝑃 [∅|M] (resp. 𝑃 [𝑢 𝑙 , . . . , 𝑢 𝑚 |M]) to define the problem (resp. subproblem for users 𝑢 𝑙 , . . . , 𝑢 𝑚 ) given some predefined allocation M of some observations. Moreover, we will use notation 𝑃 to appoint the EOSCSP 𝑃, where only requests and related observations that can be scheduled outside exclusive are considered (i.e. observations whose time windows intersect non exclusive orbit portions). Finally, we note the union of two problems 𝑃 = ⟨S, U, R, O⟩ and

𝑃 ′ = ⟨S ′ , U ′ , R ′ , O ′ ⟩, 𝑃 ∪ 𝑃 ′ = ⟨S ∪ S ′ , U ∪ U ′ , R ∪ R ′ , O ∪ O ′ ⟩.

CENTRALIZED PROBLEM SOLVING

We present here centralized approaches to EOSCSP. First, this planning problem is modeled as a MILP. Decision variables are the following. 𝑥 𝑠,𝑜 ∈ {0, 1} is the decision to perform observation 𝑜 from satellite 𝑠, 𝑡 𝑠,𝑜 ∈ R is the start date for the observation 𝑜 on satellite 𝑠, 𝛽 𝑠,𝑜,𝑝 ∈ {0, 1} is the precedence between observations on the same satellite, equals to 1 if 𝑜 is before 𝑝 on 𝑠.

max 𝑥 𝑠,𝑜 ∑ 𝑜 ∈ O,𝑠 ∈ S 𝜌 𝑜 𝑥 𝑠,𝑜 (1)
s.t. ∀𝑠 ∈ S, ∀𝑟 ∈ R, ∀𝑜 ∈ O, ∀𝑝 ∈ O, 𝑜 ≠ 𝑝 2 -𝛽 𝑠,𝑜,𝑝 -𝛽 𝑠,𝑝,𝑜 ≥ 𝑥 𝑠,𝑜 (2)
2 -𝛽 𝑠,𝑜,𝑝 -𝛽 𝑠,𝑝,𝑜 ≥ 𝑥 𝑠,𝑝 (3)
𝛽 𝑠,𝑜,𝑝 + 𝛽 𝑠,𝑝,𝑜 ≤ 1 (4)

𝑡 𝑠,𝑝 -𝑡 𝑠,𝑜 ≥ 𝜏 𝑠 (𝑜, 𝑝) + Δ 𝑜 -Δ max 𝑠,𝑜,𝑝 𝛽 𝑠,𝑜,𝑝 , Δ max 𝑠,𝑜,𝑝 > 0 (5) 𝑡 𝑠,𝑜 -𝑡 𝑠,𝑝 ≥ 𝜏 𝑠 (𝑝, 𝑜) + Δ 𝑝 -Δ max 𝑠,𝑝,𝑜 𝛽 𝑠,𝑝,𝑜 , Δ max 𝑠,𝑝,𝑜 > 0 (6) ∑ 𝑜 ∈ O 𝑥 𝑠,𝑜 ≤ 𝜅 𝑠 (7) ∑ 𝑜 ∈𝜃 (𝑟 ) 𝑥 𝑠,𝑜 ≤ 1 (8) 𝑥 𝑠,𝑜 ∈ {0, 1} (9)
𝑡 𝑠,𝑜 ∈ [𝑡 start 𝑜 , 𝑡 end 𝑜 ] ⊂ R (10) 𝛽 𝑠,𝑜,𝑝 ∈ {0, 1} (11)
with

Δ max 𝑠,𝑜,𝑝 = 𝑡 end 𝑜 -𝑡 start 𝑝 + Δ 𝑜 + 𝜏 𝑠 (𝑜, 𝑝)
This objective (1) aims to maximize the sum of the rewards from scheduled observations. ( 2) to ( 6) ensure precedence of observations and their distance is at least the transition time required on their satellite. ( 7) enforces the number of observations booked on a satellite does not exceed its capacity. ( 8) checks at most one observation per request is scheduled. ( 9) to ( 11) are domain definitions. This MILP can be solved using off-the-shelf solvers like CPLEX or Gurobi, but they will hardly scale up when dealing with larger problems (e.g. more than 100 observations with 3 satellites and 3 users). Even devising non-exact methods based on dynamic programming, for instance, do not scale with increasing constellation size [START_REF] Nag | Scheduling algorithms for rapid imaging using agile Cubesat constellations[END_REF]. To ensure observations from exclusive users have priority over non-exclusive users' observations, their reward must be set to a high value. Thus, the solver will prefer scheduling exclusive observations within their time window instead of scheduling another observation with less priority. While the solution to this problem is optimal, it requires each exclusive user to fully disclose request information to the central planner.

As to solve larger problems, one approach is to allocate in a greedy fashion, by scheduling first exclusive users's observations and then more urgent observations, as described in Algorithm 1. In practice, this is the technique used by most satellite/constellation operators and is a candidate competitor for benchmarking solution methods [START_REF] Cho | Optimization-Based Scheduling Method for Agile Earth-Observing Satellite Constellation[END_REF][START_REF] Wang | Agile Earth observation satellite scheduling over 20 years: formulations, methods and future directions[END_REF]. For doing so, observations are sorted in increasing order on priority and start time criteria (line 2). Then, for each observation 𝑜 in this sorted list, the first free slot on its satellite orbit plan is found (line 4-8), using first_slot function. This function explores the satellite schedule (𝑅 [𝑠]) to find the first empty slot, consistent with 𝑜's time constraints. This algorithm is not optimal, but provides very fast solutions. But, as for MILP, it requires sharing all the constraints and information with a central planner.

AUCTION-BASED COORDINATION

One vision to allocate resources and/or tasks between several cooperative agents (here, our exclusive users) consists in auction-based approaches, that have proven their flexibility, efficiency, fairness, and privacy-preservation of users' plans and resources. In multirobot task allocation problems, such approaches are used to allocate tasks to robots, and integrate them into their plans [START_REF] Dias | Market-Based Multirobot Coordination: A Survey and Analysis[END_REF]. In our setting, one could consider allocating requests to satellites by such auction-based mechanisms, as proposed in [START_REF] Phillips | A Case Study on Auction-Based Task Allocation Algorithms in Multi-Satellite Systems[END_REF], with the difference that distribution is not related to satellites, but to exclusive users and their exclusive orbit portions. This is the approach we follow in this section. But first, let's introduce the auction-based mechanisms we will implement.

Background on Auction-based Allocation

A generic task allocation framework consists in a set of resources and a set of tasks to be performed by resources. The objective is to assign tasks to resources so that it maximizes some objective (e.g. the number of assigned tasks, or the sum of the rewards of the tasks). So this is classical allocation problem that can be modeled as a MILP, Algorithm 1: Greedy EOSCSP solver Data: as seen in previous section. Now, the idea is that the requests to be scheduled are open for bidding by an auctioneer. Bidders (the exclusive users) valuate the requests depending on their current plan, and bid for some requests, as illustrated in Figure 3. The most expensive computations in this process are the bidding step by each bidder, which can have an exponential number of bundles to valuate, and the winner determination problem (WDP) which amounts to solving an Integer Linear Program with a potentially exponential size, and falls into the combinatorial auction (CA) frameworks [START_REF]Combinatorial Auctions[END_REF].

An EOSCSP 𝑃 = ⟨S, U, R, O⟩ Result: An assignment M 1 M ← {} 2 O sorted ← sort(O) 3 𝑅 ← {(𝑠, [])} | 𝑠 ∈ S} 4 for 𝑜 ∈ O sorted do 5 𝑡 ← first_slot(𝑜, 𝑃, 𝑅) 6 if 𝑡 ≠ ∅ then 7 M ← M ∪ {(𝑜, 𝑡)} 8 O sorted ← O sorted \ 𝜃 (𝑟 𝑜 ) 9 return M Function first_slot (𝑜, 𝑃 = ⟨S, U, R, O⟩, 𝑅) 10 for (𝑠, [𝑡 start , 𝑡 end ]) ∈ domains(𝑜) do 11 if |𝑅 [𝑠]| < 𝜅 𝑠 then 12 if 𝑅 [𝑠] = [] then 13 if 𝑡 end ≥ 𝑡 start + Δ 𝑜 then 14 𝑅 [𝑠] = {(𝑜, (𝑠, 𝑡 start ))} 15 return (𝑠, 𝑡 start ) 16 else 17 𝑖 ← 0 18 while 𝑖 ≤ |𝑅 [𝑠]| do 19 𝑡 start′ ← 𝑡 start 20 if 𝑖 > 0 then 21 (𝑜 𝑖 -1 , (𝑠, 𝑡 𝑖 -1 )) ← 𝑅 [𝑠] [𝑖 -1] 22 𝑡 start′ ← max(𝑡 start
According to literature on multi-robot task allocation [START_REF] Dias | Market-Based Multirobot Coordination: A Survey and Analysis[END_REF] and multi-satellite observation allocation [START_REF] Phillips | A Case Study on Auction-Based Task Allocation Algorithms in Multi-Satellite Systems[END_REF], to overcome these computational limits, the classical relaxation consists in only allowing bidding on item (and not on bundles). When bidders bid on the whole set of items in parallel, we fall into PSI framework [START_REF] Koenig | The Power of Sequential Single-Item Auctions for Agent Coordination[END_REF]. When the auctioneer announces items iterativelly, and bidders build their bid knowing the previous item allocation, we fall into the SSI framework [START_REF] Koenig | The Power of Sequential Single-Item Auctions for Agent Coordination[END_REF]. In general PSI has very good performances with very limited computation time, while PSI solution quality are often limited, since bidders cannot easily reason on bundles. More recently, consensus-based bundle algorithm (CBBA) combines ideas from auctions and consensus to converge faster than SSI while yielding similar solutions and having the benefits of traditional consensus algorithms [START_REF] Choi | Consensus-Based Decentralized Auctions for Robust Task Allocation[END_REF]. CBBA is a fully distributed solution to implement a computationally cheap variant of combinatorial auctions (CA). Each bidder constructs a unique bundle of items it wishes to be assigned to, with respect to the marginal cost associated with the inclusion of the considered item into its current bundle. Then during the consensus phase, the bidders compare their bids with their teammates bids. If a robot is outbid on an item 𝑡, it drops the item and all the items added after it, as the exclusion of 𝑡 made the valuation of their marginal cost obsolete. This algorithm have been extensively studied and modified to improve its performances and adapt it to specific scenarios, like multi-satellite observation allocation [START_REF] Phillips | A Case Study on Auction-Based Task Allocation Algorithms in Multi-Satellite Systems[END_REF].

Mapping EOSCSP to Auctions

Mapping an EOSCSP 𝑃 to a auction-based allocation problem is quite straightforward. Bidders are exclusives users in U ex , and items are non exclusive requests in R emitted by the central planner 𝑢 0 , playing the role of auctioneer. The idea is that each exclusive user 𝑢 computes an initial plan M 𝑢 with its own requests by solving 𝑃 [𝑢]. Then, 𝑢 0 announces the requests, either as a whole (for PSI and CBBA) or iterativelly (for SSI). Each exclusive user 𝑢 valuates each single request with function bid (for PSI and SSI) or bundle with function bundle (for CBBA) by computing the marginal cost to integrate the given item or bundle 𝑥 in its current plan. We redirect the reader to the original CBBA paper for more details about the bundle construction [START_REF] Choi | Consensus-Based Decentralized Auctions for Robust Task Allocation[END_REF]. bid(𝑟, M 𝑢 ) simply amounts to solve 𝑃 [𝑢] ∪ 𝑃 [𝑟 ] and to assess the difference with the current plan M 𝑢 . It returns the bid itself B 𝑢 [𝑟 ] (best marginal cost) and the schedule for one observation to fulfill 𝑟 , 𝜎 𝑢 [𝑟 ] = (𝑜, 𝑡). The bids (on single items or bundles) are then sent to the auctioneer 𝑢 0 (for PSI and SSI) which determines the winners, or to the other bidders sharing interest on the same request, namely N 𝑢 , to find a consensus (for CBBA). Once the winners are determined, requests are allocated to the winners. If there remain some non allocated requests, 𝑢 0 attempts to schedule them outside any exclusive window. These processes are sketched in Algorithms 2, 3 and 4.

Algorithm 2: psi EOSCSP solver

Data:

An EOSCSP 𝑃 = ⟨S, U, R, O⟩ Result: An assignment M 1 M 𝑢 0 ← ∅ 2 for each 𝑢 ∈ U ex do concurrently 3 M 𝑢 ← solve(𝑃 [𝑢]) 4 for each 𝑟 ∈ R do B 𝑢 [𝑟 ], 𝜎 𝑢 [𝑟 ] ← bid(𝑟, M 𝑢 ) // send B 𝑢 , 𝜎 𝑢 to 𝑢 0 5 for each 𝑟 ∈ R do 6 𝑤 ← arg max 𝑢 ∈ U ex {B 𝑢 [𝑟 ]} 7 M 𝑢 0 ← M 𝑢 0 ∪ {𝜎 𝑤 [𝑟 ]} 8 M 𝑤 ← M 𝑤 ⊕ 𝜎 𝑤 [𝑟 ] // send M 𝑤 [𝑟 ] to 𝑤 9 M 𝑢 0 ← solve(𝑃 [𝑢 0 |M 𝑢 0 ]) 10 return 𝑢 ∈ U M 𝑢 Algorithm 3: ssi EOSCSP solver Data: An EOSCSP 𝑃 = ⟨S, U, R, O⟩ Result: An assignment M 1 M 𝑢 0 ← ∅ 2 for each 𝑢 ∈ U ex do concurrently M 𝑢 ← solve(𝑃 [𝑢]) 3 for each 𝑟 ∈ sorted(R) do 4 for each 𝑢 ∈ U ex do 5 B 𝑢 [𝑟 ], 𝜎 𝑢 [𝑟 ] ← bid(𝑟, M 𝑢 ) // send B 𝑢 [𝑟 ], 𝜎 𝑢 [𝑟 ] to 𝑢 0 6 𝑤 ← arg max 𝑢 ∈ U ex {B 𝑢 [𝑟 ]} 7 M 𝑢 0 ← M 𝑢 0 ∪ {𝜎 𝑤 [𝑟 ]} 8 M 𝑤 ← M 𝑤 ⊕ 𝜎 𝑤 [𝑟 ] // send M 𝑤 [𝑟 ] to 𝑤 9 M 𝑢 0 ← solve(𝑃 [𝑢 0 |M 𝑢 0 ]) 10 return 𝑢 ∈ U M 𝑢
In PSI and SSI, the ⊕ operator is used to add 𝜎 𝑢 [𝑟 ] = (𝑜, 𝑡) in the current plan. Depending on the setting, it can be a simple aggregation if there is no conflict, or may require removing some already planned observations with lower reward. In SSI and CBBA, requests are sorted before looping over. This sorting can be done wrt due date, reward, or any combination of criteria. In the experiments, we will use the due date. // solve conflicts and determine M 𝑢 (see [START_REF] Choi | Consensus-Based Decentralized Auctions for Robust Task Allocation[END_REF])

11 for each 𝑢 ∈ U ex do 12 M 𝑢 0 ← M 𝑢 0 ∪ {(𝑜, 𝑡)|(𝑜, 𝑡) ∈ M 𝑢 , 𝑢 𝑜 = 𝑢 0 } 13 M 𝑢 0 ← solve(𝑃 [𝑢 0 |M]) 14 return 𝑢 ∈ U M 𝑢

DCOP-BASED COORDINATION

Another approach to implement the allocation of requests between the multiple candidate exclusive users is to adopt a distributed constraint optimization vision. We devise here a cooperation mechanism between exclusive users to coordinate their scheduling process, by exchanging messages to reach an agreement on request allocations while meeting the coupling constraints, such as the capacity constraints.

Background on DCOP

One way to model inter-agent coordination problems is to formalize them as distributed constraint optimization problems (DCOP) [START_REF] Petcu | A scalable method for multiagent constraint optimization[END_REF]. Definition 8. A Distributed Constraint Optimization Problem (or DCOP) is a tuple ⟨A, X, D, C, 𝜇, 𝑓 ⟩, where: A = {𝑎 1 , . . . , 𝑎 |𝐴| } is a set of agents; X = {𝑥 1 , . . . , 𝑥 𝑛 } are variables owned by the agents; D = {D 𝑥 1 , . . . , D 𝑥 𝑛 } is a set of finite domains, such that variable 𝑖 takes values in D 𝑥 𝑖 = {𝑣 1 , . . . , 𝑣 𝑘 }; C = {𝑐 1 , . . . , 𝑐 𝑚 } is a set of soft constraints, where each 𝑐 𝑖 defines a cost ∈ R + ∪ {+∞} for each combination of assignments to a subset of variables (a constraint is initially known only to the agents involved); 𝜇 : X → A is a function mapping variables to their associated agent; 𝑓 : D 𝑥 𝑖 → R is an objective function, representing the global cost of a complete variable assignment. The optimization objective is represented by function 𝑓 , which, in general, is considered as the sum of costs: 𝑓 = 𝑖 𝑐 𝑖 . A solution to a DCOP 𝑃 is a complete assignment to all variables. A solution is optimal if it minimizes 𝑓 .

DCOP have been widely studied and applied in many areas of reference [START_REF] Fioretto | Distributed Constraint Optimization Problems and Applications: A Survey[END_REF]. They have many interesting properties: (i) focus on decentralized approaches where agents negotiate a joint solution through local message exchanges; (ii) exploitation of the domain structure (by encoding it in constraints) to address hard computational problems; (iii) wide variety of solution methods ranging from exact methods to heuristic and approximate techniques; such as, for example, ADOPT [START_REF] Modi | ADOPT: Asynchronous distributed constraint optimization with quality guarantees[END_REF], DPOP [START_REF] Petcu | A scalable method for multiagent constraint optimization[END_REF], MaxSum [START_REF] Farinelli | Decentralised Coordination of Low-power Embedded Devices Using the Max-sum Algorithm[END_REF], DSA [START_REF] Zhang | Distributed Stochastic Search and Distributed Breakout: Properties, Comparison and Applications to Constraint Optimization Problems in Sensor Networks[END_REF] or MGM [START_REF] Maheswaran | Distributed Algorithms for DCOP: A Graphical-Game-Based Approach[END_REF], and their numerous variants and extensions, to name only the most famous.

Coordinating Exclusive Users with DCOP

As for combinatorial auctions, using DCOPs for allocating all requests as a whole is too computationally expensive to be used. So we will take inspiration from SSI, and consider requests sequentially, and coordinate exclusive user for each request using a DCOP solver, instead of auctions. This lets the non exclusive users coordinate to choose which one will fulfill it by scheduling an observation in its exclusive time windows. Algorithm 5 sketches this method, coined s_dcop (for sequential DCOP). First, exclusive users also solve their own local sub-problem concurrently (line 1). Then, for each request 𝑟 in the ordered list of remaining requests (line 2), a new DCOP instance is collectively built between the exclusive users (line 3), and then solved (line 4) using any DCOP solver available (DPOP in our experiments). Once all requests have been considered, 𝑢 0 gathers the sub-solutions to build its own final solution, by scheduling as many observation outside exclusive time windows as possible (line 6-7). Note that, the inner plan of each exclusive user remains private, and only non exclusive schedule observation are communicated to 𝑢 0 (plus some extra information to handle inter-observation transition times).

Algorithm 5: s_dcop EOSCSP solver

Data:

An EOSCSP 𝑃 = ⟨S, U, R, O⟩ Result: An assignment M 1 for each 𝑢 ∈ U ex do concurrently M 𝑢 ← solve(𝑃 [𝑢]) 2 for each 𝑟 ∈ sort(R) do 3 𝑝 ← build_DCOP(𝜃 𝑟 , M, M 𝑢 1 , . . . , M 𝑢 𝑛 , 𝑃) 4 M 𝑢 1 , . . . , M 𝑢 𝑛 ← solve_DCOP(𝑝) 5 for each 𝑢 ∈ U ex do concurrently 6 M ′ 𝑢 ← {(𝑜, 𝑡) ∈ M 𝑢 |𝑢 𝑜 ∈ U nex } // send M ′ 𝑢 to 𝑢 0 7 M 𝑢 0 ← solve(𝑃 [𝑢 0 | 𝑢 ∈ U ex M ′ 𝑢 ]) 8 return 𝑢 ∈ U M 𝑢

DCOP Model

Let's specify now the DCOP instance to be built in line 3 of Algorithm 5 for a given request 𝑟 , and a current scheduling (M, M 𝑢 1 , . . . , M 𝑢 𝑛 ), as required in Definition 8. Straightforwardly, the set of agents is the set of exclusive users which can potentially schedule the current request 𝑟 :

A = {𝑢 ∈ U ex |∃(𝑠, (𝑡 start 𝑢 , 𝑡 end 𝑢 )) ∈ 𝑒 𝑢 , ∃𝑜 ∈ 𝜃 𝑟 s.t. 𝑠 𝑜 = 𝑠, [𝑡 start 𝑢 , 𝑡 end 𝑢 ] ∩ [𝑡 start 𝑜 , 𝑡 end 𝑜 ] ≠ ∅} (12) We note O [𝑢] 𝑟 = {𝑜 ∈ 𝜃𝑟 |∃(𝑠, (𝑡 start 𝑢 , 𝑡 end 𝑢 )) ∈ 𝑒 𝑢 , s.t. 𝑠 𝑜 = 𝑠, [𝑡 start 𝑢 , 𝑡 end 𝑢 ] ∩ [𝑡 start 𝑜 , 𝑡 end 𝑜 ]
≠ ∅} these observations related to request 𝑟 that can be scheduled on 𝑢's exclusives. Each such agent owns binary decision variables, one for each observation 𝑜 ∈ O [𝑢] 𝑟 and exclusive 𝑒 in its exclusives 𝑒 𝑢 , stating whether it schedules 𝑜 in 𝑒 or not:

X = {𝑥 𝑒,𝑜 |𝑒 ∈ 𝑢 ∈ A 𝑒 𝑢 , 𝑜 ∈ O [𝑢] 𝑟 } (13)
D = {D 𝑥 𝑒,𝑜 = {0, 1}|𝑥 𝑒,𝑜 ∈ X} (14)
The mapping 𝜇 associates each variable 𝑥 𝑒,𝑜 to 𝑒's owner. Constraints should check that at most one observation is scheduled per request [START_REF] Rust | pyDCOP, a DCOP library for IoT and dynamic systems[END_REF], that satellites are not overloaded [START_REF] Shah | Scheduling the World's Largest Earth-Observing Fleet of Medium-Resolution Imaging Satellites[END_REF], that at most one agent serves the same observation [START_REF] Walker | Satellite Constellations[END_REF].

∑ 𝑒 ∈ 𝑢 ∈A 𝑒 𝑢 𝑥 𝑒,𝑜 ≤ 1, ∀𝑢 ∈ X, ∀𝑜 ∈ O [𝑢] 𝑟 (15)
∑

𝑜 ∈ {𝑜 ∈ O [𝑢 ] 𝑟 |𝑢 ∈ A,𝑠 𝑜 =𝑠 },𝑒 ∈ 𝑢 ∈A 𝑒 𝑢 𝑥 𝑒,𝑜 ≤ 𝜅 * 𝑠 , ∀𝑠 ∈ S (16)
with 𝜅 * 𝑠 being the current capacity of 𝑠 given the already scheduled observations in M, M 𝑢 1 , . . . , M 𝑢 𝑛 .

∑

𝑒 ∈ 𝑢 ∈A 𝑒 𝑢 𝑥 𝑒,𝑜 ≤ 1, ∀𝑜 ∈ O (17)
Beside, the cost to integrate an observation in the current user's schedule should be assessed to guide the optimization process. We thus add soft constraint to each 𝑥 𝑒,𝑜 :

𝑐 (𝑥 𝑒,𝑜 ) = 𝜋 (𝑜, M 𝑢 𝑜 ), ∀𝑥 𝑒,𝑜 ∈ X (18)
where 𝜋 evaluates the best cost obtained when scheduling 𝑜 and any combination of observations from M 𝑢 𝑜 , as to consider all possible revisions of 𝑢 𝑜 's current schedule. Practically, instead of computing 𝜋 each time, some constraint compilation can be used to assess all these combinations only once. These exponential number of alternatives are evaluated using polynomial greedy algorithm. To sum up: C = {(15), ( 16), ( 17), ( 18)}

EXPERIMENTAL EVALUATION

Experiments aim to analyze the performances of the investigated algorithms with a growing number of requests (and observations). They are coded in Python 3.7 and executed on 20-core Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz, 62GB RAM, Ubuntu 18.04.5 LTS. We ran 30 instances of randomly generated EOSCSP with seed in [0:29] for each problem size, and plot the average, with [0.05, 0.95] confidence. The solve procedure used in psi, ssi, cbba and s_dcop is the greedy algorithm. The DCOP algorithm used by s_dcop is the DPOP implementation from pyDCOP [START_REF] Rust | pyDCOP, a DCOP library for IoT and dynamic systems[END_REF]. Randomly generated values are uniformly chosen within provided intervals. The computation time reported latter is a centralized computation time (no real distribution over several computers).

Highly conflicting problems. We evaluate the algorithms on very conflicting small-scale problems (5 min planning horizon). We generate EOSCSPs with only 3 satellites with a capacity of 20 observations, 4 exclusive users emitting 2 to 20 requests each, 8 exclusive portions per user with a random duration in [15:20], a central planner emitting 8 to 80 requests, 10 observation opportunities per request of duration 5 that can be scheduled in a time window with duration in [10:20], and a reward in [10:50:10] for exclusive user, and in [1:5] for central planner. Satellites' time window is [0, 300]. Transition times between observations are equal to 1. Exclusives are randomly positioned, while ensuring they do not overlap. Observation time windows are randomly positioned, as to ensure they are either included in one exclusive, or outside any exclusive. There are many observation overlaps, and as many requests from central planner than all requests from the exclusive users.

Figure 4 shows the results for this setting. Reward-wise, all the distributed algorithms are almost as good as greedy, which is our baseline. Still, cbba and s_dcop provides the best distributed solutions. The decline with growing number of observations is due to the satellites' capacity saturation. s_dcop and cbba's performances are at the cost of extra computation time, while remaining reasonable (approx. 1000 seconds), contrary to optimal solver (e.g. CPLEX) that cannot solve instances with more than 100 observations (not displayed here). s_dcop's higher computation time results from pre-computing function 𝜋 and the underlying DPOP solving procedure. cbba computational overhead is due to bundle valuation. At some point (problems larger than 750 observations to schedule), cbba requires more time to compute than s_dcop. This is due to the exponentially growing number of bundles to consider and the fact that at this size, with such a conflicting setting, the cbba neighborhood network is a complete graph, meaning that each user has to resolve conflicts with all the other users. Communication-wise, psi exchanges few large messages, since all requests are communicated to all users, resulting in exchanging more 10Mb in larger instances. ssi and s_dcop exchange numerous messages of smaller size (only sending bids on requests of interest), due to the sequential process they follow. On its side, cbba exchanges fewer messages of small size (approx. total 30kB in large instances), which makes it a very relevant candidate in distributed settings, with good compromise between solution quality and communication load. If reactiveness is a requirement, ssi remains the best candidate.

Realistic problems. Here, we generate large-scale EOSCSPs, with realistic parameters, with respect with order books provided by our partners, to schedule thousands of observations in a 6-hour planning horizon. We generate instances as previously but with 8 satellites with a capacity of 500 observations, 5 exclusive users with 20 to 100 requests each, 10 exclusive orbit portions per user with a duration in [300:600], 1 central planner with 25 to 250 requests, 5 observation opportunities per request of duration of 20 that can be scheduled in a time window with duration in [40:60] included in an exclusive windows (there is no request outside exclusive windows in this setting), and the planning time window is [0, 21600]. This setting corresponds to the first phase of a real constellation to be deployed in the 2 next years.

Figure 5 shows results for this setting. All algorithms provide good quality solutions equivalent to greedy. The results obtained in this setting, only focusing on observations inside exclusive windows, confirm the performances of the different benchmarked algorithm, except that here cbba does require more time to compute than s_dcop. This is due to the fact that these larger instances are less conflicting, and that the neighborhoods are no longer complete. Let's note that both s_dcop and cbba are very distributed in nature, and performs many computation concurrently. Therefore there is room for computation speedup in real distributed settings.

CONCLUSION AND SYNTHESIS

This paper investigated for the first time the use of distributed and cooperative multi-agent techniques to solve the novel EOSCSP, keeping in mind the need to limit information disclosure between users. We defined core components of EOSCSP, and proposed a straightforward MILP encoding to optimally solve such problems. This is unfortunately non usable in practice, even on small instances. We thus proposed a greedy and fast algorithm to solve EOSCSP. We devised and implemented several distributed algorithms (psi, ssi, cbba and s_dcop), all keeping the inner user plans private. s_dcop and cbba provides solutions equivalent to the best evaluated algorithms on over-conflicting problems. This has a cost: higher communication load and computation time to assess the reward to integrate an observation in a given schedule. Yet, these techniques are fully distributable, and may gain from concurrent execution. On realistic large scale problems, the solution quality is still very good wrt. greedy. While, these problems still require less coordination because the probability for overlapping observations is smaller, EOSCSP still implies numerous observations from exclusive users, which makes the computation of the s_dcop evaluation function 𝜋 and the construction of the cbba bundles expensive. A good compromise is thus to use ssi in larger settings, since computation time, communication-load are very limited, while providing good quality solutions. Note that this investigation was also a very good terrain for confronting DCOP-based and auction-based techniques, which are most often not compared in the literature.

This work raises several perspectives, notably the development of dedicated DCOP or CBBA solvers adapted to EOSCSP specificity, e.g. the use of the evaluation function 𝜋 or the construction of bundles, that may result from a learning process, instead of a systematic assessment of every alternative. On may also consider devising dedicated bidding language to assess bundles and perform the winner determination problem in a efficient manner. Moreover, we are currently working on integrating uncertainties about observation success into the decision process, which leads to even more complex problems to solve. Finally, we aim at pushing investigations in the direction of non-cooperative and market-based settings, and notably studying incentives for exclusive users to accept observations in their schedules.

Figure 1 :

 1 Figure 1: An EOS system composed of a main mission center 𝑢 0 , distributed stations (with ranges), agencies emitting observation requests (to mission center), satellites (with image footprint), and exclusive users with their own ground stations.

Figure 2 :

 2 Figure 2: An example with 3 satellites, 2 exclusive users (red and blue) with exclusives (hashed areas), and 1 non-exclusive user (green). Observation time windows appear as transparent surfaces. Solid surfaces represent an optimal solution.

Figure 3 :

 3 Figure 3: A sample auction process with one auctioneer 𝑎 and 𝑛 bidders 𝑏 𝑖 , following five main steps: (1) item announcement of the items to allocate, (2) valuation of the items or bundles by each bidder, (3) communication of the computed bids, (4) winner determination problem solving, and (5) allocation of items to bidders.

Algorithm 4 : 5 N 6 R 9 B

 4569 cbba EOSCSP solver Data: An EOSCSP 𝑃 = ⟨S, U, R, O⟩ Result: An assignment M 1 M 𝑢 0 ← ∅ 2 for each 𝑢 ∈ U ex do concurrently M 𝑢 ← solve(𝑃 [𝑢]) 3 for each 𝑟 ∈ sorted(R) do 4 for each 𝑢 ∈ U ex do 𝑢 ← candidates(𝑟 ) 𝑢 ← R 𝑢 ∪ {𝑟 } 7 while conflict do 8 for each 𝑢 ∈ U ex do concurrently 𝑢 , W 𝑢 , T 𝑢 ← bundle(𝑢) // send B 𝑢 , W 𝑢 , T 𝑢 to N 𝑢 10 for each 𝑢 ∈ U ex do concurrently

Figure 4 :

 4 Figure 4: Results for the investigated distributed solution methods on highly conflicting small-scale problems.

Figure 5 :

 5 Figure 5: Results for the investigated distributed solution methods on problems with realistic large-scale order books.

  Mission center 𝑢 0Ex. User 𝑢 1

	EO Satellite 1	EO Satellite 2	EO Satellite 3
	Comm. station
			Ex. User 𝑢 2
		Agency

  ). A satellite is defined as a tuple 𝑠 = 𝜅 𝑠 ∈ N + its capacity (i.e. the maximum number of observations during its orbit plan), 𝜏 𝑠 :

	⟨𝑡 start 𝑠	, 𝑡 end 𝑠 , 𝜅 𝑠 , 𝜏 𝑠 ⟩ with 𝑡 start 𝑠	∈ R the start time of its orbit plan,
	𝑡 end 𝑠	∈ R the end time of its orbit plan,

  𝑟 , 𝜌 𝑟 , 𝑝 𝑟 , 𝑢 𝑟 , 𝜃 𝑟 ⟩, with a validity time window defined by 𝑡 start

	Definition 4 (Reqest). A request is defined as a tuple 𝑟 =
	⟨𝑡 start 𝑟 𝑟 , Δ 𝑟 , 𝑡 end ∈ R and 𝑡 end 𝑟

Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022), P. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.), May 9-13, 2022, Online. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

Full direct tasking means a constellation user can directly send tasks to a satellite entering in its communication window, and then download the results just before the satellite is out of range. Such user masters the schedule on its orbit slot, but still requires to meet some coupling constraints as energy constraints, memory capacity and satellite orientation.

ACKNOWLEDGMENTS

This work has been performed with the support of the French government in the context of the "Programme d'Invertissements d'Avenir", namely by the BPI PSPC project "LiChIE", coordinated by Airbus Defence and Space.