Multiagent planning under uncertainty with stochastic communication delays

We consider the problem of cooperative multiagent plan-ning under uncertainty, formalized as a decentralized par-tially observable Markov decision process (Dec-POMDP). Unfortunately, in these models optimal planning is provably intractable. By communicating their local observations be-fore they take actions, agents synchronize their knowledge of the environment, and the planning problem reduces to a cen-tralized POMDP. As such, relying on communication signif-icantly reduces the complexity of planning. In the real world however, such communication might fail temporarily. We present a step towards more realistic communication models for Dec-POMDPs by proposing a model that: (1) allows that communication might be delayed by one or more time steps, and (2) explicitly considers future probabilities of successful communication. For our model, we discuss how to efficiently compute an (approximate) value function and corresponding policies, and we demonstrate our theoretical results with en-couraging experiments