acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Multi-Agent Path Finding, Large Neighborhood Search, Conflict Elimination, LLM-driven Automatic Heuristic Design

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_DhN4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the conflict resolution problem in LNS-based multi-agent path planning, with a focus on the automatic design of “resolution” heuristic algorithms for selecting agents to participate in joint replanning. MAPF-Evo utilizes large language models (LLMs) to generate and evolve executable heuristic programs on training scenarios. Candidates have access to the conflict graph, the current path, search stagnation states, and the repair history. The framework combines crossover and mutation, joint scheduling of operators and parents, short-term reflection, and long-term memory, and performs population selection based on the solver’s fitness and the semantic novelty of the program description. The selected heuristic can be deployed either independently or within the original ALNS heuristic pool of MAPF-LNS2. Evaluation was conducted using 50 training scenarios and 40 independent test scenarios, covering five map layouts, and was supplemented by tests varying the number of agents, LLM, time budget, scheduling strategies, and unseen maps. Under a 100-second time budget, the addition of this evolutionary heuristic is reported to reduce the average number of remaining conflicts by approximately 45%, shorten the average conflict resolution time by 11.6%, and increase the success rate from 62.5% to 65%.

Critical strengths
  1. Obtaining a conflict-free feasible solution is a prerequisite for subsequent path cost optimization; therefore, eliminating conflicts is a meaningful goal of automated heuristic design. MAPF-Evo reveals conflict connectivity, the location of the first conflict, stagnation, and repair feedback, thereby enabling candidate algorithms to construct state-based neighborhood rules (Section 4.1 and Appendices A/B). The generated programs can be verified, interpreted, and integrated into existing solvers. This provides a practical foundation for the automatic design of MAPF heuristics.

  2. In Table 1, compared to MAPF-LNS2, best-ALNS reduces the average number of remaining conflicts from 154.85 to 85.15 and shortens the average solution time from 48.44 seconds to 42.80 seconds. The evaluation employed a general initial path, covering time budgets of 100 and 200 seconds, different numbers of agents, and multiple LLMs. The appendix also details the adaptive adjustments made to NNS, BALANCE, and TACKLE for conflict elimination. These results demonstrate the practical value of evolutionary algorithms as a complement to existing solvers, particularly as evidenced by the significant reduction in residual conflicts.

Critical weaknesses
  1. EoH has already achieved the co-evolution of natural language heuristic design and executable code, while ReEvo has utilized short-term and long-term reflection to guide heuristic evolution. Therefore, the incremental value provided by MAPF-Evo’s state interface, semantic novelty selection, and joint scheduling requires more explicit validation.

    These experiments primarily compare final solvers rather than adapting a general evolutionary framework to the same MAPF interface under comparable budgets. Although the scheduling ablation experiments in Section 6.4 are valuable, they mainly report the fitness of populations and candidate solutions in training scenarios; they do not demonstrate that the generated programs perform better in retention set scenarios. Semantic novelty also lacks ablation experiments or behavioral validation to demonstrate that descriptive distance indeed reflects differences in neighborhood selection behavior. The absence of a comprehensive generation and evaluation budget further limits the assessment of this framework’s effectiveness and efficiency. This is the primary factor motivating my recommendation.

  2. Table 1 indicates that the results are the mean and sample standard deviation of the aggregated values for each of the three solver seeds, covering a total of 40 test scenarios. If each seed evaluates the same 40 scenarios, the variation in success rates should be 2.5 percentage points. If the exact mean is 62.5%, the smallest non-zero sample standard deviation would be 2.5 percentage points; therefore, the result (62.50 ± 0.50%) cannot be directly obtained according to the stated protocol. Additional repetitions, weighting, or aggregation levels might explain this phenomenon, but this must be clearly specified.

    At 100 seconds, the success rate increased by 2.5 percentage points, which is equivalent to one additional success on average every 40 runs. At 200 seconds, LNS2+RL achieved an 80% success rate, while MAPF-Evo achieved 72.5% (Table 7). On the three unseen maps, both methods solved the same number of scenarios, although MAPF-Evo left fewer conflicts on the difficult maps (Table 8). These results provide stronger support for conflict reduction and improvements in average time rather than a sustained increase in feasibility. Furthermore, the initial values of the three solvers cannot substitute for independent replications of the complete LLM evolution process, the variability of which has not yet been fully characterized.

