What is the best way to divide a set of workers, such that you can efficiently handle multi-dimensional tasks with the minimum number of groups? This is a common problem in artificial intelligence (AI), where the workers are AI agents and the groups are called coalitions.
One variant of this problem is the “Simultaneous Coalition Structure Generation and Assignment problem considering Multi-dimensional Features (SCSGA-MF).” Here, multi-dimensional agents have to be partitioned into coalitions while the coalitions are simultaneously assigned to different, multi-dimensional tasks. Typically, SCSGA-MF focuses on maximising the compatibility between agents and tasks, i.e., minimising the “coalition structure value.”
A recent research paper, with primary author Tuhin Kumar Biswas (PhD student, NIT Durgapur), and co-authored by Dr. Avisek Gupta and Dr. Narayan Changder from our Institute for Advancing Intelligence (IAI), published in Information Sciences, puts forth a new SCSGA-MF algorithm that additionally focuses on task satisfaction (SCSGA-MF-TS)—a concern that has until now not been considered in research.
SCSGA-MF-TS utilises a two-phase “Compact Agent Neighborhood (CAN)” search that iteratively improves upon an initial coalition structure by reassigning agents to coalitions that provide the most compact local neighbourhood around the coalition’s task, while maintaining or increasing the number of satisfied tasks. This technique, thereby, simultaneously minimises coalition structure value while maximising task satisfaction. Empirical studies performed by the research team demonstrate that CAN search satisfies significantly more tasks than other state-of-the-art algorithms.
Click here to read the full paper
