Solving transition independent decentralized Markov decision processes
Solving transition independent decentralized Markov decision processes
复制标题
DOI：
10.1613/jair.1497
复制
发表时间：
2004-01-01
影响因子：
5
通讯作者：
Goldman, CV
中科院分区：
文献类型：
--
作者：
Becker, R;Zilberstein, S;Goldman, CV
对协作多智能体系统的正式处理一直落后于个体智能体顺序决策的快速发展。最近在分散式马尔可夫决策过程（mdp）领域的工作有助于缩小这一差距，但这些模型的计算复杂性仍然是一个严重的障碍。为了克服这种复杂性障碍，我们确定了一类特定的分散mdp，其中代理的转换是独立的。类由独立协作的代理组成，这些代理通过一个结构化的全局奖励函数联系在一起，该函数依赖于它们所有的状态和行为历史。我们提出了一种新的算法来解决这类问题，并研究了它作为最优算法和任意算法的性质。据我们所知，这是第一个最优解决非平凡分散mdp子类的算法。它为该领域在精确和近似算法方面的进一步工作奠定了基础。
Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents' transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. To the best of our knowledge, this is the first algorithm to optimally solve a non-trivial subclass of decentralized MDPs. It lays the foundation for further work in this area on both exact and approximate algorithms.