Robot navigation improves with smart waiting and rerouting decisions
SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting
Robotics
Summary
Robots often face temporary obstacles that block their way, like a door that might open soon or a hallway that might clear. The authors created a method called SPARROW that helps robots decide whether to wait, find a new path, or gather more information before moving. SPARROW uses a technique that plans while considering uncertain obstacles and learns how long they usually last. This approach helps robots reach their destinations faster both in simulations and real-life tests.
What this means in practice
- •For mobile robot developers: Improve navigation efficiency by enabling robots to decide when to wait or reroute around temporary blockages using learned obstacle clearance patterns.
- •For warehouse automation teams: Reduce delivery times by adapting robot routes dynamically based on observed temporary obstacles in warehouse environments.
Authors
Hshmat Sahak, Aoran Jiao, Nicholas Rhinehart, Timothy D. Barfoot
Abstract
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.