Yann Koeberle
email: yann.koeberle1@huawei.com

Stefano Sabatini
email: stefano.sabatini@huawei.com

Dzmitry Tsishkou
email: dzmitry.tsishkou@huawei.com

Christophe Sabourin
email: sabourin@u-pec.fr

Learning human-like driving policies from real interactive driving scenes

Keywords: Driving simulation, Learning from demonstrations, Adversarial Imitation Learning

Traffic simulation has gained a lot of interest for autonomous driving companies for qualitative safety evaluation of self driving vehicles. In order to improve self driving systems from synthetic simulated experiences, traffic agents need to adapt to various situations while behaving as a human driver would do. However, simulating realistic traffic agents is still challenging because human driving style cannot easily be encoded in a driving policy. Adversarial Imitation learning (AIL) already proved that realistic driving policies could be learnt from demonstration but mainly on highways (NGSIM Dataset). Nevertheless, traffic interactions are very restricted on straight lanes and practical use cases of traffic simulation requires driving agents that can handle more various road topologies like roundabouts, complex intersections or merging. In this work, we analyse how to learn realistic driving policies on real and highly interactive driving scenes of Interaction Dataset based on AIL algorithms. We introduce a new driving policy architecture built upon the Lanelet2 map format which combines a path planner and an action space in curvilinear coordinates to reduce exploration complexity during learning. We leverage benefits of reward engineering and variational information bottleneck to propose an algorithm that outperforms all AIL baselines. We show that our learning agent is not only able to imitate humane like drivers but can also adapts safely to situations unseen during training.

INTRODUCTION

For real world deployment, self driving systems require quantitative safety guarantees in presence of real human drivers. Traffic simulation appears as a crucial tool to continuously provide statistics of driving performances on arbitrary number of locations and scenarios [START_REF] Scheel | Urban driver: Learning to drive from real-world demonstrations using policy gradients[END_REF] without endangering human drivers. Simulation enables to expose the Self Driving Vehicle (SDV) to various interactive situations with controlled scenario modifications so that critical failures can be identified. However the reality gap between simulated and real driving behaviours can result in positive improvements in simulation whereas dramatic issues could still occur in real settings.

Animating each traffic agent during simulation requires a decision process called driving policy which can be designed in several different ways. Heuristic based simulated agents are controlled with explicit rules and can easily perform maneuvers as changing lane or car following but generated trajectories are statistically different from trajectories generated by humans [START_REF] Treiber | Congested traffic states in empirical observations and microscopic simulations[END_REF]. Learning based methods offer more flexibility to adjust driving behaviours in various situations [START_REF] Suo | Trafficsim: Learning to simulate realistic multi-agent behaviors[END_REF][START_REF] Scheel | Urban driver: Learning to drive from real-world demonstrations using policy gradients[END_REF]. Reinforcement Learning enables to learn through interactions with a simulator where the learning agent is penalized for catastrophic failures. The main limitation of this approach comes from the fact that the true reward representative of human driving style is unknown and expensive to design because it depends on various human preferences [START_REF] Knox | Reward (mis) design for autonomous driving[END_REF]. In contrast, supervised methods enables to directly leverage real demonstrations and thus can capture more naturalistic driving behaviors. The most simple supervised learning method is Behavior Cloning which maximizes the likelihood of expert actions on a training set. This approach has big limitations in long term simulations because it suffers from errors compounding and poor generalization capabilities [START_REF] Codevilla | End-to-end driving via conditional imitation learning[END_REF]. Alternatively, Adversarial Imitation Learning (AIL) enables to exploit real data through simulation interactions and deliberately exposes the policy to situations out of expert experiences. AIL provides a guidance through a datadriven reward that the learning agent is expected to maximise during training which significantly reduces catastrophic failures and helps the agent to get closer to the expert trajectory. Several works [START_REF] Ho | Generative adversarial imitation learning[END_REF][START_REF] Kuefler | Imitating driver behavior with generative adversarial networks[END_REF] already proved that realistic driving policies can be learnt with AIL on highways scenarios but interactions on straight lanes are not representative of the driving task complexity that encompasses challenges of various road topologies. Some complex intersections, roundabouts or merging with numerous traffic agents reveals particularly difficult to handle because it induces complex interplay between agents and slight trajectory offsets could lead to crashes. Another difficulty encountered by AIL algorithms is the ability to explore efficiently in the long term in order to find a correct human-like behaviors. The driving scene does not allow arbitrary displacements and exploring naively the plane with incremental shifts could quickly lead the agent to absurd situations like going off road.

In this work, we investigate to which extent AIL algorithms can be used for learning human-like driving policies able to adapt to new situations for long horizon simulation. Our main contributions are:

• An analysis of imitation performances of driving policies trained with Adversarial Imitation learning algorithms on highly interactive driving scenes extracted from Interaction Dataset.

• An action space for parsimonious exploration based on curvilinear coordinates with respect to a reference path generated by a planner that exploit the lanelet2 map format.

• An AIL algorithm that combines the benefits from variationnal information bottleneck and reward engineering.

We start to review main approaches for learning realistic driving policies in Section 2. Subsequently, Section 3 explains how we learn a driving policy from demonstration and describes the neural networks architectures. Finally, we detail experiments settings and report our results in Section 4.

RELATED WORKS

We review main traffic simulation approaches in Section 2.1 before studying more in-depth how driving polices can be learnt from demonstrations in Section 2.2.

Traffic simulation

Traffic simulation has the potential to accelerate the development of Self Driving Vehicle (SDV) [START_REF] Cao | Reinforcement learning based control of imitative policies for nearaccident driving[END_REF].The main challenge consists in guaranteeing that interacting with simulated traffic agents could provide valuable experiences. Heuristic based traffic simulator [START_REF] Lopez | Microscopic traffic simulation using sumo[END_REF] enables to generate traffic patterns with very few crashes but usually largely differ from real human traffic. Rule based driving policies like IDM [START_REF] Treiber | Congested traffic states in empirical observations and microscopic simulations[END_REF] designed for longitudinal control on highways or Mobil [START_REF] Kesting | General lane-changing model mobil for car-following models[END_REF] designed for lane changes cannot handle arbitrary road topologies where various trajectory profiles are plausible like complex intersections. Learning based methods offer more flexibility to adapt the driving policy to various scenes because they can leverage human demonstrations.

Reinforcement learning offers the possibility to design custom driving behaviours based on hand crafted rewards so that the driving agent can adapt to various situation based on explicit feedbacks like incentive to slow down at intersections, penalty in case of over-speeding, etc. Several works [START_REF] Chen | Interpretable end-to-end urban autonomous driving with latent deep reinforcement learning[END_REF][START_REF] Sharma | Wad: A deep reinforcement learning agent for urban autonomous driving[END_REF] show that RL driving policies are able to avoid safety critical failures in urban scenarios but the main limitation comes from the fact that the hand crafted reward does not constitute the true driving performance but acts as a proxy [START_REF] Knox | Reward (mis) design for autonomous driving[END_REF]. Consequently a policy that has high expected return is not guaranteed to behave as a human would do which may lead to unrealistic traffic patterns. In order to drive as a human, data based methods leverage the huge amount of real driving demonstrations available to learn trajectories that match human preferences. Simnet [START_REF] Bergamini | Simnet: Learning reactive selfdriving simulations from real-world observations[END_REF] or TrafficSim [START_REF] Suo | Trafficsim: Learning to simulate realistic multi-agent behaviors[END_REF] builds upon prediction models to learn a centralized policy to animate each agent in the driving scene, but a centralized policy can not easily scale to large scenarios because it has to handle exponential number of interactions in the number of agents for long simulation horizons. In contrast, the RAIL algorithm [START_REF] Bhattacharyya | Simulating emergent properties of human driving behavior using multi-agent reward augmented imitation learning[END_REF] formulates traffic simulation as a multi agent imitation problem and shows that realistic traffic patterns can be learnt but it also assumes that all driving agents are controlled by the same policy, driven by the same reward neglecting the diversity of real road users. Even if complementary approaches based on multi agent reinforcement enables to learn multiple policies with a centralized critic it is still very challenging to maintain training stability and convergence guarantees [START_REF] Lyu | Contrasting centralized and decentralized critics in multi-agent reinforcement learning[END_REF].

Consequently we consider traffic simulation as a decentralized problem which consists in learning single agent driving policies behaving close to human drivers for long simulation horizons.

Learning to drive from demonstration

In order to learn a realistic driving policy from human demonstrations it is possible to formulate the driving task as a supervised problem called Behavioural Cloning (BC) with the objective of matching actions generated by the learning policy and the ones selected by the expert [START_REF] Codevilla | End-to-end driving via conditional imitation learning[END_REF]. This technique suffers from compounding errors during test time because BC is trained offline in open loop with i.i.d samples whereas the closed loop evaluation of the policy induces a distributional shift due to sub optimal past decisions.

To compensate deviations in closed loop, it is possible to complete the training dataset by querying an interactive expert but online supervision is highly constraining because it either requires a human in the loop or a specific expert system [START_REF] Ross | A reduction of imitation learning and structured prediction to no-regret online learning[END_REF]). An alternative is to resort to uncertainty-based regularization with ensemble of expert policies to reduce deviations from expert trajectories distribution [START_REF] Brantley | Disagreement-regularized imitation learning[END_REF]. While this technique encourages the learner to stay close to the expert trajectories, it cannot provide explicit guidance out of distribution and remains computationally expensive to estimate accurately.

