Literature
Display
← All papers

OSCAR: Obstacle Survival Curves for Adaptive Robot Navigation

Hshmat Sahak · Aoran Jiao · Nicholas Rhinehart · Timothy Barfoot

Preprint posted · CoRL 2026 (accepted) ↗

Robotics10 min text · CondensedOriginal paper ↗
Contents

Overview

OSCAR learns how long observed obstacle classes tend to block known routes, then chooses a waiting deadline before rerouting.

At a glance

A route-following robot should sometimes wait for a short-lived obstacle and sometimes take a detour around a persistent one. OSCAR learns class-specific residual clearance-time distributions, including observations censored when the robot leaves before clearance. A time-dependent graph planner combines these distributions with remembered blockages to choose patience thresholds. Simulated mean travel time approaches a distribution-aware oracle, and physical atrium experiments show adaptation over fifty staged episodes. The method assumes a route graph and usable obstacle labels; it complements local avoidance rather than replacing it.

1 Introduction

The decision applies when an edge cannot be safely bypassed locally, such as a narrow corridor or designated route. A person and a parked object may warrant different waiting policies, but fixed class rules cannot adapt to actual persistence. OSCAR learns clearance statistics from repeated encounters and incorporates remembered obstacles elsewhere on the graph. Its objective is expected time-to-goal under a navigation-cost model, not a global safety or socially optimal behavior guarantee.

Refer to caption
Figure 1: Motivating example showing a robot navigating on a graph where it might be blocked by different objects and must decide whether to wait or reroute based on its learned survival model.

2 Related Work

Local obstacle avoidance chooses short-horizon motion, while this work chooses whether to persist with a blocked graph edge. The Canadian Traveller Problem supplies related online route uncertainty, but often treats blocked edges as static. Time-dependent routing supplies the FIFO condition needed for efficient shortest-path search. Kaplan–Meier estimation [17] supplies a nonparametric way to retain partial clearance observations rather than discarding long-lived obstacles when the robot reroutes.

3 OSCAR: Survival-Guided Wait-or-Reroute Planning

The graph has deterministic nominal edge traversal times, with temporary blockages encountered during travel. The robot observes an obstacle class, selects a maximum wait, and either continues after clearance or replans with that edge excluded. It learns over repeated episodes. The oracle knows the true distributions and class/blockage probabilities; it does not know the actual future clearance time of every obstacle.

Refer to caption
Figure 2: Our proposed pipeline. The robot follows the planned path till a blockage is detected. The reflectivity image and segmentation mask are used to determine the object type. The planner then uses the corresponding survival model to compute a patience threshold W⋆W^{\star}, waits up to that threshold, and either resumes the original path if the obstacle clears or replans if the blockage persists.

3.1 Learning Class-Conditioned Obstacle Persistence

For each class, estimate the survival function of remaining blockage time measured from first encounter, not from obstacle creation. Each observed clearance multiplies the survival estimate by the fraction of at-risk observations that remain blocked. A reroute contributes a right-censored sample: the obstacle lasted at least that long, without falsely recording clearance. Independent censoring conditional on modeled variables is a required statistical assumption, as discussed in survival-analysis theory [18].

Equation 1
S^k​(τ)=∏τj≤τ(1−djnj).\widehat{S}_{k}(\tau)=\prod_{\tau_{j}\leq\tau}\left(1-\frac{d_{j}}{n_{j}}\right). (1)

3.2 Arrival-Time-Dependent Edge Costs

For an unremembered edge, expected delay combines the learned blockage rate, encountered-class frequencies, and class mean residual lifetimes. For a remembered edge, store class and first/last observation times. At a planned future arrival, condition survival on the last confirmed observation, then mix the expected remaining delay if the old obstacle persists with the ordinary new-blockage delay if it has cleared. These are shared class/graph estimates rather than edge-specific contextual models. Finite mean delays and defined survival-ratio denominators are necessary; handling an unobserved or incompletely observed survival tail is not fully specified.

