Optimal target search: modeling complex evasive behavior with automata

Overview & Synopsis

In this study, we address the problem of target search, specifically focusing on the search allocation problem which involves optimizing the distribution of a search budget to detect a target. Previous studies in the scientific literature have made oversimplifications about target behavior, typically assuming either that the target has perfect knowledge of the searchers and makes optimal decisions, or that the target's movements are entirely predictable and will not change in response to the search efforts. To overcome these limitations, we propose a new mathematical model that represents the target as a deterministic automaton. This model allows for the representation of complex target behavior, closer from a real human behavior, where the target's strategy can evolve with partial information gained about the searchers and where suboptimal decisions are modeled. The mathematical formulation is a mixed-integer non-linear program, and we propose an adaptation of a Forward-And-Backward heuristic algorithm to provide solutions to this problem.Experimental studies evaluate the feasibility of this approach in terms of computation time and quality of the solutions and demonstrate the potentials and limits of such an approach.