Scaling Up Multiagent Planning: A Best-Response Approach

Anders Jonsson, Michael Rovatsos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the 21st International Conference on Automated Planning and Scheduling, ICAPS 2011
EditorsFahiem Bacchus, Carmel Domshlak, Stefan Edelkamp, Malte Helmert
Place of PublicationFreiburg, Germany
PublisherAAAI Press
Number of pages8
Publication statusPublished - 1 Jun 2011


Dive into the research topics of 'Scaling Up Multiagent Planning: A Best-Response Approach'. Together they form a unique fingerprint.

Cite this