Computational complexities of honey-pot searching with local sensory information

Abstract

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.