Risk-Aware Submodular Optimization for Stochastic Travelling Salesperson Problem

Abstract

We introduce a risk-aware variant of the Traveling Salesperson Problem (TSP), where the robot tour cost and reward have to be optimized simultaneously, while being subjected to uncertainty in both. We study the case where the rewards and the costs exhibit diminishing marginal gains, i.e., are submodular. Since the costs and the rewards are stochastic, we seek to maximize a risk metric known as Conditional-Value-at-Risk (CVaR) of the submodular function. We propose a Risk-Aware Greedy Algorithm (RAGA) to find an approximate solution for this problem. The approximation algorithm runs in polynomial time and is within a constant factor of the optimal and an additive term that depends on the value of optimal solution. We use the submodular function’s curvature to improve approximation results further and verify the algorithm’s performance through simulations.