A Plan Based Coalition Formation Model for Multi-agent Systems

This article addresses the coalition formation problem in a multi-agent context where agents plan their activities dynamically and use these plans to coordinate their actions and form suitable coalitions. In most coalition formation methods, when negotiating their coalitions the agents focus mainly on the immediate tasks to be executed, in order to decide which coalitions to form. Agents relegate the negotiations of the coalitions for their subsequent tasks to later stages of the coordination process. This paper deals with this issue and proposes a new coalition formation model which is based on two principles:(1) it uses the plans of the agents to guide the search for the coalitions to be formed and shows the significance of not only taking into account the immediate actions of the agents in the coalition formation process, (2) it analyzes the coalition proposals already suggested by other agents in order to derive their intentions and thus facilitate the negotiations fort he coalitions. First we analyse and develop the constraints that should be enforced on self-interested agents, in order to form suitable coalitions which guarantee significant solution concepts. Then we detail our coalition formation mechanism.