A Polynomial Algorithm for Decentralized Markov Decision Processes with Temporal Constraints

International audienceOne of the difficulties to adapt MDPs for the control of cooperative multi-agent systems, is the complexity issued from Decentralized MDPs. Moreover, existing approaches can not be used for real applications because they do not take into account complex constraints about the execution. In this paper, we present a class of DEC-MDPs, OC-DEC-MDP, that can handle temporal and precedence constraints. This model allows several autonomous agents to cooperate so as to complete a set of tasks without communication. In order to allow the agents to coordinate, we introduce an opportunity cost. Each agent builds its own local MDP independently of the other agents but, it takes into account the lost in value provoked, by its local decision, on the other agents. Existing approaches solving DEC-MDP are NEXP complete or exponential, while our OC-DEC-MDP can be solved by a polynomial algorithm with good approximation