Adversarial Imitation Learning (AIL) offers more flexibility to guide the policy and several works already showed that generative adversarial imitation learning is able to learn realistic driving policies on highways scenario despite collisions still happens [START_REF] Ho | Generative adversarial imitation learning[END_REF][START_REF] Kuefler | Imitating driver behavior with generative adversarial networks[END_REF]. More importantly, standard AIL algorithms suffer from training instabilities due to the asymmetric competition between discriminator and the generator. The discriminator quickly tends to get too accurate which leads to uninformative gradients for the policy which struggles to match the expert driving strategy. To balance the performance between the generator and the discriminator, VAIL [START_REF] Peng | Variational discriminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining information flow[END_REF] enforces a constraint on the mutual information between the input observation and the discriminator's internal representation which prevents the accuracy from getting too high. Even if this method enables to maintain informative guidance for the policy, the discriminator cannot understand the causal structure of the driving task which may lead to crashes once the policy is too far from training distribution [START_REF] De Haan | Causal confusion in imitation learning[END_REF].

To help the discriminator to avoid catastrophic failures, domain knowledge could be used to feed the discriminator with high level semantic signals like off-road driving or collision indicators [START_REF] Wang | Decision making for autonomous driving via augmented adversarial inverse reinforcement learning[END_REF]. However the value assigned to the signal is subjective and case sensitive which can deter the dis-criminator to exploit relevant features in the state action pair originally provided as input. To limit side effects on the discriminator, one can just add a penalty to the discriminator reward when the policy goes in undesired situations [START_REF] Bhattacharyya | Simulating emergent properties of human driving behavior using multi-agent reward augmented imitation learning[END_REF]. We build upon those recent advances in AIL to learn a realistic driving policy that can drive on new scenarios with better safety.

LEARNING A REALISTIC DRIVING POLICY

We formulate the driving task in Section 3.1 before detailing how to learn realistic driving policies in Section 3.2.

Problem setting

We aim to learn realistic driving policies for animating traffic agents in simulation. Traffic simulation consists in generating driving episodes from predefined driving scenarios. A driving scenario S = (M , F , ρ 0 , H, G) is composed of a simulation horizon H, a bounded map of a road-network M and a traffic flow F that spawns traffic agents at specific time on the map according to an initial state distribution ρ 0 and a set of destinations G. We consider decentralized traffic simulation where each agent is animated by its own driving policy assigned by the traffic flow. As real driving episodes are likely to include diverse policies, learning them simultaneously can turn highly unstable. Consequently, we propose to learn a single agent driving policy per episode called actor policy while other agents in the scene called workers are controlled by fixed driving policies. In order to learn a single agent driving policy, we formulate the task as Partially Obsersable Markov Decision Process (POMDP): (S , O,A,T , R ). We condition the policy π on a goal g provided at initialization by the traffic flow to specify the driving task. At each decision step, the policy gets an ego centric observation o of the scene and take an action a to reach its goal. The observation is provided by an observer model O : S → O that operates on the driving scene states S. The driving scene state s which encompasses the actor state as well as traffic workers states evolves according to the transition dynamic T which take into account the actor action and implicitly traffic workers decisions.

The reward process R is composed of two components based on domain knowledge and human demonstrations as detailed in Section 3.2.1.

Learning from real driving data

We aim to learn a single agent driving policy π θ from real demonstrations parametrized by a neural network. We build upon adversarial imitation learning and train jointly a policy and a discriminator so that the policy generates expert like trajectories while the discriminator is trained to distinguish the policy and expert trajectory samples. Similarly to GAIL [START_REF] Ho | Generative adversarial imitation learning[END_REF], we aim to solve the following problem:

min π θ max D ϕ E (s,a)∼ρ πe [log(D ϕ (s, a))]+ E (s,a)∼ρ π θ [log(1 -D ϕ (s, a))] -λH(π θ ) (1)
where H(π θ ) denotes the policy causal entropy and ρ π e , ρ π θ the marginal observation action distributions induced by expert and policy respectively. In order to solve this bi-level optimization problem [START_REF] Liu | Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond[END_REF], we alternate between optimizing the discriminator and optimizing the policy. The training procedure, depicted in Figure 1, is decomposed in three main steps repeated until the maximum number of training iterations is reached. The first step consists in collecting in parallel, multiple driving episodes with the current policy π θ and gathering them in the policy buffer B π . Subsequently, we train the discriminator on recent policy samples and expert demonstrations as described in Section 3.2.2. The third steps consists in updating the policy based on Proximal Policy Optimization (PPO) [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] on a training batch extracted from B π as detailed in Section 3.2.1. Note that the simulation horizon is progressively increased during training along with our policy improvements. In the two following sections, we explain how additionally we augment the usual AIL training procedure summarized above to leverage domain knowledge (Section 3.2.1) and to regularize the discriminator (Section 3.2.2).

Updating the policy

The policy is trained with a reward signal r that is decomposed in two terms a synthetic reward r S based on domain knowledge and data driven term r D ϕ computed with the discriminator D ϕ as detailed in Section 3.2.2. r = r S + r D ϕ (2) The synthetic reward is itself composed of two terms: one that penalizes collisions when they occur r col and one that favors forward displacement r ds :

r s = r col + αr ds (3)
While the synthetic reward enables to avoid crashes and motionless behaviour, the data driven is expected [START_REF] Schulman | High-dimensional continuous control using generalized advantage estimation[END_REF]. Subsequently, PPO objective max θ J PPO (θ) can be optimized with a clipping mechanism that tries to avoid abrupt changes of the policy parameters limited by the threshold ε π .

J PPO (θ) = E (a t ,o t )∼π θ old [min(L π (θ), L π clip (θ))] L π (θ) = µ t (θ) ÂGAE t (o t , a t ) L π clip (θ) = clip(µ t (θ), 1 -ε π , 1 + ε π ) ÂGAE t (o t , a t )

Updating the discriminator

In the original GAIL algorithm, the discriminator tends to get too accurate too quickly during training which limits the progresses of the policy. Indeed, as the classification loss is easier to optimize compared to PPO loss that has high variance, the discriminator output progressively gets close to zero for policy samples. Consequently, the data driven reward r D ϕ = log(D ϕ (o, a) + ε)log(1 -D ϕ (o, a) + ε), bounded with ε = 10 -8 to avoid exploding gradients, saturates at a negative value instead of guiding the policy. In order to balance the performance of the policy and the discriminator, we complement the original that enables to define the constrain on the information flow. The algorithm called VAIL optimizes the standard GAIL objective while maintaining the mutual information constrain by introducing a Lagrangian multiplier β updated with dual gradient ascent [START_REF] Peng | Variational discriminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining information flow[END_REF].

min ϕ max β J Disc (ϕ) + βM(ϕ) (4)
The discriminator objectiveJ Disc (ϕ) is optimized with mini batch gradient descent for K epochs on policy and expert buffers.

J Disc (ϕ) = E (o,a)∼B e [E z∼E ϕ (z|(o,a)) [log(D ϕ (z)]]+ E (o,a)∼B π [E z∼E ϕ (z|(o,a)) [log(1 -D ϕ (z)]] (5)
As the mutual information I((O, A), Z) cannot be easily computed due to the difficulty to estimate 1 The discriminator input is an Observation Action pair, hence the mutual information is written I((O, A), Z).

M(ϕ) = E (o,a)∼ π[KL[E ϕ [z|(o, a)]||r(z)]] -I c (6)
where I c = 0.5 denotes a threshold value. We update the Lagrangian multiplier β with dual gradient ascent in order to maintain the constrain on the mutual information as detailed in [START_REF] Peng | Variational discriminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining information flow[END_REF].

Once the discriminator is trained, the data driven reward is computed with the discriminator output D ϕ (o, a) that represents the probability that (o, a) was generated from an expert. In order to reduce the reward bias induced by purely negative or positive rewards, we use the reward formula introduced in [START_REF] Kostrikov | Discriminator-actorcritic: Addressing sample inefficiency and reward bias in adversarial imitation learning[END_REF]:

r D ϕ (o, a) = log(D ϕ (o, a)) -log(1 -D ϕ (o, a)) (7)

Driving policy

We detail in Section 4.1 how the driving policy observes and takes action before describing our neural network architecture in Section 4.2.

Observation and Action space

The driving policy π(a|o, p(g)) is both conditioned on an ego-centric observation of the driving scene and on a reference path p(g) that leads to its destination. The reference path p(g) is computed by a top level path planner independently from the scene context leveraging the lanelet2 map format of the driving scene.

In order to move as much as possible along p(g) we define the action space based on curvilinear coordinates (s, n) with respect to p(g) as depicted in Figure 2. We enforced the policy to output longitudinal and lateral (ds, dn) shifts at each decision step which enables to explore parsimoniously plausible trajectories and to stop simulation when actor gets too far from the route. In contrast, controlling directly the forward acceleration and the turn rate would not guide the displacement of the agent toward the goal during exploration but let it easily deviate from p(g).

In order to infer appropriate moves, we provide an observation composed of several contextual components of the driving scene in a vectorized format. We provide information about the map like the lane corridor and the reference route. The Lane corridor ,20] ] is composed of the right and left borders coordinates relative to the actor of the drivable area 2 in a 10 meter radius around the reference path. The reference route is a piece of the reference path p(g) 10 meters in front of the actor. We also provide information about the traffic context with five nearest neighbors configurations ,5] and their trajectory histories for the last 2 seconds relative to current actor -20×dt,...,t] . Each neighbor configuration contains a mask m to indicate if the i-th neighbor exists, its position relative to the actor x i , y i , its speed vector v x i , v y i , relative distances d i as well as its spatial extension with the four border points coordinates on front, rear, left and right side

