- 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
-
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.
-
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
-
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.
-
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
-
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 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.
-
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.
-
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.
-
Please clearly specify , the normalization of iteration costs, the normalization of quality, the adaptive formula for , 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.
-
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
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:
Method MAPF-LNS2 BALANCE NNS LNS2+RL TACKLE best-only best-ALNS Successes 255/400 213/400 123/400 240/400 206/400 244/400 264/400 2. Aggregation formulas and table updates. For seed , the success rate is , where 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:
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 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, , , and weight conflict reduction, iteration cost, and execution-failure penalties, respectively.
Each training scenario has an iteration budget of . If all conflicts are first eliminated at iteration , then ; otherwise, . averages 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
\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!
Response to Reviewer DhN4 (1)
Weakness 1, Q2 & Q3 :
Weakness 2 :