{"id":"dcb90215-4724-441a-88b3-d08f0ec400a7","arxiv_id":"1908.04425","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A receding-horizon sequential greedy policy with a 1/2 optimality guarantee is proposed for multi-agent persistent monitoring with concave resetting rewards, augmented by a terminal nodal-importance term.","lead":"This paper gives a greedy algorithm with a proven quality bound for sending multiple mobile robots to patrol a network of locations that need repeated visits. It is relevant to robotics and control because it turns an exponential scheduling problem into a polynomial-time rule with a guaranteed worst-case performance.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2's 1/2 gap is unsupported as written: the proof of Theorem 3.1 only handles concatenated visit sequences, while added policies interleave visits; Corollary 4.1 is also stated in the wrong direction.","rationale":"The reader's weakest-assumption analysis and my stress-test converge on the same load-bearing point: Theorem 3.2's approximation factor is only as solid as Theorem 3.1's submodularity claim, and the written proof of Theorem 3.1 does not cover the actual interleaving of visits caused by adding a new agent policy. The lemmas in the appendix are formulated for concatenated sequences, so the marginal reward comparison for a candidate policy that inserts visits between existing visits is not established. The reversed inequality in Corollary 4.1 is a concrete internal inconsistency: the proof concludes the opposite of the stated claim, and Lemma A.3 requires the corrected direction. Both issues are plausibly repairable: the per-interval insertion benefit F(u,v)=ψ(u)+ψ(v)-ψ(u+v) is monotone in u and v for concave increasing ψ, which would prove submodularity for interleaved visits, and the Corollary is likely a typo rather than a fatal flaw. Thus the mathematical claim may be true, but as written the central guarantee is not rigorously supported. This matches the reader's CONDITIONAL assessment, so no change to the verdict is warranted.","tokens_in":13984,"tokens_out":7300,"duration_ms":79174,"concrete_test":"Perform an exhaustive small-instance verification of submodularity for interleaved policies. Take one or two nodes, a concave increasing reward such as ψ(t)=sqrt(t) or ψ(t)=log(1+t), a fixed last-visit time t0=0, mission horizon up to 10, and enumerate all visit-time policies of length up to 4 for each of 2 agents. For every pair Q1⊂Q2 disjoint from a candidate policy q, compute ΔRbar(q|Q1) and ΔRbar(q|Q2) directly from the sorted visit times, and check whether ΔRbar(q|Q1) ≥ ΔRbar(q|Q2) always holds. Also test the stated Corollary 4.1 with a=1, b=1, c=4, d=4 and f=sqrt to confirm the printed inequality is reversed. If a submodularity counterexample is found, Theorem 3.1 is false; if none is found, the proof gap is repairable and the conditional verdict stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central approximation guarantee in Theorem 3.2 depends entirely on Theorem 3.1, which asserts that the augmented utility Rbar in (5) is monotone submodular. The proof of Theorem 3.1 invokes Lemmas A.2 and A.3, but both lemmas are proved only for visit sequences produced by concatenating a new sequence after the existing sequence at a node: (a) = (t) ⊕ (u) or (a) = (t) ⊕ (u) with (v) a subsequence of (t). In the actual multi-agent problem, adding a policy inserts visits at times that lie between previously scheduled visits from other agents, so the concatenation hypothesis is not satisfied. Consequently, the marginal-diminishing inequality ΔRbar(q|Q1) ≥ ΔRbar(q|Q2) required for submodularity is not derived for the interleaved case. Additionally, Corollary 4.1 as printed asserts f(c)+f(d)-f(c+d) ≤ f(a)+f(b)-f(a+b) for 0≤a≤c, 0≤b≤d, but the proof concludes the reverse inequality, and simple examples (f=sqrt, a=b=1, c=d=4) show the printed direction is false. Lemma A.3 needs the opposite (correct) direction, so the error is likely a typo, but it further weakens the written proof. If submodularity genuinely fails under interleaving, the constant-factor guarantee collapses. Independent analysis suggests the per-node insertion benefit F(u,v)=ψ(u)+ψ(v)-ψ(u+v) is nondecreasing in u and v for concave increasing ψ, which would repair the proof, but the paper does not supply this argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses persistent monitoring of a finite set of graph nodes by heterogeneous mobile agents. Each node carries a concave, increasing reward that resets upon a visit, and the dispatch problem is to select one policy per agent to maximize the total collected reward over a mission horizon. The authors state that the problem is NP-hard, prove in Theorem 3.1 that the utility, augmented with a nodal-importance term, is monotone submodular, and use this to claim a 1/2 optimality gap for their sequential greedy algorithm (Theorem 3.2), implemented in a receding horizon and decentralized fashion. A simulation study illustrates the method.","tokens_in":14345,"tokens_out":8188,"duration_ms":72297,"significance":"If the submodularity claim is correct, the paper offers a polynomial-time dispatch algorithm with a constant-factor approximation guarantee for a persistent monitoring problem with concave resetting rewards, a genuinely useful extension of submodular maximization to dynamic scheduling. The use of Karamata's inequality to study visit-interval rewards is an interesting technique and the nodal-importance term is a sensible remedy for receding-horizon shortsightedness. However, the written proof has load-bearing gaps: the auxiliary lemmas cover only concatenated visit sequences, not the interleaved insertions that arise in the actual multi-agent problem, and Corollary 4.1 is stated and proved with the wrong inequality direction. The central claim is plausible and likely repairable, but the current manuscript does not provide a gap-free derivation of the advertised 1/2 guarantee.","major_comments":[{"comment":"The submodularity proof is load-bearing: Theorem 3.2's 1/2 gap rests entirely on it. Yet Lemmas A.2 and A.3 are proved only for concatenated visit sequences of the form (t)⊕(u) or (v)⊕(u), where the newly added visits are appended after the existing visits. In the actual problem, adding a policy q to a set Q inserts visits at arbitrary times between previously scheduled visits at each node. The proof of Theorem 3.1 does not address interleaved insertion, so the marginal-diminishing inequality ΔR̄(q|Q1) ≥ ΔR̄(q|Q2) is not established for the feasible policy sets of (4). This gap must be closed, for example by proving that the per-node insertion benefit F(u,v)=ψ(u)+ψ(v)−ψ(u+v) is nondecreasing in both arguments for concave increasing ψ, or by a direct generalization of Lemmas A.2 and A.3 to interleaved sequences.","section":"Theorem 3.1 proof and Appendix Lemmas A.2, A.3"},{"comment":"Corollary 4.1 is stated with the wrong inequality direction. As printed, it claims f(c)+f(d)−f(c+d) ≤ f(a)+f(b)−f(a+b) for 0≤a≤c and 0≤b≤d, but the reverse inequality is true for increasing concave f, and a counterexample is f(t)=√t, a=b=1, c=d=4 (the left side is about 1.172, the right side about 0.586). The proof concludes the same backward inequality, so both the statement and the derivation must be corrected. Lemma A.3 uses Corollary 4.1 to conclude ΔSp ≥ 0, and that conclusion requires the opposite, correct direction. This is therefore not a harmless typo in one line; it affects the validity of Lemma A.3 and hence of Theorem 3.1 as written.","section":"Corollary 4.1 and Lemma A.3"},{"comment":"There is an inconsistency between the model and the objective function. Assumption 1 states that if more than one agent arrives at node v at the same time, the team still collects only R_v(t). However, the utility in Eq. (2) is a sum over every visit of every policy, so simultaneous visits would double-count the reward. As written, the optimization problem (3) maximizes an objective that does not match the described monitoring reward. The authors should either reformulate the utility to count each distinct reward-earning event once, or explicitly restrict the feasible set to policies with no simultaneous visits and explain how the submodularity proof extends to that restriction.","section":"Assumption 1 and Eq. (2)"},{"comment":"The monotonicity portion of the proof of Theorem 3.1 contains mismatched indices. The displayed expression compares a sum over (t_v(Q2∪q)) with a sum over (t_v(Q2)), yet the conclusion is stated as ΔR(p|Q1) ≥ 0. Neither the indexing nor the use of Lemma A.2 (which applies to concatenated sequences) establishes the intended monotonicity of R with respect to adding q to Q1. This part of the proof needs to be rewritten together with the interleaving fix described above.","section":"Theorem 3.1 proof, monotonicity step"}],"minor_comments":[{"comment":"In the final displayed inequality of Lemma A.2, the index \"n+1−1\" is unclear and appears to be a typo; it should likely read \"n+l−1\" or the intended upper limit should be stated clearly.","section":"Lemma A.2 proof"},{"comment":"In the telescoping-sum equation at the end of Lemma A.3, the second term in parentheses should be (g((t)^n_1)−g((v)^m_1)) or equivalent; as printed it repeats g((v)^m_1) and does not telescope correctly.","section":"Lemma A.3 proof"},{"comment":"Equation (2) contains a duplicated fragment: \"R : 2P→ R>0 is ¯P ⊂P, the utility function R : 2P→ R>0 is\" appears twice in a row, which disrupts the definition.","section":"Eq. (2)"},{"comment":"The definition of the clique number is incorrect: \"the number of the nodes in the largest sub-graph such that adding an edge will cause a cycle\" is not the clique number. The clique number is the size of the largest complete subgraph; the statement should be corrected.","section":"Section III-A"},{"comment":"The sentence describing what happens when an agent appears repeatedly in SEQ says the agent can \"redesign and improve its sub-optimal policy\" but does not specify the mechanism or its effect on the optimality gap. This should be made precise or removed.","section":"Algorithm 2 discussion"},{"comment":"Given the inconsistency between Assumption 1 and Eq. (2), the simulation section should state explicitly how simultaneous arrivals are resolved in the implementation.","section":"Numerical example"}],"recommendation":"major_revision","confidential_remarks":"The paper is an extended version of the authors' IFAC work [29]; the novelty relative to that prior publication should be verified by the editor. The main technical issue is a proof gap in the submodularity theorem rather than a known counterexample to the result; the authors should be asked to provide a complete proof that covers interleaved visit insertions and to correct the sign error in Corollary 4.1. With those fixes the paper could become acceptable, but the current version does not substantiate the advertised 1/2 guarantee."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's central claim—submodularity of the concave-interval reward, hence a polynomial-time greedy with 1/2 gap—is almost certainly true, but the written proof doesn't cover the actual multi-agent case and there is a sign error in a corollary. I would not accept it as-is; I would send it to referees and ask for a revised proof.\n\nThe new idea is worth stating clearly. Previous patrolling work mostly used idle time, which is a linear reward. Here the reward per node is a concave increasing function of time since last visit, which is the right model for event detection. The utility is a set function over agent policies, the authors prove monotonicity/submodularity, and then the partition-matroid constraint gives the Fisher–Nemhauser–Wolsey 1/2 gap. The receding-horizon 'nodal importance' term, which adds a terminal-cost-like reward for being near high-value regions, is a sensible heuristic, and the decentralized greedy is a nice addition. The simulation illustrates the benefit of the terminal term over a plain look-ahead greedy.\n\nThe soft spots are real and they sit in the load-bearing proof. Theorem 3.1 relies on Lemmas A.2 and A.3, but those lemmas are proved for the case where the new visits are concatenated after the existing visits at a node. In the actual problem, adding an agent policy inserts visits at times that interleave with visits from other agents. The proof never handles that. Independent reasoning says the statement is true: splitting an interval into two parts with lengths x and y produces incremental reward ψ(x)+ψ(y)−ψ(x+y), which is increasing in x and y for concave increasing ψ, so the marginals do diminish. The paper does not supply that argument. On top of that, Corollary 4.1 is stated in the wrong direction: the printed inequality is false already for f(t)=√t, a=b=1, c=d=4. The proof actually concludes the opposite, which is the direction Lemma A.3 needs, so it is probably a typo, but a typo in a lemma that Theorem 3.1 leans on is not nothing.\n\nThe simulation is a single scenario without error bars, so it is suggestive rather than evidence. The NP-hardness claim is standard.\n\nAll in all, the engineering and the high-level result are solid, the proof as written is not. This paper deserves a serious referee, but the referee should be explicitly asked to check the corrected submodularity proof under interleaving and the direction of Corollary 4.1. I would not cite the current version.","headline":"The concave-reward patrolling greedy is a good idea and likely correct, but the submodularity proof as written doesn't cover interleaved agent visits and Corollary 4.1 has a sign error; worth refereeing, not accepting as-is.","tokens_in":14881,"tokens_out":9093,"would_cite":false,"duration_ms":88611,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the persistent-monitoring dispatch utility is monotone submodular, so a sequential greedy policy over agents achieves at least half the optimal reward in polynomial time.","keywords":["persistent monitoring","multi-agent patrolling","submodular optimization","sequential greedy algorithm","receding horizon","nodal importance","mobile sensors","optimality gap"],"falsifier":"Simulate a single node with a concave reward and three visit schedules chosen so that policy q inserts a visit between two visits of the existing set; compute the marginal gain $\\Delta R(q|Q_1)$ for a smaller set $Q_1$ and a larger set $Q_2$. If any such schedule yields a marginal gain for $Q_1$ smaller than for $Q_2$, submodularity fails and the $1/2$ bound collapses. A positive check across all small exhaustive cases, for example with three or four visits, would support the missing lemma.","tokens_in":13725,"feed_emoji":"📡","tokens_out":7294,"duration_ms":64882,"temperature":0.7,"pith_summary":"This paper studies persistent monitoring, where a team of mobile agents visits interconnected nodes and each node's reward grows concavely since its last visit and resets to zero on a visit. The question is which nodes to visit, when, and by which agent to maximize total reward over the mission horizon, and the paper shows that the exact answer is NP-hard and exponential in the number of agents and horizon length. The central claim is that the total-reward utility, viewed as a function of the chosen set of agent policies, is monotone increasing and submodular, meaning the marginal value of any additional policy never increases as more policies are already in the set. Because of this, the sequential greedy algorithm that assigns one policy per agent runs in polynomial time and is guaranteed to collect at least half of the optimal reward. A receding-horizon implementation plus a nodal-importance term for reward beyond the current horizon preserves that same guarantee and gives agents a reason to head toward distant high-reward regions.","feed_headline":"Greedy dispatch can guarantee half the optimal monitoring reward","feed_subtitle":"The paper proves the patrolling reward is submodular, so a sequential greedy policy has a known 1/2 optimality bound.","key_machinery":"The load-bearing object is the augmented utility $\\bar{R}(\\bar{P})$ in (5), defined over policy sets subject to a partition-matroid constraint (at most one policy per agent). It turns an NP-hard dynamic scheduling problem into a monotone submodular set-function maximization, which is exactly the setting where the sequential greedy algorithm carries a $1/2$ optimality gap. The technical engine proving submodularity is the representation of a node's contribution as $\\sum_j \\psi_v(\\Delta t^v_j)$, where $\\Delta t^v_j$ are the gaps between consecutive visits to node $v$, together with concatenation lemmas (A.2 and A.3) based on Karamata's inequality that compare marginal gains of adding a policy to a smaller versus a larger set. The nodal-importance term $\\mathcal{L}(v,w,\\hat{t},i)$ measures the reward concentration within radius $r$ of an anchor node, normalized by travel time, and is designed to be modular so that adding it does not disturb submodularity; the paper notes its resemblance to a terminal cost in model predictive control.","core_discovery":"The paper's discovery, stated on its own terms, is that the persistent-monitoring dispatch problem, despite being NP-hard, can be approximately solved with a constant factor because its utility is well behaved. For a selected policy set $\\bar{P}$, the utility is $R(\\bar{P}) = \\sum_{p\\in\\bar{P}}\\sum_{l=1}^{n_p} R_{V_p(l)}(T_p(l))$, the sum of all node rewards collected at visit times, with each node reward of the form $\\psi_v(t-\\bar{t}_v)$ for an increasing concave $\\psi_v$. Theorem 3.1 asserts that this utility, augmented as $\\bar{R}(\\bar{P}) = R(\\bar{P}) + \\alpha\\sum_{p\\in\\bar{P}}\\max_{v\\in\\bar{V}}\\mathcal{L}(v,p)$ with relative nodal importance $\\mathcal{L}$ and any $\\alpha\\ge0$, is a monotone increasing and submodular set function over the feasible policy set under the constraint that at most one policy is chosen per agent. Theorem 3.2 then concludes that Algorithm 1, a sequential greedy pass over agents, returns a policy set $\\bar{P}$ with $\\bar{R}(\\bar{P}) \\ge \\tfrac12 \\bar{R}(P^\\star)$, where $P^\\star$ is the optimal solution of (4). The proof route rewrites each node's reward as a sum over gaps between consecutive visits and invokes Karamata-based lemmas to show diminishing returns.","pith_inferences":["The same submodularity machinery should extend to heterogeneous travel times and agent-specific scanning delays, since the per-node visit-time sequence argument does not appear to use homogeneity; testing this is a direct next step the paper does not pursue.","If submodularity holds across arbitrarily interleaved visits, the approach should generalize to stochastic rewards or time-varying $\\psi_v$ as long as concavity and reset-on-visit are preserved, but the paper makes no such claim.","The receding-horizon-plus-terminal-importance structure suggests a bridge to model predictive control theory: tightening the terminal cost could yield stability-style guarantees on long-run visit frequencies, not just horizon-by-horizon reward.","The choice of anchor nodes $\\bar{V}$ is left as a design parameter, so an adaptive anchor-selection rule based on current reward gradients is a natural testable extension that the paper does not analyze."],"forward_implications":["A user can replace exponential search over all policy combinations with one greedy pass over agents and still receive a guaranteed half-optimality certificate for the augmented utility.","The $1/2$ guarantee survives the receding-horizon shortening of plans and the addition of the nodal-importance term with any nonnegative weight $\\alpha$.","In decentralized execution with full information sharing, such as a Hamiltonian communication route or non-overlapping cloud time slots, the same $1/2$ gap holds.","When message dropouts make the information graph incomplete, the optimality gap degrades to $1/(M-\\omega(G_I)+2)$, where $\\omega(G_I)$ is the clique number of the information graph.","For event-detection rewards of the form $1-e^{\\lambda_v t}$ (Poisson arrivals), the nodal-importance term steers agents toward high-rate clusters beyond the current planning horizon, as the simulation demonstrates."],"supporting_citations":[{"why":"Supplies the theorem that maximizing a monotone submodular set function under a matroid constraint with sequential greedy returns at least 1/2 of optimal; this is exactly the optimality gap in Theorem 3.2.","marker":"[28]"},{"why":"Provides Karamata's inequality, which grounds Lemmas A.1-A.3 used to prove the reward is monotone and submodular.","marker":"[23]"},{"why":"Establishes the NP-hardness of set-value submodular optimization problems, cited for the hardness of the dispatch problem (3).","marker":"[30]"},{"why":"Preliminary version of this paper whose event-detection reward model, $1-e^{\\lambda_v t}$, is used in the numerical study.","marker":"[29]"},{"why":"Gives the degraded optimality bound for decentralized submodular maximization with incomplete information graphs, used when message dropouts occur.","marker":"[35]"},{"why":"Provides the animated numerical demonstration of the dispatch policies compared in the simulation section.","marker":"[37]"}],"fun_headline_variants":["Greedy patrols: guaranteed half the optimal reward","Submodular dispatch: 50% optimality bound for monitoring","NP-hard monitoring, but greedy gets a 1/2 guarantee","Receding-horizon monitoring with proven 1/2 gap"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee rests on the reward staying submodular when a new agent's visits are inserted between existing visits, but the proof only covers insertions appended after the current visit sequence, so the arbitrarily interleaved case is assumed rather than proved.","fun_headline_variants_meta":{"raw":{"variants":["Greedy patrols: guaranteed half the optimal reward","Submodular dispatch: 50% optimality bound for monitoring","NP-hard monitoring, but greedy gets a 1/2 guarantee","Receding-horizon monitoring with proven 1/2 gap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000336,"raw_usage":{"total_tokens":1949,"prompt_tokens":1121,"completion_tokens":828,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":755}},"tokens_in":737,"tokens_out":828,"duration_ms":8751,"temperature":1.0,"reasoning_tokens":755,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:45:18.451789+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate a single node with a concave reward and three visit schedules chosen so that policy q inserts a visit between two visits of the existing set; compute the marginal gain $\\Delta R(q|Q_1)$ for a smaller set $Q_1$ and a larger set $Q_2$. If any such schedule yields a marginal gain for $Q_1$ smaller than for $Q_2$, submodularity fails and the $1/2$ bound collapses. A positive check across all small exhaustive cases, for example with three or four visits, would support the missing lemma.","supporting_citations":[{"cited_title":"An analysis of approximations for maximizing submodular set functions—ii,","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that maximizing a monotone submodular set function under a matroid constraint with sequential greedy returns at least 1/2 of optimal; this is exactly the optimality gap in Theorem 3.2."},{"cited_title":"Inequalities of Karamata, Schur and Muirhead, and some applications,","cited_arxiv_id":null,"evidence_quote":"Provides Karamata's inequality, which grounds Lemmas A.1-A.3 used to prove the reward is monotone and submodular."},{"cited_title":"Submodular functions and convexity,","cited_arxiv_id":null,"evidence_quote":"Establishes the NP-hardness of set-value submodular optimization problems, cited for the hardness of the dispatch problem (3)."},{"cited_title":"A sub-modular receding horizon approach to persistent monitoring for a group of mobile agents over an urban area,","cited_arxiv_id":null,"evidence_quote":"Preliminary version of this paper whose event-detection reward model, $1-e^{\\lambda_v t}$, is used in the numerical study."},{"cited_title":"Distributed submodular maximization with limited information,","cited_arxiv_id":null,"evidence_quote":"Gives the degraded optimality bound for decentralized submodular maximization with incomplete information graphs, used when message dropouts occur."},{"cited_title":"A sub-modular receding horizon solu- tion for mobile multi-agent persistent monitoring: animated numerical example,","cited_arxiv_id":null,"evidence_quote":"Provides the animated numerical demonstration of the dispatch policies compared in the simulation section."}],"review_version":1}