Questions for authors
  1. Please provide the number of successful instances, the actual number of evaluations, and the aggregation formula for each solver’s initial value. How was the value (62.50±0.50(62.50\pm0.50%) derived from 40 scenarios, three initial values, and the sample standard deviation? Were additional repetitions or map/agent-count weighting involved? Please also specify the number of scenarios corresponding to each agent count in Figure 3, and whether their evaluation units align with those in the main table.

  2. Please adapt at least one relevant general-purpose framework (e.g., ReEvo or EoH) to the same MAPF state interface and evaluation objective, and include a simple “repeated generation and selection” baseline. Use comparable LLMs, training scenarios, and candidate program evaluation budgets; report complete LLM consumption metrics; and evaluate the generated programs on the same retention scenarios. This will help distinguish the respective contributions of the task interface, search budget, and the proposed evolutionary mechanisms.

  3. Under matched initialization conditions and budgets, compare the full framework with selection mechanisms that do not account for semantic novelty, and report the performance of the three scheduling strategies’ final heuristics on the retained dataset in Section 6.4. If reflection and memory are considered core contributions, corresponding control groups should also be established. Is it possible to verify the differences between the selected agent sets by utilizing a measure of embedding distance over a common set of solver states? Lower training fitness alone does not prove the generalization value of these mechanisms.

  4. Please clearly specify (w1,w2,w3)(w_1, w_2, w_3), the normalization of iteration costs, the normalization of quality, the adaptive formula for (λ)(\lambda), the embedding model, the population size, the number of generations in the main experiment, and the candidate execution timeout settings. What LLM was used to generate the programs in the main table, and how many evolutionary runs were performed? How were these programs selected? Please report the number of calls/tokens consumed by generation, scheduling, reflection, and memory updates, and provide the total time taken for solver evaluation to assess the efficiency of the entire framework.

  5. Does the 100/200-second budget include state feature construction, evolutionary heuristic execution, cross-language call overhead, and low-level fixes? The main text allocates the budget constraint to unsolved runs, but the completely failed Maze configurations in Table 8 have average times exceeding 100 seconds. Are timeouts allowed for final repairs, and is this handling consistent across different methods? Providing a breakdown of runtime between neighborhood selection and path repair would help determine the actual runtime benefits.

2 comments
AuthorsOpenReview ↗

Response to Reviewer DhN4 (1)

Weakness 1, Q2 & Q3 :

Thank you for your careful review. Since you identified Weakness 1 as the main reason for your rating, we focused our new experiments and analyses on it. Our detailed responses follow:

1. MAPF-Evo vs. EoH vs. Repeat. Thank you for your suggestion. We adapted EoH to the same MAPF interface and fitness objective, then compared it with MAPF-Evo and Repeat using the same LLM, training scenarios, and candidate count (Section 6.4). Repeat uses only the initialization operator, without evolution. Their best fitness values are 0.280, 0.304, and 0.340, and MAPF-Evo’s mean fitness is 0.332. We also report token costs: although MAPF-Evo uses more tokens, it achieves higher candidate quality when generating the same number of candidates.

MethodBest fitnessMean fitnessInput tokens (M)Output tokens (M)
Repeat0.3400.6500.3990.441
EoH0.3040.5710.9460.547
MAPF-Evo0.2800.3321.5640.789

2. Joint scheduling: test-set results. Thank you for your attention to generalization. On the test set, joint scheduling achieves 57.50% mean success and 125.37 mean remaining conflicting pairs, 6.71% fewer than operator-only scheduling and 25.12% fewer than fixed scheduling. These results suggest that joint scheduling also improves test-set performance.

Scheduling methodTraining fitnessSuccess rate (%)Conflicting pairsResolution time (s)
Fixed sequence0.28754.75 ± 3.22167.43 ± 18.8312.58 ± 2.75
LLM: operators0.28155.50 ± 2.58134.38 ± 10.0811.01 ± 2.20
LLM: operators + parents0.27057.50 ± 2.64125.37 ± 11.3512.73 ± 2.79

3. Novelty and reflection-memory ablations. Thank you for pointing out the insufficient ablations. Starting from the same initial population, semantic novelty raises the mean semantic distance over generations 1–50 from 0.139 (without novelty) to 0.173, showing that it preserves diversity in mechanism descriptions. With reflection and memory, fitness decreases by 7.13% over generations 1–5, versus 1.78% without them, showing that they accelerate early evolution. We added these experiments to the revised manuscript (Appendix C.6, Figure 10) for reviewers and readers to consult.

4. Embedding distance vs. selection differences. Thank you for raising this issue. We evaluated three candidate pairs on the same 593 solver states with 10 seeds. As semantic distance increased from 0.039 to 0.337, mean Jaccard overlap decreased from 0.999 to 0.069. These results provide preliminary evidence that greater semantic distance reflects larger differences in agent selection.

Candidate pairSemantic distanceMean Jaccard overlap
10.0390.999
20.2060.165
30.3370.069

5. Budget details. Thank you for your suggestion. Appendix C1 now reports generation and evaluation settings, LLM calls, token usage, and runtime breakdown. Together with Section 6.4, the results show that MAPF-Evo achieves lower best and mean fitness at the same candidate count, but uses more tokens. Its advantage is improved search quality within a limited number of candidate attempts, rather than lower computational cost. Solver evaluation and LLM calls account for 52.6% and 36.8% of total runtime, and are the main time costs.

Weakness 2 :

1. Table 1 correction. Thank you for your careful check. You are correct: with 3 seeds and 40 scenarios, a mean success rate of 62.50% cannot have a sample standard deviation of 0.50%. This was a transcription error in Table 1 (the correct value is 5.00%), not a different aggregation method. We apologize for the error. We rechecked all results against the original logs and, following Reviewer y9hb’s suggestion, expanded the evaluation from 3 to 10 seeds and updated all results.

2. Success rate and conflict reduction. At 100 s, exact McNemar tests show no significant success-rate gain over MAPF-LNS2 or LNS2+RL. However, the paired bootstrap 95% confidence intervals for remaining-conflict differences lie below zero against all comparison methods, supporting a significant conflict reduction. This aligns with our fitness design, which optimizes residual conflicts and iteration cost without treating success rate as a separate objective. At 200 s, LNS2+RL achieves a higher success rate. We will temper our success-rate claims and distinguish them from conflict reduction.

3. Independent evolution runs. To assess evolutionary variability, we ran MAPF-Evo 3 times independently and report each run's best-fitness curve and their mean (Appendix C.6, Figure 10(a)). All three runs improved fitness, with 4.32% relative variation in final fitness, providing preliminary support for stability across runs.

AuthorsOpenReview ↗

Response to Reviewer DhN4 (2)

Q1 :

1. Success counts and evaluation counts. Each seed evaluates the same 40 scenarios. We expanded evaluation from 3 to 10 seeds, giving 400 evaluations per method. Total success counts are:

MethodMAPF-LNS2BALANCENNSLNS2+RLTACKLEbest-onlybest-ALNS
Successes255/400213/400123/400240/400206/400244/400264/400

2. Aggregation formulas and table updates. For seed ss, the success rate is Ks/40×100%K_s/40\times100\%, where KsK_s is the number of solved scenarios. Remaining conflicts are averaged over the 40 scenarios for that seed. We then compute the mean and sample standard deviation across seeds:

SD=∑s=1n(xs−xˉ)2n−1.\mathrm{SD}=\sqrt{\frac{\sum_{s=1}^{n}(x_s-\bar{x})^2}{n-1}}.

3. Additional repetitions or weighting. Beyond the ten solver seeds, there are no additional repetitions or map/agent-count weighting.

4. Scenario counts and evaluation units in Figure 3. Each agent count in Figure 3 corresponds to 8 scenarios. The evaluation unit is the same as in the main table: one method–seed–scenario run.

Q4 :

Thank you for your detailed suggestions. We address each point below and provide the definitions and settings in the revised manuscript (Appendix C1).

1. Fitness weights and iteration cost. Fitness is F(h)=0.7R(h)+0.3T(h)+10Ninvalid(h),F(h)=0.7R(h)+0.3T(h)+10N_{\mathrm{invalid}}(h), where lower is better. R is the mean ratio of remaining to initial conflicts, T is the normalized iteration cost, and N_invalid counts instances with timeouts, crashes, or invalid outputs. Thus, w1=0.7w_1=0.7, w2=0.3w_2=0.3, and w3=10w_3=10 weight conflict reduction, iteration cost, and execution-failure penalties, respectively.

Each training scenario has an iteration budget of B=500B=500. If all conflicts are first eliminated at iteration kjk_j, then Tj=kj/(B+1)T_j=k_j/(B+1); otherwise, Tj=1T_j=1. TT averages TjT_j over all training scenarios.

2. Quality normalization and adaptive novelty weight.

Within the valid candidate pool combining parents and offspring, quality is

so lower fitness yields higher quality. The novelty weight is

λ=\lambda=

\begin{cases} 0.2,&\Delta_F\ge0.1,\ 0.4,&\Delta_F<0.1. \end{cases}

The selection score is $(1-\lambda)Q(h)+\lambda N(h\mid U)$, where $N$ is the minimum embedding cosine distance from the candidate to the selected set $U$. Smaller fitness differences increase the novelty weight to encourage exploration. Candidates with execution failures are excluded. **3. Models, population, and execution settings.** | Parameter | Setting | |---|---| | LLM generating the main-table program | Gemini-3.8 Flash | | Embedding model | Qwen3-Embedding-0.6B | | Initial candidates / Population / Offspring per generation | 8 / 6 / 4 | | Generations per run | 50 | **4. Evolution runs and program selection.** We ran 3 independent evolutions of 50 generations each. The main table uses the valid program with the lowest training fitness across all runs. **5. Calls and token costs by stage.** The following statistics cover one complete evolution run. Token counts come from the API’s usage field; M denotes million. | Stage | Calls | Input tokens (M) | Output tokens (M) | |---|---:|---:|---:| | Generation | 208 | 0.966 | 0.590 | | Scheduling | 50 | 0.067 | 0.026 | | Reflection | 50 | 0.461 | 0.067 | | Memory update | 50 | 0.070 | 0.106 | | Total | 358 | 1.564 | 0.789 | **6. Solver evaluation and total runtime.** On an Intel Core i9-14900KF, one 50-generation run takes approximately 7.1 hours.

Q5 :

1. Time budget. The budget covers the full conflict-resolution process from the shared initial paths, including state-feature construction, neighborhood selection and heuristic execution, cross-language calls, and path repair.

2. Timeout handling. We allocate no extra time for the final repair, but an ongoing low-level search cannot stop immediately at the deadline, causing Maze runtimes in Table 8 to slightly exceed 100s. This delay does not affect success-rate statistics.

3. Method settings and runtime analysis. All methods share the same initial paths and repair budget. On each method’s own solved scenarios, best-only averages 10.69 s, 40.87% below MAPF-LNS2’s 18.08 s. This reduction exceeds that obtained by pooling solved and unsolved runs. Neighborhood selection accounts for 6.08% of runtime and path repair for 93.83%, indicating that repair remains the main cost and heuristic selection accounts for a small share.

Closing Remark :

Thank you again for your careful review. Your comments helped us strengthen the experiments and better define the scope of our conclusions. We hope our revisions and responses address your concerns. Best wishes!

Reviewer_y9hbOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether the destroy heuristic of MAPF-LNS2's conflict-elimination stage — the rule that picks which agents to replan each iteration — can be authored by an LLM rather than hand-crafted. MAPF-Evo exposes a runtime-state interface (conflict graph adjacency and connected components, per-agent conflict-partner counts, first-conflict time/type/location, path detour and spatiotemporal occupancy, stagnation signals, and repair feedback), has an LLM generate executable Python destroy programs plus natural-language mechanism descriptions through four operators (complementary crossover e1, commonality enhancement e2, mechanism refinement m1, strategy restructuring m2), and evolves them on 50 training scenarios (10 per map over Empty, Random, Maze, Room and Warehouse). Fitness (Eq. 1) combines a residual-conflict ratio R, a normalized first-feasible-solution iteration-cost score T, and an invalid-run count N_invalid; population selection mixes a normalized quality score Q with an embedding-based semantic-novelty term over the LLM-written descriptions (Eqs. 2–3); short-term reflection and a long-term memory steer operator and parent scheduling. The single lowest-fitness candidate is returned and evaluated on 40 held-out scenarios (8 per map) at 100 s and 200 s budgets against MAPF-LNS2, BALANCE, TACKLE, NNS and LNS2+RL.

The headline is that inserting the evolved heuristic into the original ALNS pool (best-ALNS) raises success from 62.50% to 65.00%, cuts mean residual colliding pairs from 154.85 to 85.15 (−45.01%) and mean resolution time from 48.44 s to 42.80 s (−11.64%) relative to MAPF-LNS2 at 100 s. Supporting experiments are a four-LLM robustness sweep (Table 2), a call-share analysis (Table 3), an agent-count sweep (Fig. 3), a scheduling ablation (Fig. 4), a 200 s budget table (Table 7), time-curve plots (Fig. 7), and a five-scenario-per-map transfer probe on three unseen maps (Table 8). The paper claims to be the first to introduce LLM-driven heuristic design into LNS-based MAPF solving.

Critical strengths

The observation in §1 — that the MAPF-LNS literature has drifted toward optimising SOC on an already-feasible solution while treating conflict elimination as a solved prerequisite, even though nothing downstream can start until conflicts are gone — is a useful and correct diagnosis, and it justifies looking at the destroy rule rather than at the repair stage where most recent learning work sits. The deliverable matches that framing: unlike NNS, which must be retrained per map, MAPF-Evo returns a single readable program, and Appendix B plus Algorithm 1 do put that program in front of the reader. This matters for the decision because it means the paper's central object is auditable in principle — a reviewer can inspect what the heuristic does — and the interesting empirical signal is not confined to a binary success metric. Decomposing Table 1's mean residual into (unsolved fraction) × (mean residual | unsolved) gives 0.375 × 412.9 for MAPF-LNS2 against 0.35 × 243.3 for best-ALNS: roughly 85% of the 69.70-pair drop comes from lower residual on scenarios that remain unsolved, not from the one extra solved scenario. That is a genuine complementarity signal worth pursuing, and it is the reason the work merits a resubmission rather than abandonment.

Critical weaknesses

The headline is a pool-size change, not a test of the evolved heuristic, and the one clean test points the other way. best-ALNS runs ALNS over four heuristics {Target, CollisionGraph, Random, EvolvedBest} against MAPF-LNS2's three, so every number in the abstract comes from a four-arm-versus-three-arm comparison with no placebo arm — no randomly generated fourth program, no one-line hand-written fourth rule, no "evolved heuristic disabled but slot retained" control. A four-arm adaptive pool is a structurally different algorithm (different diversity, exploration schedule, and posterior geometry), and the paper's own Table 3 is diagnostic: the evolved heuristic takes 33.69%–37.26% of calls against 25% uniform allocation over four arms, while the three originals fall below uniform at ~20–24%; the call share is selected on measured reward by construction, so it cannot arbitrate. Meanwhile the only configuration that isolates the evolved heuristic — best-only — is 60.00% versus 62.50% at 100 s and 65.00% versus 70.00% at 200 s, and across the four LLMs the best-only rates are 35.00%, 45.00%, 60.00%, 60.00%, all at or below the unmodified pool. The paper concedes this in one clause and reframes it as "complementary strengths" without ever measuring complementarity (no per-scenario solve matrix, no selection-set diversity). Taken together, the contribution cannot currently be separated from "one more decent arm in an adaptive pool," which is precisely what the abstract claims to have surpassed. This is the belief update the paper most needs to earn and least supports.

Questions for authors
  1. Please give the per-scenario solve matrix for the four heuristics (Target, CollisionGraph, Random, EvolvedBest) across the 40 test scenarios, plus the Jaccard overlap of the agent sets they select across solver states. On what evidence is "complementary strengths" claimed rather than assumed? This determines whether the paper's causal story about best-ALNS is real or is a restatement of "four arms beat three."
  2. Add the placebo arms to Table 1 under the identical protocol: (a) the three original heuristics plus a randomly generated program satisfying the interface and returning min(k, n) agents; (b) the three originals plus a one-line hand-written rule (e.g. highest conflict-degree agent not selected last iteration); (c) the three originals plus a disabled evolved heuristic that always returns the Target selection, isolating the effect of adding a fourth ALNS slot with no new behaviour. If (a) or (b) also reaches 65.00%, the contribution collapses to "more arms help."
  3. Report per-scenario paired comparisons — exact McNemar for success, paired bootstrap or Wilcoxon for residual CP and time — over the same 40 scenario pairs, with Wilson or Clopper–Pearson intervals on every rate and a pre-declared primary comparison. Report ≥10 seeds, or drop the ± and state that the replicates are deterministic. Decompose the resolution-time metric into solved-only and unsolved components rather than averaging a censored variable, and state in the abstract that the success lead is at 100 s and that LNS2+RL leads at 200 s.
4 comments

Weakness :

Thank you for your careful review. Your key concern is that comparing pools of three and four heuristics alone cannot establish whether the gains come from pool expansion or the evolved heuristic itself. We therefore added the following experiments and analyzed differences in the selected agent sets. Our detailed responses follow:

1. Fourth-heuristic controls: pool size vs. heuristic content Following your suggestion in Q2, we added RandGen, HighDeg, and TCopy as fourth-heuristic controls to compare against EvolvedBest at the same pool size. Results are shown below and included in the revised manuscript (Section 6.1). Among these four-heuristic pools, best-ALNS achieves the highest mean success rate (66.00%) and the lowest mean remaining conflicts pairs (87.04), 28.93% below the three controls’ average (122.47). These results suggest that the gains are not merely due to a larger pool; the added heuristic’s content plays a more important role.

ConfigurationSuccess rateConflicting pairs
MAPF-LNS2 + RandGen64.25% ± 1.21%122.40 ± 17.57
MAPF-LNS2 + HighDeg64.50% ± 3.29%128.40 ± 10.49
MAPF-LNS2 + TCopy63.50% ± 2.42%116.60 ± 12.24
MAPF-Evo (best-ALNS)66.00% ± 3.57%87.04 ± 9.08

2. Pool combinations: more is not always better. Building on your suggestions, we additionally evaluated heuristic pools of increasing size, where T, C, R, and E denote Target, CollisionGraph, Random, and EvolvedBest. Mean success rate did not increase monotonically with pool size: adding C to R + E reduced it from 63.50% to 62.50%. Thus, adding more heuristics does not necessarily improve performance; the specific combination also matters.

ConfigurationSuccess rateConflicting pairs
E61.00% ± 1.75%105.35 ± 7.51
R + E63.50% ± 2.42%95.13 ± 17.45
C + R + E62.50% ± 2.36%96.74 ± 10.70
MAPF-Evo (best-ALNS)66.00% ± 3.57%87.04 ± 9.08

3. Single-heuristic comparison: clarifying the best-only results. We understand your concern about best-only results. The original comparison contrasts a single heuristic with an adaptive pool of three, so it does not isolate EvolvedBest’s quality relative to the other heuristics. We therefore compared all four heuristics individually, as shown below and added to the revised manuscript (Appendix C.4). EvolvedBest achieves a 61.00% success rate and 105.35 mean remaining conflicts, approximately 24.30% below the average of the other three heuristics. These results indicate that EvolvedBest is competitive on its own, particularly in reducing remaining conflicts.

Single heuristicSolved / 400Conflicting pairs
Target170 (42.50%)141.88 ± 12.20
Random237 (59.25%)142.21 ± 14.29
CollisionGraph241 (60.25%)133.40 ± 12.62
EvolvedBest (best-only)244 (61.00%)105.35 ± 7.51

4. Table 3 clarification. Thank you for pointing this out. We agree that the call proportions in Table 3 are adaptively determined by ALNS based on rewards and cannot independently demonstrate EvolvedBest’s effectiveness. In the revised manuscript, we interpret Table 3 only as a description of scheduling behavior in the four-heuristic pool (Section 6.3).

5. Complementarity: selection differences. Following your suggestion in Q1, we added a Jaccard overlap analysis of agent sets selected by different heuristics in the same states (Appendix C.5). EvolvedBest’s mean overlaps with Target, CollisionGraph, and Random are 0.0377, 0.0595, and 0.0180. This provides evidence of behavioral diversity, which we consider alongside the performance comparisons as supplementary support for complementarity.

Q1 :

Thank you for the suggestion. Our weakness response details the Jaccard analysis and evidence for complementarity. EvolvedBest selects different agent sets from existing heuristics in the same states, and its pool outperforms same-sized controls. Together, these findings support complementarity. The full per-scenario solution matrix is in the supplementary material. We hope these additions address your concerns.

Q2 :

Thank you for your constructive suggestions. We added all three controls under the same protocol; results are in our weakness response and Section 6.1 of the revised manuscript. EvolvedBest performs better in same-sized pools, while combination experiments show that more heuristics do not necessarily improve performance; their content also matters. We hope these additions address your concerns.

Q3 :

Thank you for your suggestions. All additional experiments used 40 scenarios and 10 seeds. Below, we compare best-ALNS with the other methods under a 100-second budget, reporting Wilson intervals for success rates, exact McNemar tests, and paired bootstrap analyses of remaining conflicts and runtime.

At 100 s, best-ALNS has the highest mean success rate (66.00%), but gains over MAPF-LNS2 and LNS2+RL are not significant. This is also consistent with the focus of our fitness design, which optimizes residual conflicts and iteration cost without including success rate as a separate objective. We report solved and unsolved runtimes separately. On each method’s own solved scenarios, best-only has the lowest mean runtime (10.69 s), 40.87% below MAPF-LNS2; all unsolved runs reach 100 s. The abstract now states that our method has a higher mean success rate at 100 s, while LNS2+RL performs better at 200 s. We hope these additions address your concerns.

MethodMcNemar pConflict difference [95% CI]Time difference [95% CI] (s)Mean solved runtime (s)Success rate [Wilson CI]
MAPF-LNS20.21875–1−54.32 [−98.47, −18.11]−5.24 [−7.85, −2.81]18.08 ± 2.1763.75% [58.93%, 68.31%]
BALANCE0.00781–0.25−68.48 [−115.28, −29.11]−13.76 [−18.47, −9.16]22.80 ± 1.6253.25% [48.35%, 58.09%]
NNS0.0000305–0.000488−190.67 [−304.11, −94.67]−29.54 [−40.46, −21.24]36.14 ± 6.7130.75% [26.43%, 35.44%]
LNS2+RL0.125–1−425.76 [−670.79, −207.10]−38.61 [−46.26, −30.47]49.39 ± 2.8860.00% [55.13%, 64.68%]
TACKLE0.00195–0.125−82.01 [−142.34, −32.60]−16.47 [−22.80, −10.64]24.99 ± 5.9251.50% [46.61%, 56.36%]
best-only0.0625–1−18.31 [−31.87, −7.38]−0.26 [−1.22, 0.55]10.69 ± 1.2861.00% [56.14%, 65.65%]
best-ALNS———14.64 ± 3.3366.00% [61.23%, 70.47%]

Closing Remark :

Thank you again for your careful review and constructive suggestions, which helped us strengthen our experiments and conclusions. We hope our revisions and responses address your concerns. With our thanks and best wishes!

Thank you for the detailed response and the substantial additional experiments. The same-size controls (RandGen, HighDeg, TCopy), the single-heuristic comparison, the revised reading of Table 3, and the updated abstract address a good part of my concerns. I also appreciate the candour in reporting that the success-rate differences are not significant.

After reading the response carefully, I am keeping my rating at 3 (weak acceptance). My remaining reservations concern the scope of what the evidence can support, rather than anything I would expect to be settled within the discussion period:

  1. Success rate. With 40 test scenarios, the advantage of best-ALNS (66.00%) over MAPF-LNS2 (63.75%) and over the same-size controls (63.50–64.50%) is within noise, as your own McNemar results indicate. This is a limit of the benchmark size, not of the analysis.

  2. Size and nature of the effect. The new controls show that the content of the evolved heuristic matters for residual conflicts, which I now see as the clearest result of the paper. They also show that part of the originally reported reduction comes from pool expansion alone: against the same-size controls the reduction is roughly 25–32% rather than 45%. Since the fitness optimises residual conflicts directly, this is a gain on the optimised objective rather than on feasibility. Complementarity remains plausible but is not yet demonstrated, as low Jaccard overlap shows that the selections differ, not that they complement each other.

  3. Method versus a single program. The controls evaluate one evolved program. Given the spread across LLMs in Table 2 (best-only between 35% and 60%), showing that the pipeline reliably produces such heuristics would require multiple independent evolution runs under the same controls, which is beyond the scope of a rebuttal.

These points bear on how strongly the claims should be worded, not on whether the work has merit, and my overall assessment remains positive. I would encourage the final version to centre the contribution on the residual-conflict result against the same-size controls. No further response is needed from my side. For the camera-ready, scenario-clustered intervals would be more appropriate than treating the 400 runs as independent. Thank you again for the constructive engagement.

Dear Reviewer y9hb,

Thank you for your careful review, constructive comments, and positive assessment of our work. Your feedback has helped us strengthen the experiments and improve the manuscript.

We will refine the final version accordingly and state our conclusions more precisely. In future work, we will carry out broader evaluations and independent evolution runs to further assess the robustness of our method and the complementarity among the heuristics.

Thank you again for your time. We wish you good health and continued success.

Best wishes,
The Authors

Reviewer_J7DPOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This is an interesting paper on synthesizing destroy heuristics for MAPF-LNS, an algorithm for Multi-Agent Path Finding. The destroy heuristic selects which "neighborhood" of agents to replan for, to try to minimize the number of conflicts they have. The idea is to let an LLM synthesize destroy heuristic, using an evolutionary algorithm where the evolution operators are calls to the LLM. Each destroy heuristic is represented by a program and a textual description. The latter is used, among other things, to quantify differences between destroy heuristics. This difference is used to ensure the population is diverse.

An experimental results show significant performance when using the generated destroy heuristics, especially when it is added to the "pool" of heuristics used by an adaptive version of MAPF-LNS (that adapts which heuristic is uses over time).

Critical strengths
  • Synthesizing heursitics with an LLM is a relevant topic
  • The experimental results are good.
  • Using LLMs as evolutionary operators is not new, yet actually making it effect is still an achievement.
  • The guidance and information given to the LLM is interesting.
Critical weaknesses

W1. The process is described very informally, leaving too much for the reader to guess. Specifically, section 4.2 loosely mentions a short term reflection and a long term memory, but it is not what these are exactly. For example, when describing the short term reflection, the authors write that the LLM "identifies effective mechanisms, ...", but it is not explained how does the LLM does this identification. Also, it is not clear what the short term reflection is expected to output. Similarly, where is the long term memory stored? what does it contains? is it unrestricted natural language? what are the "reusable insights" it considers. I also expected to see an exact list of features you used and how it was given to the LLM.

W2. I am concerned the baselines have been adapted in some way that is not fully specified. Namely, the author wrote they adapted the baselines to minimizing conflicts. I am not sure why they did this and why didn't they just run the baselines as-is.

Other issues: Section 4.2.

  • "Evaluation and selection form the initial population" - not clear what you mean here by "evaluation and selection". Which evaluation and what selection are you referring to?
  • "Each generation, the LLM jointly ..." - missing "In" in the beginning of the sentence.
Questions for authors

Q1. What does this sentence mean: Scheduling considers mechanism descriptions and fitness values in the current population" ? Q2. How is the fitness normalized? (line 248 in page 5) Q3. In page 6, you mention you adapted NNS and the other baselines to conflict elimination. Why? don't they already aim to solve the problem as fast as possible? Q4. Have you considered comparing with a LACAM based solver? Q5. Can you provide an exact list of features you used and how it was given to the LLM?

3 comments
AuthorsOpenReview ↗

Response to Reviewer J7DP: Method Clarifications and Experimental Details

W1 :

Thank you for pointing this out. We clarified these details in the revised manuscript (Sec. 4.2, Appendix A.3).

1. Short-term reflection. The LLM receives parent and offspring mechanism descriptions, offspring code, fitness, and per-instance evaluation results. It compares each offspring with its parent, analyzes mechanisms linked to performance changes, and outputs three fixed sections: (i) effective mechanisms; (ii) mechanisms to avoid; (iii) mechanisms to explore. Explanations lacking direct evidence must be labeled hypotheses. Thus, “identifying effective mechanisms” means analysis based on code and evaluation evidence, not formal proof.

2. Long-term memory. For each generation, the LLM updates existing memory using the latest reflection to retain cross-generation design experience. It has three fixed sections: (i) consistently effective mechanisms; (ii) recurring or conditional failure modes; (iii) hypotheses to test and priority exploration directions. Consistently effective mechanisms require evidence from at least two distinct generations, with conditions, supporting evidence, and counterexamples recorded.

3. Format. Both are structured natural-language texts, stored in program state and saved with the evolutionary state in local JSON checkpoints. They are fed to the LLM as labeled text during crossover and mutation. “Reusable insights” refers to accumulated design experience, now specified as “effective mechanisms, conditional failure modes, and hypotheses to test”.

W2 & Q3 :

Thank you for the question. Baselines like NNS optimize SOC from a conflict-free feasible solution, whereas our task is to obtain a feasible solution by eliminating conflicts. Thus, although both aim to solve efficiency, they address different optimization stages. NNS Appendix A.1 explicitly excludes instances without a conflict-free initial solution. To compare these baselines' neighborhood selection strategies for conflict resolution, we change only the objective from SOC to the number of conflicting pairs, keeping all other mechanisms and hyperparameters unchanged.

Other Questions :

Thank you for noting the unclear wording and grammar. We address both below: “Evaluation” embeds LLM-generated candidate heuristics into MAPF-LNS2 and computes fitness on training instances using remaining conflicts, iteration cost, and execution validity. “Selection” forms the initial population from valid candidates using a combined fitness and novelty score. We clarified these definitions in the revised manuscript (Sec. 4.2). We also changed “Each generation” to “In each generation” and will review the language throughout.

Q1 :

Thank you for noting the unclear wording. In “scheduling”, the LLM selects an evolutionary operator and parent candidates for each of four candidate-generation calls in the next generation. A candidate's “mechanism description” outlines its internal method; its “fitness value” reflects performance. These guide operator and parent selection, e.g., crossing two parents with complementary mechanisms or mutating a strong parent with room for improvement. We clarified this meaning in the revised manuscript (Sec. 4.2).

Q2 :

Thank you for the question. Fitness is f(h)=0.7R(h)+0.3T(h)+10Ninvalid(h)f(h)=0.7R(h)+0.3T(h)+10N_{\mathrm{invalid}}(h), where RR is the mean ratio of remaining to initial conflicts, TT is the mean fraction of the iteration budget used, and NinvalidN_{\mathrm{invalid}} counts instances with execution errors. Lower fitness is better.

To select the next generation, we apply min–max normalization and inversion to the pooled valid parents and offspring: Q(h)=fmax⁡−f(h)fmax⁡−fmin⁡+10−12Q(h)=\frac{f_{\max}-f(h)}{f_{\max}-f_{\min}+10^{-12}}, where fmin⁡f_{\min} and fmax⁡f_{\max} are the pool's minimum and maximum fitness. Candidates with execution errors are excluded. Higher Q(h)Q(h) is better and can be combined with novelty in a weighted sum for selection.

Q4 :

Thank you for the suggestion. We considered LaCAM, but it returns a complete conflict-free solution within the time limit or reports failure, whereas our LNS framework can return a current solution with conflicts. Thus, remaining conflicts offer no common basis for direct comparison. NNS (ICLR) and BALANCE (AAAI) also exclude LaCAM-like solvers, so we omitted LaCAM from the main table. In supplementary tests with the same budget, LaCAM solved 23/40 scenarios and MAPF-Evo (best-ALNS) solved 27/40. These results are for the reviewer's reference.

Q5 :

Thank you for the suggestion. We provide heuristic parameters (Appendix A.1) and complete feature lists for each stage (Appendix A.3) in the revised manuscript. These descriptions and corresponding state information form structured text input to the LLM.

Closing Remark :

We thank you for your patience, careful review, and encouraging feedback. Your constructive suggestions have helped us strengthen the paper. We hope our revisions and responses fully address your concerns. Best wishes!

Reviewer_J7DPOpenReview ↗

Thanks for the clarification!

The response did help clarify many points. I admit I am a bit torn still: the writing quality could (should) be improved, and even in the rebuttal I had some troubles (what is "execution validity" in this context or "inversion to the pooled valid parents and offsprin"?). I leave it up to the SPC to decide whether these concerns are significant enough. I do like the general idea of the paper.

As a side note: I am surprised that LaCAM was not stronger: are you sure you used a reasonable version of LaCAM (does not have to be the latest, of course). This is not a critical issue, as I have been convinced by the authors' argument that LaCAM is not the main baseline.

AuthorsOpenReview ↗

Response to Reviewer J7DP

Dear Reviewer J7DP,

Thank you for your reply and for your positive assessment. We sincerely apologize for the confusion caused by our unclear wording, and we will continue to use the remaining time to improve the writing and presentation of the paper. Regarding the three points you raised, our brief responses are as follows.

1. “Execution validity”: The original phrase was “using remaining conflicts, iteration cost, and execution validity.” These three items correspond to the fitness function f(h)=0.7R(h)+0.3T(h)+10Ninvalid(h)f(h)=0.7R(h)+0.3T(h)+10N_{\mathrm{invalid}}(h) (also given in our response to Q2). The first two terms express two preferences: fewer remaining conflicts is better, and lower iteration cost is better. The “execution validity” you asked about corresponds to the third term, NinvalidN_{\mathrm{invalid}}, which captures whether a candidate program generated by the LLM can actually be executed. For example, a syntax error such as a missing colon will cause execution to fail, and the third term penalizes such cases.

2. “Inversion to the pooled valid parents and offspring”: Each generation of evolution produces four offspring candidates from the parent pool. So how do we choose the parent pool for the next generation? We merge the parents with the offspring candidates and filter them jointly; this is what “pooled valid parents and offspring” means. During filtering, we consider both fitness (lower is better) and novelty (higher is better). Since the two scores point in opposite directions, the fitness score must be inverted so that both follow the “higher is better” convention — this is what “inversion” refers to.

3. The LaCAM results. We used the code repository associated with the paper “LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding” (Kei18/lacam). With a time budget of 100 seconds per instance, LaCAM solved 23 of the 40 test instances.

We hope these clarifications fully address your concerns. Improving the quality of the manuscript is our responsibility, and we would be very glad to answer any further questions you may have.

Thank you for your time and effort. We wish you and your family good health and all the best.

Sincerely,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.