Abstract
This paper considers the problem of an agent searching for a resource or a tangible good in a physical environment, where at each stage of its search it observes one source where this good can be found. The cost of acquiring the resource or good at a given source is uncertain (a-priori), and the agent can observe its true value only when physically arriving at the source. Sample applications involving this type of search include agents in exploration and patrol missions (e.g., an agent seeking to find the best location to deploy sensing equipment along its path). The uniqueness of these settings is that the expense of observing the source on each step of the process derives from the last source the agent explored. We analyze three variants of the problem, differing in their objective: minimizing the total expected cost, maximizing the success probability given an initial budget, and minimizing the budget necessary to obtain a given success probability. For each variant, we first introduce and analyze the problem with a single agent, either providing a polynomial solution to the problem or proving it is NP-Complete. We also introduce an innovative fully polynomial time approximation scheme algorithm for the minimum budget variant. Finally, the results for the single agent case are generalized to multi-agent settings.
Introduction
Traditional economic search theory, exemplified by "Pandora’s Problem," typically assumes stationary observation costs. For instance, checking prices online costs the same regardless of the previous site visited. However, in physical robotics—such as a Mars rover searching for minerals or a drone on a patrol mission—costs are inherently spatial and non-stationary. Moving to a new location to inspect a resource changes the relative distance (and thus the cost) to all other potential sites.
This paper bridges the gap between economic search and physical constraints by modeling search problems where travel costs depend on the agent's current position. The agent must decide not only when to stop but also the optimal sequence of exploration to manage limited resources like battery or time.
Methodology
The authors approach the problem through the lens of computational complexity and algorithm design, focusing primarily on agents moving along a 1D path. In this setting, the "visited" area is always a contiguous interval, which allows for manageable state spaces in Markov Decision Process (MDP) modeling.
The authors use computational complexity analysis to show that while the path setting offers some tractability, general metric spaces are NP-Hard. Surprisingly, budget-constrained variants (Max-Probability and Min-Budget) are NP-Complete even on a 1D path, due to a reduction from the Knapsack Problem. To address this, they developed a Fully Polynomial Time Approximation Scheme (FPTAS) using a "$\delta$-resolution tour" that discretizes decision points into "quantum steps."
Key Results
The study provides a comprehensive complexity landscape for physical search. While minimizing expected cost on a path is solvable in polynomial time, introducing a hard budget makes the problem significantly more difficult, often requiring complex "zig-zag" paths to optimize budget usage.
Key findings include:
- Min-Expected-Cost (Path): Solvable in $O(d^2m^2)$ for $m$ locations and $d$ prices.
- Budget Variants (Path): Proven NP-Complete; addressed by an FPTAS achieving a $(1 + \epsilon)$ approximation in $O(n \epsilon^{-6})$ time.
- Multi-Agent Scaling: For a fixed number of agents $k$, the Min-Expected-Cost problem remains solvable in polynomial time, though complexity grows exponentially with $k$.
Conclusion
This work highlights how spatial constraints transform classic search problems. While 1D paths allow for efficient algorithms in some cases, the introduction of budgets or higher-dimensional spaces quickly leads to intractability. Future research will focus on multi-agent coordination with private budgets and finding efficient approximations for multi-agent expected cost minimization in large-scale deployments.
Summary updated