This is more of an open-ended information question, but to make it concrete, here's an example problem I have thought up:
Consider an $N\times N$ grid, $N$ odd, and consider that a single chunk of rare, valuable metal, lies buried under one of the unit squares with uniform probability.
An agent, $X$, starts at the center square of this grid, and this agent can do three things:
- Move to any adjacent square, (no diagonals), with cost $M > 0$
- Dig at the current square, with cost $D > 0$, in search of the treasure. If the treasure is buried at said square, the agent is guaranteed to find it.
With cost $S, 0 < S < D$, the agent may attempt to 'detect' the presence of the treasure with a radar device. Given the actual location of the treasure, set $L$ to be the Euclidean distance between the center of $X$'s square and the square containing the treasure.
The agent then receives, after conducting the test, a random real-valued number $r$, from the uniform distribution on the interval $[0, 1/(L^2 +1) ] $. Note that the agent can, and will, with 100% probability, receive different signals from the same square over multiple tests.
Given that the agent is a perfect logician, what is the expected total cost $C$ he will incur on a search for the treasure?
My suspicion is that this problem is, at the very least, NP-hard in terms of $N^2$, the size of the grid. And though I suspect a perfect agent would, given a proper adversarial input, incur infinite cost over time, there exists a comprehensive naive solution involving no signal tests, with worst-case cost $M*(N^2-1)+D*N^2$, and so the agent must always only consider choices with expected total-cost of finding the treasure less than this bound - i.e., stick to a finite number of decision paths.
Does anyone have any experience or familiarity with a problem like this? Is there a name for this variety of problem? Is there, perhaps, some other choice of signal function that has been studied more in-depth? I'm not interested in a deterministic function, which would be rather trivial to analyze - one key property of this function that makes the problem interesting is that, for any finite number of tests, there is non-zero probability that all the signals come back in the range $0 < r < \epsilon$, where $\epsilon$ is the minimum upper bound on a signal distribution given the grid size $N$ - such an adversarial set of signals would convey 0 information asymptotically over time, which means that a deterministic, signal-based solution algorithm (much less an optimal one) is impossible.
Also, I realize that optimal strategies will likely vary wildly for different values of $M$, $S$, and $D$, so for the purpose of discussion, let's suppose they are $3$, $1$, and $10$ respectively.