Executive Summary : | Optimal Coalition Structure Generation (CSG) in Multi Agent Systems (MAS) is an important research problem that remains difficult to solve. Given a set A of n agents, A = {a_1, a_2, …, a_n} and each possible non-empty subsets C ⊆ A are assigned some real value v(C). The main aim of CSG is to partition A into mutually exclusive and exhaustive subsets such that the sum of the values of subsets are maximized. Let, we have n agents (a_1, a_2, …, a_n), then we denote any coalition C_i = {a_1, a_2, …, a_l} as a coalition of l agents a_1, a_2, …, a_l, where l ≤ n. For n agents total number of possible coalitions are ((2^n) -1). In Simultaneous Coalition Structure Generation and Task Allocation (CSGTA) problem the aim is to find the optimal coalitions for tasks. Along with n agents we have m independent tasks (t_1, t_2, …, t_m), hence we need m number of coalitions to solve CSGTA. Any coalition structure CS = {C_1, C_2, ..., C_m} over the n agents is a partitioning of n agents into m number of disjoint coalitions, where any coalition C_i is assigned to a task t_i. Let, we have 3 agents: a_1, a_2, a_3 and 2 independent tasks, then all possible coalitions are: {a_1}, {a_2}, {a_3}, {a_1, a_2}, {a_1, a_3}, {a_2, a_3}, {a_1, a_2, a_3} and all possible m sized CS are: {{a_1}, {a_2, a_3}}; {{a_2}, {a_1, a_3}}; {{a_3}, {a_1, a_2}}. From all these CS we need to identify one as a final output that can maximize the social welfare. CSG and CSGTA problems are computationally hard to solve due to its huge search space and high computational complexity. Existing algorithms for the solution of CSGTA explore 2^n number of coalitions and m*2^n coalitional values for m tasks and n agents. Using this search space, the computation of large-scale inputs (where, n=10000 and m=3000 or, more) is not feasible within a reasonable time frame. The heterogeneous environment in MAS includes a set of non-negative real valued vectors for each agent and task. These vectors are considered as a set of features which may represent the agents with certain abilities and tasks with certain requirements. A set of constraints {ct_1, ct_2, …, ct_k} can affect coalition formation process a lot in MAS, such as spatio-temporal constraint, agent type constraint etc. In light of these aspects, we will address few essential parts for solution of CSGTA through our algorithms and approaches, as we found that; working on the CSGTA problem under heterogeneous constrained MAS for a large-scale input within a reasonable time frame is a challenging task using existing algorithms. Addressing these aspects are necessary because most of the real-world problems or applications includes a large-scale heterogeneous network with various constraints. |