Learning conflicts from experience

Multi-agent path finding has been proven to be a PSPACE-hard problem. Generating such a centralised multi-agent plan can be avoided, by allowing agents to plan their paths separately. However, this results in an increased number of collisions and agents must re-plan frequently. In this paper we present a framework for multi-agent path planning, which allows agents to plan independently and solve conflicts locally when they occur. The framework is a generalisation of the CQ-learning algorithm which learns sparse interactions between agents in a multi-agent reinforcement learning setting.