On social media, it is easy to see how people are connected and find the leader, or mastermind of a network. The mastermind is responsible for the planning of the activities in the network. Hiding the mastermind is important to carry out these activities. This raises the question for the mastermind: How effectively can the mastermind hide his connections to avoid being found? We propose an efficient heuristic algorithm called HERMES (Hide Exposures by Removing Mastermind’s External Sources) to address this. Experiments on Facebook and Google networks show that HERMES hides the mastermind more effectively than the state-of-the-art, achieving time gains of 103 and 1397 seconds, respectively, and improving influence value by up to 11.11%.

International audience

Simultaneous Coalition Structure Generation and Assignment (SCSGA) is an important research problem in multi-agent systems. Given n agents and m tasks, the aim of SCSGA is to form m disjoint coalitions of n agents such that between the coalitions and tasks there is a one-to-one mapping, which ensures each coalition is capable of accomplishing the assigned task. SCSGA with Multi-dimensional Features (SCSGA-MF) extends the problem by introducing a d-dimensional vector for each agent and task. We propose a heuristic algorithm called Multiple Distance Metric (MDM) approach to solve SCSGA-MF. Experimental results confirm that MDM produces near optimal solutions, while being feasible for large-scale inputs within a reasonable time frame.

In this paper, we propose a novel algorithm to address the Coalition Structure Generation (CSG) problem. Specifically, we use a novel representation of the search space that enables it to be explored in a new way. We introduce an index-based exact algorithm. Our algorithm is anytime, produces optimal solutions, and can be run on large-scale problems with hundreds of agents. Our experimental evaluation on a benchmark with several value distributions shows that our representation of the search space that we combined with the proposed algorithm provides high-quality results for the CSG problem and outperforms existing state-of-the-art algorithms.

Organizing agents into disjoint groups is a crucial challenge in artificial intelligence, with many applications where quick runtime is essential. The Simultaneous Coalition Structure Generation and Assignment (SCSGA) problem involves partitioning a set of agents into coalitions and assigning each coalition to a task, with the goal of maximizing social welfare. However, this is an NP-complete problem, and only a few algorithms have been proposed to address it for both small and large-scale problems. In this paper, we address this challenge by presenting a novel algorithm that can efficiently solve both small and large instances of this problem. Our method is based on a new search space representation, where each coalition is codified by an index. We have developed an algorithm that can explore this solution space effectively by generating index vectors that represent coalition structures. The resulting algorithm is anytime and can scale to large problems with hundreds or thousands of agents. We evaluated our algorithm on a range of value distributions and compared its performance against state-of-the-art algorithms. Our experimental results demonstrate that our algorithm outperforms existing methods in solving the SCSGA problem, providing high-quality solutions for a wide range of problem instances.

Coalition formation is a central approach for multiagent coordination. A crucial part of coalition formation that is extensively studied in AI is coalition structure generation: partitioning agents into coalitions to maximize overall value. In this paper, we propose a novel method for coalition structure generation by introducing a compact and efficient representation of coalition structures. Our representation partitions the solution space into smaller, more manageable subspaces that gather structures containing coalitions of specific sizes. Our proposed method combines two new algorithms, one which leverages our compact representation and a branch-and-bound technique to generate optimal coalition structures, and another that utilizes a preprocessing phase to identify the most promising sets of coalitions to evaluate. Additionally, we show how parts of the solution space can be gathered into groups to avoid their redundant evaluation and we investigate the computational gain that is achieved by avoiding that redundant processing. Through this approach, our algorithm is able to prune the solution space more efficiently. Our results show that the proposed algorithm is superior to prior state-of-the-art methods in generating optimal coalition structures under several value distributions.

Coalition formation with task dependencies has been the focus of few of the literature on multi-agent coalition formation. In contrast, very little attention has been given to the case where each agent has several alternative sets of tasks leading it to its goal satisfaction. The task dependencies impact the feasibility of the coalitions depending on the considered tasks alternative at a given time. Hence, the performance of a single task, whether by coalition formation (group of agents) or by a single performance, could affect the feasibility of other coalitions in the system. However, these task dependencies play a crucial role in many real-world multi-agent applications. Against this background, we consider in this paper multiple self-interested agents each of which has a goal it needs to achieve by performing a set of tasks. Each agent has several alternative sets of tasks leading it to its goal satisfaction. The tasks in an alternative exhibit dependencies and require sequential execution. So, to jointly achieve goals, the agents may form interdependent coalitions. We introduce a new algorithm that we call the Selective Exploration Algorithm (SEA) for coalition formation that accounts for the task dependencies to consider only feasible coalitions and reduce the size of the search space to explore and identify the optimal coalition structure.

