Approximation and Heuristic Algorithms for Probabilistic Physical Search on General Graphs
This work addresses search-and-rescue or exploration missions, such as Mars rover mineral mining, by providing practical algorithms for a previously studied but unsolved problem on general graphs, representing an incremental advancement.
The paper tackles the problem of probabilistic physical search on general graphs, where an agent aims to acquire an item with uncertain prices at various locations while minimizing travel and purchase costs, and presents the first approximation and heuristic algorithms for this setting, demonstrating their effectiveness through simulations on real and synthetic graphs.
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.