Refer to caption
Figure 3: Example wait-or-reroute decision at a blocked edge. After identifying a chair, the planner uses the learned survival model to compute Aclear​(c)A_{\mathrm{clear}}(c), Aavoid​(W)A_{\mathrm{avoid}}(W), and J⁡(W)J(W). The minimizer W⋆W^{\star} gives the patience threshold; here the obstacle persists, so the robot reroutes.

3.3 Wait-or-Reroute Decision at a Blocked Edge

For each possible waiting threshold, average the time-to-goal over clearance before the threshold, then add the cost of waiting to the deadline and rerouting when the obstacle remains. Both terms include elapsed waiting from the original encounter, avoiding double counting. Minimize this expectation within a bounded horizon. With a Kaplan–Meier curve, clearance contributions become a finite sum over observed events.

Equations 2–3
J⁡(W)=∫0WAclear​(c)​d​Fk​(c)+Sk​(W)​Aavoid​(W),J(W)=\int_{0}^{W}A_{\mathrm{clear}}(c)\,dF_{k}(c)+S_{k}(W)\,A_{\mathrm{avoid}}(W), (2)
J^​(W)=∑τj≤Wp^k,j​Aclear​(τj)+S^k​(W)​Aavoid​(W).\widehat{J}(W)=\sum_{\tau_{j}\leq W}\widehat{p}_{k,j}\,A_{\mathrm{clear}}(\tau_{j})+\widehat{S}_{k}(W)\,A_{\mathrm{avoid}}(W). (3)

3.3.1 Computing A clear and A avoid

After clearance, shortest-path planning may use the newly available edge but need not do so. After abandoning the wait, planning excludes that edge. Other remembered blockages make downstream costs depend on arrival time. The main method evaluates survival event times and horizon endpoints using time-dependent Dijkstra; the appendix develops the functional Bellman–Ford view. A separate implementation paragraph specifies 300-point grids, so the exact reported search discretization is not entirely consistent across descriptions.

3.4 Online Adaptation

Record the duration observed and whether clearance occurred, then update class statistics along with blocked-edge and class frequencies. The main text describes an update after each encounter; the detailed simulation protocol instead freezes the model during an episode and updates from all accumulated observations afterward. Repeated visits can count as separate encounters because persistent physical obstacles are not explicitly associated across observations.

4 Experimental Evaluation of Survival-Guided Navigation

Simulation controls obstacle generation and provides an oracle comparison. Physical experiments validate integration with a taught route graph and semantic labeling, including a separate less-controlled person/chair setting.

4.1 Simulation Experiments

Over one thousand episodes per run and one hundred random seeds, OSCAR averages 160.7 seconds to goal versus 159.3 for the oracle, 185.9 without obstacle memory, 210.5 for a fixed class rule, 218.2 for always waiting, and 264.7 for always rerouting. All of these reach 100% success under the one-hour timeout. Greedy CTP reaches only 13.1% because it permanently forbids encountered blocked edges within each episode; timeout assignment drives its 3,135.7-second mean.

The learned policy is about 0.9% slower than this oracle on the reported mean. Sample-cap experiments indicate rapid gains with fewer than twenty observations per class, but do not provide a general sample-complexity guarantee. In a separate bimodal-lifetime ablation, retaining censored observations estimates residual clearance at 241.4 seconds versus a true 246.1, while discarding them yields 205.8.

Planning benchmarks use 49–1,024 vertices and four, eight, or sixteen classes. At the largest tested graph, reported mean and 95th-percentile threshold-computation times are below 0.172 and 0.276 seconds. Candidate-time capping limits growth with accumulated data; this measured timing is not a guarantee for arbitrary graph density or history.

