{"id":"b3eec31d-3781-4343-a4b7-102e67dc8112","arxiv_id":"2607.13403","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new regret-based branch-and-bound decision-tree planner (E-PDT) allocates heterogeneous robots to temporal-logic tasks in partially known environments, claiming near-linear scaling and lower cost than a guaranteed-region-only MILP baseline.","lead":"This paper proposes a planning algorithm that lets teams of heterogeneous robots collect resources in a partially known map while satisfying temporal-logic mission rules and minimizing worst-case regret. It reports near-linear scaling to thousands of robots, but the formal optimality guarantee is undermined by a gap between the stated completeness theorem and the implemented max-edge heuristic.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's max-edge expansion contradicts Theorem 2's exhaustive-expansion assumption, so the claimed completeness and min-max regret optimality are unsupported.","rationale":"The reader's weakest assumption identifies both the Lemma 1 lower-bound ambiguity and the Theorem 2/Algorithm 2 mismatch. I focus on the latter because it is an internal inconsistency that is independently verifiable from the text: Theorem 2's proof requires exhaustive expansion over all valid subtasks, while Algorithm 2 deliberately expands only the maximum transition edge. The paper's own experimental comparison (Table I) confirms that the excluded branches can have lower theoretical regret, which means E-PDT cannot be guaranteed to solve Problem 1. This is a load-bearing gap in the central claim. I do not rest the objection on disagreement with consensus or on missing artifacts; it is a correctness risk in the formal argument as written. The reader's verdict of REJECT is therefore unchanged.","tokens_in":20571,"tokens_out":4269,"duration_ms":44504,"concrete_test":"Implement a small exhaustive enumerator for the DFA in Example 1 (or ϕ3 from Table I): at the root, branch over all enabled transitions, not just the max-atomic-proposition edge, and compute the exact min-max regret of the best full policy under the Section V-A cost model. Run E-PDT on the same instance. If the exhaustive solution has strictly lower regret than E-PDT's output, or if E-PDT returns no feasible plan on an instance with a feasible trace through a non-max edge, the claimed optimality/completeness is falsified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that E-PDT solves Problem 1, the min-max regret allocation problem, and that Theorem 2 guarantees completeness. The proof of Theorem 2 explicitly assumes that treeExpansion 'systematically generates child nodes by considering all valid subtasks from the DFA'. But Algorithm 2 (line 2) selects only the single transition edge with the maximal set of atomic propositions. This is not exhaustive: any feasible trace that requires a different first transition is never generated. The paper's own Table I admits this: traversing all transition edges (Methods 2 and 3) 'occasionally identifies alternative policies with lower theoretical regret' along branches with fewer atomic propositions. That directly contradicts the claim of finding a min-max regret policy. The issue is not repaired by Lemma 1: Lemma 1 is about admissibility of the estimated-regret lower bound, not about covering the search space, and its proof leaves H and opt ambiguous (Section IV-C). Because the search can discard the branch containing the optimum before any regret bound is even evaluated, the completeness and optimality results collapse regardless of whether the pruning bound is valid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Extended Planning Decision Tree (E-PDT), a framework for task allocation and planning of heterogeneous multi-robot systems under syntactically co-safe LTL (scLTL) specifications in partially known environments. It introduces Region-Binding Atomic Propositions (RbAP) to encode uncertainty about resource locations directly in the automaton, formulates the problem as min-max regret optimization, and uses a regret-based branch-and-bound pruning strategy inside a planning decision tree. The authors claim formal feasibility, completeness, and min-max regret optimality, plus near-linear scalability with the number of robots and robot types. Numerical scaling experiments, simulation studies, and two physical experiments are reported to support the scalability and practical utility claims.","tokens_in":20825,"tokens_out":7022,"duration_ms":74281,"significance":"The problem addressed is important: scalable multi-robot planning under temporal logic constraints and environmental uncertainty, without assuming prior probability distributions, has clear practical value in disaster response and warehouse logistics. The paper has genuine strengths: RbAP is a clean abstraction that remains DFA-compatible; the contingent policy-tree output is appropriate for online execution; the numerical experiments cover substantially larger fleets than typical formal-methods papers; and the physical experiments demonstrate real-world applicability. If the formal optimality and completeness claims were correct, this would be a significant practical and theoretical advance. However, the central theoretical claims are not supported by the algorithm as written. The mismatch between Theorem 2's exhaustive-expansion assumption and Algorithm 2's greedy single-edge expansion is load-bearing, and the admissibility proof of the pruning bound has unresolved definitional ambiguities. Because the main contribution is framed as solving Problem 1 (min-max regret) with completeness guarantees, I cannot recommend acceptance in the current form.","major_comments":[{"comment":"Theorem 2's proof explicitly assumes that treeExpansion 'systematically generates child nodes by considering all valid subtasks from the DFA.' Algorithm 2, however, initializes by selecting only the single transition edge with the maximal set of atomic propositions (Algorithm 2, line 2; Section IV-B). The search therefore never generates branches whose first DFA transition is not the maximal edge. The paper's own Table I confirms that traversing all transition edges (Methods 2 and 3) 'occasionally identifies alternative policies with lower theoretical regret' along branches with fewer atomic propositions. Since Theorem 2 does not prove that the maximal-edge choice preserves min-max regret optimality, the claimed solution to Problem 1 is unsupported. The formal claim must either be weakened to a heuristic statement, or the algorithm must enumerate all valid transitions; the latter would i","section":"§V (Theorem 2) vs. §IV-B (Algorithm 2)"},{"comment":"Lemma 1 is the sole support for admissibility of the pruning rule, but the proof does not pin down the definitions of H and opt. Section IV-C says H(Nd.O) is 'calculated strictly within Wopt, assuming the agent is simply directed to the nearest region containing the resource.' If H is the cost of a concrete nearest-region policy, it is generally an upper bound on the optimal optimistic cost-to-go, not an admissible lower bound; if it is meant to be an optimistic estimate, that property is asserted but not proved. Likewise, opt(Nd.O) is described as 'the minimum possible cost to satisfy the specification from initial given the current belief' — it is unclear whether this is computed from the initial state or from node Nd, and the two readings lead to different inequalities in the proof. Without a precise definition and proof that H is a lower bound on the optimal remaining cost for every","section":"§IV-C and §V-A, Lemma 1"},{"comment":"There is a gap between the completeness theorem and the actual pruned algorithm. Theorem 2 explicitly assumes that the min-max pruning rule is disabled. Lemma 1 then claims that the pruning strategy preserves completeness, but its proof only addresses admissibility of the estimated-regret lower bound. It does not analyze Rule 2, which prunes nodes on repeated (automaton state, observation) with a smaller regret value; no dominance argument is provided to show that a smaller regret at an intermediate node implies dominance of all future completions. It also does not address the early-exit behavior of Rule 3, which aborts policy evaluation after a single violating observation. Admissibility of a lower bound is necessary but not sufficient to prove completeness when branches can be discarded before they are generated. Thus the formal claims for the algorithm with pruning are not established","section":"§V-A, Theorem 2 vs. Definition 11"}],"minor_comments":[{"comment":"The DFA definition writes S0 ∈ S and SF ∈ S, but these should be subsets of S (S0 ⊆ S, SF ⊆ S). The notation is inconsistent with the text describing them as sets.","section":"Definition 1"},{"comment":"There are two nearly identical paragraphs describing the two-level greedy allocation mechanism. One should be removed to avoid duplication.","section":"§IV-B"},{"comment":"The last row has a typo: 'Filed' should be 'Failed'.","section":"Table III"},{"comment":"The notation N ds(π) is used in (3) but not defined before the equation. Please define it explicitly.","section":"Eq. (3)"},{"comment":"The statement 'if the min-max pruning rule is disabled' conflicts with the later assertion that the BnB strategy preserves completeness. Please clarify which theorem applies to the pruned algorithm and which applies to the unpruned tree.","section":"§V-A, Theorem 2"},{"comment":"The complexity analysis is careful to separate per-node cost from the number of visited nodes, but the abstract's 'near-linear scalability' should be qualified as being with respect to robots and types for a fixed environment and fixed scLTL formula. The worst-case N_visited remains exponential in the number of uncertain regions.","section":"§V-B"}],"recommendation":"reject","confidential_remarks":"The empirical side of the paper — scaling behavior and physical experiments — may be salvageable as a heuristic planning framework if the formal optimality and completeness claims are withdrawn. As submitted, however, the gap between Theorem 2's exhaustive-expansion assumption and Algorithm 2's greedy single-edge expansion is fundamental and affects the paper's main claim of solving Problem 1. This is not a local or presentation-level issue; it requires either a nontrivial optimality-preservation proof for the maximal-edge heuristic or a redesign of the algorithm, so I recommend rejection but would encourage the authors to resubmit an honest heuristic version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what's actually new: the paper combines RbAP (binding atomic propositions to sets of regions) with an extended planning decision tree and a regret-based branch-and-bound pruning rule. That combination is not in the PDT/regret literature I know, and it gives a concrete way to handle resource-location uncertainty without prior probabilities. The empirical scalability is the strongest part: the reported runtimes do grow near-linearly with fleet size and type count, and the physical experiments show the pipeline works on real robots. The authors also deserve credit for Table I, which honestly reports that traversing all transition edges occasionally finds policies with lower theoretical regret than the max-edge choice.\n\nThe soft spots are real. Theorem 2's proof rests on the claim that treeExpansion generates all valid subtasks, but Algorithm 2's first step selects only the single transition edge with the maximal set of atomic propositions. Those are different search spaces. The paper's own Table I admits the excluded branches can have lower regret, so the min-max regret optimality claim collapses as stated. This is not a minor proof gap; it is the load-bearing assumption. Lemma 1, which is supposed to make the pruning admissible, is also a sketch: H and opt are defined loosely, and it is not clear whether H is an optimistic lower bound or a greedy nearest-region cost, nor whether opt is the hindsight optimum from the initial state or from the current belief. A serious revision needs to pin those down.\n\nThe MILP baseline is configured to plan only toward guaranteed regions, so the \"significantly outperforming\" claim is not a fair comparison against a general MILP formulation. And there is no code or data release, which makes reproducibility hard to judge.\n\nIn short: this is a useful engineering contribution with a genuine scalability result, but the formal claims currently overstate what the algorithm does. The paper deserves a serious referee — the framework is worth engaging with — but it should not be accepted until the completeness proof is aligned with the actual expansion rule, the lower-bound argument is made precise, and the baseline comparison is fairer. I would bring it to a reading group as a case study in how to frame heuristics without overclaiming.","headline":"The E-PDT framework is a plausible practical planner with a nice scalability story, but the completeness and min-max regret optimality claims are not supported as written because Theorem 2 assumes exhaustive expansion while Algorithm 2 expands only the max-edge subtask.","tokens_in":21275,"tokens_out":3560,"would_cite":false,"duration_ms":35941,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a regret-based branch-and-bound planning tree, E-PDT, solves min-max regret task allocation for heterogeneous robot teams under temporal logic in partially known environments, preserving completeness and scaling to th","keywords":["min-max regret","task allocation","heterogeneous multi-robot systems","partially known environment","scLTL","planning decision tree","regret-based branch-and-bound","temporal logic planning"],"falsifier":"Construct the smallest environment where a potential region is empty, compute the exact regret of every policy by enumerating all environmental instantiations, and run E-PDT on the same instance; if any pruned policy has true regret below the returned policy's regret, Lemma 1 fails and the pruning rule is inadmissible. A more targeted version: check whether H(N_d.O) is ever larger than the true remaining cost under the realized environment, because the lower-bound argument requires H to be an underestimate.","tokens_in":20431,"feed_emoji":"🤖","tokens_out":5095,"duration_ms":72012,"temperature":0.7,"pith_summary":"The paper tries to establish that task allocation for large heterogeneous robot teams under temporal logic specifications can be solved efficiently even when the environment is only partially known. It formulates the problem as min-max regret: choose a contingent policy whose worst-case extra cost over a hindsight-optimal plan is minimized, without assuming probability priors on resource locations. The proposed mechanism is an extended planning decision tree whose nodes carry the automaton state, cost, belief, and regret, and a branch-and-bound rule that prunes policies once their estimated regret hits the current best global regret. The paper argues this pruning is admissible because the estimated regret is a lower bound on the true regret, and reports experiments in which the planner handles thousands of robots in seconds while outperforming mixed-integer programming baselines.","feed_headline":"Regret pruning plans 9,000 robot tasks in seconds","feed_subtitle":"A planning tree with regret-based pruning handles temporal-logic missions under resource uncertainty, beating optimization baselines.","key_machinery":"The central object is the Extended Planning Decision Tree (E-PDT), where each node stores a hybrid policy, a DFA state, predicted robot locations and times, a world belief, an accumulated cost, and a regret value. The identity that carries the argument is the estimated regret, Equation (3): for a policy, it takes the maximum over nodes of accumulated cost plus optimistic future cost-to-go minus the optimistic hindsight-optimal cost. Because both future terms are computed in an idealized world where every potential region contains the resource, the paper claims this estimate is a strict lower bound on true regret, making the branch-and-bound prune admissible.","core_discovery":"On its own terms, the paper's central claim is that the extended planning decision tree algorithm solves Problem 1 — minimizing worst-case regret over all environmental instantiations consistent with the robot team's initial belief — for scLTL tasks expressed with Region-Binding Atomic Propositions (RbAPs). The supporting results are Theorem 1 (any returned plan is a feasible accepting run on the DFA), Theorem 2 (if a feasible plan exists and regret pruning is disabled, the exhaustive tree will find it), and Lemma 1 (the estimated regret in Equation (3) is a lower bound on the true regret, so regret-based pruning preserves completeness). The empirical claim is near-linear computation in the","pith_inferences":["The paper's completeness theorem assumes the tree expands over all valid subtasks, while Algorithm 2 expands only the transition edge with the maximal set of atomic propositions; a full completeness guarantee would need either a proof that max-edge expansion preserves an optimal policy or a modified search that broadens expansion.","A direct falsification experiment within the paper's own machinery would instrument a small instance with exact regret computed by enumeration and check that no pruned policy has lower true regret than the returned policy; the paper does not report such a check.","Because the framework assumes a known static map topology with uncertain resource locations, a natural extension is coupling the regret-based tree with reactive replanning for dynamic or unknown environments, which the paper identifies as future work.","The RbAP representation could be reused beyond mobile robots: any task-allocation setting with unknown resource locations, such as sensor placement or logistics staging, can express its uncertainty as a set of region-bound atomic propositions."],"forward_implications":["If Lemma 1 is correct, the regret-based pruning rule never discards the optimal policy, so the returned contingent policy tree is guaranteed to have regret no larger than the best complete plan found.","The framework enables offline generation of a contingent policy tree; online, robots execute one branch and the real observation selects the next precomputed branch, avoiding heavy replanning.","The reported scaling means formal-specification planning for thousands of heterogeneous robots is computationally feasible, a regime where MILP-based allocation fails.","The crossover-probability experiments indicate that regret-based planning becomes better than worst-case planning once potential regions are reasonably likely to contain resources, and this threshold drops as environments grow more complex."],"fun_headline_variants":["Min-max regret planning for robots in unknown areas","Regret pruning makes multi-robot planning nearly linear","Heterogeneous robot teams: robust planning with regret bounds","Branch-and-bound regret cuts robot planning complexity","Near-linear task allocation for robots under uncertainty"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the estimated regret in Equation (3) is always a lower bound on the true regret in Equation (2), so pruning a policy whose estimated regret reaches the current upper bound can never eliminate the optimal policy.","fun_headline_variants_meta":{"raw":{"variants":["Min-max regret planning for robots in unknown areas","Regret pruning makes multi-robot planning nearly linear","Heterogeneous robot teams: robust planning with regret bounds","Branch-and-bound regret cuts robot planning complexity","Near-linear task allocation for robots under uncertainty"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000156,"raw_usage":{"total_tokens":1059,"prompt_tokens":750,"completion_tokens":309,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":494,"completion_tokens_details":{"reasoning_tokens":237}},"tokens_in":494,"tokens_out":309,"duration_ms":4574,"temperature":1.0,"reasoning_tokens":237,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T05:17:09.767804+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct the smallest environment where a potential region is empty, compute the exact regret of every policy by enumerating all environmental instantiations, and run E-PDT on the same instance; if any pruned policy has true regret below the returned policy's regret, Lemma 1 fails and the pruning rule is inadmissible. A more targeted version: check whether H(N_d.O) is ever larger than the true remaining cost under the realized environment, because the lower-bound argument requires H to be an underestimate.","supporting_citations":[],"review_version":1}