Coalition Formation (CF) aims at finding the opti-mal coalition structure that maximizes social welfare. However, the search space of coalition structures is often too large to be fully explored. In this paper, we propose a novel algorithm to address the Coalition Structure Generation (CSG) problem. Specifically, we use a novel representation of the search space that enables it to be explored in a new way. We introduce an index-based exact algorithm. Our algorithm is anytime, produces optimal solutions, and can be run on large-scale problems with hundreds of agents. Our experimental evaluation on a benchmark with several value distributions and an electric vehicle allocation problem shows that our representation of the search space that we combined with the proposed algorithm provides high-quality results for the CSG problem and outperforms existing state-of-the-art algorlthms.

Coalition structure generation, i.e., the problem of optimally partitioning a set of agents into disjoint exhaustive coalitions to maximize social welfare, is a fundamental computational problem in multi-agent systems. In this paper, we provide a new algorithm for optimal coalition structure generation. We analyze how parts of the solution space can be searched individually with guarantees of fully searching them. We introduce a new algorithm that searches the entire solution space using dynamic programming with a branch-and-bound technique both focused on solution subspaces. With experiments over several common value distributions, we show that dividing the search process enables our algorithm to rapidly search the solution subspaces and outperform current state-of-the-art for several value distributions.

High-speed highway on-ramp merging is a significant challenge toward realizing fully automated driving (level 4). Connected Autonomous Vehicles (CAVs), that combine communication and autonomous driving technologies, may improve greatly the safety performances when performing highway on-ramp merging. However, even with the emergence ofCAVs, some keys constraints should be considered to achieve a safe on-ramp merging. First, human-driven vehicles will still be present on the road, and it may take decades before all the commercialized vehicles will be fully autonomous and connected. Also, onboard vehicle sensors may provide inaccurate or incomplete data due to sensors limitations and blind spots, especially in such critical situations. To resolve these issues, the present work introduces a novel solution that uses an off-board Road-Side Unit (RSU) to realize fully automated highway on-ramp merging for connected and automated vehicles. Our proposed approach is based on an Artificial Neural Network (ANN) to predict drivers’ intentions. This prediction is used as an input state to a Deep Reinforcement Learning (DRL) agent that outputs the longitudinal acceleration for the merging vehicle. To achieve this, we first propose a data-driven model that can predict the behavior of the human-driven vehicles in the main highway lane, with99% accuracy. We use the output of this model as input state to train a Twin Delayed Deep Deterministic Policy Gradients (TD3) agent that learns “safe” and “cooperative” driving policy to perform highway on-ramp merging. We show that our proposed decision-making strategy improves performance compared to the solutions proposed previously.

In this paper, we focus on the Coalition Structure Generation (CSG) problem, which involves finding exhaustive and disjoint partitions of agents such that the efficiency of the entire system is optimized. We propose an efficient hybrid algorithm for optimal coalition structure generation called BOSS. When compared to the state-of-the-art, BOSS is shown to perform better by up to 33.63% on benchmark inputs. The maximum time gain by BOSS is 3392 seconds for 27 agents.

High-speed highway on-ramp merging is one of the most difficult and critical tasks for any autonomous driving system. This work studies this problem by combining deep deterministic policy gradient (DDPG) reinforcement learning with drivers’ intentions prediction. Our proposed solution is based on an artificial neural network to predict drivers’ intentions, used as an input state to the DDPG agent that outputs the longitudinal acceleration to the merging vehicle. We show that this solution improves safety performances.

In this paper, we propose a new algorithm for the Coalition Structure Generation (CSG) problem that can be run with more than 28 agents while using a complete set of coalitions as input. The current state-of-the-art limit for exact algorithms to solve the CSG problem within a reasonable time is 27 agents. Our algorithm uses a novel representation of the search space and a new code-based search technique. We propose an effective heuristic search method to efficiently explore the space of coalition structures using our code based technique and show that our method outperforms existing state-of-the-art algorithms by multiple orders of magnitude.

International audience

Finding the optimal coalition structure is an NP-complete problem that is computationally challenging even under quite restrictive assumptions. In this paper, we propose a new algorithm for the Coalition Structure Generation (CSG) problem, which provides good enough quality solutions and that can be run with hundreds of agents. The Fast code-based Algorithm for Coalition Structure generation (FACS) uses a novel representation of the search space of coalition structures and a new code-based search technique. We devise an effective heuristic search method to efficiently explore the space of coalition structures using our code-based technique. Results show that our method outperforms existing state-of-the-art algorithms by multiple orders of magnitude while providing high-quality solutions.

