{"id":"850fa14c-e20d-4bcd-9259-5fc0d146981b","arxiv_id":"1908.05347","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A UAV surveillance routing problem with per-target viewing-angle and dwell-time constraints is approximated by sampling configurations and solving a generalized traveling salesperson problem, with a conditional resolution-completeness guarantee.","lead":"This paper introduces a sampling-based planning framework for a fixed-wing UAV that must film ground targets with specific camera angles, view directions, and dwell times, while balancing total tour time against how quickly the first target is reached. It turns the continuous routing problem into a discrete graph search solvable with existing traveling-salesperson solvers, and proves that the solution approaches optimal as sampling becomes finer.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's proof assumes dense DWL_j samples land in INL_epsilon; when INL_epsilon has empty relative interior (e.g., epsilon equals the Dubins minimum on a lower-dimensional DWL_j), a dense sample can avoid it, so Algorithm 5 may return infeasible and resolution completeness is unproven even…","rationale":"The exact-GTSP caveat the reader flags is real but is explicitly acknowledged in the appendix and is standard for sampling-based completeness theorems; it limits the implemented algorithm, not the idealized algorithm. The more load-bearing issue is a gap in the idealized theorem. In the proof of Theorem 3, dense sampling of DWL_j (Definition 5) is used to conclude a sample lies in U, but U is constrained to CLS_epsilon. When INL_epsilon has empty relative interior in DWL_j—possible when epsilon is the minimum Dubins distance and the minimizer set is a curve or surface—a dense sequence in DWL_j can avoid INL_epsilon entirely. The discrete problem is then infeasible for every N, contradicting the theorem's assertion of feasible tours with lengths converging to LGTH*. Definition 4's non-degeneracy does not exclude this because it only forbids isolated points. This is not a mere implementation issue; it affects the theorem as stated. The proposed test—constructing such a two-target instance and checking that no grid sample meets the epsilon constraint—would settle it. If the concern lands, the theorem can likely be repaired by requiring INL_epsilon to have nonempty relative interior in DWL_j or by sampling DWL_j∩INL_epsilon directly; hence the verdict remains CONDITIONAL rather than REJECT.","tokens_in":90,"tokens_out":22470,"duration_ms":386321,"concrete_test":"Search for a two-target instance satisfying Theorem 3's hypotheses in which DWL_j∩INL_epsilon is a non-isolated, empty-interior subset of DWL_j (e.g., set epsilon equal to the minimum of DIST(v0,·) over a symmetric DWL_j, such as a full-circle dwell set). For that instance, run Algorithm 5 under the grid spacings of Table 2. If no sampled node satisfies W(v0,v)<=epsilon for any spacing, so Algorithm 5 returns 'Problem 2 Infeasible' despite Definition 4 classifying the instance as non-degenerate, the theorem's conclusion is contradicted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 3's proof hinges on the step 'Since the sampling procedure is dense, for some N, there will be a discrete node placed inside of the set U.' Dense sampling (Definition 5) is applied to each DWL_j, but U is chosen inside CLS_epsilon, i.e., the first component must lie in INL_epsilon. If v*_1 lies on a positive-codimension subset of INL_epsilon—for example, if epsilon equals the minimum of DIST(v0,·) over DWL_j, so INL_epsilon is the (closed) minimizer set with empty relative interior—then no open neighborhood of v*_1 is contained in DWL_j∩INL_epsilon. A dense sequence in DWL_j can be chosen to avoid such a closed empty-interior set entirely. Consequently, every sampled node may have DIST(v0,v)>epsilon, Algorithm 4's discrete INL_epsilon is empty, and Algorithm 5 returns 'Problem 2 Infeasible' for all N. Non-degeneracy (Definition 4) only excludes isolated first components, not lower-dimensional reachable sets, so the theorem's hypotheses do not prevent this. The claimed feasibility-and-convergence for every N then fails. This gap is independent of the exact-GTSP assumption: it concerns the idealized theorem itself.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a sampling-based framework for planning a fixed-wing UAV surveillance tour under per-target visibility and dwell-time constraints. A bi-objective formulation (closed-tour time and initial-maneuver time) is scalarized via an epsilon-constraint method, then discretized by sampling the UAV configuration space at configurations that support feasible dwell maneuvers. The resulting discrete problem (Problem 2) is solved by a heuristic reduction to a Generalized Traveling Salesperson Problem (GTSP) via Algorithm 4. Theorems 1 and 2 state, respectively, that Algorithm 4 always returns a feasible solution and that, under structural conditions on the initially reachable node set, optimal GTSP solutions map to optimal solutions of Problem 2. Theorem 3 claims resolution completeness of the full construction under non-degeneracy, dense sampling, and exact GTSP solving. The paper closes with numerical examples illustrating Pareto-front behavior, comparisons against a greedy baseline, and a hand-constructed convergence example.","tokens_in":17010,"tokens_out":11092,"duration_ms":124732,"significance":"If the advertised convergence property held for the implemented algorithm, the paper would be a useful extension of the prior Polygon-Visiting Dubins TSP sampling framework to dwell-time behaviors and a second objective. The problem formulation is careful and the modular reduction to GTSP is practically appealing; Theorem 2's equivalence result is clean and the numerical study is transparent about the solvers used. However, the central resolution-completeness claim is substantially weaker than the abstract suggests: Theorem 3 requires an exact GTSP oracle that the implementation does not provide, and its denseness argument has a gap for feasible sets of empty relative interior. The paper therefore needs either a repaired theorem or a reframed set of claims before it can be accepted.","major_comments":[{"comment":"The step \"Since the sampling procedure is dense, for some N, there will be a discrete node placed inside of the set U\" is not justified. Dense sampling is defined on each DWL_j, but the first component of the required discrete node must lie in DWL_j∩INL_epsilon. If INL_epsilon∩DWL_j has empty relative interior—for example if epsilon equals the minimum of DIST(v0,·) over a positive-dimensional continuum in DWL_j—then a dense sequence in DWL_j can be chosen that avoids this set entirely. In that case Algorithm 4 returns \"Problem 2 Infeasible\" for every N, contradicting the claimed feasibility of each INL_MNVRN. Definition 4 only excludes a first component that is isolated in INL_epsilon; it does not exclude a non-isolated point lying on a positive-codimension reachable set. The theorem needs an additional relative-interior assumption around the optimal first component, or the conclusion must be weakened to approximate feasibility with an initial-maneuver slack that tends to zero.","section":"Appendix, Theorem 3 proof"},{"comment":"The statement of Theorem 3 explicitly assumes \"(iii) an optimal GTSP solution is found (Algorithm 4, line 5)\", but the numerical implementation in Section 6 solves GTSPs through a Noon-Bean transformation followed by the Lin-Kernighan heuristic (LKH). The Appendix itself concedes that \"it is not generally possible to find optimal solutions to GTSPs\" and that the theorem's utility is mainly to provide intuition. Consequently, the proven result applies to an idealized algorithm with an exact GTSP oracle, not to the Algorithm 5 as implemented. The abstract's claim that the heuristic \"is shown to have resolution completeness properties\" should be qualified accordingly, or a separate convergence statement for the heuristic should be supplied.","section":"Theorem 3 and Section 6 (experimental setup)"},{"comment":"The authors' own example at epsilon=16.26 s shows that when the feasible initial set is a single configuration, Algorithm 5 is not resolution complete, and they argue this is a degenerate case. This is an isolated-point degeneracy, which Definition 4 does exclude. However, it does not address the non-isolated lower-dimensional case in the first major comment, where no point is isolated in INL_epsilon but the intersection DWL_j∩INL_epsilon still has empty relative interior. The numerical evidence in Figure 9 is limited to one hand-constructed nondegenerate instance, so it provides only weak support for the claim that the theorem's conditions are typically satisfied in practice.","section":"Section 6.3 and Definition 4"}],"minor_comments":[{"comment":"The phrase \"in many cases, this approximation is equivalent to a generalized traveling salesperson problem\" is imprecise: the discrete problem is solved by a heuristic reduction to a GTSP, and equivalence to Problem 2 holds only under the conditions of Theorem 2. Please adjust the wording to avoid overstating the scope of the equivalence.","section":"Abstract and Section 5.1"},{"comment":"The notation \"ÐM j=1[ϵ_j, ϵ_j]\" appears to be a rendering artifact; it should presumably be a union of intervals, e.g., ∪_{j=1}^{M}[ϵ_j, ϵ_j].","section":"Remark 8"},{"comment":"The y-axis label \"Closed Trajectory Time Error (s)\" in Figure 7 is misleading: the plotted quantity is the difference between the greedy method and Algorithm 5, not an error with respect to an optimal solution. Consider renaming it \"Difference in closed trajectory time\" or \"Improvement over greedy.\"","section":"Figure 7"},{"comment":"It would clarify the procedure to state explicitly that the subset INL*_epsilon is chosen nonempty; otherwise the GTSP instance constructed in line 5 may have an empty node set for the selected target.","section":"Algorithm 4, line 3"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a relevant and well-motivated problem, and the discrete formulation is a solid contribution. My main concern is that the advertised resolution-completeness guarantee is substantially weaker than the abstract suggests, due to the exact-GTSP assumption and the denseness gap identified above. I would be willing to reconsider after the claims are reframed and Theorem 3 is repaired or weakened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a read if you work on Dubins routing or sampling-based planning. The paper does something concrete: it takes the polygon-visiting Dubins TSP from Obermeyer et al., adds per-target visibility regions, dwell-time loops, and an epsilon-constraint on the initial maneuver, and shows how to approximate the continuous problem by a GTSP. The graph construction is careful, Theorems 1 and 2 are correct and clean, and the numerical study gives sensible evidence that the method works. The connection to prior work is honest—Remark 3 states clearly when the problem reduces to [7]. That part of the paper is solid.\n\nThe soft spots are in the resolution-completeness claim. The reader's report flags the exact-GTSP issue: Theorem 3 assumes Algorithm 4 solves the GTSP to global optimality, while the implementation uses LKH. The appendix concedes this, but the abstract still promises resolution completeness without qualifiers. That is a real mismatch.\n\nThere is a sharper problem that the report doesn't capture. The proof of Theorem 3 argues that because sampling is dense, some sample will fall inside a neighborhood U of the optimal first configuration. That step only works if U contains an open ball inside INL_epsilon. If the optimal first configuration lies on the boundary of INL_epsilon—for instance, if epsilon equals the minimum Dubins distance and the minimizer set is a curve—then INL_epsilon has empty relative interior there. A dense sampling sequence can be chosen to miss that lower-dimensional set entirely, so the discrete INL_epsilon is empty for every N and Algorithm 5 returns 'infeasible.' Non-degeneracy (Definition 4) only rules out isolated points, not boundary points on a continuum, so the theorem's hypotheses don't prevent this. The proof is not just incomplete in practice; the stated theorem is false as written. The authors do say at the end of the appendix that Theorem 3 should be viewed as intuition, but the main text and abstract don't carry that caveat.\n\nBottom line: the framework is worth keeping, and most of the mathematics is honest. But the paper needs a corrected Theorem 3—either add a condition that the optimal first component lies in the interior of INL_epsilon, or downgrade the claim to a conjecture—and the abstract should match what the implemented heuristic actually guarantees. I'd send it to a serious referee, but I'd ask them to focus on the appendix. Also, the authors don't provide code or data; for a sampling-based method that would help a lot.\n\nFor a reading group: maybe, if you want a concrete example of how sampling-based proofs can slip on boundary cases. I'd recommend a cautious revise.","headline":"A genuinely useful sampling-based framework for UAV surveillance with visibility and dwell-time constraints, but Theorem 3's resolution-completeness guarantee has a gap that goes beyond the exact-GTSP caveat.","tokens_in":17588,"tokens_out":8582,"would_cite":true,"duration_ms":82848,"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":"Sampling the UAV flight space turns surveillance routing with viewing and dwell-time requirements into a generalized traveling salesperson problem, and provably approaches the continuous optimum as sampling is refined.","keywords":["UAV surveillance","dwell-time constraints","visibility regions","Dubins vehicle","generalized traveling salesperson problem","sampling-based path planning","resolution completeness","epsilon-constraint scalarization"],"falsifier":"Run the two-target example of Section 6.3 with the initial-time bound set to 16.26 s, the value at which the reachable set collapses to a single configuration: any sampling grid that omits that exact configuration makes the discrete problem infeasible, so no sequence of tours exists and the claimed resolution completeness fails.","tokens_in":16476,"feed_emoji":"✈️","tokens_out":9596,"duration_ms":92089,"temperature":0.7,"pith_summary":"This paper is trying to establish that a practical, sampling-based path planner can produce near-optimal tours for a fixed-wing UAV that must image multiple ground targets, each with its own required camera azimuth, tilt angle, and dwell time. The authors reformulate the mission as an epsilon-constraint optimization — minimize the closed tour length subject to a bound on the initial maneuver time — and then show that careful discretization of the UAV's configuration space turns this infinite-dimensional problem into a finite graph search. In many instances the discrete problem is exactly a generalized traveling salesperson problem (GTSP), which can be attacked with existing solvers. The paper's central theoretical result is a resolution-completeness theorem: under a non-degeneracy condition and a structural condition on the feasible initial-maneuver set, tour lengths produced by the heuristic converge to the length of an optimal continuous tour as the sampling density tends to infinity. This matters because it provides a principled justification for a heuristic pipeline that is otherwise easy to distrust.","feed_headline":"Refined sampling provably converges UAV tours to the optimum","feed_subtitle":"A sampling-based UAV surveillance planner provably reaches optimal tour length as sampled maneuvers are refined.","key_machinery":"The central object is a weighted directed graph $G=(V\\cup\\{v_0\\},E,W)$ built from sampled UAV configurations, where each node is a configuration (position and heading) paired with a feasible dwell-time loop at a particular target, and each edge weight is the duration of the dwell loop at the source node plus the optimal Dubins path time from the source to the destination configuration. The named identity doing the work is the augmented Dubins distance; because the Dubins distance satisfies a triangle inequality, the graph weights inherit it, which permits the reduction to a GTSP. The equivalence theorem (Theorem 2) and the resolution completeness theorem (Theorem 3) rest on the structure of the set $\\text{INL}_\\epsilon$ of configurations reachable from the start within the allowed initial time, together with the continuity of the closed-tour length function away from a finite set of degenerate surfaces.","core_discovery":"The central claim is that the continuous, multi-objective UAV tour problem with visibility and dwell-time constraints can be approximated to arbitrary accuracy by a discrete graph problem. By sampling configurations that are each the start and end point of a feasible dwell-time maneuver, and by weighting edges with the sum of the dwell time at the source and the optimal Dubins travel time to the destination, the authors obtain a finite graph whose optimal tours approximate those of the continuous problem. The approximation is exact in a well-defined sense: whenever the set of configurations reachable within the allowed initial time is nested either inside or around the dwell-time set of a single target (Theorem 2), optimal solutions of the corresponding GTSP map to optimal solutions of the discrete problem. The resolution completeness theorem (Theorem 3) then shows that, for non-degenerate instances, the length of tours produced by the full Algorithm 5 converges to the continuous optimum as the number of samples per target grows, provided the GTSP is solved exactly at each step.","pith_inferences":["Because the proven convergence requires an exact GTSP solver, a testable extension is to compute exact solutions via branch-and-bound for small target counts and compare the observed convergence rate with the resolution-completeness prediction.","The nesting condition on the reachable set is likely to hold when the initial position is much closer to one target than to any other; in cluttered or symmetric layouts where the condition fails, the heuristic has no such equivalence guarantee, and degraded performance is plausible.","The same sampling-plus-GTSP machinery extends naturally to multiple vehicles or to targets with time windows, but the equivalence theorems would need to be re-derived, since the initial-maneuver constraint would couple vehicles."],"forward_implications":["When target spacing is large, the condition for Theorem 2 is typically satisfied, so optimal GTSP solutions translate directly into optimal solutions of the discrete approximation, and hence into near-optimal continuous tours.","Varying the epsilon bound produces a family of routes that trace an approximate Pareto front trading initial response time against total tour duration, which can be computed with existing GTSP and asymmetric TSP solvers.","The framework reduces to the polygon-visiting Dubins traveling salesperson problem when all dwell-times are zero and epsilon is unconstrained, showing it is a genuine generalization of prior work.","The resolution completeness result guarantees that the discrete approximation faithfully reflects the continuous problem in the limit; any residual suboptimality in practice comes from the finiteness of the sampling grid and from the heuristic rather than exact GTSP solving.","As dwell-time requirements increase, the advantage of the GTSP-based heuristic over greedy nearest-target planning grows, since greedy choices can strand the vehicle far from targets that require multiple loops."],"supporting_citations":[{"why":"supplies the sampling-based polygon-visiting Dubins TSP framework and the continuity arguments on which the resolution-completeness proof is built.","marker":"[7]"},{"why":"defines the Dubins vehicle model and the optimal path distances used as edge weights in the graph.","marker":"[37]"},{"why":"introduces the epsilon-constraint scalarization method used to pose the multi-objective routing problem as a constrained optimization.","marker":"[6]"},{"why":"provides the transformation from a generalized traveling salesperson problem to an asymmetric TSP that the solution procedure relies on.","marker":"[32]"},{"why":"establishes the triangle inequality for Dubins distances with neighborhoods, which justifies the 'exactly one node per set' GTSP formulation.","marker":"[29]"},{"why":"supplies the practical solver used for the numerical experiments.","marker":"[20]"}],"fun_headline_variants":["Sampling refinement yields asymptotically optimal UAV tours","UAV tours converge to optimal with refined sampling","Provably convergent sampling for optimal UAV surveillance","Sampling-based UAV routing: convergence to optimum","Refined sampling ensures optimal UAV tour convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence theorem assumes that the generalized traveling salesperson problem on the sampled graph is solved to global optimality at every sampling density, but exact solvers are not generally available and the numerical implementation uses a heuristic solver, so the proven guarantee does not apply to the implemented algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Sampling refinement yields asymptotically optimal UAV tours","UAV tours converge to optimal with refined sampling","Provably convergent sampling for optimal UAV surveillance","Sampling-based UAV routing: convergence to optimum","Refined sampling ensures optimal UAV tour convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000249,"raw_usage":{"total_tokens":1526,"prompt_tokens":897,"completion_tokens":629,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":560}},"tokens_in":513,"tokens_out":629,"duration_ms":7366,"temperature":1.0,"reasoning_tokens":560,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:23:51.326635+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two-target example of Section 6.3 with the initial-time bound set to 16.26 s, the value at which the reachable set collapses to a single configuration: any sampling grid that omits that exact configuration makes the discrete problem infeasible, so no sequence of tours exists and the claimed resolution completeness fails.","supporting_citations":[{"cited_title":"Sampling-based path planning for a visual reconnais- sance UAV","cited_arxiv_id":null,"evidence_quote":"supplies the sampling-based polygon-visiting Dubins TSP framework and the continuity arguments on which the resolution-completeness proof is built."},{"cited_title":"Oncurvesofminimallengthwith a constraint on average curvature and with prescribed initial and terminal positions and tangents","cited_arxiv_id":null,"evidence_quote":"defines the Dubins vehicle model and the optimal path distances used as edge weights in the graph."},{"cited_title":"Nonlinear Multiobjective Opti- mization","cited_arxiv_id":null,"evidence_quote":"introduces the epsilon-constraint scalarization method used to pose the multi-objective routing problem as a constrained optimization."},{"cited_title":"A Lagrangian based approach for the asymmetric generalized travel- ing salesman problem","cited_arxiv_id":null,"evidence_quote":"provides the transformation from a generalized traveling salesperson problem to an asymmetric TSP that the solution procedure relies on."},{"cited_title":"Dubins traveling salesman problem with neighborhoods: A graph-based approach","cited_arxiv_id":null,"evidence_quote":"establishes the triangle inequality for Dubins distances with neighborhoods, which justifies the 'exactly one node per set' GTSP formulation."},{"cited_title":"An effective implementation of theLin–Kernighantravelingsalesmanheuristic","cited_arxiv_id":null,"evidence_quote":"supplies the practical solver used for the numerical experiments."}],"review_version":1}