Enhancing PIBT for Multi-Agent Path Finding via MLP-Based Candidate Selection and Priority Perturbation

The Multi-Agent Path Finding (MAPF) problem aims to compute a set of conflict-free paths for multiple agents in a shared environment, ensuring that all agents reach their respective goal locations. MAPF has a wide range of applications, particularly in automated warehouse systems. In practice, MAPF algorithms are often constrained by task allocation requirements and limited by computation speed. Priority Inheritance with Backtracking (PIBT) is an iterative approach to solving MAPF that, in each timestep, operates in near-linear time with respect to the number of agents, enabling efficient handling of both local and global coordination. However, inherent limitations of PIBT result in suboptimal path quality and a tendency to encounter deadlocks in certain scenarios. To address these issues, this paper proposes an enhanced approach that integrates a Multi-Layer Perceptron (MLP)-based candidate point selection mechanism with a random priority perturbation strategy. The MLP model leverages local neighborhood information to improve decision-making and reduce unnecessary yielding, while the priority perturbation helps resolve deadlocks caused by rigid priority assignments. Experimental results demonstrate that the proposed method significantly improves PIBT’s ability to solve MAPF instances across diverse scenarios, yielding higher-quality paths and improved robustness.