Arrow Research search

Author name cluster

Narayan Changder

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.

15 papers
2 author rows

Possible papers

15

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

AAAI Conference 2025 Short Paper

Hide Exposures by Removing Mastermind’s External Sources on Social Network (Student Abstract)

  • Nilanjana Saha
  • Narayan Changder
  • Redha Taguelmimt
  • Samir Aknine
  • Animesh Dutta

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%.

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

AAAI Conference 2024 Short Paper

Coalition Formation for Task Allocation Using Multiple Distance Metrics (Student Abstract)

  • Tuhin Kumar Biswas
  • Avisek Gupta
  • Narayan Changder
  • Redha Taguelmimt
  • Samir Aknine
  • Samiran Chattopadhyay
  • Animesh Dutta

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.

PDF Details DOI

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

BOSS: A Bi-directional Search Technique for Optimal Coalition Structure Generation with Minimal Overlapping (Student Abstract)

  • Narayan Changder
  • Samir Aknine
  • Sarvapali D. Ramchurn
  • Animesh Dutta

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.

PDF Details

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

AAAI Conference 2020 Conference Paper

Learning the Value of Teamwork to Form Efficient Teams

  • Ryan Beal
  • Narayan Changder
  • Timothy Norman
  • Sarvapali Ramchurn

In this paper we describe a novel approach to team formation based on the value of inter-agent interactions. Specifically, we propose a model of teamwork that considers outcomes from chains of interactions between agents. Based on our model, we devise a number of network metrics to capture the contribution of interactions between agents. This is then used to learn the value of teamwork from historical team performance data. We apply our model to predict team performance and validate our approach using real-world team performance data from the 2018 FIFA World Cup. Our model is shown to better predict the real-world performance of teams by up to 46% compared to models that ignore inter-agent interactions.

PDF Details

AAAI Conference 2020 Conference Paper

ODSS: Efficient Hybridization for Optimal Coalition Structure Generation

  • Narayan Changder
  • Samir Aknine
  • Sarvapali Ramchurn
  • Animesh Dutta

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.

PDF Details

AAAI Conference 2019 Short Paper

An Imperfect Algorithm for Coalition Structure Generation

  • Narayan Changder
  • Samir Aknine
  • Animesh Dutta

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).

PDF Details

SoCS Conference 2019 Conference Paper

An Improved Algorithm for Optimal Coalition Structure Generation

  • Narayan Changder
  • Samir Aknine
  • Animesh Dutta

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

Details