不確実で時間変動する報酬を持つオリエンテーリング問題：日常サービスロボティクスのためのフレームワークとベンチマーク
Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics
報酬が事前に不明で時間とともに変動するオリエンテーリング問題（OP-UTVR）を提案し、観測から報酬動態を推定して将来を予測する3つのプランナーを比較、屋内環境の移動サービスロボットベンチマークで評価した。
著者: Masafumi Endo, Kohei Honda, Yuu Jinnai, Ryo Yonetani
分類: cs.RO, cs.AI
原文アブストラクト
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.