The orienteering Problem with Replenishment

摘要

The planning of long-duration missions for resource-constrained agents is a longstanding challenge not only in field robotics research, but also in the fields of vehicle routing and logistics. To efficiently plan missions over a larger time scale than an agent’s resource capacity natively allows, it is necessary to exploit the availability of recharging stations, where an agent can replenish its spent resources at the cost of time. This paper presents the Orienteering Problem with Replenishment, a novel extension of the orienteering problem, which can fully utilise the existence of recharging stations by not only revisiting such stations, but also intelligently managing the amount of time spent recharging at each stop. By leveraging the above mechanisms for overcoming the resource limitations of the platform, the proposed problem formulation allows for the planning of longer term missions. A suite of computational tests are performed to assess the proposed formulation, and its performance is analysed with respect to the impact of intelligent utilisation of the recharge points on reward acquisition. Finally, limitations of the proposed problem formulation are discussed, and avenues for future work are presented.