  Decentralized partially observable Markov decision processes (Dec-POMDPs) are
rich models for cooperative decision-making under uncertainty, but are often
intractable to solve optimally (NEXP-complete). The transition and observation
independent Dec-MDP is a general subclass that has been shown to have
complexity in NP, but optimal algorithms for this subclass are still
inefficient in practice. In this paper, we first provide an updated proof that
an optimal policy does not depend on the histories of the agents, but only the
local observations. We then present a new algorithm based on heuristic search
that is able to expand search nodes by using constraint optimization. We show
experimental results comparing our approach with the state-of-the-art DecMDP
and Dec-POMDP solvers. These results show a reduction in computation time and
an increase in scalability by multiple orders of magnitude in a number of
benchmarks.
