Decision-Theoretic Planning Under Anonymity in Agent Populations
Decision-Theoretic Planning Under Anonymity in Agent Populations
复制标题
代理群体中匿名决策理论规划
DOI：
10.1613/jair.5449
复制
发表时间：
2017-08
影响因子：
5
通讯作者：
Prashant Doshi
中科院分区：
文献类型：
--
作者：
Ekhlas Sonu;Yingke Chen;Prashant Doshi
我们研究的问题，自利规划的不确定性下的设置共享超过一千个其他代理人，其中每个计划在自己的个人水平。我们将如此大量的代理人称为代理人群体。采用交互式部分可观测马尔可夫决策过程（I-POMDP）的决策理论形式化方法对Agent的自利规划进行建模。这篇文章的第一个贡献是一个方法，大大扩展有限嵌套的I-POMDP某些代理人口的第一次。我们的方法利用了两种类型的结构，这是经常表现出的代理人口-匿名性和上下文特定的独立性。我们提出了一种称为多代理I-POMDP的变体，该变体对这两种类型的结构进行建模，以便在多代理设置中的不确定性下有效地进行计划。特别是，在多代理I-POMDP的信念更新和解决方案的复杂性是多项式的代理数量相比，指数增长的挑战，原来的框架。
虽然利用结构有助于减轻许多代理人的诅咒，但众所周知的历史诅咒困扰着I-POMDPs，继续挑战规划视野的可扩展性。这篇文章的第二个贡献是分支定界方案的应用，以减少搜索树的指数增长的前瞻。为此，我们引入了新的快速计算的上界和下界的精确值函数的多代理I-POMDP。这在不牺牲最优性的情况下加快了前瞻计算，并降低了内存和运行时间复杂度。第三个贡献是对三个新问题领域的方法进行了全面的实证评估--维持大型抗议活动的治安，控制忙碌十字路口的交通拥堵，以及改善流行的部落冲突多人游戏的AI。我们证明了精确的自利规划在这些大问题的可行性，我们的方法，加快规划是有效的。总而言之，这些贡献代表了一个原则性的和重大的进展，在现实世界的应用中移动不确定性下的自利规划。
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. The 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.
登录
查看更多内容
DOI：
10.7551/mitpress/4168.001.0001
发表时间：
1993-05
期刊：
--
影响因子：
--
作者：
L. Kaelbling
通讯作者：
L. Kaelbling
DOI：
10.1609/aaai.v24i2.18818
发表时间：
2010-07
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Brenda Ng;C. Meyers;K. Boakye;J. Nitao
通讯作者：
Brenda Ng;C. Meyers;K. Boakye;J. Nitao
DOI：
--
发表时间：
1996-08
期刊：
ArXiv
影响因子：
--
作者：
Craig Boutilier;N. Friedman;M. Goldszmidt;D. Koller
通讯作者：
Craig Boutilier;N. Friedman;M. Goldszmidt;D. Koller
DOI：
10.1609/aaai.v30i1.10133
发表时间：
2015-11
期刊：
ArXiv
影响因子：
--
作者：
P. Robbel;F. Oliehoek;Mykel J. Kochenderfer
通讯作者：
P. Robbel;F. Oliehoek;Mykel J. Kochenderfer
DOI：
10.1609/aimag.v33i4.2402
发表时间：
2012-12
期刊：
AI Mag.
影响因子：
--
作者：
Prashant Doshi
通讯作者：
Prashant Doshi