Branch-and-cut-and-price for Multi-Agent Path Finding

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)


The Multi-Agent Path Finding problem aims to find a set of collision-free paths that minimizes the total cost of all paths. The problem is extensively studied in artificial intelligence due to its relevance to robotics, video games and logistics applications, but is seldom considered in the mathematical optimization community. This paper tackles the problem using a branch-and-cut-and-price algorithm that incorporates a shortest path pricing problem for finding paths for every agent independently and thirteen classes of constraints for resolving different types of conflicts. Experimental results show that this mathematical approach solves 2402 of 4430 instances compared to 2039 and 1939 by the state-of-the-art solvers Lazy CBS and CBSH2-RTC published in artificial intelligence venues.

Original languageEnglish
Article number105809
Number of pages13
JournalComputers and Operations Research
Publication statusPublished - Aug 2022


  • Column generation
  • Cutting plane
  • Multi-agent path finding
  • Multi-agent planning
  • Valid inequality

Cite this