Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Adaptive Probabilistic Planning for the Uncertain and Dynamic Orienteering Problem
The Orienteering Problem (OP) is a well-studied routing problem that has been extended to incorporate uncertainties, reflecting stochastic or dynamic travel costs, prize-collection costs, and prizes. Existing approaches …
SchedulingA Spatio-Temporal Representation for the Orienteering Problem with Time-Varying Profits
We consider an orienteering problem (OP) where an agent needs to visit a series (possibly a subset) of depots, from which the maximal accumulated profits are desired within given limited time budget. Different from most …
Searching k-Optimal Goals for an Orienteering Problem on a Specialized Graph with Budget Constraints
We propose a novel non-randomized anytime orienteering algorithm for finding k-optimal goals that maximize reward on a specialized graph with budget constraints. This specialized graph represents a real-world scenario wh…
Clustered Orienteering Problem with Subgroups
This paper introduces an extension to the Orienteering Problem (OP), called Clustered Orienteering Problem with Subgroups (COPS). In this variant, nodes are arranged into subgroups, and the subgroups are organized into c…
Efficiently solving the thief orienteering problem with a max-min ant colony optimization approach
We tackle the Thief Orienteering Problem (ThOP), an academic multi-component problem that combines two classical combinatorial problems, namely the Knapsack Problem and the Orienteering Problem. In the ThOP, a thief has …
Benchmarking