A Formal Analysis of Required Cooperation in Multi-Agent Planning. Zhang, Y., Sreedharan, S., & Kambhampati, S. In
A Formal Analysis of Required Cooperation in Multi-Agent Planning [link]Paper  abstract   bibtex   
While previous research has been motivated by the understanding that, through cooperation, multiple agents can achieve tasks that are unachievable by a single agent, there are no formal characterizations of situations where cooperation is <\em required> to achieve a goal, thus warranting the application of multi-agent systems. In this paper, we provide such a formal characterization from the planning aspect. We first show that determining whether there is required cooperation (RC) is in general intractable. Then, by dividing the problems that require cooperation (referred to as RC problems) into two classes – problems with heterogeneous and homogeneous agents, we identify the conditions that can cause RC in them. We establish that when none of these conditions hold, the problem is single-agent solvable. For problems with heterogeneous agents, we propose that the concept of <\em transformer agent> can be used to improve performance by reducing the number of agents to be considered in planning for many domains. Furthermore, with a few assumptions, we provide upper bounds on the minimum number of agents required for RC problems with homogeneous agents. Finally, we implement a planner using our theoretical results and compare it with one of the best IPC CoDMAP planners in the centralized track. Results show that our planner significantly improves performance on most IPC CoDMAP domains.
@inproceedings {icaps16-198,
    track    = {​Main Track},
    title    = {A Formal Analysis of Required Cooperation in Multi-Agent Planning},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13185},
    author   = {Yu Zhang and  Sarath Sreedharan and  Subbarao Kambhampati},
    abstract = {While previous research has been motivated by the understanding that, 
through cooperation, 
multiple agents can achieve tasks that are unachievable by a single agent, 
there are no formal characterizations of situations where cooperation is <\em required> to achieve a goal, 
thus warranting the application of multi-agent systems. 
In this paper, we provide such a formal characterization from the planning aspect. 
We first show that determining whether there is required cooperation (RC) is in general intractable. 
Then, by dividing the problems that require cooperation (referred to as RC problems) into two classes 
-- problems with heterogeneous and homogeneous agents, 
we identify the conditions that can cause RC in them. 
We establish that when none of these conditions hold, the problem is single-agent solvable. 
For problems with heterogeneous agents, 
we propose that the concept of <\em transformer agent> can be used to improve performance 
by reducing the number of agents to be considered in planning for many domains. 
Furthermore, with a few assumptions, 
we provide upper bounds on the minimum number of agents required for RC problems with homogeneous agents. 
Finally, we implement a planner using our theoretical results and compare it with one of the best IPC CoDMAP planners in the centralized track.
Results show that our planner significantly improves performance on most IPC CoDMAP domains.},
    keywords = {Distributed and multi-agent planning}
}
Downloads: 0