Abstract / Description of output
Multiagent planning is computationally hard in the general case due to the exponential blowup in the action space induced by concurrent action of different agents. At the same time, many scenarios require the computation of plans that are strategically meaningful for self-interested agents, in order to ensure that there would be sufficient incentives for those agents to participate in a joint plan. In this paper, we present a multiagent planning and plan improvement method that is based on conducting iterative best-response planning using standard single-agent planning algorithms. In constrained types of planning scenarios that correspond to congestion games, this is guaranteed to converge to a plan that is a Nash equilibrium with regard to agents' preference profiles over the entire plan space. Our empirical evaluation beyond these restricted scenarios shows, however, that the algorithm has much broader applicability as a method for plan improvement in general multiagent planning problems. Extensive empirical experiments in various domains illustrate the scalability of our method in both cases.
|Title of host publication||Proceedings of the 21st International Conference on Automated Planning and Scheduling, ICAPS 2011|
|Editors||Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp, Malte Helmert|
|Place of Publication||Freiburg, Germany|
|Number of pages||8|
|Publication status||Published - 1 Jun 2011|