Energy-efficient Orienteering Problem in the Presence of Ocean Currents

Abstract

In many environmental monitoring applications robots are often tasked to visit various distinct locations to make observations and/or collect specific measurements. The problem of scheduling and assigning robots to the various tasks and planning feasible paths for the robots can be posed as an Orienteering Problem (OP). In the standard OP, routing and scheduling is achieved by maximizing an objective function by visiting the most rewarding locations while respecting a limited travel budget. However, traditional formulations for such problems usually neglect some environmental features that can greatly impact the tour, e.g., flows, such as wind or ocean currents. This is of particular importance for applications in marine and atmospheric environments where vehicle motions can be significantly impacted by the environmental dynamics and the environment exerts a non-negligible force on the vehicles. In this paper, we tackle the OP in fluid environments where robots must operate in the presence of ocean and/or atmospheric currents. We introduce a novel multi-objective formulation that combines both task and path planning problems, and whose goals are to (i) maximize the collected reward, while (ii) minimizing the energy expenditure by leveraging the environmental dynamics wherever possible. We validate our strategy using simulated ocean model data to show that our approach can generate a diverse set of solutions that have an adequate compromise between both objectives.