A revision algorithm for invalid encodings in concurrent formation of overlapping coalitions

In multi-agent systems, agents are inclined to form coalitions to improve individual performance and perform tasks more efficiently. However, the most existing researches assume that the desired outcome is a coalition structure that consists of disjoint coalitions where every agent that has joined a coalition is no longer available to join other coalitions, which leads to waste of resources. In a number of practical scenarios an agent may have to be involved in executing more than one task simultaneously, and distributing its resources to several completely different coalitions. To tackle such problems, we propose the concurrent formation of overlapping coalitions and introduce a two-dimensional binary encoding to search the coalition space. We mainly focus on the revision algorithm for invalid encodings. Specifically, by using the proposed revision algorithm, an agent may join in several different coalitions at the same time without any resource conflict. Moreover, we prove by mathematical induction that the proposed algorithm will not discard any invalid encoding and can revise any invalid encoding into a valid one. Finally, a contrast experiment is illustrated to demonstrate the proposed algorithm.