Multi-Objective Search Game : Long-Term vs Short-Term

This study focuses on investigating a multi-objective search allocation game problem, specifically addressing the distribution of a search budget (player 1) across a searched area to detect an evading target (player 2). The game is characterized as a two-person zero-sum game, as an optimal search strategy must consider the target’s optimal evasion strategy. Traditionally, the detection probability at the end of the time horizon has been the primary objective function in search theory literature. Our work extends the problem by proposing a multi-objective formulation that aims to strike a balance between long-term and short-term search objectives. In this context, the objective is to maximize the detection probability of the target at the end of each time period (e.g., hourly) throughout the time horizon. The main challenge in this problem lies in handling a multitude of objective functions, where the number of objective functions is determined as input data. To the best of our knowledge, no prior research has explored such a multi-objective search allocation game. Therefore, we meticulously examine the significance of this problem by highlighting the disparities and conflicts among these objectives. Subsequently, we propose an solution approach based on the epsilon-constraint algorithm, as well as a heuristic method that decomposes the problem into smaller multi-objective subproblems. A series of experiments is conducted to evaluate two key aspects of the results: computation time and quality, by comparing the exact and approximate outcomes