Refer to caption
Figure 4: Race to 200. Oracle comes first place. Our method is best amongst alternatives (198).
Refer to caption
(a) Mean time-to-goal across episodes.
Refer to caption
(b) Effect of limiting Kaplan–Meier samples.
Figure 5: Simulation performance and data-efficiency results. (a) The learned policy improves with experience, outperforms the heuristic baselines, and approaches the oracle policy. (b) Performance improves sharply with a small number of clearance samples and then saturates near the oracle policy.
Table 1: Summary of simulation results over 100 runs (1000 episodes per run). All metrics are averaged per episode. Reroutes denotes the number of route changes, waiting time is the cumulative time spent waiting, and blocked edges counts obstacle encounters, including repeated encounters with the same edge. OSCAR achieves the lowest mean time-to-goal among non-oracle methods by balancing waiting and rerouting.
Method Time-to-goal (s) ↓\downarrow Success rate ↑\uparrow Reroutes Waiting time Blocked edges
Always Wait 218.2 100.0% 0.0 186.2 2.8
Always Reroute 264.7 100.0% 24.2 0.0 24.2
Rule-Based 210.5 100.0% 11.9 29.0 16.1
Greedy CTP 3135.7 13.1% 3.4 0.0 2.5
OSCAR w/o Memory 185.9 100.0% 1.8 149.8 4.5
OSCAR (Ours) 160.7 100.0% 0.5 121.9 3.4
Oracle 159.3 100.0% 0.5 121.7 3.3
[Uncaptioned image]
Figure 6: Navigation performance with and without censored observations (10 seeds).
[Uncaptioned image]
Figure 7: Mean W⋆W^{\star} computation time by graph size and obstacle class count.
Refer to caption

(a) Strategy comparison

Refer to caption

(b) Learned patience thresholds

Figure 8: Simulation analysis of the learned KM policy on a grid graph. (a) Comparison of navigation strategies across 300 episodes, showing mean time-to-goal, waiting time, obstacle encounters, and reroutes. (b) Distribution of selected patience thresholds W⋆W^{\star} for each obstacle class. OSCAR generally waits for people, balances waiting and rerouting for chairs and bins, and reroutes immediately for tubes.

4.2 Real-World Experiments

A physical robot follows an atrium route network using teach-and-repeat navigation [9]. A vision–language model labels masked lidar reflectivity images as person, chair, bin, or tube; the graph planner then chooses the wait. Fifty main episodes recreate simulator-generated placement and clearance schedules. Travel time improves toward roughly two hundred seconds and compares favorably with always waiting in the plotted deployment.

People usually receive long waits, chairs and bins mixed waiting/rerouting, and tubes frequent immediate reroutes. Maximum waits are chosen empirically from objective curves. Infinite-wait cases mean no alternate path exists, rather than an inferred finite clearance deadline. These staged physical results establish integration and adaptation under controlled scenarios, not an unbiased evaluation of natural obstacle lifetimes.

Refer to caption

(a) Atrium graph

Refer to caption

(b) Example obstacle encounter sequence

Figure 9: Real-world deployment setup. (a) Graph and allowable obstacle spawn locations in the atrium. Each color represents a distinct corridor segment connecting junctions in the taught-route network. (b) Representative obstacle encounter sequence illustrating wait and reroute decisions.
Refer to caption

(a) Time-to-goal

Refer to caption

(b) Wait vs. reroute decisions

Refer to caption

(c) Selected patience thresholds

Figure 10: Real-world experiment results. (a) Time-to-goal over 50 navigation episodes, showing how performance improves with online experience. (b) Frequency of wait and reroute decisions made by the learned policy during deployment. (c) Distribution of selected patience thresholds W⋆W^{\star}.

5 Limitations and Future Work

The reroute estimate treats the alternative as a committed route and does not fully account for later replanning, potentially making detours look too expensive. Kaplan–Meier estimation also relies on noninformative censoring. Adaptive deadlines do not automatically violate that assumption in the class-conditioned simulator, but real context could affect both clearance time and the attractiveness of rerouting.

Spatially shared blockage statistics ignore route-specific activity; repeated encounters may concern the same physical obstacle; and labeling errors can choose the wrong survival model. More detailed contextual classes, obstacle association, and semantic priors are proposed improvements. The framework does not establish theoretical learning guarantees under all these feedback effects.

6 Conclusion

