A near optimal algorithm for the extended cow-path problem in the presence of relative errors

Abstract

In classical path finding problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many problems, we want to charge a cost proportional to the distance between queries (e.g., the time required to travel between two query points). With this cost function in mind, the original w-lane cow-path problem [8] was modeled as a navigation problem in a terrain which consists of w-concurrent avenues. In this paper we study a variant of this problem where the terrain is an uniform b-ary tree, and there is a lower-bound estimate of the cost function. We present a strategy CowP for this class of problems where the relative error is bounded by a known constant and show that its worst case complexity is less than or equal to [4b/(b−1)] times optimal.