In a generic problem in search theory we have some metric search space and two players - a target T and a searcher S. Mostly T is static in the space according to some specified probability distribution or in some cases dynamic, and S starts its search at some arbitrary start point. The usual goal will be to design a strategy that minimizes the expected time for S to find T. S knows the search space but has no other information and T could be a fully or partially informed target. In some versions, S has visibility characteristics allowing it to see a small distance δ from its location. This kind of exploration problems relate to various contexts, such as robot motion planning in hazardous or inaccessible terrain, maintaining security of large networks, and searching, indexing, and analyzing digital data in the Internet [1] [2] [3]. One of the earliest examples of such problems is the linear search problem, proposed by Bellman [4] and Beck [5]. Here, the search space is an infinite line, with the searcher initially at an arbitrary origin, and the target located at an unknown point on the line, at distance d from the origin. The objective is to minimize the worst-case ratio of the distance traveled by the searcher over d. Different scenario (with cycles) is considered in cops and robbers problem [6] where the cops and robbers take alternate turns in movements and the question usually posed is how many pursuers are necessary to ensure the eventual capture of all the robbers. The Isaac’s Princess and Monster problem [7] is also a related problem but with different scenario. The Lost Cow problem [8] is stated as a short-sighted cow following along an infinite fence and wants to find the gate. The lost cow problem is limited in the idea that the target is static. In case of one dimensional space, if a moving target wants to escape, then it can do so by constantly moving away from the searcher. And in case of a cyclic graph, a fully informed target can move around in cycles and never be found by the searcher. The present study stands out in that it studies the problem in case of undirected acyclic graph which was not studied before. But the proposed search space offers an interesting environment to both target and the searcher. To the target, it provides an opportunity to move towards the searcher without being found; and to the searcher it provides an easier search space by removing the case of cyclic movement of the target. Sleator and Tarjan [9] suggested evaluating the performance of an online algorithm using competitive analysis. This paper proposes an online algorithm for the provided search space and also attempts to find upper and lower bounds of the competitive ratio.

Target Searching Problem Online Search Uninformed Search