Coalition Structure Generation (CSG) is an NP-complete problem that remains difficult to solve on account of its complexity. In this paper, we propose an efficient hybrid algorithm for optimal coalition structure generation called ODSS. ODSS is a hybrid version of two previously established algorithms IDP (Rahwan and Jennings 2008) and IP (Rahwan et al. 2009). ODSS minimizes the overlapping between IDP and IP by dividing the whole search space of CSG into two disjoint sets of subspaces and proposes a novel subspace shrinking technique to reduce the size of the subspace searched by IP with the help of IDP. When compared to the state-of-the-art against a wide variety of value distributions, ODSS is shown to perform better by up to 54.15% on benchmark inputs.

This paper proposes a new approach for predicting drivers' intentions in a Highway on-ramp merge situation using a central road side unit (RSU) with probabilistic classifiers.

International audience

This work explores the design of a central collaborative driving strategy between connected cars with the objective of improving road safety in case of highway on-ramp merging scenario. Based on a suitable method for predicting vehicle motion and behavior for a central collaborative strategy, a dynamic Bayesian network method that predicts the intention of drivers in highway on-ramp is proposed. The method was validated using real data of detailed vehicle trajectories on a segment of interstate 80 in Emeryville, California.

Optimal Coalition Structure Generation (CSG) is a significant research problem that remains difficult to solve. Given n agents, the ODP-IP algorithm (Michalak et al. 2016) achieves the current lowest worst-case time complexity of O(3n). We devise an Imperfect Dynamic Programming (ImDP) algorithm for CSG with runtime O(n2n). Imperfect algorithm means that there are some contrived inputs for which the algorithm fails to give the optimal result. Experimental results confirmed that ImDP algorithm performance is better for several data distribution, and for some it improves dramatically ODP-IP. For example, given 27 agents, with ImDP for agentbased uniform distribution time gain is 91% (i.e. 49 minutes).

International audience

Coalition formation is one of the most studied topics in multi-agent systems. Central to this endeavor is the problem of partitioning the set of agents into exhaustive and disjoint coalitions so as to maximize social welfare. The coalition structure generation problem is challenging due to the fact that it needs to explore an exponential number of partitions. The fastest exact algorithm to solve this combinatorial optimization problem is ODP-IP [1], which is a hybrid version of two previously established algorithms, namely IDP (Improved Dynamic Programming [2] and IP [3]. Given this, it is desirable to come up with a new algorithm which could build on the same principles as IDP follows and which in turn, improves upon the state. In this paper, we propose a new algorithm EDP (Effective Dynamic Programming). This algorithm is a new design paradigm for this difficult problem. Both EDP and IDP have been implemented and tested on well-known data distribution. We prove that EDP is practically faster than IDP.

The Coalition Structure Generation (CSG) problem is a partitioning of a set of agents into exhaustive and disjoint coalitions to maximize social welfare. This NP-complete problem arises in many practical scenarios. Prominent examples are included in the field of transportation, e-Commerce, distributed sensor networks, and others. The fastest exact algorithm to solve the CSG problem is ODP-IP, which is a hybrid version of two previously established algorithms, namely Improved Dynamic Programming (IDP) and IP. In this paper, we show that the ODP-IP algorithm performs many redundant operations. To improve ODP-IP, we propose a faster abortion mechanism to speed up IP’s search. Our abortion mechanism decides at runtime which of the IP's operations are redundant to skip them. Then, we propose a modified version of IDP (named MIDP) and an improved version of IP (named IIP). Based on these two improved algorithms, we develop a hybrid version (MIDP-IIP) to solve the CSG problem. After a detailed description of the new algorithm MIDP-IIP, an experimental comparison is conducted against ODP-IP. Our analysis shows that MIDP-IIP performs fewer operations than ODP-IP. In addition, MIDP-IIP reduced significantly many problem instances running times (11% to 37 %), and improved drastically some of them.

Traffic congestion has a significant impact on quality of life and the economy. This paper presents a decentralised traffic management mechanism for intersections using a distributed constraint optimisation approach (DCOP). Our solution outperforms the state of the art solution both for stable traffic conditions (about 60% reduced waiting time) and robustness to unpredictable events.

Collective decision-making is a process in which participants make a collective choice from several alternatives. In this paper, we focus on collective decision contexts in which more than two selfish agents negotiate over multiple issues. We specifically consider a case of joint household energy purchase where the concerned households have to define a collective energy contract. The households involved may each be interested only in a subset of the issues at stake. We devise an effective protocol to regulate the interactions among the (household) agents and reduce their reasoning complexity. The mechanism we introduce is fully decentralized, it facilitates multi-lateral negotiation, and it reduces the complexity of the solution despite the inherent complexity of the problem.

To make buses more attractive to users, transportation services aim to assure their efficiency and reliability, but these are subjected to traffic conditions. To do that, it is possible to grant them priority at traffic lights, but this solution is not efficient. In a dense traffic context, priority is not enough since it may lead buses to congestion. The spread of communication technologies in vehicles and personal devices enables new solutions. Regulation mechanisms based on real-time information are possible and allow intersections to apply a fine regulation policy with no traffic lights needed. We develop a distributed coordination-based mechanism using a constraint-based model allowing buses to reserve the right-of-way on their trajectory. With this mechanism, each intersection on this trajectory adapts its regulation policy in order to provide a clear path for the bus, allowing it to reach the bus stops in time. The policy of an intersection is based on a bi-level coordination model with the vehicles.

Future smart grids will empower home owners to buy energy from real-time markets, coalesce into energy cooperatives, and sell energy they generate from their local renewable energy sources. Such interactions by large numbers of small prosumers (that both consume and produce) will engender potentially unpredictable fluctuations in energy prices which could be detrimental to all actors in the system. Hence, in this paper, we propose negotiation mechanisms to orchestrate such interactions as well as pricing mechanisms to help stabilise energy prices on multiple time scales. We then prove 1) that our solution guarantees that, while prices fluctuations can be constrained, 2) that it is individually rational for agents to join energy cooperatives and 3) that the negotiation mechanisms we employ result in pareto-optimal solutions.

