Author name cluster

Djamila Boukredera

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

AAAI Conference 2025 Conference Paper

A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder
Tuomas Sandholm

Coalition structure generation (CSG), i.e. the problem of optimally partitioning a set of agents into coalitions to maximize social welfare, is a fundamental computational problem in multiagent systems. This problem is important for many applications where small run times are necessary, including transportation and disaster response. In this paper, we develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures. Our algorithm utilizes a variety of heuristics and strategies to perform the search and guide it. It is an anytime algorithm that can handle large problems with hundreds and thousands of agents. We show empirically on nine standard value distributions, including disaster response and electric vehicle allocation benchmarks, that our algorithm enables a rapid finding of high-quality solutions and compares favorably with other state-of-the-art methods.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder
Tuomas Sandholm

Coalition structure generation (CSG) is a critical problem in multiagent systems, involving the optimal partitioning of agents into disjoint coalitions to maximize social welfare. This paper introduces SALDAE, a novel multiagent path finding algorithm for CSG on a coalition structure graph. SALDAE employs various heuristics and strategies for efficient search, making it an anytime algorithm suitable for handling large-scale problems.

PDF

AAMAS Conference 2024 Conference Paper

Efficient Size-based Hybrid Algorithm for Optimal Coalition Structure Generation

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder
Tuomas Sandholm

Coalition Structure Generation (CSG) involves dividing agents into coalitions in such a way as to coordinate them into solving problems together efficiently. In this paper, we revisit the CSG problem and propose a new search method that introduces an offline phase to speed up the search process, where the best coalition sets to search are preprocessed. These sets are calculated only once regardless of the coalition values and can be reused each time a CSG instance is to be solved. Then our search in the online phase combines dynamic programming with integer partition-based search in a novel way.

PDF

IJCAI Conference 2024 Conference Paper

Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder
Tuomas Sandholm

Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Anytime Index-Based Search Method for Large-Scale Simultaneous Coalition Structure Generation and Assignment

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder

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.

Details

IJCAI Conference 2023 Conference Paper

Optimal Anytime Coalition Structure Generation Utilizing Compact Solution Space Representation

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder
Tuomas Sandholm

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.

PDF Details DOI

AAAI Conference 2023 Short Paper

Parallel Index-Based Search Algorithm for Coalition Structure Generation (Student Abstract)

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder

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.

PDF Details DOI

AAAI Conference 2021 Short Paper

FACS: Fast Code-based Algorithm for Coalition Structure Generation (Student Abstract)

Redha Taguelmimt
Samir Aknine
Djamila Boukredera
Narayan Changder

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.

PDF Details

EUMAS Conference 2014 Conference Paper

Modeling a Multi-issue Negotiation Protocol for Agent Extensible Negotiations

Samir Aknine
Souhila Arib
Djamila Boukredera

Abstract In this paper, we study how to achieve more effective negotiations by extending during the negotiation process, the negotiation object with new relevant items. Indeed, the possibility to extend the initial set of items defined by the requester agent with other items related to the original query can help find an agreement. In doing so, with extended proposals, the requester agent may be incentivized to be more flexible, e. g. , by making concessions or relaxing some constraints on the issues. This may help to achieve an agreement which is more beneficial for both parties than breaking down the negotiation. Such extensible negotiations may lead to win-win outcomes which otherwise can not be achieved with some usual negotiation strategies where it is hard to dynamically alter the set of items under negotiation during the course of the process. In this paper, we first outline a negotiation strategy which allows the extension of the negotiation space by extending the negotiation object with new relevant items. Based on this, we then propose a new multi-issue negotiation protocol which relies on the bidding-based mechanism and deals with such extensible negotiation strategies.

Details