Survival learning, remembered blockages, and arrival-time-aware route costs provide an effective wait-or-reroute policy in the tested settings. Censored observations and memory both contribute. The result is near-oracle performance for the specified model and experiments, with broader real-world reliability depending on perception, context, and model assumptions.

Appendix Appendix A Functional Time-Dependent Planner and Proofs

The proof appendix establishes FIFO edge-arrival functions, monotone functional shortest-path costs, and a finite threshold candidate set for the Kaplan–Meier objective.

Appendix A.1 FIFO Edge Arrival Functions

For an unremembered edge, arrival time equals departure plus a constant expected cost, so it is monotone. For a remembered obstacle, multiply survival probability by conditional residual life to obtain an integrated survival tail divided by survival at last observation. Differentiating leaves nonnegative terms because survival cannot increase and elapsed age cannot decrease. For stepwise Kaplan–Meier curves, slopes are nonnegative between events and jumps cannot go downward. Thus the specified expected-cost model is FIFO, assuming valid denominators and finite integrals; this is a property of the planning approximation, not every possible stochastic traffic process.

Equations
Φe​(t)=t+w⁡(e)+Δ^​(e,t),\Phi_{e}(t)=t+w(e)+\widehat{\Delta}(e,t),
t1≤t2⟹Φe​(t1)≤Φe​(t2).t_{1}\leq t_{2}\quad\Longrightarrow\quad\Phi_{e}(t_{1})\leq\Phi_{e}(t_{2}).
Δ^​(e,t)=Δ^new,\widehat{\Delta}(e,t)=\widehat{\Delta}_{\mathrm{new}},
Φe​(t)=t+w⁡(e)+Δ^new,d​Φed​t=1≥0.\Phi_{e}(t)=t+w(e)+\widehat{\Delta}_{\mathrm{new}},\qquad\frac{d\Phi_{e}}{dt}=1\geq 0.
ae=tlast​(e)−tfirst​(e),be​(t)=t−tfirst​(e),a_{e}=t_{\mathrm{last}}(e)-t_{\mathrm{first}}(e),\qquad b_{e}(t)=t-t_{\mathrm{first}}(e),
Δ^​(e,t)=qe​(t)​μ^eold​(t)+(1−qe​(t))​Δ^new,\widehat{\Delta}(e,t)=q_{e}(t)\widehat{\mu}^{\mathrm{old}}_{e}(t)+(1-q_{e}(t))\widehat{\Delta}_{\mathrm{new}},
qe​(t)=S​(be​(t))S⁡(ae)q_{e}(t)=\frac{S(b_{e}(t))}{S(a_{e})}
μ^eold​(t)=∫0∞S​(be​(t)+r)S​(be​(t))​𝑑r.\widehat{\mu}^{\mathrm{old}}_{e}(t)=\int_{0}^{\infty}\frac{S(b_{e}(t)+r)}{S(b_{e}(t))}\,dr.
qe​(t)​μ^eold​(t)=1S⁡(ae)​∫0∞S⁡(be​(t)+r)​𝑑r=1S⁡(ae)​∫be​(t)∞S⁡(r)​𝑑r.q_{e}(t)\widehat{\mu}^{\mathrm{old}}_{e}(t)=\frac{1}{S(a_{e})}\int_{0}^{\infty}S(b_{e}(t)+r)\,dr=\frac{1}{S(a_{e})}\int_{b_{e}(t)}^{\infty}S(r)\,dr.
Φe​(t)=t+w⁡(e)+1S⁡(ae)​∫be​(t)∞S⁡(r)​𝑑r+(1−S​(be​(t))S⁡(ae))​Δ^new.\Phi_{e}(t)=t+w(e)+\frac{1}{S(a_{e})}\int_{b_{e}(t)}^{\infty}S(r)\,dr+\left(1-\frac{S(b_{e}(t))}{S(a_{e})}\right)\widehat{\Delta}_{\mathrm{new}}.
d​Φed​t=1−S​(be​(t))S⁡(ae)−S′​(be​(t))S⁡(ae)​Δ^new.\frac{d\Phi_{e}}{dt}=1-\frac{S(b_{e}(t))}{S(a_{e})}-\frac{S^{\prime}(b_{e}(t))}{S(a_{e})}\widehat{\Delta}_{\mathrm{new}}.
S′​(be​(t))≤0.S^{\prime}(b_{e}(t))\leq 0.
S⁡(be​(t))≤S⁡(ae).S(b_{e}(t))\leq S(a_{e}).
1−S​(be​(t))S⁡(ae)≥0,1-\frac{S(b_{e}(t))}{S(a_{e})}\geq 0,
−S′​(be​(t))S⁡(ae)​Δ^new≥0.-\frac{S^{\prime}(b_{e}(t))}{S(a_{e})}\widehat{\Delta}_{\mathrm{new}}\geq 0.
d​Φed​t≥0.\frac{d\Phi_{e}}{dt}\geq 0.
d​Φed​t=1−S​(be​(t))S⁡(ae)≥0.\frac{d\Phi_{e}}{dt}=1-\frac{S(b_{e}(t))}{S(a_{e})}\geq 0.
(1−S​(be​(t))S⁡(ae))​Δ^new\left(1-\frac{S(b_{e}(t))}{S(a_{e})}\right)\widehat{\Delta}_{\mathrm{new}}

