Multi-skill agents coalition formation under skill uncertainty

摘要

In a multi-agent system, there are situations in which agents are unable to do their tasks individually. Therefore forming coalitions is inevitable. In natural settings, an agent decides to form coalition based on beliefs it has regarding the capabilities of other agents. In the previous works, it was assumed that a single type can reflects all capabilities an agent has. We introduce multi-skill agents which have a value per skill. This helps us to solve more problems and to reason about the results, more exactly. We use Bayesian Reinforcement Learning (BRL) as the learning mechanism. Through the repeated use of BRL, agents can form more rewarding coalitions. We extend existing algorithms of the repeated coalition formation under type uncertainty to the skill uncertainty and exploit them in experimental studies that type uncertainty couldn't do or reason about. Average long term discounted expected reward that agents accumulate in the learning process, is the criteria we test our methods based on. We test the algorithms on a sample soccer sub-team formation problem. To have a notion of the best performance, we solve the problem in the absence of uncertainty. Results show that the VPI method does approximately 85% of the best performance.