  We study the problem of incorporating risk while making combinatorial
decisions under uncertainty. We formulate a discrete submodular maximization
problem for selecting a set using Conditional-Value-at-Risk (CVaR), a risk
metric commonly used in financial analysis. While CVaR has recently been used
in optimization of linear cost functions in robotics, we take the first step
towards extending this to discrete submodular optimization and provide several
positive results. Specifically, we propose the Sequential Greedy Algorithm that
provides an approximation guarantee on finding the maxima of the CVaR cost
function under a matroidal constraint. The approximation guarantee shows that
the solution produced by our algorithm is within a constant factor of the
optimal and an additive term that depends on the optimal. Our analysis uses the
curvature of the submodular set function, and proves that the algorithm runs in
polynomial time. This formulates a number of combinatorial optimization
problems that appear in robotics. We use two such problems, vehicle assignment
under uncertainty for mobility-on-demand and sensor selection with failures for
environmental monitoring, as case studies to demonstrate the efficacy of our
formulation. In particular, for the mobility-on-demand study, we propose an
online triggering assignment algorithm that triggers a new assignment only can
potentially lead to reducing the waiting time at demand locations. We verify
the performance of the Sequential Greedy Algorithm and the online triggering
assignment algorithm through simulations.
