Coalition formation in multi-agent systems is a process where agents form coalitions and work together to solve a joint problem via cooperating or coordinating their actions within each coalition. It is important for distributed applications ranging from electronic business to mobile and ubiquitous computing where adaptation to changing resources and environments is crucial. Coalition formation is useful as it may increase the ability of agents to accomplish tasks and achieve their goals. However, in complex real-world environments that agents operate in, the available resources are generally constrained. Agents only have incomplete even inaccurate information about the dynamically changing world. The occurrence of events may require the agents to react in a real-time manner. Agents' actions may result in uncertain outcomes. These factors inevitably influence the formation process and formation outcome of a coalition.

We employ a learning-based two-phased coalition formation approach to help agents form coalitions in complex environments. The approach consists of (1) a two-phase (planning and instantiation) coalition formation model, (2) a two-level (strategic and tactical) learning mechanism, (3) an adaptive, confidence-based negotiation strategy, and (4) a hybrid negotiation model. We have implemented the approach in a partially-observable, resource-constrained, dynamic, uncertain, real-time, and noisy environment. Because of each agent's incomplete view of the complex environment, our approach is not to obtain a specific optimal solution, but a good-enough, soon-enough one. By planning, an agent constructs a coalition formation strategy for the current task based on its past coalition formation experience. In plan (strategy) instantiation, the agent negotiates with others to form a coalition. By strategic learning agents learn how to make coalition formation strategies (or plans) and focus on learning about how to allocate resources to handle multiple coalitions. By tactical learning agents learn how to instantiate the plans tactically and focus on learning about the dynamic behavior of other agents. The experimental results have shown that the two-phased coalition formation (with planning) can outperform the single-phased coalition formation (without planning) in improving coalition formation outcomes. The combination of strategic and tactical learning enables agents to learn how to trade off between efficiency and effectiveness correctly in a complex environment, resulting in a good balance in dealing with both costs and outcomes. For the negotiations between agents during coalition formation, we have designed and implemented a novel confidence-based negotiation strategy for concurrent negotiation management, and built a generic hybrid negotiation model for conducting specific negotiations. Our learning-based two-phased coalition formation approach is novel in that it addresses both the quality of the coalition formation outcome and the quality of the coalition formation process in complex environments.