When to Switch: Planning and Learning for Partially Observable Multi-Agent Pathfinding

Multi-agent pathfinding (MAPF) is a problem that involves finding a set of non-conflicting paths for a set of agents confined to a graph. In this work, we study a MAPF setting, where the environment is only partially observable for each agent, i.e., an agent observes the obstacles and other agents only within a limited field-of-view. Moreover, we assume that the agents do not communicate and do not share knowledge on their goals, intended actions, etc. The task is to construct a policy that maps the agent’s observations to actions. Our contribution is multifold. First, we propose two novel policies for solving partially observable MAPF (PO-MAPF): one based on heuristic search and another one based on reinforcement learning (RL). Next, we introduce a mixed policy that is based on switching between the two. We suggest three different switch scenarios: the heuristic, the deterministic, and the learnable one. A thorough empirical evaluation of all the proposed policies in a variety of setups shows that the mixing policy demonstrates the best performance is able to generalize well to the unseen maps and problem instances, and, additionally, outperforms the state-of-the-art counterparts (PRIMAL2 and PICO). The source-code is available at https://github.com/AIRI-Institute/when-to-switch.

I. Introduction

Multi-agent pathfinding (MAPF) is a challenging problem with topical applications in robotics, video games, logistics, etc. Typically, in MAPF, agents are confined to a graph, and at each timestep, an agent can either move to an adjacent vertex or stay put [1]. The task of each agent is to reach a predefined goal vertex. If the graph is undirected, the solution can be found in polynomial time [2] while finding the optimal solution with respect to a range of the objective functions is NP-hard [3]. Moreover, if the graph is directed, even the decision variant of MAPF is intractable [4].