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 they can move from cell i to one of the adjacent cells. They gain a value V(t) on the detection of the target at time t but expends cost co(i,t) for the search in cell i at t. In this paper, the authors 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. They use a branch and bound procedure with an upper bound estimation given by solving the problem relaxed in continuous search effort.