{"id":"618d5e6f-7825-4737-a51c-5e0ecf4f3d2c","arxiv_id":"2412.01277","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper proves wait actions are redundant in Action Dependency Graphs and presents a quasi-linear-time construction algorithm (SCP) that produces sparser graphs.","lead":"This paper improves the Action Dependency Graph framework for multi-robot plan execution by proving that wait actions can be removed without breaking correctness, and by introducing a faster graph construction algorithm (SCP). A generalist reader might care because these changes could make warehouse-scale multi-robot coordination faster and the graph-building step far cheaper.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 2's formal OR condition is too weak to support Theorems 1–3, so the central redundancy and SCP-correctness claims are not proven as stated.","rationale":"The reader identified Definition 2 as the weakest assumption; my read agrees and sharpens it: the formal statement is not merely an unverified condition but is internally inconsistent with the prose and with the proof steps. Theorems 1 and 2 both rely on Definition 2 to rule out equal time steps, and Theorem 3 relies on it to rule out equal start vertices among candidate actions. Under the literal OR condition, those equalities are allowed, so the proofs do not go through. This is load-bearing because wait-action redundancy and SCP correctness are the paper's two principal contributions. The SCP runtime analysis and the sparsity claim are plausible, and Algorithm 3's odd k-- then continue branch appears to be a harmless dead branch rather than a correctness bug, so I do not see a deeper flaw. A corrected Definition 2, together with a benchmark check that the solutions satisfy it, would resolve the concern. That is a fixable revision, so the reader's CONDITIONAL verdict remains appropriate and my read does not change it.","tokens_in":8471,"tokens_out":21791,"duration_ms":201046,"concrete_test":"Build the minimal two-action instance satisfying Definition 2 literally: w=<v,v,t,R> (a wait) and a'=<u,v,t,R'> with u≠v. This instance has a'.t=w.t and a'.g=w.s, so Theorem 1's first bullet claims a contradiction with Definition 2, yet no contradiction exists under the OR formalization. Check whether the claimed redundancy w→a' still holds in this instance; if it fails, replace the OR in Definition 2 with the intended condition (a.s≠b.s AND a.g≠b.g, plus the analogous start/end exclusions) and re-verify Theorems 1–3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 2 states: if a.t=b.t then a.s≠b.s ∨ a.g≠b.g. This forbids only actions that share both start and goal at the same time. It does not forbid two actions with the same start vertex and different goals, nor one action ending at a vertex while another starts there, nor a second action ending at a wait action's vertex at the wait's time step. That matters because Theorems 1 and 2 use Definition 2 to force strict inequalities: in Theorem 1, a'.t>w.t is inferred from a'.g=w.s and a'.t≥w.t, but under the literal definition a'.t=w.t with a'.s≠w.s is permitted, so the inference fails. Theorem 3 begins by asserting that no two consecutive candidate actions can have the same time step, which requires forbidding equal start vertices at equal times; the OR condition does not. Thus the two central claims, that wait actions contribute no unique dependencies and that SCP preserves execution correctness, do not follow from the definition as written. The prose of Definition 2 suggests a stronger intended collision-freedom condition, but the paper does not state it precisely or verify that the benchmark solutions satisfy it. The evaluation also silently excludes pre-computed solutions that led to cycles in the ADG, so the empirical data may not even satisfy the intended condition. Fixing the OR to the intended conjunction is likely straightforward, but until then the proofs are formally invalid.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the computational cost of constructing an Action Dependency Graph (ADG) for multi-agent path-finding plans. It makes two principal claims: (i) wait actions are redundant and can be removed from the ADG without altering the action execution order, which also leads to faster execution; and (ii) a new construction algorithm, Sparse Candidate Partitioning (SCP), builds the ADG in O(n log n) time and produces at most one incoming type2 dependency per action. The paper reports experiments on a standard MAPF benchmark comparing construction runtimes of the exhaustive, candidate-partitioning, and SCP algorithms, plus a simulation of execution makespan with and without wait actions.","tokens_in":8747,"tokens_out":13879,"duration_ms":118793,"significance":"The problem is relevant: the original ADG construction is quadratic, and reducing both construction time and graph density has practical value for lifelong MAPF and warehouse execution. The paper's strengths are a clearly stated formal framework, a public implementation, and the use of a standard MAPF benchmark. If the technical gaps identified below are repaired, the claimed improvements would be a useful, modest step toward scalable ADG construction. The empirical part is weaker: the makespan experiment is a simulation whose main conclusion is largely built into the chosen speed parameters, so it does not by itself validate the abstract's claim about real robot systems.","major_comments":[{"comment":"The formal condition 'if a.t=b.t then a.s≠b.s ∨ a.g≠b.g' only excludes actions that share both the same start and the same goal at the same time step. It permits one action to start at a vertex while another action ends there, and it permits two actions to share a start vertex (or an end vertex) at the same time if their other endpoint differs. Theorems 1, 2, and 3 all rely on the stronger property that no vertex is used by two actions at the same time step; for example, in Theorem 1, the case a'.t=w.t with a'.g=w.s is not excluded by the stated disjunction. Please replace the formal condition with the intended collision-freedom condition, e.g., for all a,b with a.t=b.t, require a.s, a.g, b.s, and b.g to be pairwise distinct (or state the exact intended vertex-occupancy condition), and verify that the benchmark plans satisfy it.","section":"Section 2, Definition 2"},{"comment":"Lines 9-11 of Algorithm 3 contain a concrete bug: when k<0 or c_k.R=a_i.R, the pseudocode executes k←k−1 and then 'continue', so no type2 dependency is added even if an earlier candidate from a different robot exists. The binary-search step is supposed to find the latest candidate with c_k.R≠a_i.R; as written, it simply skips the action entirely. This means the constructed graph need not satisfy Theorem 3. Replace the conditional with a loop that decrements k while k≥0 and c_k.R=a_i.R, then adds the dependency if k≥0.","section":"Section 3.3.1, Algorithm 3"},{"comment":"After wait actions are removed, consecutive remaining actions of the same agent generally have time steps that differ by more than one. Definition 3 still defines a type1 edge only when a.t=b.t−1, so the instruction in Section 3.2 to 'connect all consecutive actions of the same shuttle with type1 dependencies' is inconsistent with the formal definition. Without a revised definition of type1 edges, based on order in the reduced plan rather than on consecutive time steps, the proof that removing waits does not alter the action execution order is incomplete.","section":"Section 3.2 and Definition 3"},{"comment":"The proof that every consecutive candidate pair c_i, c_{i+1} satisfies c_i⇝c_{i+1} only treats the case where c_i→b_{i+1} is created as a type2 edge. If c_i and c_{i+1} belong to the same robot, then b_{i+1} has the same robot as c_i, so no type2 edge c_i→b_{i+1} is added, and if c_i=b_{i+1} the edge would be a self-loop. The proof should split this case and use the type1 chain between same-robot actions. As written, the theorem's proof does not cover all candidate pairs.","section":"Section 3.3.2, proof of Theorem 3"},{"comment":"The evaluation excludes pre-computed solutions that led to cycles in the ADG without reporting how many or why, so the reader cannot assess whether the retained subset is representative or whether those solutions violate the assumptions behind Definition 2 and the ADG construction. In addition, the makespan simulation hard-codes consecutive moves at 0.8s and isolated moves/wait actions at 1.0s, so the observed improvement when wait actions are omitted follows directly from this modeling choice. This does not support the abstract's claim of faster overall execution on real robot systems; please report the excluded cases and present the makespan result as an illustrative simulation or provide empirical/kinematic support.","section":"Section 4.2, experimental evaluation"}],"minor_comments":[{"comment":"The statement contains the typo \"a'→w.t\"; the target of the dependency should be the wait action w, not a time value.","section":"Section 3.1, Theorem 2"},{"comment":"The sentence \"we will show that every candidate action c_i is reachable from a\" states the reverse of the intended claim; the notation c_i⇝a means a is reachable from c_i, so the wording should be aligned with the notation.","section":"Section 3.3.2, first paragraph"},{"comment":"The pseudocode for both CP and SCP does not show the type1 construction step; please state explicitly that type1 edges are added before the loops so that the full construction is unambiguous.","section":"Section 3.2, Algorithms 2 and 3"},{"comment":"The text uses \"shuttle\" and \"agent\" interchangeably; a single consistent term would improve readability.","section":"Section 4.2, notation"}],"recommendation":"major_revision","confidential_remarks":"This is a promising paper with a fixable formal gap. The central issue is that the written definition of collision freedom is weaker than what the proofs need; once that is corrected, the wait-redundancy and SCP-correctness proofs are likely repairable, and the Algorithm 3 loop bug is straightforward to fix. The editor may also wish to ensure that the makespan experiment is reframed as a simulation rather than as evidence about real robot systems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives two things the ADG community can use: a proof that wait actions are redundant (prior SE-ADG work removed them without proof) and the SCP construction algorithm that brings worst-case construction down to O(n log n) and at most one type2 dependency per action. The core ideas are good. The wait argument is conceptually simple and correct under the standard collision-freedom reading of MAPF solutions. SCP's observation that only the latest candidate needs a direct edge, with earlier candidates reachable through the next action's type1 chain, is sound in spirit, and the runtime plots show the expected trend. Code and benchmark are public, which is real evidence.\n\nThe soft spots, in order of severity: First, Definition 2 is formally too weak. The prose says no two actions start or end at the same vertex at the same time, but the formal condition (if a.t=b.t then a.s≠b.s ∨ a.g≠b.g) only forbids identical start and goal pairs. It permits an action to end at a wait's vertex at the same time step, which Theorems 1 and 2 need to exclude. The stress-test is right: the proofs as written don't go through. The intended condition is obvious, and fixing it is a one-line change, but it is load-bearing.\n\nSecond, Theorem 3's proof omits the case where two consecutive candidate actions belong to the same robot. That case is probably handled by the type1 dependency between them, but the proof should say so. Third, Algorithm 3's pseudocode is wrong: the k<-k-1 branch after a same-robot or negative check does not loop, can produce a negative index, and then falls through to add the dependency anyway. Fourth, the abstract says \"real robot systems,\" but the makespan experiment is a discrete-event simulation with a hand-set faster-consecutive-move parameter (0.8s vs 1.0s). That is fine as an illustration, not as a measured claim. Finally, the paper excludes pre-computed solutions that produced cycles; it discloses this, but it narrows the evaluation.\n\nNone of this changes my view that the underlying results are likely correct and useful. The paper is a contribution, not a breakthrough. It deserves a serious referee: the fixes are routine, and the wait-redundancy proof and SCP algorithm are worth having in the literature. I'd send it out.","headline":"Useful incremental ADG results—wait-action redundancy and O(n log n) SCP construction—but Definition 2 as written undercuts the proofs; worth reviewing after a straightforward fix.","tokens_in":9249,"tokens_out":3437,"would_cite":true,"duration_ms":29917,"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":"This paper proves that wait actions can be safely removed from Action Dependency Graphs for multi-robot plans without changing execution order, and that Sparse Candidate Partitioning builds such graphs in $O(n \\log n)$ time with at most…","keywords":["MAPF","ADG","Runtime Optimization","Multi-Agent Systems","Plan Execution","wait actions","Sparse Candidate Partitioning","multi-agent path finding"],"falsifier":"Take any benchmark plan and compare the transitive closure of the exhaustive ADG built with wait actions against the SCP graph built without them; if any action becomes unreachable from another after removing wait actions and keeping only the latest candidate edge, the redundancy or SCP theorems are false. A second check is to scan the benchmark solutions for actions that start or end at the same vertex and time step, since the paper's scope condition is never verified.","tokens_in":8235,"feed_emoji":"🤖","tokens_out":8072,"duration_ms":69157,"temperature":0.7,"pith_summary":"Multi-agent path finding (MAPF) plans are often executed through an Action Dependency Graph (ADG), where edges say which robot action must finish before another starts. This paper tries to establish two improvements to that framework. First, it proves that wait actions—actions where a robot stays in place—contribute no unique dependencies, so they can be removed from the graph without altering execution flow, and removing them can shorten the overall makespan when robots move faster in consecutive motion than in stop-and-go. Second, it proves that for each action only the latest conflicting action from another robot needs to be linked, which yields the Sparse Candidate Partitioning (SCP) algorithm with worst-case $O(n \\log n)$ construction time and at most one incoming dependency per action. If correct, ADG construction scales to much larger robot fleets and runs with less communication and memory overhead.","feed_headline":"Dependency graphs for robot plans: wait actions are redundant","feed_subtitle":"Removing waits shortens makespans; new SCP algorithm builds these graphs in quasi-linear time.","key_machinery":"The central object is the Action Dependency Graph (ADG), a directed acyclic graph whose vertices are actions and whose edges are type1 dependencies (consecutive actions of the same robot) and type2 dependencies (conflicts between different robots). The proof engine is the candidate action list: for each action $a$, the candidate set $C$ of actions that end where $a$ starts, sorted by time, reduced by SCP to just the latest candidate from a different robot. The key identity carrying the argument is that consecutive candidate actions cannot share a time step, so a chain of indirect dependencies connects all earlier candidates to the latest one, while wait actions collapse onto their neighboring move actions.","core_discovery":"The paper's central claim is that wait actions are redundant in the ADG framework. Given a valid MAPF solution (no two actions start or end at the same vertex at the same time step), any dependency that involves a wait action—either a dependency from the wait action to another agent's action or from another agent's action to the wait action—is already implied through the wait action's neighboring move action via type1 dependencies (Theorems 1 and 2). Hence every wait action can be deleted without changing which actions are reachable from which. The second claim is that in constructing the remaining graph, a single type2 dependency per action suffices: for an action $a$, only the latest candidate action $c_k$ from a different robot with $c_k.t \\le a.t$ needs a direct edge, because all earlier candidate actions remain reachable through chains of consecutive candidate actions (Theorem 3). This justifies SCP, which sorts candidate lists and uses binary search, and the authors show by runtime analysis and benchmark experiments that construction becomes $O(n \\log n)$ and generates at most one incoming type2 dependency per action.","pith_inferences":["The redundancy proof relies entirely on Definition 2, so plans that allow simultaneous vertex entry and exit, such as agents swapping positions within one time step, fall outside the guarantee; checking benchmark solutions for such violations would be a cheap empirical scope check.","The experimental section excludes benchmark solutions that produce cycles in the ADG, so the reported runtimes and makespan gains are measured only on the subset of plans that admit an acyclic dependency graph; how often this exclusion occurs on real solver outputs is not quantified.","Since SCP keeps only the latest incoming candidate, the type2 edges form chains per goal vertex; this structure might allow execution schedules to be maintained incrementally when agents are delayed, a direction the paper does not explore.","The makespan improvement from dropping wait actions is conditional on consecutive moves being faster than stop-and-go; if a robot's motion controller does not exploit continuous motion, the benefit disappears even though the redundancy proof still holds."],"forward_implications":["ADG construction for a plan with $n$ actions drops from worst-case quadratic to $O(n \\log n)$, enabling repeated graph rebuilding in lifelong MAPF settings.","Every action in the constructed graph has at most one incoming type2 dependency, so communication and memory overhead per agent shrink.","Omitting wait actions removes a source of unnecessary synchronization: if a preceding robot finishes early, the dependent robot can start immediately, shortening makespan in simulations and on robots with fast consecutive motion.","The sparser graph makes the ADG framework more practical for fleets with hundreds to thousands of agents."],"supporting_citations":[{"why":"Defines the original ADG framework and its quadratic construction algorithm that this paper streamlines; supplies the baseline definitions and the exhaustive-check approach.","marker":"[8]"},{"why":"Provides the pre-computed MAPF solutions from six maps on which construction runtime and makespan experiments are run.","marker":"[13]"},{"why":"The official MAPF benchmark suite from which the six test maps and scenarios are drawn.","marker":"[11]"},{"why":"Prior work that transforms an ADG into a spatially exclusive graph without wait actions; this paper contrasts with that by proving wait actions can simply be dropped.","marker":"[3]"},{"why":"Establishes the MAPF problem formulation and the notion of valid collision-free solutions that underpin Definition 2.","marker":"[12]"}],"fun_headline_variants":["Wait actions are redundant: robot plans run faster","Removing wait actions cuts graph size and build time","Wait actions redundant: new SCP graph construction is quasi-linear","Streamlined ADG: drop waits, build graphs quasi-linearly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Definition 2: a valid MAPF solution never has two actions that start or end at the same vertex at the same time step; if a planner's plans violate this, both the wait-action redundancy proof and the SCP correctness proof fail.","fun_headline_variants_meta":{"raw":{"variants":["Wait actions are redundant: robot plans run faster","Removing wait actions cuts graph size and build time","Wait actions redundant: new SCP graph construction is quasi-linear","Streamlined ADG: drop waits, build graphs quasi-linearly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000879,"raw_usage":{"total_tokens":3787,"prompt_tokens":916,"completion_tokens":2871,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":2804}},"tokens_in":532,"tokens_out":2871,"duration_ms":18656,"temperature":1.0,"reasoning_tokens":2804,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T04:32:33.341869+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any benchmark plan and compare the transitive closure of the exhaustive ADG built with wait actions against the SCP graph built without them; if any action becomes unreachable from another after removing wait actions and keeping only the latest candidate edge, the redundancy or SCP theorems are false. A second check is to scan the benchmark solutions for actions that start or end at the same vertex and time step, since the paper's scope condition is never verified.","supporting_citations":[{"cited_title":"Durham, and Nora Aya- nian","cited_arxiv_id":null,"evidence_quote":"Defines the original ADG framework and its quadratic construction algorithm that this paper streamlines; supplies the baseline definitions and the exhaustive-check approach."},{"cited_title":"Stuckey, and Daniel Harabor","cited_arxiv_id":null,"evidence_quote":"The official MAPF benchmark suite from which the six test maps and scenarios are drawn."}],"review_version":1}