Enhancing MAS Cooperative Search Through Coalition Partitioning

Efrat Manisterski, David Sarne,Sarit Kraus

In this paper we present new search strategies for agents with diverse preferences searching cooperatively in complex environments with search costs. The uniqueness of our proposed mechanism is in the integration of the coalition's ability to partition itself into sub-coalitions, which continue the search autonomously, into the search strategy (a capability that was neglected in earlier cooperative search models). As we show throughout the paper, this strategy is always favorable in comparison to currently known cooperative and autonomous search techniques: it has the potential to significantly improve the searchers' performance in various environments and in any case guarantees reaching at least as good a performance as that of other known methods. Furthermore, for many common environments we manage to significantly eliminate the consequential added computational complexity associated with the partitioning option, by introducing innovative efficient algorithms for extracting the coalition's optimal search strategy. We illustrate the advantages of the proposed model over currently known cooperative and individual search techniques, using an environment based on authentic settings.