Negotiation is a fundamental mechanism in multi-agent systems. It may be a complex mechanism involving multiple agents with conflicting interests that need to reach a joint agreement. Complexity intensifies when moving from bilateral to multilateral negotiation. An important issue in such negotiation is to define a specific and effective protocol that guides the interactions between the agents. In this paper, we propose a novel, fully decentralized mechanism for multilateral negotiation, that reduces the inherent complexity of the problem. We specifically reduce the complexity of searching in the agreement search space, utilizing the divide and conquer approach. The proposed negotiation mechanism structures the negotiation by dividing a set of agents into several groups. Proposals are initially exchanged only within groups, and only later across groups. This structure is enhanced with various interaction policies. These policies include rules that determine permissible behaviors of the agents within the structure. Via structure and policies our negotiation protocol controls the negotiation time and facilitates feasible multi-lateral negotiation. We provide theoretical and experimental results showing the efficiency of our protocol.

Contract Net Protocol (CNP) is probably the most widely used task allocation protocol in distributed multi-agent systems (MAS). To cope with real-world applications, this protocol must be expanded by addressing some major challenging issues in the current distributed systems. Temporal interaction aspects and reliability issues of such systems, critical to guaranteeing performance, are the focus of this paper. Many researchers have proposed various methods to expand and to improve CNP but those challenges have not been much addressed in a formal way. To cope with these limitations, this paper proposes a Petri net-based model that extends the conventional contract net with real time constraints, often defined as interaction duration and message deadlines, and fault tolerance to handle the agent death exception. Our aim is, hence, to devise an extended CNP that achieves the reliability of the manager agent in the case of contractor crash failure while operating in an open and large scale multi-agent system under time constraints. To address the challenge problem of crash failure detection of the contractor in CNP, we propose to formally model the watchdog/heartbeat mechanism into the communication between the manager and the contractor. Using such mechanism, the manager can detect the crash failure on time and may hence trigger an appropriate recovery procedure to move the system into a safe and a consistent state. The proposed extended CNP model is developed using stochastic timed colored Petri nets which include systematic specification, design and implementation of components of the system. Various useful results will be drawn by simulation as well as state space analysis. This formal analysis shows that the protocol terminates correctly either in a safety case or in a failure situation. It also proves that the protocol meets the key properties namely model correctness, deadline respect, absence of deadlocks and livelocks, absence of dead code, agent terminal states consistency, concurrency, and validity.

