Search papers, labs, and topics across Lattice.
This paper introduces the orienteering problem with uncertain time-varying rewards (OP-UTVR), which extends traditional orienteering formulations by incorporating the uncertainty of rewards that change over time, reflecting real-world scenarios like fluctuating customer demand. The authors develop three distinct planning strategies that vary in their planning horizons and adaptability to online observations, providing a theoretical framework for understanding their performance under reward variability. Experimental results highlight the advantages of long-horizon planning combined with online adaptation, showcasing its effectiveness in navigating complex environments with unpredictable reward dynamics.
Long-horizon planning with online adaptation can significantly enhance service robots' efficiency in environments with unpredictable, time-varying rewards.
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.
