Risk-Aware Submodular Optimization for Multi-objective Travelling Salesperson Problem
This addresses optimization for robots in uncertain environments, but it is incremental as it builds on prior submodular TSP work by adding risk-awareness.
The paper tackles a risk-aware multi-objective Traveling Salesperson Problem with uncertain submodular costs and rewards, proposing a greedy algorithm (RAGA) that achieves a constant-factor approximation with an additive term in polynomial time.
We introduce a risk-aware multi-objective Traveling Salesperson Problem (TSP) variant, where the robot tour cost and tour reward have to be optimized simultaneously. The robot obtains reward along the edges in the graph. We study the case where the rewards and the costs exhibit diminishing marginal gains, i.e., are submodular. Unlike prior work, we focus on the scenario where the costs and the rewards are uncertain and seek to maximize the Conditional-Value-at-Risk (CVaR) metric of the submodular function. We propose a risk-aware greedy algorithm (RAGA) to find a bounded-approximation algorithm. The approximation algorithm runs in polynomial time and is within a constant factor of the optimal and an additive term that depends on the optimal solution. We use the submodular function's curvature to improve approximation results further and verify the algorithm's performance through simulations.