Appendix A.2 Functional Bellman–Ford Computation

Functional Bellman–Ford propagates earliest-arrival functions rather than scalar times. Each relaxation composes the upstream function with the FIFO edge-arrival function and takes a pointwise minimum. Composition and minimum preserve monotonicity. Under Kaplan–Meier costs the functions are piecewise affine, with breakpoints introduced by survival events and route comparisons. The learned implementation evaluates candidate times with Dijkstra instead of explicitly propagating every function.

Equation
Bv​(z)←min⁡{Bv​(z),Φe​(Bu​(z))}.B_{v}(z)\leftarrow\min\left\{B_{v}(z),\,\Phi_{e}(B_{u}(z))\right\}.

Clear case.

For the clearance case, initialize the current vertex’s arrival time to the clearance parameter and all other vertices to infinity. Mark the encountered edge available and relax graph edges for at most the number of vertices minus one passes. The resulting goal-arrival function includes both waiting and subsequent travel.

Equations
Bv0clear​(c)=c,B^{\mathrm{clear}}_{v_{0}}(c)=c,
Bvclear​(c)=+∞,v≠v0.B^{\mathrm{clear}}_{v}(c)=+\infty,\qquad v\neq v_{0}.
Bvclear​(c)←min⁡{Bvclear​(c),Φe​(Buclear​(c))}B^{\mathrm{clear}}_{v}(c)\leftarrow\min\left\{B^{\mathrm{clear}}_{v}(c),\,\Phi_{e}(B^{\mathrm{clear}}_{u}(c))\right\}
Aclear​(c)=Bgclear​(c).A_{\mathrm{clear}}(c)=B^{\mathrm{clear}}_{g}(c).

Avoid case.

For the avoidance case, initialize the current vertex at the patience deadline, remove the still-blocked edge, and perform the same functional relaxations. The goal-arrival function includes the abandoned wait and the best remaining route under the modeled downstream costs.

Equations
Bv0avoid​(W)=W,B^{\mathrm{avoid}}_{v_{0}}(W)=W,
Bvavoid​(W)=+∞,v≠v0.B^{\mathrm{avoid}}_{v}(W)=+\infty,\qquad v\neq v_{0}.
Bvavoid​(W)←min⁡{Bvavoid​(W),Φe​(Buavoid​(W))},e=(u,v)≠eb.B^{\mathrm{avoid}}_{v}(W)\leftarrow\min\left\{B^{\mathrm{avoid}}_{v}(W),\,\Phi_{e}(B^{\mathrm{avoid}}_{u}(W))\right\},\qquad e=(u,v)\neq e_{b}.
Aavoid​(W)=Bgavoid​(W).A_{\mathrm{avoid}}(W)=B^{\mathrm{avoid}}_{g}(W).

