{"id":"e621e72b-ab53-42c4-9130-812155176798","arxiv_id":"2505.07779","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A receding-horizon hierarchical factorization algorithm for multi-agent path finding that reduces time-to-first-action by up to 60% versus an offline baseline.","lead":"A new online planner for multi-robot warehouses computes only a few steps of each robot's route at a time instead of solving the whole problem upfront. In tests, robots get their first move up to 60% faster than with an offline baseline, while keeping total travel time similar or better.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The factorization has no stated feasibility or completeness guarantee; if congestion resolution enlarges groups to a constant fraction of agents, the core scalability claim fails.","rationale":"The reader's weakest-assumption analysis identifies the same structural gap: the hierarchical factorization lacks a formal feasibility and termination guarantee, and congestion resolution may degrade to centralized replanning. My reading confirms this is the most load-bearing concern. The paper's empirical evidence is real but limited: two maps, 200 runs each, and per-step latencies under 30ms. Those results support a workshop-level conditional acceptance, not a proof that the method scales with agent count and horizon in general. The TNBE comparison is an appropriate first-response metric, but it only matters if subsequent planning steps keep up with execution; the paper provides per-step latency but no end-to-end makespan or throughput comparison. No theorem or pseudo-code is given, so the central claim rests on the empirical behavior of the factorization, and the group-enlargement fallback is precisely where the claimed scalability could collapse. My recommendation is unchanged: conditional acceptance pending a concrete feasibility guarantee or a stress test that rules out worst-case group growth.","tokens_in":4641,"tokens_out":4611,"duration_ms":51964,"concrete_test":"Implement the Section II algorithm and run it on random-64-64-10 with N in {100,300,500,900} and H in {5,10,20}, logging the largest reachability-group size and the number of congestion-resolution expansions per iteration. If the largest group grows roughly linearly in N for any tested H instead of remaining a small constant fraction, the parallelism advantage is not preserved. To test feasibility directly, exhaustively enumerate all start/goal configurations on a 6x6 grid with 3 agents and compare the algorithm's first move against a brute-force check that a collision-free joint move exists; any solvable instance where the algorithm fails to move would refute the implicit soundness of the factorization.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II describes the composition rule: conflict-free agents are finalized and treated as dynamic obstacles, conflicting agents are grouped by horizon-limited reachability and replanned with PIBT, and failures trigger group enlargement. The paper never states a lemma that the one-step joint plan produced by composing finalized individual trajectories with group PIBT re-plans is always executable, nor that the process terminates with a bounded group size. Because only the first move is executed each iteration, the framework can recover from many failures; however, the claimed advantage over offline planners depends on most agents being conflict-free within horizon H. No formal complexity analysis is provided, and the two benchmark maps do not establish that reachability-based grouping avoids the worst case. In a dense random map, a long horizon H can cause almost all agents to conflict, so groups may be enlarged until a single group contains O(N) agents; at that point the method computes a centralized PIBT replan over horizon H, reintroducing the scalability problem the abstract says it solves. This is the load-bearing gap between the demonstrated 30ms step times on two maps and the general claim of scalable online planning.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes Finite-Horizon Hierarchical Factorization (FHHF), an online MAPF method that plans one step at a time in a receding-horizon manner. At each iteration, robots compute individual paths in parallel; conflicts within a planning horizon H are detected; conflict-free robots are finalized and treated as dynamic obstacles, while conflicting robots are grouped by horizon-limited reachability and replanned with an adapted PIBT algorithm. If replanning fails, a congestion-resolution module enlarges the group. Only the first move of the merged plan is executed, and the process repeats. Experiments on two benchmark maps (warehouse-20-40-10-2-2 and random-64-64-10) with up to 900 robots compare the time-to-first-action (TNBE) and sum-of-costs (SOC) against the offline anytime planner LaCAM*. The authors report up to 60% reduction in TNBE and consistently lower SOC on the tested configurations, concluding that the method is a practical alternative for real-time multi-robot coordination.","tokens_in":4987,"tokens_out":6072,"duration_ms":59896,"significance":"If the empirical results are taken at face value, the method offers a useful engineering contribution: a parallelizable, online MAPF scheme with fast first-action latency and competitive solution quality on the tested benchmarks. The idea of limiting factorization to a finite horizon and grouping only conflicting agents by reachability is clearly presented and addresses a real gap in the MAPF literature. The paper also uses a reasonable anytime comparison protocol (giving LaCAM* a time budget equal to the total time of the proposed method) and reports standard deviation and min-max ranges, which is a positive sign for reproducibility. However, the manuscript is an extended abstract rather than a full paper: no formal guarantees are provided, no code is released, and the evaluation covers only two maps and one baseline. The central novelty—the hierarchical factorization—is not analyzed in terms of group-size growth, which is the key to its scalability. The contribution is therefore promising but not yet fully supported.","major_comments":[{"comment":"The paper never states a lemma or proof that the one-step joint plan produced by composing finalized individual trajectories with group PIBT replans is executable (i.e., free of vertex and edge conflicts). Since only the first move is executed, the framework can recover from many failures, but the claimed scalability relies on the assumption that most agents remain conflict-free within the horizon and that groups stay small. If the congestion resolution module keeps enlarging a group, the method degrades to centralized PIBT over O(N) agents, which reintroduces the scalability problem the abstract claims to solve. Please add a formal feasibility argument for the composition, a termination/bounded-group-size analysis of the congestion resolution, or at least an empirical study of group-size distributions on a variety of maps to support the scalability claim.","section":"Section II, Algorithm composition"},{"comment":"The experimental evaluation is limited to two maps (warehouse-20-40-10-2-2 and random-64-64-10) and a single baseline, LaCAM*. The abstract's claim that the method 'outperforms state-of-the-art offline baselines across a range of problem sizes and planning horizons' is not supported by this evidence: a range of problem sizes is shown (N=100, 500, 900) but only on these two maps, and no comparison is made to other scalable MAPF algorithms (e.g., PIBT, LaCAM, MAPF-LNS2, EECBS). Moreover, no absolute TNBE values are reported—only ratios—so the reader cannot judge the practical latency numbers. The paper also does not report success rates (i.e., whether all 200 runs completed within a time/memory limit) or the variance of group sizes. Please extend the benchmark set (at least one dense map and one maze-like map), add at least one additional baseline, and report absolute TNBE, total planning time, and success rates.","section":"Section III, Experimental setup and results"},{"comment":"The SOC comparison protocol, in which LaCAM* is allowed to refine until the proposed method has completed all planning steps, is a legitimate anytime budget but must be described with absolute times. The claim in the text that the method 'consistently yields higher-quality solutions' is based on mean SOC values, yet the figures show overlapping standard-deviation and min-max ranges in several panels (e.g., random map with N=100 and warehouse with N=500 at short horizons). Please report the actual wall-clock time budgets, use paired statistical tests (e.g., Wilcoxon signed-rank) or report the fraction of runs in which the proposed method achieves lower SOC, and clarify whether the differences are practically significant.","section":"Section III, Solution quality comparison"}],"minor_comments":[{"comment":"The phrase 'Each experiment was run 200 times' is ambiguous: what is randomized across runs (start-goal pairs, seeds, or identical instances)? If the same instances are used, explain what the variance represents.","section":"Section III, Experiment Setup"},{"comment":"The figure caption and step numbering are informative, but a formal pseudocode block (Algorithm 1) would greatly improve reproducibility and precision.","section":"Section II, Figure 1"},{"comment":"The phrase 'state-of-the-art offline baselines' appears prematurely in the abstract and introduction; the only offline baseline evaluated is LaCAM*. Please soften to 'the offline anytime planner LaCAM*' or similar.","section":"Abstract and Section I"},{"comment":"The axes are labeled 'Horizon Parameter' but the text calls it 'planning horizon H'; be consistent. Also, the figures use ×10^4 on the SOC y-axis; consider normalizing SOC by the lower bound or the number of agents to make comparisons more interpretable.","section":"Section III, Figures 2 and 3"},{"comment":"The sentence 'This yields solution quality competitive with leading offline methods' is stronger than what the experiments show; the method only outperforms LaCAM* on two maps. Please align the conclusion with the evidence.","section":"Section IV, Discussion and Conclusion"},{"comment":"Reference [14] is appropriate, but the paper would benefit from citing the current MAPF benchmark suite and the most recent LaCAM* variants more precisely (references [12] and [13] are both arXiv preprints).","section":"Section I, Related Work"},{"comment":"The sentence 'we observe a 60% reduction in TNBE' at N=900, H=20 should be accompanied by the exact absolute TNBE values for both methods, as a single ratio can be misleading if the baseline is very fast.","section":"Section III, Time needed before execution"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is quite short and reads like a workshop or extended abstract. The core idea is nice, but for a serious journal the experimental and theoretical support need strengthening. No issues with citations or novelty. The paper appears to be from a well-known group, and the Amazon support is acknowledged. I would encourage the editors to treat it as a promising but incomplete contribution that could become publishable after substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is not a rehash. The finite-horizon hierarchical factorization — parallel greedy individual planning, conflict detection over horizon H, finalizing conflict-free robots, grouping the rest by reachability, PIBT replanning, execute one step — is a new architecture. It directly targets time-to-first-action, a metric that matters in warehouses and one that offline planners structurally can't optimize. The 60% TNBE reduction over LaCAM* is plausible from the method, and letting LaCAM* keep refining until their own planner finishes makes the SOC comparison conservative in the baseline's favor. That's the right instinct.\n\nThe paper also does a few things honestly: it reports mean, std, and min-max; it shows the random map's non-monotonic behavior with H instead of hiding it; and the exposition is clear about the pipeline.\n\nNow the soft spots. They are real but not disqualifying. Experiments are two maps and one baseline. LaCAM* is a strong anytime solver, but \"outperforming state-of-the-art offline baselines across a range of problem sizes and planning horizons\" is a claim that needs more baselines (CBS-family, MAPF-LNS2, other LaCAM variants) and more maps before it can be taken at face value. The comparison budget — TNBE measured while LaCAM* runs without a time cap — is fine for latency but makes the SOC comparison hard to interpret; they should report wall-clock time to a given suboptimality gap or similar.\n\nThe bigger gap is formal. The composition rule — finalized conflict-free agents treated as dynamic obstacles, conflicting agents group-replanned with PIBT, groups enlarged on failure — has no stated lemma that the one-step joint plan is always executable, nor that group size stays bounded. The stress-test worry that dense scenarios can produce groups of size O(N), collapsing the factorization, is a real unresolved question. The one-step execution buffer softens this, because the planner can recover next iteration, but the claim that the method \"preserves feasibility\" or scales better than centralized replanning needs a guarantee or at least a characterization of when the factorization succeeds. The paper gestures at future work on \"tighter guarantees,\" which is fine, but the guarantees are load-bearing for the scalability claim, not a side detail.\n\nAlso, no code is released, and the video link is not a substitute. For a systems-style paper in robotics, code would materially raise confidence.\n\nBottom line: I'd send this to peer review. The core idea is worth evaluating, the latency metric is practically important, and the experiments, while thin, are honestly reported. A serious referee should ask for more baselines, a feasibility/complexity analysis of group enlargement, and code. I'd probably cite it if I worked on MAPF; I'd bring it to reading group as an example of receding-horizon factorization.\n\nRecommendation: accept with major revision if the formal gap is addressed; otherwise this is a workshop-paper-to-strong-short-paper with the right idea.","headline":"A genuinely new online MAPF architecture with a meaningful latency result, but the evidence is thin (two maps, one baseline, no code) and the scalability claim rests on an unproven assumption about group sizes.","tokens_in":5329,"tokens_out":2124,"would_cite":true,"duration_ms":21623,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A receding-horizon, hierarchically factored multi-agent path-finding planner lets large robot fleets start acting before any complete joint plan exists, cutting time-to-first-action by up to 60% on benchmark maps while keeping solution…","keywords":["multi-agent path finding","finite-horizon planning","hierarchical factorization","parallel planning","conflict resolution","time-to-first-action","warehouse robotics","PIBT"],"falsifier":"On a dense grid where every robot conflicts within the next $H$ steps, run the method and measure whether all agents collapse into a single reachability group; if time-to-first-action then grows with fleet size roughly as fast as an offline planner, the claimed scalability fails. More directly, after executing the first-step plans, check whether any agent enters a vertex occupied by a finalized robot within the following $H$ timesteps, which would falsify the composability assumption.","tokens_in":4487,"feed_emoji":"🤖","tokens_out":6578,"duration_ms":63293,"temperature":0.7,"pith_summary":"The paper tries to establish that multi-agent path finding can be solved online, one timestep at a time, without losing solution quality to offline planners. It proposes a finite-horizon hierarchical factorization: robots plan individually in parallel for the next $H$ steps, conflict-free robots are finalized as dynamic obstacles, and only robots that actually conflict are grouped and replanned together. This shifts most computation from a single exponential joint search to many small parallel subproblems. If the claim is right, large fleets can begin executing their first moves almost immediately, and later moves can be planned while robots are already acting. The reported experiments show up to a 60% reduction in time-to-first-action and lower sum-of-costs than the LaCAM* baseline on two benchmark maps.","feed_headline":"Warehouse robots start moving up to 60 percent sooner","feed_subtitle":"Online horizon-based planning keeps fleets acting immediately while matching offline solution quality.","key_machinery":"The load-bearing object is the two-level factorization controlled by the horizon parameter $H$. The first level uses spatial-hash conflict detection to split agents into finalized conflict-free robots and conflicted robots; the second level groups only the conflicted robots by reachability within $H$ and solves each group with the PIBT algorithm, enlarging groups through congestion resolution when replanning fails. This decomposition is what makes planning parallelizable: most robots stay conflict-free over short horizons, so the expensive joint search is confined to small groups, and executing only the first step keeps the plan adaptive.","core_discovery":"On its own terms, the paper claims that the MAPF problem can be factored by a finite planning horizon $H$ into a fast individual layer and a targeted conflict-resolution layer. At each iteration every robot first computes a greedy plan; a spatial-hash conflict check over the next $H$ timesteps finalizes the conflict-free robots, which then serve as moving obstacles. The remaining robots are recursively grouped by horizon-limited reachability and replanned with the PIBT routine; when a group replan fails, a congestion-resolution module enlarges the group until it succeeds. Only the first move of the merged trajectory is executed, and the cycle repeats. The paper's experimental claim is that this pipeline, run with 12 threads, completes each planning step in under 30 ms even with 900 robots, reaches first action up to 60% faster than LaCAM*, and produces better sum-of-costs on the warehouse map and competitive or better results on the random map.","pith_inferences":["Because only one step is committed per cycle, the same factorization should extend directly to lifelong MAPF with online task arrivals, although the paper only lists this as future work.","The non-monotonic horizon effect seen on the random map suggests an adaptive controller that tunes $H$ by local robot density could improve average solution quality; this is not tested in the paper.","A formal proof that finalized dynamic obstacles and group replans compose feasibly would turn the empirical claim into a guarantee; one testable route is verifying that every group replan avoids finalized robots exactly for the full $H$ steps, not just the first.","The 60% time-to-first-action reduction should be re-measured under different thread counts and denser maps, since the speedup rests on most robots staying conflict-free within the horizon; at high density that fraction shrinks."],"forward_implications":["The first move of every robot is fixed and executable before any complete joint plan is computed, so fleets start acting immediately and planning continues while they move.","Because conflict-free robots are never replanned over the horizon, the joint-search bottleneck is confined to small conflict groups, keeping each planning step under 30 ms at the tested scales.","The online cycle naturally adapts to new conflicts or changes each timestep, since only the current first step is committed and later steps are recomputed from the new state.","On structured maps longer horizons improve solution quality by resolving conflicts earlier; on random maps an intermediate horizon balances coordination against the cost of drawing more robots into replanning."],"supporting_citations":[{"why":"Supplies the LaCAM* baseline whose time-to-first-action and sum-of-costs are compared throughout the experiments.","marker":"[12]"},{"why":"Provides the PIBT priority-inheritance backtracking routine used to replan conflict groups and resolve conflicts.","marker":"[19]"},{"why":"Defines the MAPF problem, vertex/edge conflict semantics, and the benchmark maps used in the experiments.","marker":"[4]"},{"why":"Identifies the engineered LaCAM* variant as the state of the art for near-optimal offline planning, motivating the choice of baseline.","marker":"[13]"},{"why":"Prior subdimensional expansion approach that the paper positions as a bottom-up factorization over the full horizon, in contrast to the proposed finite-horizon factorization.","marker":"[7]"}],"fun_headline_variants":["Receding-horizon MAPF cuts first-move delay by 60%","Finite-horizon factorization speeds robot fleets","Plan-ahead robots act 60% faster via hierarchical MAPF","Online MAPF: first move in 30ms, 60% sooner","Robot fleets move sooner with horizon-based planning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm assumes that treating conflict-free robots as fixed moving obstacles and composing their one-step moves with separately replanned groups always produces an executable joint plan; the paper demonstrates this empirically on two maps but gives no formal feasibility proof.","fun_headline_variants_meta":{"raw":{"variants":["Receding-horizon MAPF cuts first-move delay by 60%","Finite-horizon factorization speeds robot fleets","Plan-ahead robots act 60% faster via hierarchical MAPF","Online MAPF: first move in 30ms, 60% sooner","Robot fleets move sooner with horizon-based planning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000195,"raw_usage":{"total_tokens":1310,"prompt_tokens":852,"completion_tokens":458,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":369}},"tokens_in":468,"tokens_out":458,"duration_ms":4352,"temperature":1.0,"reasoning_tokens":369,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:07:31.496180+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a dense grid where every robot conflicts within the next $H$ steps, run the method and measure whether all agents collapse into a single reachability group; if time-to-first-action then grows with fleet size roughly as fast as an offline planner, the claimed scalability fails. More directly, after executing the first-step plans, check whether any agent enters a vertex occupied by a finalized robot within the following $H$ timesteps, which would falsify the composability assumption.","supporting_citations":[{"cited_title":"Priority inheritance with backtracking for iterative multi-agent path finding","cited_arxiv_id":null,"evidence_quote":"Provides the PIBT priority-inheritance backtracking routine used to replan conflict groups and resolve conflicts."},{"cited_title":"Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T","cited_arxiv_id":null,"evidence_quote":"Defines the MAPF problem, vertex/edge conflict semantics, and the benchmark maps used in the experiments."},{"cited_title":"Subdimensional expansion for multirobot path planning","cited_arxiv_id":null,"evidence_quote":"Prior subdimensional expansion approach that the paper positions as a bottom-up factorization over the full horizon, in contrast to the proposed finite-horizon factorization."}],"review_version":1}