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.

  • $\begingroup$ On a quick read, this seems like many problems that are encountered in the field of planning (under uncertainty). There are very practical problems in which the agent needs to decide when to move and where, when to measure something using what measurement channel, and so on. $\endgroup$ – Juho May 17 '13 at 2:06
  • $\begingroup$ @Juho - can you think of, or link to, any particular problems similar in nature to the signal-based search here? "Planning under uncertainty" is a very helpful search term, so thank you, but the papers I'm finding are largely all too abstract, talking about AI and generic state-transition graphs with goal states. $\endgroup$ – torquestomp May 17 '13 at 2:43
  • $\begingroup$ I'm no expert, but also partially observable Markov decision process come to mind. I recently saw a robot solving a problem that I think was similar to yours but more complex, and it was solving POMDPs using different techniques. Maybe they fit your problem too, but I'm not really thinking hard at the moment :-) $\endgroup$ – Juho May 17 '13 at 3:20
  • $\begingroup$ In a similar vein to @Juho's suggestions I'd add optimal stopping problems, and the multi-armed bandit problem in particular. $\endgroup$ – Wandering Logic May 17 '13 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.