{"id":"47cdb682-731b-4b21-b5fd-05e73d69da62","arxiv_id":"2608.00792","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"StochSIPP plans a contingent route on a temporal road map with uncertain, locally sensed blockages, using SIPP macro-actions and bounded AND/OR search to minimize expected arrival time.","lead":"This paper presents a new robot navigation planner that decides whether to risk a shortcut based on what it observes along the way, rather than committing to one fixed path in advance. The planner comes with mathematical guarantees for safety and expected arrival time, and outperforms fixed-route methods in simulated warehouses.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6's optimality guarantee assumes 'complete macro-action generation,' but the paper never specifies or proves such a generator; without it the implemented planner may miss relevant endpoint-time pairs and the central expected-optimality claim is unsupported.","rationale":"The paper is a well-scoped, honestly conditioned work: the abstract and theorems explicitly state that completeness of action generation and correctness/independence of probabilities are required for optimality, and the experiments section explicitly states that the trajectory-level evaluations are correlated and therefore do not enjoy Theorem 6's guarantee. The proofs in the supplement are detailed and the bound arguments are sound. The single most load-bearing condition is the completeness of the macro-action generator, because it is the one assumption that (a) is essential to the optimality proof, (b) is not established by the text, and (c) is not verified by the experiments. If the generator is incomplete, the central 'minimizes expected arrival time' claim fails for the implemented system even under the ideal independence model. The reader identified this same issue as the primary weak assumption; I agree. The proposed test—comparing the generator's output to an exhaustive enumeration on small instances—would directly settle whether the assumption is satisfiable and whether the implementation meets it. Since the paper's claims are conditional and the gap is fixable, the appropriate verdict remains CONDITIONAL/UNCHANGED.","tokens_in":20645,"tokens_out":9666,"duration_ms":114377,"concrete_test":"Generate, for a set of small random roadmaps (e.g., |V|=6, T_max=12, 2-4 uncertain intervals), the exhaustive set of applicable endpoint-time pairs at each reachable state by enumerating all certified-safe paths in a time-expanded graph and recording every first-observation/goal endpoint. Run the implemented StochSIPP generator from the same states and compare the two sets. Then compute the exact optimal expected arrival time by brute-force Bellman backup over the full AND/OR graph (or by solving the MDP) and compare it to the value returned by StochSIPP. If any endpoint pair is missing or any value differs, the 'complete' generator assumption fails; if the sets and values match across many instances, the condition is satisfiable and the concern is mitigated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4 (Macro-action losslessness) and Theorem 6 (finite-roadmap optimality) both rely on the assumption that the macro-action generator includes every applicable endpoint-time pair. An endpoint pair (q',t') is applicable iff there exists a certified-safe schedule from (q,t) to (q',t') whose internal arrivals have empty newly-observed sets and whose endpoint is goal or has a nonempty N. The paper states that SIPP is used to generate these macro-actions and Algorithm 1 calls 'Generate complete A(s_v)', but it gives no algorithm, pseudocode, or proof that SIPP enumerates all such pairs. This is not a minor implementation detail: if the generator drops even one endpoint-time pair used by an optimal primitive policy, the macro-action policy class is strictly smaller than the primitive policy class, J*_mac(s) > J*_prim(s), and Theorem 6's conclusion of minimal expected arrival among all proper primitive policies is false. The safety theorem is unaffected because it does not depend on completeness. The experiments cannot detect this: they do not compute exact optimal values, and the trajectory-level worlds are correlated, so Theorem 6's assumptions do not even apply to the evaluation. Thus the central expected-optimality claim is conditional on an unverified, potentially unrealizable completeness condition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces StochSIPP, an offline contingent planner for finite temporal roadmaps in which edge and vertex safety is governed by independent Bernoulli interval-status variables revealed locally during execution. The planner defines a macro-action abstraction, generated with SIPP, over certified-safe schedules that terminate at the next observation or at the goal, and then performs bounded AND/OR search over a cached action–observation graph. Optimistic and robust SIPP relaxations provide admissible lower and upper bounds, and the paper proves safety and finite-roadmap expected-arrival-time optimality under stated assumptions: exact sensing, timing, and status support for safety; and correct independent probabilities plus complete action and outcome generation for optimality. PSPACE-hardness is shown by reduction from stochastic CTP. Experiments on controlled roadmaps, gated scenarios, and a Gazebo illustration compare StochSIPP with fixed-path baselines and study scaling with simultaneous ambiguity.","tokens_in":20958,"tokens_out":6589,"duration_ms":77665,"significance":"If the formal claims are fully supported, the paper makes a valuable contribution: it extends the Canadian Traveler Problem structure to time-indexed vertex and edge uncertainties, provides a finite-state abstraction that avoids explicit time expansion, and supplies detailed proofs in the supplement. The safety theorem is clean and appropriately scoped, and the hardness result is a useful placement of the problem. The authors are unusually careful in stating that optimality is conditional on exact independent probabilities and on complete action and outcome generation, and that correlated trajectory-level experiments do not fall under the optimality theorem. The main gap is the unverified and potentially unrealizable completeness condition on the macro-action generator, which is load-bearing for the central optimality claim.","major_comments":[{"comment":"The finite-roadmap optimality theorem (Theorem 6; main-text Theorem 3) and the losslessness lemma (Lemma 4) both assume a 'complete macro-action generator' that includes every applicable endpoint-time pair. Algorithm 1 requires such a generator as input (line 5: 'Generate complete A(s_v)'), and the text says only that SIPP is used to generate the macro-actions, but no algorithm, pseudocode, or proof is provided showing that SIPP can enumerate all applicable endpoint-time pairs in general. This is not a minor implementation detail: if the generator drops even one endpoint-time pair used by an optimal primitive policy, the macro-action policy class is strictly smaller, giving J*_mac(s) > J*_prim(s), so the conclusion of Theorem 6 would be false. The safety theorem is unaffected, and the experiments cannot detect the issue because they do not compute exact optimal values. Please supply a co","section":"Problem Formulation / States, Actions, and Objective; Algorithm 1; Lemma 4; Theorem 6"}],"minor_comments":[{"comment":"Cross-referencing is inconsistent: the main text labels safety as Theorem 2 and optimality as Theorem 3, but proof sketches, the Scope of the guarantee, and the conclusion refer to 'Theorem 5', while the experiments refer to 'Theorem 6'. The supplement renumbers the same statements as Theorems 4–6. Please unify the numbering.","section":"Theoretical Analysis and Conclusion"},{"comment":"The term 'CAO*' is used but not defined; the cited work by Aksakalli, Sahin, and Ari describes an 'AO* based exact algorithm'. Please introduce the terminology explicitly.","section":"StochSIPP / Bounded Exact Search"},{"comment":"The column headers '2-rt%' and '3-rt%' are not explained in the caption. They appear to be success rates on the two gated scenarios, but they should be defined, e.g., '2-route success %' and '3-route success %'.","section":"Experiments / Table 1"},{"comment":"The LRTA-style refinement is described only in a few lines and referenced to the supplement; a brief algorithmic description or pseudocode in the main text would help reproducibility, since it is part of one of the compared configurations.","section":"Experiments / Search-Aid Ablation"}],"recommendation":"major_revision","confidential_remarks":"The completeness of the macro-action generator is the central technical gap. If the authors can provide a rigorous construction or proof that their SIPP-based generation covers every applicable endpoint-time pair, the paper would be publishable. I would not require new experiments, but the optimality claim should not be presented as verified until this condition is either proved or explicitly delegated to a specified input component."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look. StochSIPP does something new: it combines SIPP-style certified-safe macro-actions with bounded AND/OR search to solve a temporal generalization of stochastic CTP where edge and vertex intervals have independent Bernoulli statuses. The model is cleanly stated, the Bellman equations are straightforward, and the supplement gives real proofs, not sketches. The paper is also unusually candid about what the guarantees do not cover: correlated statuses, sensing errors, or timing deviations. That honesty is earned, not decorative.\n\nThe main theoretical claim, Theorem 6, is that the returned policy minimizes expected arrival time among all proper primitive policies, given exact independent probabilities and complete action and outcome generation. The stress-test concern lands: the completeness of the macro-action generator is an assumption, not a result. Lemma 4 and Theorem 6 both rely on it, but Algorithm 1 just says \"Generate complete A(s_v)\" with no method or proof that SIPP enumerates every applicable endpoint-time pair. If the generator misses an endpoint-time pair that an optimal primitive policy would use, then the macro-policy class is strictly smaller and J*_mac > J*_prim, so the theorem's conclusion is false. This is a load-bearing gap, not a nitpick. It is also empirically invisible: the experiments never compute exact optimal values, and the trajectory-level worlds induce correlated statuses, which the paper itself acknowledges invalidates Theorem 6's independence assumption for the evaluation. So the empirical results are best read as demonstrating practical value, not optimality.\n\nThat said, the safety theorem does not depend on completeness and is solid under the stated assumptions. The bounds are sensible, the pruning rule is sound, and the ablation shows the search aids help substantially. The scalability study is honest about its limits. The paper deserves a serious referee. The main fix is to either specify a complete generator and prove it, or weaken the optimality claim to optimality among generated macro-actions. The correlated-experiments issue is less damaging because it is disclosed, but the authors should be pushed to either use independent status draws or call the experiments an approximate evaluation with no optimality claim.\n\nI would cite this if I work on contingent planning or SIPP extensions. Take it seriously, but read the completeness assumption before relying on the optimality result.","headline":"StochSIPP is a genuinely new exact contingent planner with careful proofs and honest scope caveats, but the central expected-optimality claim rests on a completeness assumption that is asserted rather than shown.","tokens_in":21391,"tokens_out":1206,"would_cite":true,"duration_ms":16518,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"StochSIPP is a contingent planner that, under a finite model of independent interval-status probabilities, returns a provably collision-free policy that minimizes expected arrival time within the roadmap and horizon.","keywords":["contingent planning","safe interval path planning","AND/OR search","Canadian Traveler Problem","uncertain dynamic obstacles","expected arrival time","PSPACE-hardness"],"falsifier":"A concrete check: on a two-route, one-gate roadmap with one independent Bernoulli gate, brute-force all primitive policies and compute the true minimum expected arrival time; StochSIPP's value must equal that minimum exactly. Any simulated execution that collides while following a declared probability-one interval under planned timing would also falsify the safety claim.","tokens_in":20583,"feed_emoji":"🤖","tokens_out":10221,"duration_ms":115171,"temperature":0.7,"pith_summary":"StochSIPP addresses motion planning on a roadmap where each edge and vertex can be safe or blocked for an interval of time, with only probabilities and local observations available before the robot commits to motion. The paper's central claim is that a contingent policy—one that waits to see whether a gate is open before choosing a route—can be computed exactly by combining SIPP's certified-safe macro-actions with AND/OR search over observation outcomes. Under the stated assumptions, the returned policy is provably collision-free, and when the supplied probabilities are correct and independent, it minimizes expected arrival time within the finite roadmap and horizon. Experiments on controlled maps show the planner matching the 100 percent success of safe fixed-path baselines while reducing mean arrival time, and returning plans in gated scenarios where conservative baselines find none.","feed_headline":"StochSIPP gives provably safe routes that cut arrival time","feed_subtitle":"It commits to a route only after observing each uncertain gate, matching safe baselines while cutting mean arrival by up to 31 percent","key_machinery":"The load-bearing object is the certified-safe macro-action: a fixed, time-stamped sequence of roadmap edges and waits that is safe under current observations, stops at the first new observation event or at the goal, and has no new sensing at internal arrivals. These macro-actions feed a cached action–observation graph: OR nodes are decision states (vertex, time, observed statuses), and AND nodes average over every observation outcome at a macro's endpoint. Two pieces make the search exact: the macro-action is lossless relative to primitive policies, so optimizing over macro-actions is equivalent to optimizing over primitive edge choices; and the optimistic and pessimistic SIPP arrival-time f","core_discovery":"Temporal uncertainty in a roadmap is solved exactly by compressing time out of the contingent search. Each interval of edge or vertex use is an episode-fixed status, known by a probability and observed locally before use. Macro-actions are certified-safe schedules that stop at the next observation event, turning the problem into a finite acyclic AND/OR graph over states (vertex, time, observed statuses). Bellman equations on this graph, with optimistic and pessimistic SIPP bounds as admissible lower and upper values and a strict pruning rule, terminate with the exact optimal contingent policy. The macro-action abstraction is lossless: every primitive policy segments into such schedules with","pith_inferences":["Because the safety guarantee needs only support-correct intervals and exact sensing, a practical variant could preserve collision freedom even when probabilities are misestimated, at the cost of optimality; the paper leaves correlated uncertainty as future work.","The lossless segmentation at observation boundaries is a general recipe: any planner that can certify a safe interval could likely be lifted into a contingent planner by requiring schedules to end at the next observation event, potentially transferring the approach to other motion-planning representations.","The gated-scenario results imply that requiring a fully safe fixed path throws away all plans when uncertainty is unavoidable; contingent observation converts uncertainty from a failure mode into a decision resource.","The exponential growth with simultaneous ambiguity points to factorized observation aggregation or approximate value functions as the natural path to scalability, sacrificing exactness for broader applicability."],"forward_implications":["A robot can execute StochSIPP's policy without online replanning: after each observation it simply follows the precomputed schedule for the observed outcome.","Conservative planners that require certainty return no plan when every route passes through an uncertain gate; StochSIPP still returns a safe plan by disambiguating gates one at a time.","The expected-arrival-time optimality is relative to the supplied finite roadmap, horizon, and independent interval model, not to the continuous space or to correlated obstacle trajectories.","Because the decision problem is PSPACE-hard, exact contingent planning is inherently expensive as the number of simultaneously observed uncertain statuses grows; the experiments document rapid compounding growth beyond six statuses.","If the supplied probabilities are wrong, safety survives but expected-cost optimality does not, so model calibration is the practical boundary of the optimality guarantee."],"supporting_citations":[{"why":"Supplies SIPP, the safe interval path planner whose certified-safe intervals become StochSIPP's macro-actions.","marker":"Phillips and Likhachev 2011"},{"why":"Provides any-start-time SIPP arrival-time functions that yield the optimistic and pessimistic bounds used in search.","marker":"Thomas et al. 2023"},{"why":"Defines the Canadian Traveler Problem whose local-observation structure StochSIPP generalizes to time-indexed roadmaps.","marker":"Bar-Noy and Schieber 1991"},{"why":"Supplies the best-first AND/OR search procedure that StochSIPP adapts with SIPP-based bounds.","marker":"Aksakalli, Sahin, and Ari 2016"},{"why":"Establishes PSPACE-completeness of stochastic CTP variants, the basis of the paper's hardness reduction.","marker":"Fried et al. 2013"},{"why":"Provides the classical admissible AND/OR graph-search formulation underlying the exact search.","marker":"Chang and Slagle 1971"}],"fun_headline_variants":["StochSIPP: observe each gate, then commit to a safe route","Exact contingent routes that cut arrival time under uncertainty","Provably safe navigation that adapts to gate observations","StochSIPP compresses time to solve uncertain mapping optimally","Secure your path: StochSIPP observes uncertain gates first"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The plan is only as good as the list of options the action generator can enumerate; if a useful arrival place-and-time combination is missing, or if the interval statuses are actually correlated instead of independent, the optimality proof no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["StochSIPP: observe each gate, then commit to a safe route","Exact contingent routes that cut arrival time under uncertainty","Provably safe navigation that adapts to gate observations","StochSIPP compresses time to solve uncertain mapping optimally","Secure your path: StochSIPP observes uncertain gates first"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000317,"raw_usage":{"total_tokens":1615,"prompt_tokens":717,"completion_tokens":898,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":461,"completion_tokens_details":{"reasoning_tokens":813}},"tokens_in":461,"tokens_out":898,"duration_ms":10558,"temperature":1.0,"reasoning_tokens":813,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T00:12:47.942738+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: on a two-route, one-gate roadmap with one independent Bernoulli gate, brute-force all primitive policies and compute the true minimum expected arrival time; StochSIPP's value must equal that minimum exactly. Any simulated execution that collides while following a declared probability-one interval under planned timing would also falsify the safety claim.","supporting_citations":[],"review_version":1}