Appendix A.3 Monotonicity of A clear and A avoid

Both cases start from nondecreasing functions and preserve that property through every relaxation. Therefore delaying clearance or delaying abandonment cannot reduce total arrival time measured from the original encounter. Downstream expected waiting can decrease with later arrival, but the FIFO proof bounds that decrease so it cannot outweigh the extra elapsed wait.

Equations
Bv0clear​(c)=c,B^{\mathrm{clear}}_{v_{0}}(c)=c,
Aclear​(c)=Bgclear​(c)A_{\mathrm{clear}}(c)=B^{\mathrm{clear}}_{g}(c)
Bv0avoid​(W)=WB^{\mathrm{avoid}}_{v_{0}}(W)=W
Aavoid​(W)=Bgavoid​(W)A_{\mathrm{avoid}}(W)=B^{\mathrm{avoid}}_{g}(W)

Appendix A.4 Finite Candidate Set for the KM Objective

Between observed clearance events, no new probability mass enters the clearance sum and the survival weight stays constant. The only changing term is the nondecreasing avoid-route cost, so an interval’s best threshold lies at its left endpoint. Consequently zero and survival event times within the horizon suffice; adding the upper endpoint is harmless. This exact argument applies to the discrete estimated distribution, not an arbitrary continuous distribution or an approximate capped grid.

Equations
0<τ1<τ2<⋯<τJ.0<\tau_{1}<\tau_{2}<\cdots<\tau_{J}.
J^​(W)=∑τj≤Wp^k,j​Aclear​(τj)+S^k​(W)​Aavoid​(W),\widehat{J}(W)=\sum_{\tau_{j}\leq W}\widehat{p}_{k,j}A_{\mathrm{clear}}(\tau_{j})+\widehat{S}_{k}(W)A_{\mathrm{avoid}}(W),
p^k,j=S^k​(τj−1)−S^k​(τj).\widehat{p}_{k,j}=\widehat{S}_{k}(\tau_{j-1})-\widehat{S}_{k}(\tau_{j}).
J^​(W)=Cj+S^k​(τj)​Aavoid​(W),\widehat{J}(W)=C_{j}+\widehat{S}_{k}(\tau_{j})A_{\mathrm{avoid}}(W),
W⋆=arg​minW∈𝒞⁡J^​(W),𝒞={0}∪{τj:τj≤Wmax}.W^{\star}=\operatorname*{arg\,min}_{W\in\mathcal{C}}\widehat{J}(W),\qquad\mathcal{C}=\{0\}\cup\{\tau_{j}:\tau_{j}\leq W_{\max}\}.
𝒞impl={0,Wmax}∪{τj:τj≤Wmax}.\mathcal{C}_{\mathrm{impl}}=\{0,W_{\max}\}\cup\{\tau_{j}:\tau_{j}\leq W_{\max}\}.

Appendix Appendix B Simulation Details

Simulation uses a known route network, fixed start, farthest goal vertex, and speed of 0.95 meters per second. Multiple routes permit nontrivial choices between waiting and detouring.

Refer to caption
Figure 11: Graph used for simulation experiments. The graph contains multiple alternate routes, allowing policies to trade off waiting against rerouting when obstacles temporarily block edges.

Appendix B.1 Ground-Truth Obstacle Distributions

Each class has a lognormal lifetime from spawn, with people shorter-lived and tubes longest-lived. An obstacle encountered at a random steady-state time is length-biased: longer-lived obstacles are more likely to be present. The relevant residual survival is the normalized integral of the original lifetime survival, not that raw lifetime curve. The robot learns this remaining-time distribution directly from encounters.