L = [L r = [(x i , y i )] i∈[1,20] , L l = [(x i , y i )] i∈[1
N = [(m i , x i , y i , v x i , v y i , d i , B i p ] i∈[1
position H N = [H i = [(x i t , y i t , θ i t ] t∈[t
B i p = [b i f l , b i f r , b i rr , b i rl ]
. Lastly, we add two components to specify the actor current state x ego and the coordinates of its trajectory for the last 2 seconds 2 The drivable area is extracted based on the sequence of lanelets [START_REF] Poggenhans | Lanelet2: A high-definition map framework for the future of automated driving[END_REF] that constitutes the reference path p(g).

τ ego = [X t-20×dt , ...X t-dt , X t ].

Neural network Architecture

The driving policy π θ is implemented with a neural network that parametrizes the next action [ds t , dn t ] with two independent gaussian distributions whose mean and variance are both learned. The network first embeds each observation components with specific sub networks built upon Fully Connected (FC) layers and generates a set of observation features F = [F i ] i∈ [1,..,6] depicted with colored rectangles in Figure 2. In order to handle the variable number of neighbors in the scene, individual configuration and history are embedded for each neighbor with two separate networks shared for all neighbors. The feature vectors F 3 , F 4 that represent neighbors histories and neighbors configurations are computed by summing individual embeddings when the agent exists as indicated by a mask. At the end of the Observation network backbone, observation features are combined by concatenation and a FC layer computes the final observation embedding vector. The policy and value heads composed of consecutive FC layers share the same observation embedding vector but the value gradients are not back-propagated through the backbone which would perturb the policy for the next data collection. Regarding the discriminator, it shares same architecture for computing the observation embedding vector but has a separate network. The encoder and decoder networks are built with consecutive (FC) layers. Note that z is sampled using the reparametrization trick : z = µ z + ε.σ z with ε ∼ N (0, I) during discriminator updates whereas the mean µ z is directly used to feed the decoder D ϕ when the reward is computed for PPO updates.

EXPERIMENTS

Simulation Dataset and metrics

In order to learn a driving policy from real demonstrations through interactions, we build a driving simulator on top of driving scenes extracted from the Interaction dataset [START_REF] Zhan | Interaction dataset: An international, adversarial and cooperative motion dataset in interactive driving scenarios with semantic maps[END_REF]. The dynamics of traffic workers is approximated by replaying their original trajectories during simulations because we ignore how to animate them realistically on new situations. We focus on three different maps with high number of interactions: the roundabout called DR DEU Roundabout OF, the intersection called DR USA Intersection EP0 and the merging called DR DEU Merging MT . Since we aim to imitate the driving style of road users on specific spots we train our driving policy separately on three training sets for each map. For each of the training set, we extracted 200 driving scenarios for each of the following temporal horizons: 2.5, 5, 7.5, 10, 12.5 and 15 seconds which gives a total of 1200 training scenarios per area 3 . The three associate validation sets are each composed of 128 new real scenarios of 15 seconds in order to focus on long term simulation performances. In order to evaluate the imitation of the actor driving policy we compute the Average Distance Error with respect to the human demonstration (ADE) after 5 and 15 second of simulation. We also report the percentage of episodes that contains a collision (CR) to estimate if the driving behaviour is safe.

Results

We analyse the performances of different AIL algorithms for learning realistic driving policy based on real driving demonstration of the validation set. We trained several baselines that we list below:

• BC: implements standard behavioural cloning that only exploit expert demonstrations [START_REF] Codevilla | End-to-end driving via conditional imitation learning[END_REF].

• GAIL: implements a standard implementation of GAIL algorithm without the variational information bottleneck [START_REF] Ho | Generative adversarial imitation learning[END_REF].

• SGAIL: implements GAIL algorithm whose reward is augmented by the addition of a synthetic component r S = r col + 0.1r ds as detailed in Section 3 inspired from [START_REF] Bhattacharyya | Simulating emergent properties of human driving behavior using multi-agent reward augmented imitation learning[END_REF]. The penalty equals r col = -2 when the collision occurs and the bonus for longitudinal displacement r ds = max(1.0, ds ds max ) depends on the maximal speed allowed ds max = 50km/hour.

• SVGAIL: implements the VAIL algorithm detailed in Section 3.2 and adds the synthetic reward the same way as SGAIL.

We trained all those baselines with the neural network architecture detailed in Section 4.2 on the demonstrations of each training set separately. We compare imitation and safety metrics on the validation set and we 3 This enables to extract as much demonstrations as possible even if some agents do not stay a long time on the recorded scene report the metrics in Table 1. We first compare GAIL performances with Behaviour Cloning that does not learn through simulation interactions. We observe that BC suffers from compounding errors with high ADEs and tends to collide on a majority of scenarios. GAIL outperforms BC performances for long term imitation and gets significantly safer than BC with a much lower rate of episode with collisions. As GAIL still often collides it could be beneficial to penalize it more intensively with a synthetic reward for this specific event. We observe that SGAIL successively improves safety performance of GAIL while keeping similar imitation metrics. The results of SVAIL shows that imitation performances can further been improved compared to SGAIL by modulating the accuracy of the discriminator. We conclude that original GAIL can significantly benefit from modifications proposed in SGAIL and VAIL. Comparing the ADE-15 variations of SVAIL between the three maps, we note that its is harder to imitate human driving style on scenarios built on the intersection. This can be explained by the fact that the interaction map contains more lanes and junctions than the roundabout and the merging with numerous agent spawning locations encoded in the initial state distribution ρ O4 . Consequently the expert trajectory distribution on the intersection has a bigger support which is more difficult to learn both for the discriminator and the policy.

CONCLUSIONS

In this work, we analyse imitation and safety performances of AIL algorithms on real and highly interactive scenarios extracted from Interaction Dataset. We propose an efficient action space based on a reference path and curvilinear coordinates which enables to explore plausible human trajectories parsimoniously. We propose an advanced version of the VAIL algorithm that exploits a synthetic reward based on domain knowledge and the lanelet2 map format for observation extraction to better guide the policy during training. We show that our algorithm outperforms all the baselines in imitation and safety on driving scenarios unseen during training. For future works, we plan to better control the trade off between human imitation and safe driving which still limits practical applications.

F4Figure 2 :

 2 Figure 2: On the left side, illustration of the components of the observation provided to the policy as well as the action generated by the policy and on the right side, architecture of the discriminator-actor-critic neural network.

  problem 3.2 by constraining the information flow in the discriminator by means of an information bottleneck. We enforce a constraint on the mutual information I((O, A), Z) between the input of the discriminator 1 and its internal representation Z to modulate the discriminator's accuracy. Consequently the discriminator D ϕ is composed of two parts: an encoder E ϕ that maps an observation action pair (o, a) to a stochastic encoding z ∼ E(z|(o, a)) and a decoder D ϕ that classifies samples drawn from the encoder distribution as human-like or not. The encoder outputs the mean µ z (φ) and the standard deviation σ z (φ) of a multi variate Gaussian distribution N (µ z (φ), σ z (φ))

  the marginal distribution p(z), we approximate p(z) with a multivariate normal r(z) = N (0, I). Consequently we obtain an upper bound denoted M(ϕ) on I((O, A), Z) which we use as a regularizer.

  The actor configuration contains, its last action [ds t-dt , dn t-dt ], a collision flag f col , and its spatial extension in terms of border points coordinates

The reader can refer to Interaction Dataset description[START_REF] Zhan | Interaction dataset: An international, adversarial and cooperative motion dataset in interactive driving scenarios with semantic maps[END_REF] to observe the difference.


Tenda Okimoto

Emir Demirovic Nicolas Schwind

Katsumi Inoue

Pierre Marquis

Robust Coalition Structure Generation

Keywords: Multi-Agent System, Coalition Structure Generation, Robustness

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Coalition Structure Generation (CSG) [START_REF] Rahwan | Coalition structure generation: Dynamic programming meets anytime optimization[END_REF][START_REF] Sandholm | Coalitions among computationally bounded agents[END_REF] is a key issue for a number of applications related to multi-agent cooperation, e.g., waste-water treatment system [START_REF] Dinar | Application of stochastic cooperative games in water resources[END_REF], distributed vehicle routing [START_REF] Sandholm | Coalitions among computationally bounded agents[END_REF] and multi-sensor networks [START_REF] Dang | Overlapping coalition formation for efficient data fusion in multi-sensor networks[END_REF]. CSG involves partitioning a set of agents into coalitions so that the sum of the values of all coalitions is maximized. In CSG, it is well-known that finding an optimal coalition structure which maximizes the social surplus is NP-hard. Indeed, the decision problem associated with CSG is equivalent to the complete set partition problem [START_REF] Yeh | A dynamic programming approach to the complete set partitioning problem[END_REF] which is NP-complete.

Robustness (i.e., it is not required to recompute new coalitions of CSG even if some agents break down) is an expected property of CSG. In this paper, the focus is laid on the Robust Coalition Structure Generation (RCSG) problem. A formal framework for the RCSG problem is presented and some decision and optimization problems for RCSG are pointed out. A coalition structure is viewed as k-robust (for a given non-negative integer k) if removing any subset of k agents from it leads the remaining coalitions to still be beneficial. The RCSG decision problem consists in determining whether there exists a u-beneficial and k-robust coalition structure, for a given reward threshold u and robustness threshold k. We identify the computational complexity of the RCSG decision problem. While the standard CSG problem is NP-complete, we show that the RCSG decision problem is inherently harder unless the polynomial hierarchy collapses (RCSG is Σ p 2 -complete). One of the optimization counterparts of this problem consists in fixing the robustness threshold k and finding one of the most beneficial coalition structures meeting the robustness requirement. Dually, one can also fix the reward threshold u and optimize the robustness of a u-beneficial coalition structure. Lastly, one can consider the bi-objective optimization problem where the aim is to optimize both the reward and the robustness of a coalition structure.

As an application domain, we believe that the vehicle routing problem [START_REF] Sandholm | An implementation of the contract net protocol based on marginal cost calculations[END_REF] is promising area, which can be formalized as CSG, where geographically dispersed dispatch centers of several companies cooperate. When we consider both the effectiveness and robustness of the drivers' groups, this problem amounts to a robust CSG problem. Another application area is about the multi-sensor networks [START_REF] Dang | Overlapping coalition formation for efficient data fusion in multi-sensor networks[END_REF], which can be also formalized as CSG. Consider several sensors in an airport or in a shopping center where some sensors collaborate and observe a certain area for the security reason. Then, forming effective and robust groups of sensors, amounts to solving a RCSG problem.

Related to our work is the team formation problem (TF) [START_REF] Nair | Hybrid bdi-pomdp framework for multiagent teaming[END_REF][START_REF] Vidal | The effects of co-operation on multiagent search in task-oriented domains[END_REF]. Compared to the TF problem, CSG is similar to the complete set partition problem [START_REF] Yeh | A dynamic programming approach to the complete set partitioning problem[END_REF], while TF is equivalent to the set cover problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. The robustness issue has recently been considered in TF [START_REF] Okimoto | How to form a task-oriented robust team[END_REF]. Our approach of robustness in CSG is similar to the one developed in this work. However, this paper focuses on the robustness issue for CSG. Also, the significant difference between RCSG and robust TF lies in the complexity of each of the corresponding decision problems: RCSG is shown here to be Σ p 2 -complete, whereas robust TF is "only" NP-complete. To the best of our knowledge, the robustness issue for CSG have been left unaddressed so far in the literature.

Coalition Structure Generation

Let us start with some preliminary definitions. Let A = {a 1 , a 2 , . . . , a n } be a finite set of agents. A coalition from A, denoted as C, is a non-empty subset of A. A coalition structure on A, denoted as CS, is a partition on A, i.e., a jointly exhaustive set of pairwise disjoint coalitions from A. Formally, a coalition structure CS (on A) is a set of coalitions {C 1 , . . . , C m } such that for each i, j ∈ {1, 2, . . . , m} such that i ̸ = j, we have that

C i ∩ C j = ∅ and ∪ Ci∈CS C i = A.
Definition 1 (CSG problem description). A coalition structure generation problem description is defined by a pair CSG = ⟨A, v⟩ where A = {a 1 , a 2 , . . . , a n } is a set of agents and v : 2 A → N is a function called a characteristic function.

The value of a coalition C, denoted as v(C), is given by the characteristic function v. The value of a coalition structure CS, denoted as V (CS), is the sum of the values of each coalition, i.e.,

V (CS) = ∑ Ci∈CS v(C i ).
A coalition structure is said to be optimal, denoted as CS * , if CS * satisfies the followings: ∀CS, V (CS) ≤ V (CS * ).

Example 1 (CSG).

Let us consider the following scenario. The olympic games will be held in Tokyo and it requires some interpreters in different stadiums, e.g., athlet-ics stadium, swimming stadium and basketball stadium etc. A service company dispatching interpreters with three employees (Ana, Becky and Carol) has received the requests of the simultaneous interpretation and send them employees to different stadiums: request 1 requires Ana, and the company gets $20 for it; request 2 pays $30 and needs Becky's language skill; request 3 needs Carol and pays $10; request 4 pays $80 and needs Ana and Becky; request 5 pays $90 and needs Ana and Carol; request 6 needs Becky and Carol and pays $70; request 7 requires all employees and pays $110. Assume that you are the manager of this service company and want to assign the employees to job(s) so that the sum of the rewards is maximized. Then, this problem can be represented as a CSG: let CSG = ⟨A, v⟩ be a CSG problem description with A = {Ana, Becky, Carol}, and the function v is characterized as follows:

v({Ana}) = $20, v({Becky}) = $30, v({Carol}) = $10, v({Ana, Becky}) = $80, v({Ana, Carol}) = $90, v({Becky, Carol}) = $70, v({Ana, Becky, Carol}) = $110.
The optimal coalition structure is CS * = {{Becky}, {Ana, Carol}}, and the obtained value by

CS * is V (CS * ) = v({Becky}) + v({Ana, Carol}) = $30 + $90 = $120.
An expected property for coalition structures is to ensure a given level of efficiency. Formally, this (quite standard) property can be stated as follows:

Definition 2 (Beneficialness). Let CSG = ⟨A, v⟩ be a CSG problem description. Given a coalition structure CS and a non-negative integer u, CS is said to be ubeneficial if the value of CS is larger than u: V (CS) ≥ u.

Let us stress an important remark as to the representation of the characteristic function v in a CSG. In our running example about the service company dispatching interpreters, v is defined "implicitly", i.e., it is viewed as an oracle. One possible generalization of our example above to an arbitrary number n of agents would be to associate with every coalition C a number depending on the size of C only; in such a case, the corresponding characteristic function v can be represented with a size in O(n). A number of representation settings for characteristic functions have been pointed out in the literature, and some of them have been adapted to CSG and studied from the computational complexity viewpoint [START_REF] Ohta | Coalition structure generation utilizing compact characteristic function representations[END_REF]. Among the representation frameworks which have been developed are marginal contribution nets (MC-nets) [START_REF] Ieong | Marginal contribution nets: A compact representation scheme for coalitional games[END_REF] and synergy coalition groups (SCGs) [START_REF] Conitzer | Complexity of constructing solutions in the core based on synergies among coalitions[END_REF]. Contrastingly, some early work [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF][START_REF] Sandholm | Coalitions among computationally bounded agents[END_REF] assume that v is provided "fully extensionally" as an input of a CSG problem description, i.e., v is given as a table with 2 n -1 entries, associating with every coalition a number. Providing such an extensional representation of v makes the size of an input CSG to be exponential in the number of agents and may be an unrealistic assumption for relatively large problems. Yet there exist many real world applications involving only a dozen of agents (e.g. because of the limited resources), for which an extensional representation of v is feasible [START_REF] Dang | Overlapping coalition formation for efficient data fusion in multi-sensor networks[END_REF][START_REF]Distributed Sensor Networks: A Multiagent Perspective[END_REF][START_REF] Sandholm | An implementation of the contract net protocol based on marginal cost calculations[END_REF]. Thus, cooperative games can be used to analyze cost allocation problems, where the players are willing to form coalitions in order to get extra monetary savings as an effect of cooperation. For instance, in [START_REF] Dinar | Application of stochastic cooperative games in water resources[END_REF] the authors address the problem where nearby municipalities must take the decision on whether to cooperate in order to implement a Waste-water Treatment System (WTS). These types of problem can be represented formally as a CSG and it involves a few agents in essence, so that (i) considering a few number of agents for experimentations, and (ii) assuming an extensional representation of the characteristic function, can sometimes be considered as reasonable.

So both choices of representation for v (i.e., "implicit" vs. "extensional") have been considered in the literature. It turns out that for a number of implicit representations of v (including MC-nets and SCG, see [START_REF] Ohta | Coalition structure generation utilizing compact characteristic function representations[END_REF]), the complexity of computing a beneficial coalition structure (cf. Definition 2) is NP-hard: Definition 3 (DP-CSG).

-Input: A coalition structure generation problem description CSG = ⟨A, v⟩, and a non-negative integer u, -Question: Does there exist a coalition structure CS such that CS is u-beneficial?

As mentioned above, the complexity of DP-CSG is NP-complete in general: Theorem 1 ( [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]). If the characteristic function v is computable in polynomial time, then DP-CSG is NP-complete.

In the next section, we will show that computing a "robust" coalition structure is an intrinsically harder problem than the traditional CSG problem.

Robust Coalition Structure Generation

In this section, a formal framework for Robust Coalition Structure Generation (RCSG) is defined. Furthermore, both the decision and optimization problems for RCSG are considered. Also, the computational complexity of RCSG is identified.

Let A = {a 1 , . . . , a n } be a set of agents and A ′ ⊆ A. The restriction on A ′ of a coalition C from A is defined as the set C ∩ A ′ . We extend this notion of restriction on coalition structures as follows. The restriction on A ′ of a coalition structure CS = {C 1 , . . . , C m } on A is defined as the coalition structure CS ′ = {C ′ 1 , . . . , C ′ m } \ {∅} on A ′ , where for each i ∈ {1, . . . , m}, C ′ i is the restriction on A ′ of C i . Consider the same coalition structure generation problem in our example of the service company dispatching interpreters. Let us consider the coalition structure CS = {{Ana, Becky}, {Carol}} and A ′ = {Ana, Carol}. Then, the restriction on A ′ of CS is the coalition structure {{Ana}, {Carol}}. Robustness can now be defined in formal terms as follows:

Definition 4 (Robust Coalition Structure). Let CSG = ⟨A, v⟩ be a CSG problem description. For a given coalition structure CS on A and non-negative integers u and k, CS is said to be (u, k)-robust if for every

A ′ ⊆ A, such that |A ′ | ≥ n -k, the restriction on A ′ of CS is u-beneficial.
That is to say, a coalition structure is (u, k)-robust if whenever k agents are removed from it, the "remaining" coalition structure is u-beneficial. Obviously enough, robustness generalizes the usual notion of beneficialness in CSG. Indeed, we trivially have that for any non-negative integer u, a CSG is u-beneficial if and only if it is (u, 0)-robust.

Example 1 (continued).

Let us consider the service company dispatching interpreters with three employees. The manager of this company planed to assign Becky to the request 2 and Ana and Carol to the request 5 so that he/she gets the maximal rewards. However, what's happen if one of them cannot work on the day because of the illness or other unexpected matters. For instance, let u = $70 and k = 1, that is, the manager wants to have at least $70 even if such an event would occur. In this example, the optimal coalition structure planed in advance is CS * = {{Becky}, {Ana, Carol}}. To check whether CS * is (70, 1)-robust, we check for each removed agent from CS * whether the remaining coalition structure is 70-beneficial. We have that:

V (CS * \ {Ana}) = v({Becky}) + v({Carol}) = $40, V (CS * \ {Becky}) = v({Ana, Carol}) = $90, V (CS * \ {Carol}) = v({Ana}) + v({Becky}) = $50.
When we remove Ana from CS * , the remaining coalition structure is not 70-beneficial. Intuitively, this comes from the fact that it is not "safe" to form the coalition {Ana, Carol} to get a reward of $90, since the absence of Ana from this coalition would leave Carol alone, getting a reward of $10. Thus, CS * is not (70, 1)-robust. However, CS = {{Ana, Becky, Carol}} is (70, 1)-robust, since all remaining coalition structures are 70-beneficial after we remove each agent from CS, i.e., V (CS \ {Ana}) = $70, V (CS \ {Becky}) = $90, and V (CS \ {Carol}) = $80.

In the following, we assume that the characteristic function v of CSG = ⟨A, v⟩ satisfies the property of monotonicity, i.e., for all coalitions

C, C ′ , if C ⊆ C ′ then v(C) ≤ v(C ′ ).
This property requires that adding an agent to a given coalition is harmless, or stated otherwise, removing an agent from a coalition does not result in an increase of its value. This assumption is very natural when considering the robustness issue, as we are interested in dealing with the "damages" caused to a coalition structure when removing a number of agents from it. 6 Nonetheless, this assumption does not affect the following complexity results, that is, it does not make the RCSG problem computationally easier.

Definition 5 (DP-RCSG).

-Input: A CSG problem description CSG = ⟨A, v⟩, with v computable in polynomial time, and two non-negative integers u and k, -Question: Does there exist a coalition structure CS such that CS is (u, k)-robust?

In the general case, computing a robust coalition structure is a harder problem than computing a beneficial one (unless the polynomial hierarchy collapses): the mapping x associating any literal over X with a pair of agents from A, defined for every (possibly negated) literal

Proposition 1. DP-RCSG is Σ p 2 -complete. Σ p 2 -
x i as x(x i ) = {a i , āi } if x i is a positive literal, otherwise x(x i ) = {b i , bi };
the mapping y associating any literal over Y with a pair of agents from A, defined for every (possibly negated) literal y i as y(

y i ) = {a i , b i } if y i is a positive literal, otherwise y(y i ) = { āi , bi }.
Additionally, we assume that α is viewed as a set of clauses written as (l i , l j , l k ), where l i , l j , l k are literals from X ∪ Y , and such that the literals l i , l j , l k are ordered in such a way that if

l i ∈ Y (resp. l j ∈ Y ) then l j , l k ∈ Y (resp. l k ∈ Y ). Then a clause (l i , l j , l k ) ∈ α can be of the form (x i , x j , y k ), (x i , y j , y k ) or (y i , y j , y k )
, since the presence of clauses of the form (x i , x j , x k ) make the QBF trivially not valid. Then given the QBF ∀X∃Y.α, the characteristic function v is defined as follows. Consider the function p associating any literal p q from X ∪ Y with a pair of agents from A, defined as p(p q ) = x(x l ) if p q = x l , otherwise p(p q ) = y(y m ) when p q = y m . For each coalition C ⊆ A, we set:

(i) v(C) = 2n + 1 if there exists i ∈ {1, . . . , n} such that {a i , āi } ⊆ C or {b i , bi } ⊆ C; (ii) v(C) = n + 1 if there exists a clause (p i , p j , p k ) from α such that p(p q ) ∩ C ̸ = ∅,
for any q ∈ {i, j, k}; (iii) v(C) = 1 in the remaining cases.

We often refer to these conditions as (i), (ii) and (iii) in the rest of the proof.

First, one can easily check that v satisfies (monotonicity). Indeed, one can see that for any coalition C ⊆ A, if C satisfies condition (i) (resp., condition (ii), (iii), (iv)), then any coalition C ′ such that C ⊆ C ′ also satisfies condition (i) (resp., condition (ii), (iii), (iv)). Hence, for all coalitions

C, C ′ ⊆ A, if C ⊆ C ′ then v(C) ≤ v(C ′ ). Therefore, v satisfies (monotonicity).
We intend now to prove that the QBF ∀X∃Y.α is valid if and only if there does not exist any coalition structure which is (2n + 1, 2n)-robust, i.e., if and only if for every coalition structure CS on A, there exists a set A ′ ⊆ A, |A ′ | = 2n, such that the restriction on A ′ of CS is not (2n + 1)-beneficial. This would show that the complementary problem of RCSG is Π p 2 -hard, thus that RCSG is Σ p 2 -hard.

(If part) We show the contraposite of the claim. Assume that the QBF ∀X∃Y.α is not valid, i.e., ∃X∀Y.¬α is satisfiable, and let us prove that there exists a coalition structure which is (2n + 1, 2n)-robust. So let ω X be an interpretation over X such that for any interpretation ω Y over Y , one the clauses of α is not satisfied by ω X ∪ ω Y . Define the coalition structure CS r as CS r = {C r , C 1 r , . . . , C n r }, where:

-C r = {a i , āi | i ∈ {1, . . . , n}, ω X (x i ) = 0} ∪ {b i , bi | i ∈ {1, . . . , n}, ω X (x i ) = 1}; -for each i ∈ {1, . . . , n}, C i r = {a i , āi , b i , bi } \ C r .
Let us show that CS is (2n, 2n + 1)-robust, i.e., for any set A ′ ⊆ A such that |A ′ | = 2n, the restriction on A ′ of CS is (2n + 1)-beneficial. From condition (i), we know that for any coalition C, if there exists i ∈ {1, . . . , n} such that {a i , āi } ⊆ C or {b i , bi } ⊆ C, then v(C) = 2n+1, so that for any coalition structure CS containing such a coalition C we would get that v(CS) ≥ 2n + 1. Yet by construction of our coalition structure CS r = {C r , C 1 r , . . . , C n r }, for every i ∈ {1, . . . , n} we have that {a i , āi } ⊆ C for some coalition C ∈ CS r and {b i , bi } ⊆ C for some coalition C ∈ CS r . And we have 4n elements in A, thus for any set

A ′ ⊆ A such that |A ′ | = 2n, in the case where {a i , āi } ⊆ A ′ or {b i , bi } ⊆ A ′ for some i ∈ {1, . . . , n}, we get that v(C ∩A ′ ) = 2n+1 for some coalition C ∈ CS r (cf. condition (i)), i.e., the restriction CS ′ r on A ′ of CS r satisfies v(CS ′ r ) ≥ 2n + 1
, and thus CS ′ r is (2n + 1)-beneficial, which makes CS r (2n, 2n + 1)-robust, that was to be shown. So consider the remaining cases and assume that A ′ is formed of exactly one element among {a i , āi } and exactly one element among {b i , bi }, for each i ∈ {1, . . . , n}. So now, for any coalition C i r ∈ CS r (i ∈ {1, . . . , n}), it can be checked by definition of C i r that C i r ∩ A ′ contains exactly one element from A. This means that none of the conditions (i), (ii), (iii) are satisfied by C ∩ A ′ , and thus v(C ∩ A ′ ) = 1 (cf. condition (iv)). To sum up, we have that v(C i r ∩ A ′ ) = 1 for each coalition C i r ∈ CS r (i ∈ {1, . . . , n}), and we need to prove that the restriction

CS ′ r of CS r on A ′ satisfies v(CS ′ r ) ≥ 2n + 1; yet v(CS ′ r ) = ∑ C∈CSr v(C ∩ A ′ ), so v(CS ′ r ) = ∑ C i r ∈CSr,i∈{1,...,n} v(C i r ∩ A ′ ) + v(C r ∩ A ′ ) = n + v(C r ∩ A ′ ).
Then we need to prove that v(C r ∩A ′ ) ≥ (2n+1)-n, i.e., we must prove that v(C r ∩A ′ ) ≥ n+1. Let us show that v(C r ∩ A ′ ) = n + 1. This is enough to show that C r ∩ A ′ satisfies condition (ii) or (iii). Let us associate with C r and A ′ the interpretation ω Y over Y defined as follows, for each i ∈ {1, . . . , n}:

in the case where

{a i , āi } ⊆ C r , then: ω Y (y i ) = 0 if a i ∈ A ′ , otherwise ω Y (y i ) = 1 (i.e., if āi ∈ A ′ ); -in the remaining case (i.e., {b i , bi } ⊆ C r ) then: ω Y (y i ) = 0 if b i ∈ A ′ , otherwise ω Y (y i ) = 1 (i.e., if bi ∈ A ′ );
We know that there is at least one clause c from α which is not satisfied by ω X ∪ ω Y . Such a clause c is of the form (x i , y j , y k ) or (y i , y j , y k ), but in any of the two cases we have that none of the literals of the clause is satisfied by ω X ∪ ω Y . It can be a literal from X (denoted x i below) or from Y (denoted y i below). Let us denote l this literal, we fall into one of the two following cases:

l is a literal x i . If x i is a positive literal, then ω X (x i ) = 0. Yet we know by definition of the coalition C r ∈ CS r that {a i , āi } ⊆ C r , and we already know that A ′ contains exactly one element from {a i , āi }, thus we get that {a i , āi } ∩ (C r ∩ A ′ ) ̸ = ∅. If x i is a negative literal, then ω X (x i ) = 1. By a similar reasoning, we get that

{b i , bi } ∩ (C r ∩ A ′ ) ̸ = ∅. Stated otherwise, we get that x(x i ) ∩ (C r ∩ A ′ ) ̸ = ∅.
l is a literal y i . If y i is a positive literal, then ω Y (y i ) = 0. Yet we know by definition of ω Y that we are in the case where ({a i , āi } ⊆ C r and

a i ∈ A ′ ) or ({b i , bi } ⊆ C r and b i ∈ A ′ ). Thus C r ∩A ′ = {a i } or C r ∩A ′ = {b i }. Hence, {a i , b i }∩(C r ∩A ′ ) ̸ = ∅. If x i is a negative literal, then ω Y (y i ) = 1.
Yet similarly by definition of ω Y we are in the case where ({a i , āi } ⊆ C r and āi

∈ A ′ ) or ({b i , bi } ⊆ C r and bi ∈ A ′ ). Thus C r ∩ A ′ = { āi } or C r ∩ A ′ = { bi }. Hence, { āi , bi } ∩ (C r ∩ A ′ ) ̸ = ∅. Stated otherwise, we get that y(y i ) ∩ (C r ∩ A ′ ) ̸ = ∅.
From these two points, we can claim for the clause c which is not satisfied by

ω X ∪ ω Y that: if c is of the form (x i , y j , y k ), then x(x i ) ∩ (C r ∩ A ′ ) ̸ = ∅, y(y j ) ∩ (C r ∩ A ′ ) ̸ = ∅ and y(y k )∩(C r ∩A ′ ) ̸ = ∅; and if c is of the form (y i , y j , y k ), then y(y i )∩(C r ∩A ′ ) ̸ = ∅, y(y j ) ∩ (C r ∩ A ′ ) ̸ = ∅ and y(y k ) ∩ (C r ∩ A ′ ) ̸ = ∅.
By definition of the characteristic function v (cf. conditions (ii) and (iii)), we get that v(C r ∩ A ′ ) = n + 1, that was left to be shown and concludes this part of the proof.

(Only if part)

We show the contraposite of the claim. Assume that there exists a coalition structure which is (2n + 1, 2n)-robust, and let us prove that the QBF ∀X∃Y.α is not valid, i.e., ∃X∀Y.¬α is satisfiable. Let us introduce a preliminary notion. For a given q ∈ {0, . . . , n}, we say that a coalition structure CS is q-normal if CS = {A} when q = 0, and if CS = {C, C 1 , . . . , C q } when q ∈ {1, . . . , n} such that:

for all i ∈ {1, . . . , q}, C i = {a i , āi } or

C i = {b i , bi }; -C = A \ ∪ {C i | C i ∈ CS, i ∈ {1, . . . , q}}.
For instance, when n = 4, the coalition structure

CS = {C, C 1 , C 2 , C 3 } defined such that C 1 = {a 1 , ā1 }, C 2 = {b 2 , b2 }, C 3 = {b 3 , b3 } and C = {b 1 , b1 , a 2 , ā2 , a 3 , ā3 , a 4 , ā4 , b 4 , b4 } is 3-normal.
What we first intend to prove is that there exists a coalition structure which is n-normal and (2n + 1, 2n)-robust. Beforehand, we want to show that for each q ∈ {1, . . . , n}, there exists a coalition structure CS which is q-normal and such that for any A ′ ⊆ A, |A ′ | = 2n, there exists a coalition C ′ ∈ CS ↓A ′ which satisfies condition (i), (ii) or (iii), where CS ↓A ′ denotes the restriction of CS on A ′ (for short, we say that CS is (i)-(ii)-(iii)-consistent in the following). So to recap, we want to show that for each q ∈ {1, . . . , n}, there exists a coalition structure CS which is q-normal and (i)-(ii)-(iii)-consistent. We prove it by recursion on q:

-Base case (q = 0): since the only 0-normal coalition structure is defined as CS 0 = {A}, it is enough to show that CS 0 is (ii)-(iii)-consistent, i.e., that for every set A ′ ⊆ A such that |A ′ | = 2n, A∩A ′ satisfies condition (ii) or (iii). Yet we know that there exists a coalition structure which is (2n + 1, 2n)-robust, so let CS r be such a coalition structure. So for every set

A ′ ⊆ A such that |A ′ | = 2n, the restriction of CS r on A ′ is (2n + 1)-beneficial. Let A ′ ⊆ A, |A ′ | = 2n
, such that for each i ∈ {1, . . . , n}, A ′ contains exactly one element among {a i , āi } and exactly one element among {b i , bi }. We can see then that no coalition from CS r↓A ′ satisfies condition (i). Let us prove there exists a coalition from CS r↓A ′ satisfying condition (ii) or (iii). Toward a contradiction, assume that there is no such coalition. Then for every coalition C ∈ CS r↓A ′ , v(C) = 1 (cf. condition (iv)). Yet there are 2n elements in A ′ , which means that v(CS r↓A ′ ) ≤ 2n (we get that v(CS r↓A ′ ) = 2n in the case where each coalition from CS r↓A ′ is a singleton set). And yet CS r is (2n+ 1, 2n)-robust, so CS r↓A ′ is (2n + 1)-beneficial, which leads to a contradiction. Hence, there exists a coalition from CS r↓A ′ satisfying condition (ii) or (iii); let C ′ be such a coalition. We know that C ′ is a coalition from CS r↓A ′ , so C ′ ⊆ A ′ . But we also have

C ′ ⊆ A, thus C ′ ⊆ A ∩ A ′ .
Hence, since C ′ satisfies condition (ii) or (iii), it is easy to see that A ∩ A ′ satisfies condition (ii) or (iii) as well. Therefore, CS 0 is (i)-(ii)-(iii)-consistent. -Recursion step: let CS q = {C, C 1 , . . . , C q } be a q-normal coalition structure for some q ∈ {0, . . . , n -1} (CS 0 = {A}), and assume that CS q is (i)-(ii)-(iii)consistent. Let us prove that there exists a coalition structure CS q+1 which is (q + 1)-normal and (i)-(ii)-(iii)-consistent. Let us associate with

CS q = {C, C 1 , . . . , C q } the coalition structure CS q+1 a = {C a , C 1 , . . . , C q , C q+1 a } where C a = C \ {a q+1 , āq+1 } and C q+1 a = {a q+1 , āq+1 }; similarly, we associate with CS q = {C, C 1 , . . . , C q } the coalition structure CS q+1 b = {C b , C 1 , . . . , C q , C q+1 b } where C b = C \ {b q+1 , bq+1 } and C q+1 b = {b q+1 , bq+1 }.
It is easy to verify that CS q+1 a and CS q+1 b are well-defined coalitions structures, and that both of them are (q + 1)-normal. So this is enough to show that one of these coalitions is (i)-(ii)-(iii)consistent. Since CS q is either (i)-(ii)-(iii)-consistent, for any A ′ ⊆ A, |A ′ | = 2n, there exists a coalition C ′ ∈ CS q ↓A ′ which satisfies condition (i), (ii) or (iii). So let A ′ ⊆ A, |A ′ | = 2n, and let C ′ ∈ CS q ↓A ′ , we know that C ′ satisfies condition (i), (ii) or (iii). Yet by construction of CS q+1 a and CS q+1 b it is easy to see that if C ′ satisfies condition (i) (resp. condition (ii)), then both CS q+1 a↓A ′ and CS q+1 b↓A ′ contain a coalition which satisfies condition (i) (resp. condition (ii)). So assume that C ′ does not satisfy condition (i) nor (ii), so that C ′ satisfies condition (iii). But then, it is easy to verify that one of the two following cases holds: (1) for every

A ′′ ⊆ A, |A ′′ | = 2n, CS q+1
a↓A ′′ contains a coalition which satisfies condition (iii), or (2) for every

A ′′ ⊆ A, |A ′′ | = 2n, CS q+1
b↓A ′′ contains a coalition which satisfies condition (iii). Overall, we have shown that either

CS q+1 a or CS q+1 b is (i)-(ii)-(iii)-consistent.
We have now proved that there exists a coalition structure CS = {C, C 1 , . . . , C n } which is n-normal and such that for any A ′ ⊆ A, |A ′ | = 2n, there exists a coalition C ′ ∈ CS ↓A ′ which satisfies condition (i), (ii) or (iii). Let us show that such a coalition structure CS is (2n, 2n + 1)-robust. Let A ′ ⊆ A, |A| = 2n and let us show that CS ↓A ′ is (2n + 1)-beneficial. Let C ′ ∈ CS ↓A ′ . Assume first that C ′ satisfies condition (i), then one can see that v(C ′ ) = 2n + 1 and thus CS ↓A ′ is (2n + 1)-beneficial. So assume that C ′ does not satisfiy condition (i), i.e., C ′ satisfies condition (ii) or (iii). Note that in this case (because C ′ does not satisfy condition (i)), we know that A ′ contains exactly one element from {a i , āi } and exactly one element from {b i , bi }, for each i ∈ {1, . . . , n}. Then for each coalition C i ∈ CS, i ∈ {1, . . . , n}, we get that C i ∩ A ′ is a singleton set and C i satisfies none of the conditions (ii) and (iii), and thus v(

C i ∩ A ′ ) = 1 (condition (iv)). We have have that v(CS ↓A ′ ) = v(C ∩ A ′ ) + v(C 1 ∩ A ′ ) + • • • + v(C n ∩ A ′ ) = v(C ∩A ′ )+n = v(C ′ )+n = (n+1)+n = 2n+1. Hence, CS ↓A ′ is (2n+1)-beneficial.
We have proved that there exists a coalition structure which is n-normal and (2n, 2n+ 1)-robust, denote it CS r = {C r , C 1 r , . . . , C n r }. Now, it remains to show that the QBF ∃X∀Y.¬α is valid. Let us associate with CS r the interpretation ω X over X defined for each i ∈ {1, . . . , n} as ω

X (x i ) = 0 if C i r = {b i , bi }, otherwise ω X (x i ) = 1
(in the remaining case where C i = {a i , āi }). Now, let ω Y be any interpretation over Y . It remains to show that ω X ∪ω Y does not satisfy α, i.e., there exists a clause from α which is not satisfied by ω X ∪ω Y . With ω Y we associate the set A ′ ⊆ A characterized as follows:

for each i ∈ {1, . . . , n}, {a i , b i } ⊆ A ′ and { āi , bi } ∩ A ′ = ∅ if ω Y (y i ) = 0, otherwise { āi , bi } ⊆ A ′ and {a i , b i } ∩ A ′ = ∅.
Note that for each i ∈ {1, . . . , n}, A ′ contains exactly one element among {a i , āi } and exactly one element among {b i , bi }. This means that for each i ∈ {1, . . . , n}, C i r ∩ A ′ is a singleton set and thus v(

C i r ∩ A ′ ) = 1 (condition (iv)). So v(CS r↓A ′ ) = v(C r ∩ A ′ ) + v(C 1 r ∩ A ′ ) + • • • + v(C n r ∩ A ′ ) = v(C r ∩ A ′ ) + n. Yet CS r is (2n, 2n + 1)-robust, so that v(CS r↓A ′ ) ≥ 2n + 1, and thus v(C r ∩ A ′ ) ≥ n + 1, which means that C r ∩ A ′ satisfies condition (i), (ii) or (iii).
But by construction of A ′ , one can see that C r ∩ A ′ does not satisfy condition (i), so it satisfies condition (ii). We will show that the clause that enables condition (ii) to be satisfied, is not satisfied by ω X ∪ ω Y . Let p q be a literal from a clause from condition (ii):

-Assume first that p q = x l for some l ∈ {1, . . . , n}.

• If x l is a positive literal, then we know that p(p

q ) = x(x l ) = {a l , āl }. Since {a l , āl } ∩ C r ∩ A ′ ̸ = ∅, it follows that C l r = {b l , bl }. But then ω X (x l ) = 0. • If x l
is a negative literal, we analogously conclude that ω X (x l ) = 1. In both cases ω X does not satisfy the clause when p q = x l for some l ∈ {1, . . . , n}.

-So assume now the remaining case holds, i.e., that p q = y m for some m ∈ {1, . . . , n}.

• If y m is a positive literal, then p(p q ) = y(y m ) = {a m , b m }. Since {a m , b m } ∩ C r ∩ A ′ ̸ = ∅, we can conclude that {a m , b m } ⊆ A ′ and thus ω Y (y m ) = 0. • If y m is a negative literal, we analogously conclude that ω Y (y m ) = 1.
In both cases ω Y does not satisfy the clause when p q = y m for some m ∈ {1, . . . , n}.

We have just shown that the QBF ∃X∀Y.¬α is valid, which concludes this part of the proof.

We have shown that the QBF ∀X∃Y.α is valid if and only if there does not exist a coalition structure CS which is (2n + 1, 2n)-robust, which means that the complementary problem RCSG is Π p 2 -hard. Therefore, RCSG is Σ p 2 -hard.

⊓ ⊔

Beyond the decision problem of RCSG, the following optimization problem could be considered: one sets a robustness threshold k and intend to optimize the beneficialness of the coalition structure; or one sets a beneficialness threshold u and intend to optimize the robustness of the coalition structure. We can also view the RCSG problem as a bi-objective constraint optimization problem, and be interested in computing Pareto optimal (i.e., non-dominated) coalition structures.

The AmorCSG algorithm

We now describe AmorCSG, our complete algorithm to compute the coalition structure of maximum beneficialness. The algorithm is based on the integer-partitioning (IP) approach [START_REF] Michalak | A hybrid exact algorithm for complete set partitioning[END_REF][START_REF] Rahwan | An anytime algorithm for optimal coalition structure generation[END_REF]. We briefly describe the IP-approach and refer to the original works [START_REF] Michalak | A hybrid exact algorithm for complete set partitioning[END_REF][START_REF] Rahwan | An anytime algorithm for optimal coalition structure generation[END_REF] for more details. It starts by decomposing the search space into disjoint parts (integer partitions) and applies branch-and-bound to each subspace. Every integer partition of n (the number of agents) defines a subspace by associating the integers in the partition to the number of agents in each coalition (e.g. 1 + 3 is a subspace with two coalitions with one and three agents). Note that the integer partitions generated by n are non-overlapping. The main advantage of the decomposition is that effective upper bounds can be calculated for partial solutions from a particular partition, which is an essential for pruning the search space in the branch-and-bound algorithm. Our algorithm follows the same structure as the IP algorithm, with the addition of the following important components: calculation of the robustness for coalitions and coalition structures, robust upper bounds, and our pruning technique for branch-and-bound. These are described in detail below. The pseudo-code of AmorCSG is given in Algorithm 1 and 2. We considered extending other state-of-the-art CSG algorithms for RCSG namely ODP [START_REF] Michalak | A hybrid exact algorithm for complete set partitioning[END_REF], ODP-IP [START_REF] Michalak | A hybrid exact algorithm for complete set partitioning[END_REF], and inclusion-exclusion DP [START_REF] Björklund | Set partitioning via inclusion-exclusion[END_REF]. However, these approaches are not applicable to RCSG, as they are based on dynamic programming and the Bellman property does not hold for RCSG. Our method uses dynamic programming during its execution but the core part of the algorithm is branch-and-bound.

Definition 6 (Robustness of a Coalition (Structure)). Let CSG = ⟨A, v⟩ be a CSG problem description. For a given coalition structure CS on A and non-negative integer k, the k-robustness of CS, denoted r(CS, k), is the maximal value u such that CS is (u, k)-robust. Similarly, the k-robustness of a coalition C, denoted r(C, k), is the maximal value u if the coalition structure {{C}} is (u, k)-robust.

Robustness Values For Each Coalition

For every coalition C we calculate r(C, k ′ ) for each k ′ ∈ [1, min(k, |C|)] as a preprocessing step, which represents the lowest beneficial value obtainable after removing k ′ agents from C. We compute r(C, k ′ ) using a dynamic programming:

r(C, 0) = v(C), (1) r(C, k ′ ) = min C ′ ⊂C |C ′ |=|C|-1 (r(C ′ , k ′ -1)), ∀k ′ ∈ [1, min(k, |C|)].
Robustness Values For a Particular Coalition Structure For a given coalition structure CS we compute its robust value as r(CS, k) = V (CS)-e(CS, k), where e(CS, k) is defined as the optimal value of the following multidimensional knapsack problem:

e(CS, k) = max ∑ C∈CS ∑ j∈[1,|C|] r(C, j) * x (C,j) (2)
∑ C∈CS ∑ j∈[1,|C|] j * x (C,j) ≤ k (3) ∑ j∈[1,|C|] x (C,j) ≤ 1 ∀C ∈ CS (4) x (C,j) ∈ {0, 1} ∀C ∈ CS, j ∈ [1, |C|] (5)
The value e(CS, k) denotes the maximum penalty that can be achieved by removing k agents. The variables x (C,j) indicates if j agents are selected for removal from coalition C.

Robust Upper Bounds For a given subspace generated by the partition I = [I 0 , I 1 , . . . , I m-1 ] we compute the upper bound as:

U B rob (I) = max ∑ j y j ≤k y j ∈N 0 ( ∑ j∈[0,m) (U B(max(0, I j -y j )))) (6)
In other words, we calculate maximum upper bound of all subspaces that can be generated by removing at most k agents from the subspace I. The upper bound of a partition I, UB(I), is computed as in the integer-partition approach [START_REF] Michalak | A hybrid exact algorithm for complete set partitioning[END_REF][START_REF] Rahwan | An anytime algorithm for optimal coalition structure generation[END_REF].

Branch-And-Bound Pruning The partial solution CS can be pruned if it cannot be extended to a solution with a higher beneficial value than the best solution found so far (denoted LB best ). This is determined based on the upper bounds of the unassigned coalitions and LB best :

r(CS, k) + ∑ j∈[d+1,m) (U B(I i )) ≤ LB best (7)
The solution CS can be pruned from the search if the above equation holds. Note that the (partial) solution CS has its first d coalitions assigned at search tree depth d.

Incremental Computation of r(CS, k)

The robust value r(CS, k) is computed in each iteration incrementally using dynamic programming. Let c be the coalition that is added to the partial solution CS, we then have:

r(CS ∪ c, k) = min{r(CS, k -i) + r(c, i)|i ∈ [0, k]} (8) 14
(1) number of agents computation time (in seconds) k=3 k=2 k=1 k=0 (f) Beta Fig. 1: Average runtime (five benchmarks for each n, the number of agents) on a variety of distributions with different values for k. Number of timeouts with a limit of 1 hours shown in brackets.

Experimental Evaluation

We implemented AmorCSG and the integer-partition approach for CSG [START_REF] Michalak | A hybrid exact algorithm for complete set partitioning[END_REF][START_REF] Rahwan | An anytime algorithm for optimal coalition structure generation[END_REF] in C++. The experiments were run on an Intel i7-7700HQ CPU @ 2.80GHz with 32 GB of RAM. We experimented with instances based on several probability distributions for the characteristic function v used in the literature:

-Uniform: v(C) = U nif orm(0, |C|) [START_REF] Larson | Anytime coalition structure generation: an average case study[END_REF]. The benchmarks were adjusted to ensure monotonicity. We compared the runtime for different values of n (number of agents) and k ∈ [0, 3] (robustness parameter). Note that RCSG with k = 0 degenerates to CSG. The results are summarized in Figure 1, averaged over five instances for each n.

The distribution used plays an important role in the execution time, more so than for standard CSG (k = 0). The main reason is that bounds on robustness cannot be approximated as accurately in general and this is further amplified for certain distributions. Furthermore, the strength of the robust bounds weakens with the increase in k. Hence, the algorithm must explicitly explore a large part of the search space, leading to higher run times when compared to CSG. In return, guarantees on robustness are provided.

Conclusion

In this paper, the robustness issue for CSG has been investigated. The contributions of this paper are as follows: A notion of robustness in the CSG framework has been formalized and shown useful. Furthermore, the corresponding decision and (bi-objective) optimization problems for RCSG have been studied and the computational complexity has been identified. Finally. a complete algorithm has been presented for solving a RCSG problem.

This work paves the way for a number of perspectives. Our complete algorithm (AmorCSG) can solve RCSG problem instances such as waste-water treatment system. For addressing large-scale RCSG instances, we plan to develop approximate algorithms. Another perspective will consist in considering the robustness issue in a probabilistic setting. In the framework presented in this paper, the robustness of a coalition structure is evaluated from the "worst-case" viewpoint. Another approach would be to consider each agent as "reliable" to a certain extent, e.g., by associating with each agent a i a value α(a i ) ∈ [0, 1] standing for the probability that the agent may remain in its coalition at the next step. Obviously enough, this probabilistic setting departs from the one we proposed here. Lastly, we plan to extend our framework to a dynamic setting in which the set of agents A may change w.r.t. time, with the objective to apply it to a distributed robot team reconfiguration problem [START_REF] Dasgupta | Robust multi-robot team formations using weighted voting games[END_REF].

Algorithm 1 : 2 CS 3 CS 4 Ci ←-∅, ∀i 5 while depth ≥ 0 do 6 if depth = m then 7 depth ←-depth - 1 8 12 C 17 depth ←-depth + 1 18 return CS best Algorithm 2 : 2 IP 3 U 6 4 5 do 6 foreach I ∈ IP do 7 if 11 Inext

 1234567112171223656711 Branch-And-Bound Subspace Search input: CSG, I = [I0, .., Im-1], k output: CS in subspace I with the highest r(CS, k)1 begin best ←-∅; LB best ←--∞; depth ←-0 ←-[C0, C1, .., Cm-1] if r(CS, k) > LB best then 9 LB best ←-r(CS, k) 10 CS best ←-CS 11 else depth ←-select next coalition not explored // if no new C depth possible, backtrack 13 if C depth = ∅ then 14 depth ←-depth -1 15 continue 16 if r(CS, k) + ∑ depth<j<m U B(Ij) > LB best then AmorCSG Algorithm Outline input: CSG = ⟨A, v⟩, k output: CS * = argmaxCS(r(CS, k)) 1 begin ←-generate integer partitions of |A| B rob ←-computeRobustU pperBounds(IP ) // Eq. LB best ←--∞; CS * ←-∅ U B rob (I) ≤ LB best then 8 IP ←-IP \ {I}9 if IP = ∅ then 10 break ←-argmax{U B rob (I) : I ∈ IP } 12 (val, CS) ←-searchSubspace(CSG, I, k) // Algorithm 1 13 if val ≥ LB best then 14 LB best ←-val 15 CS * ←-CS 16 while IP ̸ = ∅ 17 return CS *

-

  Normal: v(C) = N ormal(µ = 10 * |C|, σ 2 = 0.1) [16]. -NDCS: v(C) = N ormal(µ = |C|, σ 2 = √ |C|) [17]. -Modified uniform: v(C) = U niform(0, 10 * |C|)+a, where a = U nif orm(0, 50) with probability 0.2 and a = 0 otherwise [21]. -Modified normal: v(C) = N ormal(10 * |C|, 0.01) + a, where a is as above [15]. -Beta: v(C) = |C| * Beta(α = β = 0.5)[10].

  hardness holds even if the characteristic function satisfies monotonicity.Proof. Let us first prove that RCSG is in Σ p 2 . Let CSG = ⟨A, v⟩ be a CSG problem description such that A = {a 1 , . . . , a n }, and u and k be two non-negative integers. Consider the following non-deterministic polynomial algorithm with NP oracle:1. Guess a set CS = {C 1 , . . . , C m } of coalitions from A; 2. Check that CS is a coalition structure on A; 3. Check using an NP oracle that there does not exist a set of agents A ′ ⊆ A such that |A ′ | = n -k and such that the restriction of CS on A ′ is not u-beneficial. -hardness holds for RCSG by consider a reduction in polynomial time to the complementary problem of RCSG from the following Π p 2 -hard problem, that is, the validity problem for 3-CNF quantified boolean formulas (QBFs) of the form ∀X∃Y.α where X = {x 1 , . . . , x n } and Y = {y 1 , . . . , y n } are two disjoint sets of propositional atoms and α is 3-CNF propositional formula such that V ar(α) = X ∪ Y . Consider such a QBF ∀X∃Y.α, and let us associate with it an RCSG problem description ⟨A, v⟩, where A is the set of agents A = {a 1 , ā1 , b 1 , b1 , . . . , a n , ān , b n , bn }, and v is a characteristic function v : 2 A → N given as follows. Let us first define:

	This algorithm decides RCSG, showing that RCSG is in Σ p 2 . We prove that Σ p 2

Note that the property of monotonicity differs from the super-additivity which requires that for all coalitions C, C ′ , it holds v(C) + v(C ′ ) ≤ v(C ∪ C ′ ) and is stronger than monotonicity.