Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents

Abstract

Goal-satisfaction in multi-agent environments via coalition formation may be beneficial in cases where agents cannot perform goals by themselves or they do so ineffi ciently. Agent coalition formation typically requires that each agent must be a member of only one coalition. This may lead to a waste of resources and capabilities. Therefore, we present algorithms that lead agents to the formation of overlapping coalitions, where each coalition is assigned a goal. The algorithms we present are appropriate for agents working as a Distributed Problem Solving system in non-super-additive environments. They are any-time distributed algorithms with a low computational complexity and low ratio-bound.