We address the problem of efficient coordination protocols in the contexts where mobile and ad-hoc devices which harbor the selfish agents must achieve a set of dynamic tasks. This work assumes that, due to the dynamic behaviors of the agents induced by the unpredictable availability of these devices and the dynamic of the tasks, it is not possible to devise an efficient coordination which uses prior knowledge about the information of the agents ahead of task achievements. In these contexts, we provide both protocols called depth exploration protocol and width exploration protocol which are based on the formalism of the MDP (Markov Decision Process) and on alliance principle. The aim of our protocols is to ensure and to adapt dynamically the stability of the agent's coordination teams (coalitions) which take into account the agent's withdrawal and the dynamic evolving of the tasks. We develop a theoretical study of our mechanism and we provide an analytical and experimental performance evaluation.

In this paper we are interested in solving the problems of continuity of service using a Multiagent System (MAS) deployed on Mobile Ad-Hoc Networks (MANETs). We investigate the aspects of mobility and the losses it costs in terms of continuity of service. The aim of this research is the development of agents' coordination protocols for these highly dynamic environments like MANETs. One of the difficulties in MANETs is the spontaneous mobility of nodes, especially when devices with limited resources are used. All the constraints of agents' development thus have to be re-examined in order to be adapted to these situations. In this paper, we propose two protocols Pessimistic Ad-hoc Coordination Protocol (PACP) and Optimistic Ad-hoc Coordination Protocol (OACP)) to provide coordination amongst the agents. In our considered ad-hoc scenario, the nodes represent the chargers and the wheelchairs upon which the intelligent agents are deployed. These protocols have been evaluated and tested using this scenario.

In this article, we address the problem of coalition formation in multiagent systems. Our work focuses on the class of hedonic games, where the satisfaction of each agent depends on other agents taking part in the coalition. We present in this paper some strategies, which could be used by agents. We describe two types of strategies: proposal acceptance strategies, which allow agents to accept or reject a coalition formation proposal and proposal selection strategies based on the analysis of the history of a negotiation, which allow agents to select interesting coalitions to propose. We underline that a compromise between high and low selectivity allows agents to obtain a higher probability to form coalitions with a satisfying utility. Our proposal selection strategies allow agents to reduce the number of proposals to send during the coalition formation process without losing much utility. This speeds up considerably the process.

In a multiagent system, coalition formation is a coordination method for agents aiming to form groups of interest. In this paper, we focus on the particular context of hedonic games. In hedonic games, the objective of the agents is to form coalitions, which are groups of agents. The satisfaction of an agent depends on other members of its coalition. In this context, autonomous agents need strategical behaviors to efficiently form their coalitions. In this article, we describe two types of strategies which could be used by agents: proposal acceptance strategies, used by agents to decide to join a coalition and proposal selection strategies, based on the analysis of the history of a negotiation, used by agents to select interesting coalitions to propose to other agents. Then we present our experiments and discuss the results we have obtained. We underline that a compromise between high and low selectivity allows agents to obtain a higher probability to form coalitions with a satisfying utility. Our proposal selection strategies allow agents to reduce the number of proposals to send during the coalition formation process without losing much utility. This speeds up considerably the process.

In a maritime area supervision context, we seek providing a human operator with dynamic information on the behaviors of the monitored entities. Linking raw measurements, coming from sensors, with the abstract descriptions of those behaviors is a tough challenge. This problem is usually addressed with a two-stepped treatment: filtering the multidimensional, heterogeneous and imprecise measurements into symbolic events and then using efficient plan recognition techniques on those events. This allows, among other things, the possibility of describing high level symbolic plan steps without being overwhelmed by low level sensor specificities. However, the first step is information destructive and generates additional ambiguity in the recognition process. Furthermore, splitting the behavior recognition task leads to unnecessary computations and makes the building of the plan library tougher. Thus, we propose to tackle this problem without dividing the solution into two processes. We present a hierarchical model, inspired by the formal language theory, allowing us to describe behaviors in a continuous way, and build a bridge over the semantic gap between measurements and intents. Thanks to a set of algorithms using this model, we are able, from observations, to deduce the possible future developments of the monitored area while providing the appropriate explanations.

Coalition formation is a major research issue in multiagent systems in which the agents are self-interested. In these systems, agents have to form groups in order to achieve common goals, which they are not able to achieve individually. A coalition formation mechanism requires two definition levels: firstly agents need a common protocol to reach an agreement and secondly individual strategies are required to make efficient proposals. Both issues are addressed in this paper. First, we propose a two-phase decentralized protocol that allows agents to interact directly through message passing. Secondly we propose some strategies which allow agents to make clever proposals using the information that has already been collected from other agents. The experimental evaluation shows that the proposed mechanism allows agents to efficiently form coalitions and that the strategies make real improvements for the coalition search process.

International audience