Exploiting symmetries for single- and multi-agent Partially Observable Stochastic Domains

详细信息    查看全文

• 作者：Byung Kon Kang ^{bkkang@ai.kaist.ac.kr} ; Kee-Eung Kim ; ^{kekim@cs.kaist.ac.kr}
• 关键词：POMDP ; POSG ; Symmetry ; Graph automorphism
• 刊名：Artificial Intelligence
• 出版年：2012
• 出版时间：May, 2012
• 年：2012
• 卷：182-183
• 期：Complete
• 页码：32-57
• 全文大小：567 K

文摘

While Partially Observable Markov Decision Processes (POMDPs) and their multi-agent extension Partially Observable Stochastic Games (POSGs) provide a natural and systematic approach to modeling sequential decision making problems under uncertainty, the computational complexity with which the solutions are computed is known to be prohibitively expensive.

In this paper, we show how such high computational resource requirements can be alleviated through the use of symmetries present in the problem. The problem of finding the symmetries can be cast as a graph automorphism (GA) problem on a graphical representation of the problem. We demonstrate how such symmetries can be exploited in order to speed up the solution computation and provide computational complexity results.