Greedy Priority Inheritance with Backtracking for Multi-agent Pathfinding Problem

Some real-world transportation systems require moving robots from their start points to goal points without collision, which can be formalized as the multi-agent pathfinding (MAPF) problem. The Priority Inheritance with Backtracking (PIBT) algorithm is an efficient approach for MAPF with low-degree polynomial time complexity and proven completeness. PIBT employs a dynamic prioritization scheme to determine the order of sequential agent planning. However, this scheme may lead to low solution quality, which is measured by the sum of time steps each agent takes to reach its goal for the first time. In this work, we propose two greedy variants of the PIBT algorithm that improve solution quality while preserving completeness: Backflow-based Greedy PIBT (GPIBT-B) and Reduction-based Greedy PIBT (GPIBT-R). GPIBT-B introduces a backflow mechanism that allows a determined agent to adjust its plan during the planning of another agent, achieving higher solution quality while maintaining the same low time complexity as PIBT. GPIBT-R formulates the planning problem as a Mixed-Integer Linear Programming (MILP), enabling the use of efficient MILP solvers to find high-quality solutions. Experimental results show that GPIBT-B substantially improves solution quality with minimal additional computation time, while GPIBT-R achieves even better solution quality at the cost of increased computational time.

© 2026 IEEE. All rights reserved, including rights for text and data mining, and training of artificial intelligence and similar technologies. Personal use is permitted, but republication/redistribution requires IEEE permission.