  We consider an agent seeking to obtain an item, potentially available at
different locations in a physical environment. The traveling costs between
locations are known in advance, but there is only probabilistic knowledge
regarding the possible prices of the item at any given location. Given such a
setting, the problem is to find a plan that maximizes the probability of
acquiring the good while minimizing both travel and purchase costs. Sample
applications include agents in search-and-rescue or exploration missions, e.g.,
a rover on Mars seeking to mine a specific mineral. These probabilistic
physical search problems have been previously studied, but we present the first
approximation and heuristic algorithms for solving such problems on general
graphs. We establish an interesting connection between these problems and
classical graph-search problems, which led us to provide the approximation
algorithms and hardness of approximation results for our settings. We further
suggest several heuristics for practical use, and demonstrate their
effectiveness with simulation on real graph structure and synthetic graphs.
