Discovering and exploiting synergy between hierarchical planning agents

Abstract

It is critical for agents in a multiagent environment to avoid interfering with each other when carrying out their tasks. However, to avoid execution inefficiencies, they also should capitalize on cooperative opportunities. In state oriented domains [14], identifying overlapping effects between agents' plans enables some agents to leave some tasks to others, thereby reducing the cost of execution and improving the overall efficiency of the multiagent system. This is what we term synergy. In this paper, we define criteria for finding a certain type of synergy involving agents with overlapping goals. We also develop algorithms for discovering this synergy between planning agents that exploit hierarchical plan representations. Our results show that our approach not only can reduce the costs of finding synergies compared to non-hierarchical strategies, but can also find synergies that might otherwise be missed.