An Efficient Computing of Correlated Equilibrium for Cooperative $Q$-Learning-Based Multi-Robot Planning

Abstract

Traditional multi-agent Q-learning (MAQL) induced planning needs to evaluate computationally expensive Nash/correlated equilibrium (CE) at a given joint state during both learning and planning phases. This paper introduces a novel approach to adapt composite rewards of all the agents in one Q-table in joint state-action space during learning, and uses these rewards to compute CE in an efficient way during the planning phases. Two schemes of MAQL have been proposed. If mutual cooperation among the agents leads to success of at least one agent and is enough to make the team successful, then scheme-I is employed. However, if an agent's success is contingent upon other agents' mutual cooperation as well as simultaneous success of the agents is mandatory then scheme-II is employed. New algorithms for multi-agent learning/planning have been proposed, centering on the said schemes. It is shown that the equilibrium obtained by the proposed algorithms and the traditional correlated Q-learning are identical. In order to restrict the exploration within the feasible joint states, constraint versions of the said algorithms are also proposed. An analysis is included to demonstrate the significant saving of computational time and space by the proposed algorithms. In addition, convergence analysis of the proposed algorithms is done. Experiments have been undertaken to validate the performance of the proposed algorithms in multi-robot planning on both simulated and real platforms.