Algorithms for Informed Cows
Ming‐Yang Kao, Michael L. Littman · 1997
We extend the classic on-line search problem known as the cow-path problem to the case in which goal locations are selected according to one of a set of possible known probability distributions. We present a polynomial-time linear-programming algorithm for this problem. Introduction In on-line search, a great deal of work has been carried out concerning how to minimize the worst-case performance of a search strategy, for example as compared to an omniscient searcher. In many applications, this notion of optimal performance is simply too conservative---the agent might know, based on its prior experience, that some locations are more promising as targets than others. In this paper, we address the problem of finding good search strategies given a particular kind of prior knowledge. The search scenario we consider is the classic cow-path problem (Baeza-Yates, Culberson, & Rawlins 1993), in which a cow stands on a path and wants to find a pasture in which to feed (see Figure 1). There are...