Skip to content. | Skip to navigation

Personal tools
Log in
Sections
You are here: Home Papers Exploiting Symmetries for Single and Multi-Agent Partially Observable Stochastic Domains

Byung Kon Kang and Kee-Eung Kim (2012)

Exploiting Symmetries for Single and Multi-Agent Partially Observable Stochastic Domains

Artificial Intelligence, 182-183:32-57.

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.