MAPF-Evo: LLM-Driven Evolution of Heuristics for Conflict Elimination in Multi-Agent Path Finding

Large Neighborhood Search (LNS) is one of the leading approaches for solving large-scale Multi-Agent Path Finding (MAPF), but its performance depends heavily on destroy heuristics—the strategy for selecting which agents to replan. Existing methods mostly rely on hand-crafted, fixed heuristics that cannot adapt well to different problem instances, whereas learning-based methods such as Neural Neighborhood Search (NNS) require training a separate model for each map type, which limits their generality. Therefore, we propose a Large Language Model (LLM) driven evolutionary framework (MAPF-Evo) that automatically designs interpretable destroy heuristics for LNS. By feeding the solver's runtime state back to the LLM, MAPF-Evo evolves heuristics that leverage detailed conflict-structure information to balance solution quality and speed. Experiments on five types of map (40 scenarios in total) show that, compared with the recent best method, MAPF-LNS2, adding the heuristic evolved by MAPF-Evo to the original heuristic pool reduces average remaining conflicts by about 45.0% and improves resolution speed by 11.6%. Gains are especially significant on structurally complex maps such as maze and room. This work is the first to introduce LLM-driven heuristic design into LNS-based MAPF solving, offering a more general and less manually tuned solution to this problem.