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

Masafumi Endo; Kohei Honda; Yuu Jinnai; Ryo Yonetani

cs.ROAug 19, 2026

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

Authors: Masafumi Endo, Kohei Honda, Yuu Jinnai, Ryo Yonetani

Organizations: CyberAgent Inc. · Nagoya University

Abstract

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.

Figures & tables

Figure 1: Motivating application: Service robot benchmark for OP-UTVR. A robot plans a path to maximize pedestrian interactions within a time budget $T$ . Vertices are gathering spots, with colors indicating visitor density (red, green, blue, white from high to empty). Rewards change as visitors move, a setting that traditional OP cannot handle.

Figure 2: Solution overview. Left: observations (top row) refine predictions over time (lower rows). Badges A–C mark the information each planner uses. Right: (A) One-Step Planner maximizes immediate reward, (B) Offline Planner follows a precomputed multi-step plan, (C) Adaptive Online Planner updates both predictions and plans as observations arrive.

Panel of Figure 3 — Figure 3: 3D views of example indoor environments from HM3D. We use bird’s-eye view maps from these scans.

Figure 4: Statistical performance comparison of five planners across 100 instances (10 vertex placements

\times

10 maps). (a) Total reward. (b) Optimality gap relative to

\pi^{\mathrm{oracle}}

. (c) Reward-computation tradeoff, with points as instances and circles as means.

Figure 5: Snapshots of three planners for robot orienteering among pedestrians. $R_{\mathrm{tot}}$ denotes the total reward at each snapshot. Voronoi cell colors indicate predicted rewards (warmer for higher values), with gray dashed boundaries. Annotations: black diamonds (graph vertices), dark gray (obstacles), cyan dot (robot), trajectory cyan-to-magenta over time, green dots (pedestrians).

Figure 6: Environmental effect on planner performance. Point colors indicate maps. (a) Free space ratio vs. reward variance. (b) Reward variance vs. improvement of

\pi^{\mathrm{adapt}}

over

\pi^{\mathrm{offline}}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Parameter	Value
Environment size	25 m $\times$ 25 m
Number of environments (maps)	10
Vertex placements per environment	10
Gathering spots per environment ( $\|\mathcal{V}\|$ )	13
Number of pedestrians ( $N$ )	20
Time budget ( $T_{\mathrm{max}}$ )	240 s

Appendix

Table 1: Experimental parameters.

Service Robotics

See all 12 papers

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests
Sep 24, 2026Duo Zhang, Jintong Li, Junshan Huang +1Motion Planning Sampling-Based Motion Planning
Department of Computer Science, Rutgers, the State University of New Jersey, Piscataway, NJ, USA
Trajectory-Safe Orienteering for Human-Robot Shared Environments
Sep 28, 2026Songqun Gao, Elena Basei, Marco Roveri +2Trajectory Generation Robot Safety
Department of Industrial Engineering, Universit`a di Trento, Trento, Italy. · Interdepartmental Robotics Labs (IDRA), University of Trento, Trento, Italy · Department of Information Engineering and Computer Science, Universit`a di Trento, Trento, Italy.
Learning to Solve Orienteering Problem with Time Windows and Variable Profits
Mar 6, 2026Songqun Gao, Zanxi Ruan, Patrick Floor +3Learning to Optimize Combinatorial Optimization
Department of Industrial Engineering, Università di Trento, Trento, Italy · Interdepartmental Robotics Labs (IDRA), Trento, Italy · Department of Engineering for Innovation Medicine, Università di Verona, Verona, Italy +2

Sep 24, 2026J/K move · Enter open · S save

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests

Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu

Department of Computer Science, Rutgers, the State University of New Jersey, Piscataway, NJ, USA

Motion Planning Sampling-Based Motion Planning Dynamic Obstacle Avoidance Kinodynamic Motion Planning

Open paper AskPDF arXiv

We propose ST-pRRTC, a GPU-parallel space- time RRT-Connect motion planner for problems with known obstacle trajectories and unspecified arrival time. Searching over many arrival times broadens temporal coverage but divides a finite planning budget among more backward trees. To address the challenge, ST-pRRTC builds a shared forward tree and an adaptive forest of backward goal-time trees. Its interval root formulation samples goal arrival times continuously and guarantees probabilistic completeness and asymptotic arrival- time optimality under the stated assumptions in a bounded time domain. The practical root recycling policy has no such guar- antees. It adapts a fixed number of backward trees, replacing later roots while retaining useful search progress. Experiments on three dynamic benchmarks show that both variants achieve lower mean first-solution times and earlier mean final arrivals than ST-RRT* and SI-RRT on problems solved by all compared methods. Further experiments demonstrate the benefit of recy- cling over broad arrival-time ranges. Real-robot demonstrations show root-recycling ST-pRRTC planning motions for a UR5e among moving Crazyflie quadrotors.

Abstract

Service Robotics

Explore similar work

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests

Trajectory-Safe Orienteering for Human-Robot Shared Environments

Learning to Solve Orienteering Problem with Time Windows and Variable Profits