The optimal searcher path problem with a visibility criterion in discrete time and space

In this paper, the problem of path planning for a ground search unit looking for an object of unknown location is considered. As in the classical optimal searcher path problem, the probability of finding the search object is the main criterion of optimality and the search unit is constrained by the environment topology that influences its choices for a navigable path as well as its detection capabilities. This paper proposes an extension to the classical optimal searcher path problem in discrete time and space by integrating inter-region visibility as an additional criterion. This new formulation allows a refinement in the discretization of the space in which a ground search unit evolves. A general mixed-integer programming model is proposed, and experimental results with a moving object in grid environments are discussed.