Equations
C(k)∼LogNormal⁡(μk,σk),C^{(k)}\sim\mathrm{LogNormal}(\mu_{k},\sigma_{k}),
SC(k)​(t)=ℙ⁡(C(k)>t)S_{C}^{(k)}(t)=\mathbb{P}(C^{(k)}>t)
SR(k)​(t)=ℙ⁡(R(k)>t),S_{R}^{(k)}(t)=\mathbb{P}(R^{(k)}>t),
SR(k)​(t)=1𝔼⁡[C(k)]​∫t∞SC(k)​(u)​𝑑u.S_{R}^{(k)}(t)=\frac{1}{\mathbb{E}[C^{(k)}]}\int_{t}^{\infty}S_{C}^{(k)}(u)\,du.
Refer to caption
Figure 12: Ground-truth obstacle clearance distributions used in simulation. Top: clearance-time densities from obstacle spawn time. Bottom: clearance survival SC​(t)S_{C}(t) and residual survival SR​(t)S_{R}(t) at obstacle encounter. The residual distribution is the distribution relevant to the robot’s wait-or-reroute decision.

Appendix B.2 Poisson Obstacle Spawning

A global Poisson process chooses spawn locations uniformly; attempts on an occupied edge are ignored. Each edge alternates free and blocked periods. The rate is selected so mean blocked time divided by mean cycle time equals the desired occupancy, using five percent in the main setting. A 1,500-second warm-up brings the field toward stationarity before navigation begins.

Equations
α=λm.\alpha=\frac{\lambda}{m}.
C¯=∑k∈𝒦qk​𝔼​[C(k)],\bar{C}=\sum_{k\in\mathcal{K}}q_{k}\,\mathbb{E}[C^{(k)}],
pblock=C¯1/α+C¯=α​C¯1+α​C¯.p_{\mathrm{block}}=\frac{\bar{C}}{1/\alpha+\bar{C}}=\frac{\alpha\bar{C}}{1+\alpha\bar{C}}.
α=pblockC¯​(1−pblock),\alpha=\frac{p_{\mathrm{block}}}{\bar{C}(1-p_{\mathrm{block}})},
λ=m​α=m​pblockC¯​(1−pblock).\lambda=m\alpha=\frac{mp_{\mathrm{block}}}{\bar{C}(1-p_{\mathrm{block}})}.
pblock=0.05,p_{\mathrm{block}}=0.05,

Appendix B.3 Class Spawn Weights

Encountered class frequencies weight spawn frequencies by mean lifetime. To target a 55/30/10/5 percent encounter mix, the appendix uses approximately 94.4/4.3/1.0/0.3 percent spawn probabilities for person/chair/bin/tube. This differs from the main text’s statement that 55/30/10/5 are spawn probabilities. The appendix’s explicit lifetime-corrected construction is retained as the detailed protocol.

Equations
rk=qk​𝔼​[C(k)]∑jqj​𝔼​[C(j)].r_{k}=\frac{q_{k}\mathbb{E}[C^{(k)}]}{\sum_{j}q_{j}\mathbb{E}[C^{(j)}]}.
qk∝rk𝔼⁡[C(k)],q_{k}\propto\frac{r_{k}}{\mathbb{E}[C^{(k)}]},
rperson=0.55,rchair=0.30,rbin=0.10,rtube=0.05.r_{\mathrm{person}}=0.55,\qquad r_{\mathrm{chair}}=0.30,\qquad r_{\mathrm{bin}}=0.10,\qquad r_{\text{tube}}=0.05.
2626,119,28,82626,\quad 119,\quad 28,\quad 8
94.4%,4.3%,1.0%,0.3%.94.4\%,\quad 4.3\%,\quad 1.0\%,\quad 0.3\%.

Appendix B.4 Learning and Planning Settings

The learned policy starts without seeded clearance samples and updates once per completed episode, with no explicit exploration. This paragraph specifies 300 points for both patience and downstream time grids, a global 2,000-second cap, and class caps of 300 seconds for people and 1,000 for each other class. These settings differ in description from the event-time-only search in the main method. Initial empty-curve behavior and finite-tail conventions are not fully documented.

Equations
Wmax=2000​s.W_{\max}=2000\,\mathrm{s}.
Wmaxperson=300​s,Wmaxchair=1000​s,Wmaxbin=1000​s,Wmaxtube=1000​s.W_{\max}^{\mathrm{person}}=300\,\mathrm{s},\qquad W_{\max}^{\mathrm{chair}}=1000\,\mathrm{s},\qquad W_{\max}^{\mathrm{bin}}=1000\,\mathrm{s},\qquad W_{\max}^{\text{tube}}=1000\,\mathrm{s}.

