Robotics Research Hub
SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting

SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting

Hshmat Sahak, Aoran Jiao, Nicholas Rhinehart, Timothy D. Barfoot · N/A · 2026

reinforcement-learning planning
PDF arXiv

Framework

N/A

License

N/A

Stars

N/A

Summary

Temporary obstacles that may block a robot's planned route create a sequential navigation problem: a robot must decide whether to wait for a blockage to clear, reroute, or acquire more information about the obstacle before acting.

Abstract Summary

Temporary obstacles that may block a robot's planned route create a sequential navigation problem: a robot must decide whether to wait for a blockage to clear, reroute, or acquire more information about the obstacle before acting. We formulate graph navigation among temporary obstacles as a partially observable semi-Markov decision process and introduce SPARROW, a belief-space planner built on Partially Observable Monte Carlo Planning (POMCP). SPARROW searches over traversal, observation, and finite-duration waiting actions while maintaining a particle belief over latent obstacle classes and clearance times. Class-conditioned survival models are learned online from both clearance observations and right-censored encounters where the robot reroutes before clearance is observed. A generative model simulates obstacle arrivals and clearances as each action unfolds, so the planner can account for blockages that may occur along alternative routes. We further introduce a value-of-learning criterion that trades the immediate cost of collecting labelled survival data against its expected reduction in future navigation regret. Across two simulation graphs and multiple obstacle-class settings, SPARROW reduces mean time-to-goal by 12-26% relative to OSCAR, a recent survival-based method for the same problem. On a physical mobile robot, SPARROW reduces mean time-to-goal by 20.5% relative to OSCAR while selectively observing, waiting, and rerouting as environment conditions change.

Key Points

  • Temporary obstacles that may block a robot's planned route create a sequential navigation problem: a robot must decide whether to wait for a blockage to clear, reroute, or acquire more information about the obstacle before acting.
  • We formulate graph navigation among temporary obstacles as a partially observable semi-Markov decision process and introduce SPARROW, a belief-space planner built on Partially Observable Monte Carlo Planning (POMCP).
  • SPARROW searches over traversal, observation, and finite-duration waiting actions while maintaining a particle belief over latent obstacle classes and clearance times.
  • Class-conditioned survival models are learned online from both clearance observations and right-censored encounters where the robot reroutes before clearance is observed.
  • A generative model simulates obstacle arrivals and clearances as each action unfolds, so the planner can account for blockages that may occur along alternative routes.

Problem Formulation

We consider navigation on a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ from start $v_{s}$ to goal $v_{g}$. Edge $e$, when unblocked, has nominal traversal time $d_{e}$, but may become temporarily blocked, preventing traversal. We formulate the task as a stochastic shortest-path partially observable semi -Markov decision process (POSMDP) [ 15 ] .

Problem Formulation — SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting
Fig. 2: SPARROW combines within-episode belief-space lookahead with cross-episode value-of-learning exploration.

Method

SPARROW combines online class-conditioned survival learning with particle-based POMCP. Within an episode, the current learned obstacle model is fixed and POMCP searches for the action minimizing expected remaining travel time. Between episodes, newly collected labeled obstacle encounters update the survival models.

An outer value-of-learning calculation decides when deliberately collecting such a sample is worth the cost it adds to the current episode.

Method — SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting
Fig. 3: Main simulation result. Left: the two evaluation graphs; S and G mark start and goal. Right: mean time-to-goal versus episode for $K=1,2,4$ latent obstacle classes on Atrium (top) and Grid-$5\times 5$ (bottom). Curves are trailing $20$-episode means over $10$ seeds, bands are $\pm 1$ standard error across seeds, and oracle variants are dashed.

Simulation Experiments

We evaluate on two graph families. Atrium : a metric graph of poses and traversable edges, is obtained by a teach-and-repeat navigation system [ 27 ] from a robot deployment in an indoor campus atrium.

For planning, chains of degree-two localization vertices are contracted into corridor-level edges, yielding a decision graph whose vertices are junctions and whose edges are the corridors of the deployed route; obstacles block corridors, matching the granularity at which the robot can actually commit to an alternative.

Simulation Experiments — SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting
Fig. 4: Key ablations on Atrium, $K{=}4$. Top: time-to-goal; bottom: median planning latency. Replan compares planning only when the intended edge is blocked with replanning at every decision epoch. Leaf compares route simulation with our expected-cost leaf evaluator. $N_{\mathrm{sim}}$ varies the POMCP simulation budget. KG compares value-of-learning exploration off/on. Blue marks our selected configuration; lower is better. KG uses the right scale.

Real-World Robot Experiments

We deploy SPARROW on a Clearpath Jackal navigating a taught route with the Visual Teach and Repeat (VT&R) navigation stack [ 27 ] , in a $22.1\times 20.9$ m indoor campus atrium. The robot executes the same graph-level actions as in simulation while the low-level controller follows the taught geometry between vertices.

Real-World Robot Experiments — SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting
Fig. 5: Real-world SPARROW deployment. (a) The deployed route graph: taught edges coloured by the corridor they contract into, decision vertices marked. (b) A representative encounter. (c) Time-to-goal per episode (trailing $10$-episode mean); the dashed line marks where the survival estimates are treated as converged. (d) Action selected at blocked encounters. (e) Wait-versus-reroute outcome by obstacle class. (f) Empirical distribution of onboard planning latency at blocked decisions, showing the fraction of decisions completed within each time; median, 90th-percentile, and maximum latencies are all below the $5$ s deadline.

Sources and Demonstrations

Figures are reproduced from Sahak et al. See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.

Share

Related Papers

AcousticDiffusion: Semantically Conditioned Audio-Guided Diffusion Policy for Search-and-Rescue Assistance
arXiv preprint

AcousticDiffusion: Semantically Conditioned Audio-Guided Diffusion Policy for Search-and-Rescue Assistance

Iana Zhura, Didar Seyidov, Dmitrii Plotnikov et al.

Navigating toward human callers is an important capability for rescue robots operating where visual contact is degraded or occluded. We present AcousticDiffusion, a semantically conditioned, audio-guided diffusion policy for human-directed navigation.

locomotion vision reinforcement-learning planning
PDF Advanced
Actively Resolving Contextual Uncertainty for Underspecified Tasks in Natural Language
arXiv preprint

Actively Resolving Contextual Uncertainty for Underspecified Tasks in Natural Language

Zachary Ravichandran, Jonathan Diller, Fernando Cladera et al.

Foundation models provide robots with the ability to interpret natural language and reason about environmental context, yet most language-conditioned policies assume that goals are well-specified and that task-relevant information is provided upfront via a prior map.

vla reinforcement-learning planning
Code PDF Advanced
GitHub ★ —