Research On Agent Coalition Formation Under Uncertainty

Coalition formation is an important research topic within Multiagent system liter-ature. However, most research has been focused on the case where everything is with certainty. In other words, the environment is assumed to be perfect information. But since uncertainty is the inherent property of Multiagent system, so whether such uncer-tainty can be tackled is crucial for coalition formation techniques’s applying to reality. Motivated by this, this thesis is focused on tackling such uncertainty existed in the pro-cess of coalition formation. More concretely, when there exists uncertainty, there will be several severe problems that the classic coalition formation based task allocation model can’t solve:First, the classic model doesn’t consider the uncertainty existing in the environment. But whether such uncertainty can be solved effectively is crucial for the quality of coalition that formed. Secondly, in the classic model, its main goal is to maximize current utility. However, when uncertainty exists, if the whole concerning is maximize current utility, the true maximized utility may can’t be obtained. Finally, in the classic model, it doesn’t consider the case when agent may leave or join current system. While it may happens with high probability, especially when the system is large.This thesis tries to generalize the classic problem existed in coalition formation that task allocation based on coalition formation to the cases where uncertainty exists. On the other hand, most coalition formation research only consider maximizing the payoff for one-shot, i.e, they only consider myopic payoff. Apparently, in many cases, people are more concerned with maximizing their long-term payoff.Due to this, this thesis also consider such algorithms that can maximize agents’ long term payoff.In summary, the main contribution of this thesis can be summarized as follows:1. Generalizing the classic problem of coalition based task allocation to the case where uncertainty exists. To represent such uncertainty, agent’s capacity is mod-eled by multivariate gaussian distribution in this thesis. And Normal-Inverse-Wishart Distribution is used as a prior on agent’s capacity. Based on these, a Bayesain coalition formation algorithm is proposed.2. The model is further generalized to the case when long-term payoff is the main focus. And in order to solve the exploration vs. exploitation dilemma existing in our model, value of information is introduced. And based on this, a bayesian re- inforcement learning based long term coalition formation algorithm is proposed. A experiment is designed to verify the validity of the algorithm.3. And further, the model is generalized to the case when the environment is dy-namic. In order to solve the problem that agent can leave or join the system at times, the proposed bayesian reinforcement learning based long term coalition formation algorithm is generalized to tackle the problem of dynamic coalition formation.4. When there exists many tasks, more learning methods can be used to help coali-tion formation. So, a weighted-based coalition formation algorithm is proposed. However, such an algorithm can’t always find the optimal coalition, so a random-ized weighted-based coalition formation is proposed. But deciding when to use which algorithm is hard, so a concept of similarity degree is proposed. And in order to determine the best similarity degree threshold, a reinforcement learning algorithm is proposed.