Policy computation for constrained communicating agents

Decentralized Markov Decision Processes (DECMDPs) provide powerful modeling tools for cooperative multiagent decision making under uncertainty. However, as basic models, they fail in modeling problems where decision makers must act under time pressure and regarding complex constraints. In this paper, we focus on adapting DEC-MDP model in order to take into account temporal constraints, precedence constraints and uncertain action durations. Particularly, we extend a solution method called opportunity cost DEC-MDP to handle more complex precedence constraints. Because problems we consider require a tight coordination, we introduce communication among agents. We aim at optimizing communication decisions since dealing with offline planning for communication is intractable. To this end, we propose to exploit problem structure in order to limit information sharing. Experimental results show that even if communication is costly, it improves the degree of coordination between agents and it increases team performances regarding constraints.