Source-linked AI summary
Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics
Masafumi Endo, Kohei Honda, Yuu Jinnai, Ryo Yonetani
TL;DR
OP-UTVR addresses routing when rewards change stochastically and cannot be known in advance. The paper develops three planners and a robot benchmark, finding that long-horizon planning with online adaptation performs best among the proposed approaches.
Problem
Existing orienteering formulations largely assume known rewards, leaving uncertain stochastic changes and limited-horizon prediction errors insufficiently represented.
Method
The paper introduces OP-UTVR, three planners with different prediction horizons and online adaptivity, theoretical performance bounds, and a mobile service robot benchmark.
Results
A 2.1% optimality gap made the adaptive planner closest to the oracle, versus 8.9% offline and 22.5% one-step gaps.
Takeaways & Limitations
Effective OP-UTVR planning combines long-horizon planning with runtime observation updates under uncertain pedestrian movements.
Takeaways & Limitations
The study focuses on Markovian dynamics, leaving nonlinear or non-Markovian transition models for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces OP-UTVR, a routing problem for collecting stochastic, time-varying rewards when agents can forecast them only over a limited horizon. It proposes three prediction-based planners and a mobile service robot benchmark to study this setting.
- Motivation: Real-world rewards are dynamic and uncertain, creating challenges for routing in applications such as transportation and disaster response.Passenger demand shifts over time, while rescue success probabilities can diminish under uncertain dynamics.
- Problem: Existing orienteering formulations commonly assume static rewards or reward dynamics known to the agent, causing a gap when actual rewards deviate from expectations.These assumptions rarely hold in practice.
- Novelty: OP-UTVR models rewards that vary stochastically over time and limits agents to predicting time-varying rewards for only a finite horizon h.The formulation directly captures two challenges arising from reward uncertainty.
- Planning Algorithms: The study analyzes three planners: One-Step Planner, Offline Planner, and Adaptive Online Planner, which differ in prediction use and replanning behavior.The planners range from greedy immediate-reward selection to full-path planning with online replanning at visited locations.
- Benchmark: The evaluation introduces a mobile service robot benchmark in reconstructed indoor environments, where pedestrian interactions provide uncertain time-varying rewards.The robot seeks interactions for activities such as greeting or advertising while navigating among moving pedestrians.
2 Preliminaries
This section reviews the classical orienteering problem (OP), which selects and orders vertices to maximize rewards under a time budget, and its known time-varying-reward extension. The key distinction is that classical rewards are static and certain, whereas time-varying rewards depend on visit time and are assumed known in advance.
- Classical OP: The classical OP selects and orders vertices to maximize collected rewards under a time budget.An instance includes vertices, edges, rewards, travel times, and an initial vertex.
- Classical OP: In classical OP, static and certain rewards allow the optimal path to be planned entirely in advance.This assumption applies to settings such as tourist trip planning, where location values are predetermined.
- Known time-varying rewards: The time-varying extension assigns each vertex a reward rtv(v, t), so optimization must jointly determine vertex selection and visit timing.The reward function maps vertex-time pairs to nonnegative rewards.
- Known time-varying rewards: Prior time-varying OP methods assume reward dynamics are completely known in advance, as in factory production schedules or periodic patterns.Ma et al. introduced the extension, and Cao et al. improved efficiency through heuristic search.
3 Orienteering Problem with Uncertain Time-Varying Rewards (OP-UTVR)
OP-UTVR extends the orienteering problem to uncertain, time-varying rewards that can be predicted from observations over short horizons, while allowing repeated vertex visits. The agent observes rewards online, estimates transition dynamics, and selects an adaptive policy to maximize expected total reward.
- Problem formulation: OP-UTVR features uncertain time-varying rewards whose dynamics can be predicted from observations over a short horizon, and permits consecutive or repetitive vertex revisits.The formulation models applications such as a service robot predicting pedestrian locations within a battery limit.
- Problem formulation: The true reward vector rtv and transition matrix P are unknown in advance; the agent observes rtv(t) at each timestep and accesses an estimate ˆP ≈ P.The underlying reward dynamics are assumed to follow a Markov chain over vertices.
- Reward prediction: Using ˆP and the initial observation rtv(0), the agent estimates expected future rewards as E[ˆrtv(t) | rtv(0)] = rtv(0) ˆP^t.The estimate can be updated from observations during traversal, enabling decisions under uncertainty.
- Online decision-making: OP-UTVR solutions are adaptive policies π that choose the next vertex from current circumstances, including agent and reward positions and remaining timesteps.Online adaptation allows the agent to respond to unexpected traversal outcomes.
- Objective and structure: Because rewards move and can accrue while occupying a vertex, the agent may revisit vertices consecutively to wait or repetitively to obtain new rewards.The objective is to maximize expected total reward Rtot(π); with known dynamics, the problem can be cast as an MDP, although P is unavailable here.
4 Planning Algorithms
Section 4 introduces three planners for OP-UTVR that differ in their use of predicted rewards and online observations. It motivates adaptive replanning and derives guarantees showing that model error and reward stochasticity determine planner performance.
- Planner overview: The framework compares One-Step, Offline, and Adaptive Online Planners, alongside performance guarantees under stochastic reward dynamics.The planners select successive vertices using different information about uncertain, time-varying rewards.
- One-Step Planner: One-Step Planner greedily maximizes predicted reward at only the next vertex, without considering future rewards.It makes its decision upon arrival at each vertex.
- Offline Planner: Offline Planner precomputes a fixed plan maximizing expected total reward, but cannot remain optimal when rewards change nondeterministically or transition estimates accumulate error.It follows the plan regardless of observations during execution, using only initial reward observations and estimated transitions.
- Adaptive Online Planner: Adaptive Online Planner replans at every vertex arrival using updated reward observations, allowing it to respond when later rewards differ from initial expectations.Its replanning can change the selected destination as current observations update estimated total rewards.
- Performance guarantees: With the true reward transition model, Adaptive Online Planner achieves the optimal solution; with empirical estimates from i.i.d. demonstrations, its suboptimality bound shrinks as transition samples increase.The analysis identifies model error as the source of replanning loss and reward stochasticity as a distinct fundamental challenge.
- Performance guarantees: Offline performance degrades relative to adaptive planning as reward-transition stochasticity increases, while the advantage of adaptation grows with that stochasticity.Theorem 3 analyzes this relationship under an exact transition model.
5 Experiments
Experiments benchmark five planners in simulated indoor environments with stochastic pedestrian rewards, showing that predicted reward dynamics improve performance over greedy planning. Adaptive replanning achieves near-oracle performance at higher computational cost, with larger benefits in environments exhibiting greater reward variance.
- Experimental setup: The benchmark uses ten 25 m × 25 m indoor environments, each containing 13 gathering spots and 20 pedestrians transitioning stochastically between spots.Environments come from HM3D and Gibson scans and are simulated in IR-SIM.
- Quantitative results: All three proposed planners using predicted reward dynamics outperform πgreedy, while πoracle achieves the highest total reward using true future pedestrian distributions.The comparison covers five planners across 100 test instances.
- Quantitative results: πadapt achieves the highest total reward in 64 cases, versus 25 for πoffline and 11 for πone-step.Their optimality gaps relative to πoracle are 2.1%, 8.9%, and 22.5%, respectively, reflecting adaptive, full-horizon, and myopic planning.
- Computational tradeoffs: πadapt demands the highest computation because it replans, whereas πone-step uses minimal computation and πoffline incurs moderate computation from solving once.The computational tradeoff accompanies πadapt’s near-oracle performance.
- Environmental effects: Higher free space ratio correlates with greater reward variance (r = 0.36, p < 0.001), which increases πadapt’s improvement over πoffline (r = 0.29, p < 0.01).Free space ratio ranges from 0.34–0.53 across maps.
6 Related Work
The paper situates OP-UTVR within research on budgeted orienteering, robotic applications, and uncertain or time-varying rewards. It distinguishes the setting from MDP formulations because transitions are known and deterministic while reward dynamics alone are uncertain.
- OP and its variants: The orienteering problem sequences vertex visits to maximize rewards under budget constraints and has been studied for optimality, computational efficiency, and scalability.OP is NP-hard and has received extensive operations-research attention.
- Robotic applications: OP’s flexible resource-constrained formulation supports robotic applications including environmental monitoring, exploration, and search-and-rescue.Robotic objectives can involve maximizing task completion under time or energy constraints.
- Uncertain/dynamic rewards: Prior stochastic and time-varying reward formulations address uncertainty but assume known future reward dynamics, whereas this work combines time-varying rewards with uncertain dynamics.The paper identifies complete knowledge of future reward dynamics as an assumption rarely satisfied in practice.
- Relation to MDP: Unlike MDP methods that learn state transitions and reward functions, this setting has deterministic, known agent transitions and requires learning only reward transitions.The distinction applies because only reward dynamics are uncertain in the paper’s formulation.
7 Conclusion · A Proofs · orienteering problem with uncertain time-varying rewards (OP-UTVR).
The paper formulates OP-UTVR as an orienteering variant with stochastic, initially unknown rewards that agents predict from observations, and evaluates three planners with theoretical performance bounds. It also introduces a real-world 3D-scan mobile service robot benchmark and reports planning-horizon trade-offs.
- 7 Conclusion: OP-UTVR models rewards that change stochastically and cannot be known in advance.This differs from prior formulations assuming known reward dynamics.
- orienteering problem with uncertain time-varying rewards (OP-UTVR).: Agents predict future reward transitions from observations to support routing under uncertain rewards.The formulation explicitly permits prediction rather than requiring rewards to be known beforehand.
- 7 Conclusion: The study investigates three planning algorithms for OP-UTVR.The planners are evaluated within the proposed uncertain-reward formulation.
- 7 Conclusion: The paper provides theoretical bounds on the performance of the investigated algorithms.These bounds address planner performance under the OP-UTVR setting.
- 7 Conclusion: The benchmark uses a mobile service robot operating with real-world 3D scans.This supplies a robotics evaluation setting for OP-UTVR.
- 7 Conclusion: Experiments reveal trade-offs between planning horizons.The conclusion identifies planning horizon as an experimentally consequential design dimension.
- A Proofs: The proofs establish Theorems 1–3 and their supporting lemmas.The supplied proofs section passage states that these results are proved.
A.1 Proof of Theorem 1
The proof models OP-UTVR with exact reward-transition estimates as a Markov decision process, then shows Adaptive Online Planner computes its optimal policy.
- Optimality: Adaptive Online Planner achieves the optimal solution because, with known transition dynamics, it selects at each state the action maximizing expected total reward.This matches the optimal MDP policy obtainable through dynamic programming or policy iteration.
- MDP construction: When ˆP = P, an OP-UTVR instance is an MDP whose state includes the agent’s position, current reward distribution, and remaining time budget.The action space selects the next vertex; reward distributions evolve according to P raised to the travel time, and the process becomes absorbing when the time budget expires.
- MDP construction: The MDP policy corresponds exactly to the OP-UTVR policy, and their expected total rewards coincide.The agent receives the reward at the selected vertex upon arrival.
A.2 Proof of Theorem 2
Theorem 2 establishes a high-probability bounded-suboptimality guarantee for Adaptive Online Planner when demonstrations are i.i.d. and the empirical transition distribution estimates the true dynamics. The proof bounds value-function error from transition mismatch and controls empirical estimation error using concentration and a union bound.
- Theorem 2: Under i.i.d. demonstrations, Adaptive Online Planner using empirical transition estimate ˆP has expected total reward bounded suboptimally with high probability.The guarantee is stated in terms of the maximum vertex reward rmax, the number of transition samples |D|, and failure probability δ.
- Proof via value-function error: If ∥ˆP −P∥∞≤ϵ, the value-function discrepancy is bounded recursively by transition mismatch, using the reward bound rmaxTmax.The transition error limits the next-state distribution difference in total variation, and unrolling the recursion over Tmax steps gives the finite-horizon bound.
- Proof via concentration: Hoeffding’s inequality bounds each empirical transition entry, while a union bound over all |V|2 entries yields a simultaneous high-probability estimate for ˆP.Combining this estimation guarantee with the lemma’s value bound completes the proof of Theorem 2.
A.3 Proof of Theorem 3
Theorem 3 bounds the advantage of adaptive online planning over offline planning when reward transitions are stochastic and estimated dynamics are correct. Its proof compares expected maxima with maxima of expectations and shows the gap vanishes for deterministic transitions.
- Theorem 3: Under the assumption ˆP = P, Theorem 3 bounds the performance difference using the maximum per-vertex reward and the number of nondeterministic reward objects.The theorem explicitly assumes correct transition-model knowledge and defines rmax as the maximum reward obtainable at any vertex.
- Lemma 3: Adaptive Online Planner achieves expected per-step reward E[maxv∈V Xv], whereas Offline Planner achieves at most maxv∈V E[Xv].The comparison follows by representing future vertex rewards as random variables and contrasting the expectation of the maximum with the maximum of expectations.
- Proof: Using independent stochastic reward-object transitions, the proof applies concentration to bound the gap between the expected maximum and the maximum of expectations over vertices.Each reward object contributes a value in [0, rmax], transitions independently according to P, and vertex totals are sums of independent variables.
- Corollary 1: When P is deterministic, each Xv is fixed, so E[maxv Xv] = maxv E[Xv] and the adaptive-versus-offline gap is zero.Deterministic transitions remove the randomness in vertex rewards, making the two expressions equal.
B Experimental Details
Experiments used a CPU-only Python implementation with parameters fixed a priori as realistic service-robot benchmark choices rather than tuned by hyperparameter search.
- Implementation: Experiments ran on 8 CPU cores with 30 GB RAM and required no GPU.The implementation was written in Python 3.12.
- Parameterization: All experimental parameters were fixed a priori as benchmark design choices rather than selected through hyperparameter search.The choices were based on realistic service-robot settings.
- Parameterization: Table 1 lists the parameters used in the experiments.The transition matrix P was designed as described in Sec. 5.1.