It is well known that to get maximum benefits, agents need to group to achieve complex tasks. The grouping of agents into several teams is called coalition structure generation (CSG). Reasons agents would join coalitions are, for instance, because they cannot complete tasks alone or want to complete their tasks more quickly. The CSG problem is a well-known hard problem. In this thesis, we aim to devise new algorithms for this problem. CSG has numerous practical applications. Development of new understandings of the CSG problem in different ways will help to solve the problem efficiently, which in turn will help to solve other collaboration problems like for instance robot rescue operation, winner determination, crew scheduling, social ridesharing and many more. The major issue in the CSG problem is its exponential time complexity. The need for solving the CSG problem efficiently is obvious from real-life applications. In that sense, the CSG problem must be investigated further. This research will, therefore, seek to explore and investigate “How to make the efficient grouping of agents”? At a practical level, there are several applications contexts where these algorithms are likely to produce some exciting results such as in crew scheduling, winner determination, autonomous vehicle control.

In the three last years, we have designed several new algorithms for the CSG problem. We have developed a new exact algorithm called EDP (Effective Dynamic Programming). The EDP algorithm is based on a new search technique [1]. One of the objectives of this thesis is to make a hybrid version EDP-IP based on EDP and IP [2]. To reduce the runtime of EDP-IP, we will provide more positive synergies between EDP and IP. In our previous works [5, 6], we have observed that the ODP-IP algorithm [2,4] is performing many duplicated processing. In EDP-IP, we can efficiently distribute the processing between EDP and IP algorithms. We will make the branch and bound technique faster in the IP algorithm by using the previous processing already done by EDP. We will also propose a Bi-directional search process for the CSG and will divide the search process among n agents. This algorithm has to be theoretically analyzed. Then we have to test it experimentally on several data distributions.

Since the CSG problem is an NP-complete problem, we intend to develop an imperfect algorithm, which produces the exact result most of the time and does not fail too often. Imperfect algorithm means that there are some contrived inputs for which the algorithm fails to give the optimal result, but the algorithm will run in linear time with respect to input sizes. For NP-complete problems, imperfect algorithms are useful if these algorithms do not fail too often. In a previous work, we have proposed a first imperfect algorithm, ImDP [3]. Our next step is to develop some new heuristics to limit failures in our proposed algorithm. We will also develop a hybrid version of our imperfect algorithm [3] and existing IP algorithm [2]. ImDP is faster in practice, and IP is a tree search algorithm, we believe that ImDP and IP hybrid version will make the overall runtime shorter.

Our third objective is to increase the number of inputs for the CSG problem. To do that, we intend to make constraints on the size of the coalitions to consider. As for n agents, there are 2n inputs. It is challenging to go for large sets of agents, which is currently the limit of all existing algorithms. Reaching this step is a milestone because it will provide valuable support for many practical applications. This new algorithm will be tested for the Social Ridesharing problem, where a set of commuters, connected through a social network, form coalitions and arrange one-time rides at short notices. Our main goal is to form the travelers’ coalitions that minimize the travel cost of the overall system. To do that, we intend to propose a first technic based on a hybrid version of CPLEX and Algorithm X [7].

References.

[1] Narayan Changder, Samir Aknine, and Animesh Dutta. “An Effective Dynamic Programming Algorithm for Optimal Coalition Structure Generation (Accepted)”. In: ICTAI 2019: The 31st International Conference on Tools with Artificial Intelligence. 2019.

[2] Talal Rahwan, Sarvapali D Ramchurn, Viet Dung Dang, Andrea Giovannucci, and Nicholas R Jennings. “Anytime optimal coalition structure generation”. In: AAAI. Vol. 7. 2007, pp. 1184–1190.

[3] Narayan Changder, Samir Aknine, and Animesh Dutta. “An Imperfect Algorithm for Coalition Structure Generation”. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pp. 9923–9924.

[4] Tomasz Michalak, Talal Rahwan, Edith Elkind, Michael Wooldridge, and Nicholas R Jennings. “A hybrid exact algorithm for complete set partitioning”. In: Artificial Intelligence 230 (2016), pp. 14–50.

[5] Narayan Changder, Samir Aknine, Sarvapali Ramchurn, and Animesh Dutta. “ODSS: Efficient Hybridization for Optimal Coalition Structure Generation. (Accepted)”. In: Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-2020). 2020.

[6] Narayan Changder, Samir Aknine, and Animesh Dutta. “An Improved Algorithm for Optimal Coalition Structure Generation”. In: Proceedings of the Twelfth International Symposium on Combinatorial Search, SOCS, Napa, California, 16-17 July. 2019, pp. 166–167.

[7] Donald E Knuth. “Dancing links”. In: arXiv preprint cs/0011047 (2000).