Appendix B.5 Episodes, Timeouts, and Baselines

Episodes exceeding 3,600 seconds count as failures and receive that full duration in time statistics. One hundred seeds each run one thousand episodes. Greedy CTP permanently excludes observed blocked edges for the rest of the episode, which can disconnect the effective graph; its poor timeout-dominated result should be interpreted against this specific heuristic, not all planners for the Canadian Traveller Problem.

Appendix B.6 Scenario Manifests for Real-World Experiments

Scenario manifests specify obstacle class, location, and timing for later physical runs. Logs from one run update survival estimates before the next manifest is used. This permits controlled reconstruction of traffic events and explains why the main physical evaluation is orchestrated.

Appendix B.7 Generalization Across Graph Topologies and Blockage Rates

Three graph topologies and blockage rates of two, five, and ten percent test different detour costs. Results use the final one hundred episodes of ten seeds. At ten percent on the original graph, OSCAR takes 268.8 seconds versus 311.2 for waiting and 512.5 for immediate rerouting. On a warehouse graph, expensive detours make waiting competitive with OSCAR; on a grid, cheap alternatives make immediate rerouting competitive at low occupancy. These results show adaptation to the tested cost structure rather than uniform dominance of every heuristic in every regime.

Appendix Appendix C Obstacle Classification Prompt

The complete original classifier prompt and deployment settings are preserved. The model receives a reflectivity image and, when available, a binary obstacle mask; it returns one fixed-format label from person, chair, bin, and sonotube. A person beside an object is treated according to the prompt’s object-priority rule. The classifier supplies labels only—clearance-duration estimation is disabled and navigation decisions remain in the planner. Deterministic wording and a fixed schema do not guarantee correct or deterministic model outputs, especially when the mask is unavailable.

Developer:
You are a deterministic robotics assistant for obstacle classification.
Follow instructions exactly and be consistent.

User:
You are an expert in indoor mobile robot navigation (Clearpath Jackal).
You are given a LiDAR intensity image (reflectivity/signal) and a
separate mask image highlighting the obstacle region. Focus ONLY on the
masked obstacle region(s). If there is both a person and another
obstacle like a chair or door, the other obstacle (chair/door) is the
dominant obstacle.

Second image is a binary mask aligned with the LiDAR image, where white
pixels mark the obstacle region and black is background. Focus ONLY on
the object in the white region.

Classify the dominant obstacle in the masked region by choosing EXACTLY
ONE label: {person, chair, sonotube, bin}.
A sonotube is a portable upright cardboard cylindrical column (a movable
fake pillar) on the floor.

Output EXACTLY: Obstacle: <label>.
Refer to caption
Figure 13: Example obstacle-classification log. The VLM receives a LiDAR reflectivity image and an aligned binary obstacle mask, and returns a deterministic class label in the required parseable format.

Appendix Appendix D Person/Chair-Only Real-World Results

A supplementary run uses naturally appearing people and chairs without prescribed removal timers. Waiting remains common for people, while chairs elicit more detours. Travel time later rises as obstacle counts increase, so the curve is not a controlled stationary learning comparison. Bin and sonotube labels in this run are classification errors, not additional present object types. This provides useful qualitative evidence outside the staged protocol while directly exposing perception limitations.

Refer to caption

(a) Time-to-goal

Refer to caption

(b) Encounter outcomes

Refer to caption

(c) Patience thresholds

Figure 14: Unorchestrated person–chair real-world experiment. Unlike the orchestrated real-world scenarios, obstacles are not introduced or removed according to a prescribed timer. The learned policy usually waits for people, more often reroutes around chairs, and selects patience thresholds consistent with these behaviors. Bin and sonotube entries correspond to ChatGPT obstacle-labeling misclassifications in an environment containing only people and chairs.
Concept demonstration

Open image ↗