  Consider a general path planning problem of a robot on a graph with edge
costs, and where each node has a Boolean value of success or failure (with
respect to some task) with a given probability. The objective is to plan a path
for the robot on the graph that minimizes the expected cost until success. In
this paper, it is our goal to bring a foundational understanding to this
problem. We start by showing how this problem can be optimally solved by
formulating it as an infinite horizon Markov Decision Process, but with an
exponential space complexity. We then formally prove its NP-hardness. To
address the space complexity, we then propose a path planner, using a
game-theoretic framework, that asymptotically gets arbitrarily close to the
optimal solution. Moreover, we also propose two fast and non-myopic path
planners. To show the performance of our framework, we do extensive simulations
for two scenarios: a rover on Mars searching for an object for scientific
studies, and a robot looking for a connected spot to a remote station (with
real data from downtown San Francisco). Our numerical results show a
considerable performance improvement over existing state-of-the-art approaches.
