@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}
}

{"_id":"pCptn8KHkHJwoJ8Jz","bibbaseid":"zhang-sreedharan-kambhampati-aformalanalysisofrequiredcooperationinmultiagentplanning","downloads":0,"creationDate":"2016-03-09T03:04:32.869Z","title":"A Formal Analysis of Required Cooperation in Multi-Agent Planning","author_short":["Zhang, Y.","Sreedharan, S.","Kambhampati, S."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","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":[{"firstnames":["Yu"],"propositions":[],"lastnames":["Zhang"],"suffixes":[]},{"firstnames":["Sarath"],"propositions":[],"lastnames":["Sreedharan"],"suffixes":[]},{"firstnames":["Subbarao"],"propositions":[],"lastnames":["Kambhampati"],"suffixes":[]}],"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","bibtex":"@inproceedings {icaps16-198,\r\n track = {​Main Track},\r\n title = {A Formal Analysis of Required Cooperation in Multi-Agent Planning},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13185},\r\n author = {Yu Zhang and Sarath Sreedharan and Subbarao Kambhampati},\r\n abstract = {While previous research has been motivated by the understanding that, \r\nthrough cooperation, \r\nmultiple agents can achieve tasks that are unachievable by a single agent, \r\nthere are no formal characterizations of situations where cooperation is <\\em required> to achieve a goal, \r\nthus warranting the application of multi-agent systems. \r\nIn this paper, we provide such a formal characterization from the planning aspect. \r\nWe first show that determining whether there is required cooperation (RC) is in general intractable. \r\nThen, by dividing the problems that require cooperation (referred to as RC problems) into two classes \r\n-- problems with heterogeneous and homogeneous agents, \r\nwe identify the conditions that can cause RC in them. \r\nWe establish that when none of these conditions hold, the problem is single-agent solvable. \r\nFor problems with heterogeneous agents, \r\nwe propose that the concept of <\\em transformer agent> can be used to improve performance \r\nby reducing the number of agents to be considered in planning for many domains. \r\nFurthermore, with a few assumptions, \r\nwe provide upper bounds on the minimum number of agents required for RC problems with homogeneous agents. \r\nFinally, we implement a planner using our theoretical results and compare it with one of the best IPC CoDMAP planners in the centralized track.\r\nResults show that our planner significantly improves performance on most IPC CoDMAP domains.},\r\n keywords = {Distributed and multi-agent planning}\r\n}\r\n\r\n","author_short":["Zhang, Y.","Sreedharan, S.","Kambhampati, S."],"key":"icaps16-198","id":"icaps16-198","bibbaseid":"zhang-sreedharan-kambhampati-aformalanalysisofrequiredcooperationinmultiagentplanning","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13185"},"keyword":["Distributed and multi-agent planning"],"metadata":{"authorlinks":{}}},"search_terms":["formal","analysis","required","cooperation","multi","agent","planning","zhang","sreedharan","kambhampati"],"keywords":["distributed and multi-agent planning"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}