Decision-Theoretic Planning Under Anonymity in Agent Populations

Ekhlas Sonu, Yingke Chen, Prashant Doshi

    Research output: Contribution to journalArticle

    128 Downloads (Pure)

    Abstract

    We study the problem of self-interested planning under uncertainty in settings shared with more than a thousand other agents, each of which plans at its own individual level. We refer to such large numbers of agents as an agent population. The decision-theoretic formalism of interactive partially observable Markov decision process (I-POMDP) is used to model the agent’s self-interested planning. The first contribution of this article is a method for drastically scaling the finitely-nested I-POMDP to certain agent populations for the first time. Our method exploits two types of structure that is often exhibited by agent populations – anonymity and context-specific independence. We present a variant called the many-agent I-POMDP that models both these types of structure to plan efficiently under uncertainty in multiagent settings. In particular, the complexity of the belief update and solution in the many-agent I-POMDP is polynomial in the number of agents compared with the exponential growth that challenges the original framework. While exploiting structure helps mitigate the curse of many agents, the well-known curse of history that afflicts I-POMDPs continues to challenge scalability in terms of the planning horizon. The second contribution of this article is an application of the branch-and-bound scheme to reduce the exponential growth of the search tree for look ahead. For this, we introduce new fast-computing upper and lower bounds for the exact value function of the many-agent I-POMDP. This speeds
    up the look-ahead computations without trading off optimality, and reduces both memory and run time complexity. Thsudoe third contribution is a comprehensive empirical evaluation of the methods on three new problems domains – policing large protests, controlling traffic congestion at a busy intersection, and improving the AI for the popular Clash of Clans multiplayer game. We
    demonstrate the feasibility of exact self-interested planning in these large problems, and that our methods for speeding up the planning are effective. Altogether, these contributions represent a principled and significant advance toward moving self-interested planning under uncertainty to real-world applications.
    Original languageEnglish
    Pages (from-to)725-770
    JournalJournal of Artificial Intelligence Research
    Volume59
    DOIs
    Publication statusPublished - 24 Aug 2017

    Bibliographical note

    Author can archive post-print (ie final draft post-refereeing) For full details see http://www.sherpa.ac.uk/romeo/issn/1076-9757/ [Accessed 26/02/2018]

    Fingerprint Dive into the research topics of 'Decision-Theoretic Planning Under Anonymity in Agent Populations'. Together they form a unique fingerprint.

  • Cite this