Searching for a Moving Hider on a Star
Jennifer Iglesias · 2012
In a search game, a seeker searches for a hider in some space. In some versions of the problem, the hider is stationary, and other times the hider is allowed to move but has a maximum speed, w. The seeker will always have maximum speed 1. The space in which the game takes place can also be varied. In all cases, the seeker is denied some information about the game, whether it is the hider’s location or information on the search space itself. The goal of the hider is to avoid capture if possible, and if he can’t avoid capture then to maximize the time until capture. In contrast, the seeker wishes to minimize the time until guaranteed capture. Search games have been studied on different types of graphs including stars in (1), and trees in (2). In these cases, only the case where the hider is immobile is investigated. Presented here are some results on the case where the hider is also allowed to move within the search space. For clarity’s sake, we will refer to the hider as he, and the the seeker as she. The search spaces to be investigated here are stars. A star is a a graph in which all the edges emanate from one vertex. We will call a star a n-star if it has exactly n edges, and we will call the center vertex from which all edges emanate the origin. We will assume that all legs have length 1. Some examples of stars are given below in 1