# Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics

arXiv: https://arxiv.org/abs/2608.18672 · HTML: https://mlsanity.com/paper/2608.18672/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 25 references that are in the map.
- First posted on arXiv 19 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [Habitat-Matterport 3D Dataset (HM3D): 1000 Large-scale 3D Environments for Embodied AI](https://mlsanity.com/paper/2109.08238/) (2021)
- [Gibson Env: Real-World Perception for Embodied Agents](https://mlsanity.com/paper/1808.10654/) (2018)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Large Scale Markov Decision Processes with Changing Rewards](https://mlsanity.com/paper/1905.10649/) (2019)
- [FIG-OP: Exploring Large-Scale Unknown Environments on a Fixed Time Budget](https://mlsanity.com/paper/2203.06316/) (2022)
- [A Spatio-Temporal Representation for the Orienteering Problem with Time-Varying Profits](https://mlsanity.com/paper/1611.08037/) (2016)

## Abstract (arXiv)

We present the orienteering problem with uncertain time-varying rewards (OP-UTVR), a novel variant of the orienteering problem (OP). While most existing OP formulations assume rewards to be known in advance, practical applications involve uncertain and time-varying rewards, as with shifting customer demand for delivery agents. OP-UTVR relaxes this assumption by allowing agents to estimate reward dynamics from observations and forecast future rewards. This enables informed routing decisions despite stochastic reward changes and inevitable prediction errors. We address this problem using three planners that differ in planning horizon and online adaptivity, and derive theoretical bounds on their performance under reward stochasticity. We further introduce a mobile service robot benchmark for OP-UTVR, where a robot navigates among pedestrians in indoor environments. Experiments reveal trade-offs between planning horizon and adaptivity, and demonstrate the effectiveness of long-horizon planning with online adaptation.