Computational complexities of honey-pot searching with local sensory information
Bhaskar DasGupta, João P. Hespanha, Eduardo D. Sontag · 2004
We investigate the problem of searching for a hidden target in a bounded region of the plane, by an autonomous robot, which is only able to use limited local sensory information. We formalize a discrete version of the problem as a "reward-collecting" path problem and provide efficient approximation algorithms for various cases.