Path Constrained Search Problem With Reward Criterion

A target is moving on a finite number of cells in discrete time. Knowing the probabilities of the target's path selection, a searcher is searching for the target in this search space with constraints that he can move from cell i to one of the adjacent cells. He gains a value V(t) on the detection of the target at time t but expends cost c_0(i,t) for the search in cell i at t. In this paper, we propose a method to find an optimal path for the searcher, which maximizes the expected reward defined as the expected value minus the expected cost. We use a branch and bound procedure with an upper bound estimation given by solving the problem relaxed in continuous search effort.