The Cow Path Problem
And Related Problems I Find Interesting
Jared Coleman 
This document is a work in progress and will be updated regularly.
Contents
2 An Optimal Strategy
3 A Lower Bound
4 Related Work and Further Reading
4.1 Our Work
References
1 Introduction
The cow path problem is a classic in computer science and is fundamental to search theory. The problem, as formulated in one of the most celebrated papers that studies it (and the ﬁrst, as far as I am aware, to actually call it “the cow path problem”) [25], is as follows: a cow named Bessie is standing at a crossroads with two paths leading oﬀ into unknown territory. On one of the paths lies a green pasture a distance $d\ge 1$ away while the other path simply goes on forever (see Figure 1). Bessie’s eyesight is very poor, so she can only tell whether she has reached the pasture or not when she is standing on it. What strategy should Bessie use to reach the pasture as quickly as possible?
Clearly, if Bessie knows which direction the pasture is, she can simply walk to it, traveling a total distance of $d$. We are interested in the case where Bessie does not know which direction the pasture is. Our goal is to ﬁnd a strategy with the minimum competitive ratio, which is the ratio of the total distance Bessie walks using the strategy to the distance $d$ to the pasture. For a strategy $\mathcal{\mathcal{A}}$ let ${T}_{\mathcal{\mathcal{A}}}$ denote the total distance Bessie walks using the strategy. Then the competitive ratio of $\mathcal{\mathcal{A}}$ is ${T}_{\mathcal{\mathcal{A}}}\u2215d$. In other words, the competitive ratio tells us how many times further Bessie walks than she needs to in order to reach the pasture.
Motivation
Why study the cow path problem? The cow path problem is a classic problem in search theory and is the gateway to all kinds of even more interesting problems in search theory. Direct applications of the cow path problem include robotics applications (e.g., search and rescue missions) and hybrid algorithm execution (e.g., how long should we run an optimization algorithm before switching to a diﬀerent one?).
The many variants of the cow path and related problems
A Quick WarmUp
As a warmup excersie, let’s consider the case where Bessie knows $d$ but not the direction of the pasture. In this case, there’s only one thing for her to do: pick a direction and walk along it a distance of $d$. If she travels a distance of $d$ and has not reached the pasture, then she knows the pasture is in the other direction.
What is the competitive ratio of this strategy?
 1.
 The pasture is in the direction Bessie walks ﬁrst.
 2.
 The pasture is in the other direction.
In the ﬁrst case, the competitive ratio is trivially $1$ – Bessie walks a distance of $d$ and reaches the pasture, travelling the best possible distance $d$ ($d\u2215d=1$). In the second case, however, Bessie walks a distance of $d$ in one direction, then has to walk back to the crossroads and walk a distance of $d$ in the other direction. In total, Bessie walks a distance of $3d$ to reach the pasture, so the competitive ratio is $3$.
The competitive ratio of the strategy where Bessie walks a distance of $d$ in one direction and then walks back to the crossroads and walks a distance of $d$ in the other direction is $3$.
2 An Optimal Strategy
Spoiler alert: it turns out that there is a relatively simple strategy that has a competitive ratio of just nine! In other words, this strategy guarantees that, no matter how far away the pasture is, Bessie will travel at most nine times the best possible distance to reach the pasture. The strategy is as follows:
 1.
 Bessie walks a distance of $1$ in one direction.
 2.
 If she has not reached the pasture, she walks back to the crossroads and walks a distance of $2$ in the other direction.
 3.
 If she has not reached the pasture, she walks back to the crossroads and walks a distance of $4$ in the ﬁrst direction.
 4.
 She continues doing this, switching directions and doubling the distance she walks each time, until she reaches the pasture.
In other words, in each round (a trip out and back from the crossroads) $k=0,1,2,\dots $, Bessie walks a distance of ${2}^{k}$ away from the crossroads and back in the opposite direction of the previous round.
Let’s start by analyzing the time it takes Bessie to reach the pasture using this strategy. First of all, observe that she’s guaranteed to reach it eventually since she’s increasing the distance she walks each round. Let $k$ denote the number of rounds it takes for Bessie to reach the pasture. Note that since $d\ge 1$, then $k>0$. We know two things about $d$ and $k$:
 1.
 $d\le {2}^{k}$: Clearly, if Bessie reaches the pasture in round $k$, where she planned to walk a maximum distance of ${2}^{k}$, then the distance to the pasture must be at most ${2}^{k}$.
 2.
 $d>{2}^{k2}$: In round $k2$ Bessie walks a distance of ${2}^{k2}$ in the same direction as in round $k$ (when she reaches the pasture). If $d\le {2}^{k2}$, then Bessie would have reached the pasture in round $k2$ instead of round $k$.
What is the total distance Bessie traveled in the ﬁrst $k1$ rounds (before reaching the pasture)?
The comeptitive ratio of the strategy is then:
$$\begin{array}{lll}\hfill \frac{{2}^{k+1}2+d}{d}\le \frac{{2}^{k+1}}{d}+1& \phantom{\rule{2em}{0ex}}& \hfill \end{array}$$We’re interested in the worstcase competitive ratio, so we want to maximize this expression with respect to $d$. As you can see, since $d$ is on the denominator, the competitive ratio is maximized when $d$ is minimized. Recall, however, that ${2}^{k2}<d\le {2}^{k}$, so the worstcase competitive ratio is given by:
$$\begin{array}{lll}\hfill \underset{d\to {({2}^{k2})}^{+}}{\mathrm{lim}}[\frac{{2}^{k+1}}{d}+1]=\frac{{2}^{k+1}}{{2}^{k2}}+1={2}^{3}+1=9& \phantom{\rule{2em}{0ex}}& \hfill \end{array}$$The competitive ratio of the strategy where Bessie walks a distance of $1$ in one direction, then walks a distance of $2$ in the other direction, then walks a distance of $4$ in the ﬁrst direction, and so on, is $9$.
3 A Lower Bound
So we proved that the “doubling strategy” has a competitive ratio of $9$, but is this the best we can do? Why not triple in each round? or just increase our search distance by $50\%$?
In general, a geometrically increasing strategy follows the same pattern as the doubling strategy, but instead of doubling the distance Bessie walks each round, she walks a distance of ${a}^{i}$ in round $i=0,1,2,\dots $. The doubling strategy is a special case of this where $a=2$. Could it be that a diﬀerent value of $a$ could yield a better competitive ratio?
To answer this question, let’s analyze the competitive ratio of a general geometrically increasing strategy. Again, let $k$ denote the number of rounds it takes for Bessie to reach the pasture. Then we know that $d\le {a}^{k}$ and $d>{a}^{k2}$. The total distance Bessie travels in the ﬁrst $k1$ rounds is:
$$\begin{array}{lll}\hfill 2\cdot {a}^{0}+2\cdot {a}^{1}+2\cdot {a}^{2}+\dots +2\cdot {a}^{k2}+2\cdot {a}^{k1}=a\sum _{i=0}^{k1}{a}^{i}=2(\frac{{a}^{k}1}{a1})& \phantom{\rule{2em}{0ex}}& \hfill \end{array}$$The competitive ratio of the strategy is then:
$$\begin{array}{lll}\hfill \frac{2(\frac{{a}^{k}1}{a1})+d}{d}=\frac{2(\frac{{a}^{k}1}{a1})}{d}+1& \phantom{\rule{2em}{0ex}}& \hfill \end{array}$$Again, observe that the competitive ratio is maximized when $d$ is minimized. Since ${a}^{k2}<d\le {a}^{k}$, the worstcase competitive ratio is:
$$\begin{array}{lll}\hfill \frac{2({a}^{2}{a}^{2k})}{a1}+1& \phantom{\rule{2em}{0ex}}& \hfill \end{array}$$Again, we’re interested in the worstcase competitive ratio, so we want to maximize this expression with respect to $k$. The competitive ratio is maximized when $k=2$, so the worstcase competitive ratio is:
$$\begin{array}{lll}\hfill \underset{k\to \infty}{\mathrm{lim}}[\frac{2({a}^{2}{a}^{2k})}{a1}+1]=\frac{2({a}^{2}0)}{a1}+1=\frac{2{a}^{2}}{a1}+1& \phantom{\rule{2em}{0ex}}& \hfill \end{array}$$Great! We now have a general formula for the competitive ratio of any geometrically increasing strategy! Now the question is – what value of $a$ minimizes this expression? We’ll leave it as an excersise for the reader to show that the competitive ratio is minimized when $a=2$ (it’s not too diﬃcult with a little calculus). Figure 2 show a plot, though, of the competitive ratio as a function of $a$. You can see very clearly that the best geometrically increasing strategy is the doubling strategy!
It’s important to note that we have only shown that the doubling strategy is the best geometrically increasing strategy. In order to prove a true lower bound for the problem, we would need to consider all possible strategies. In other words, we would need to show that there must exist a geometrically increasing strategy that does at least as well as any other strategy. This has indeed been proven, but it’s a bit more involved and I won’t go into it here. If interested, the following references all provide diﬀerent complete proofs for the problem [2, 3, 11, 25].
4 Related Work and Further Reading
This problem was ﬁrst studied by Bellman and Beck in the 1960’s [2, 3] (though with a diﬀerent formulation) and has since been the subject of much research. As a fundamental problem in search theory, many variants of the original cowpath problem have been proposed and solved for diﬀerent models and using a variety of techniques. For multiagent systems, it is sometimes framed as an evacuation problem, where the goal is to minimize the time for every agent to ﬁnd and travel to an exit whose location is unknown [4, 19]. The Group Search problem, on the other hand, requires any one agent to ﬁnd the target [17]. These problems have been studied for many diﬀerent topologies including the bounded line [5], the ring [24, 27], the disk [18], simple polygons [26], for multiple paths (the original problem is a twopath system  left and right from the starting location of the agent) [25], the plane [22], in graphs [4], and in trees [21]. Competitive algorithms for multiagent systems have been proposed [4, 9, 18, 19, 20, 22, 24, 27], sometimes the agents to be faulty [20, 24] or mobile [14, 15]. A randomized algorithm has also been shown to dramatically improve the competitive ratio by a factor of almost $2$ for the original problem (and to a lesser extent for the multipath variant) [25]. Search for mobile targets has also been studied [7, 11, 23].
Another related area of particular interest to me is delivery, whereby an agent or team of agents must cooperate to trasport a target object to a given location. Recently, there has been work in data delivery by systems of mobile agents on the line [8, 13], in the plane [10, 12, 16], and in graphs by energyconstrained agents [1, 6]. In 2021, we proposed the Pony Express Communication Problem [13], where agents must cooperate to transmit an object from one endpoint of a line segment to the other, is most similar to the problem we study in this paper. In the oﬄine setting, where the locations of the object and all agents are known to every agent ahead of time, our problem is equivalent to the Pony Express Communication Problem, for which an optimal oﬄine algorithm exists.
4.1 Our Work
 [10]

Jared Coleman et al. “Delivery to Safety with Two Cooperating Robots”. In: CoRR abs/2210.04080 (2022). doi: 10.48550/arXiv.2210.04080. arXiv: 2210.04080.
 [11]

Jared Coleman et al. “Line Search for an Oblivious Moving Target”. In: CoRR abs/2211.03686 (2022). doi: 10.48550/arXiv.2211.03686. arXiv: 2211.03686.
 [12]

Jared Coleman et al. “Message Delivery in the Plane by Robots with Diﬀerent Speeds”. In: Stabilization, Safety, and Security of Distributed Systems  23rd International Symposium, SSS 2021, Virtual Event, November 1720, 2021, Proceedings. Ed. by Colette Johnen, Elad Michael Schiller, and Stefan Schmid. Vol. 13046. Lecture Notes in Computer Science. Springer, 2021, pp. 305–319. doi: 10.1007/9783 030910815\_20.
 [13]

Jared Coleman et al. “The Pony Express Communication Problem”. In: Combinatorial Algorithms  32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 57, 2021, Proceedings. Ed. by Paola Flocchini and Lucia Moura. Vol. 12757. Lecture Notes in Computer Science. Springer, 2021, pp. 208–222. doi: 10.1007/9783030799878\_15.
 [14]

Jared Ray Coleman, Lorand Cheng, and Bhaskar Krishnamachari. “Search and Rescue on the Line”. In: Structural Information and Communication Complexity  30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 69, 2023, Proceedings. Ed. by Sergio Rajsbaum et al. Vol. 13892. Lecture Notes in Computer Science. Springer, 2023, pp. 297–316. doi: 10.1007/978 3031327339\_13. url: https://doi.org/10.1007/9783031327339%5C_13.
 [15]

Jared Ray Coleman et al. “Linear Search for an Escaping Target with Unknown Speed”. In: Combinatorial Algorithms  35th International Workshop, IWOCA 2024, Ischia, Italy, July 13, 2024, Proceedings. Ed. by Adele Anna Rescigno and Ugo Vaccaro. Vol. 14764. Lecture Notes in Computer Science. Springer, 2024, pp. 396–407. doi: 10.1007/9783031630217\_30. url: https://doi.org/10.1007/9783031630217%5C_30.
 [16]

Jared Ray Coleman et al. “Optimal Delivery with a Faulty Drone”. In: CoRR abs/2404.17711 (2024). doi: 10 . 48550 / ARXIV . 2404 . 17711. arXiv: 2404 . 17711. url: https://doi.org/10.48550/arXiv.2404.17711.
References
 [1]

Andreas Bärtschi and Thomas Tschager. “EnergyEﬃcient Fast Delivery by Mobile Agents”. In: Fundamentals of Computation Theory  21st International Symposium, FCT 2017, Bordeaux, France, September 1113, 2017, Proceedings. Ed. by Ralf Klasing and Marc Zeitoun. Vol. 10472. Lecture Notes in Computer Science. Springer, 2017, pp. 82–95. doi: 10.1007/9783662557518\_8.
 [2]

Anatole Beck. “On the linear search problem”. In: Israel Journal of Mathematics 2.4 (1964), pp. 221–228.
 [3]

R. Bellman. “An optimal search”. In: Siam Review 5.3 (1963), pp. 274–274.
 [4]

Piotr Borowiecki et al. “Distributed Evacuation in Graphs with Multiple Exits”. In: Structural Information and Communication Complexity  23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 1921, 2016, Revised Selected Papers. Ed. by Jukka Suomela. Vol. 9988. Lecture Notes in Computer Science. 2016, pp. 228–241. doi: 10.1007/9783319483146\_15.
 [5]

Prosenjit Bose, JeanLou De Carufel, and Stephane Durocher. “Revisiting the Problem of Searching on a Line”. In: Algorithms  ESA 2013  21st Annual European Symposium, Sophia Antipolis, France, September 24, 2013. Proceedings. Ed. by Hans L. Bodlaender and Giuseppe F. Italiano. Vol. 8125. Lecture Notes in Computer Science. Springer, 2013, pp. 205–216. doi: 10.1007/978364240450 4\_18.
 [6]

Iago A. Carvalho, Thomas Erlebach, and Kleitos Papadopoulos. “On the fast delivery problem with one or two packages”. In: J. Comput. Syst. Sci. 115 (2021), pp. 246–263. doi: 10.1016/j.jcss.2020. 09.002.
 [7]

Eowyn Cenek. “Chases and escapes by Paul J. Nahin”. In: SIGACT News 40.3 (2009), pp. 48–50. doi: 10.1145/1620491.1620500.
 [8]

Jérémie Chalopin et al. “Data Delivery by EnergyConstrained Mobile Agents on a Line”. In: Automata, Languages, and Programming  41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 811, 2014, Proceedings, Part II. Ed. by Javier Esparza et al. Vol. 8573. Lecture Notes in Computer Science. Springer, 2014, pp. 423–434. doi: 10.1007/9783662439517\_36.
 [9]

Marek Chrobak et al. “Group Search on the Line”. In: SOFSEM 2015: Theory and Practice of Computer Science  41st International Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 2429, 2015. Proceedings. Ed. by Giuseppe F. Italiano et al. Vol. 8939. Lecture Notes in Computer Science. Springer, 2015, pp. 164–176. doi: 10.1007/9783662460788\_14.
 [10]

Jared Coleman et al. “Delivery to Safety with Two Cooperating Robots”. In: CoRR abs/2210.04080 (2022). doi: 10.48550/arXiv.2210.04080. arXiv: 2210.04080.
 [11]

Jared Coleman et al. “Line Search for an Oblivious Moving Target”. In: CoRR abs/2211.03686 (2022). doi: 10.48550/arXiv.2211.03686. arXiv: 2211.03686.
 [12]

Jared Coleman et al. “Message Delivery in the Plane by Robots with Diﬀerent Speeds”. In: Stabilization, Safety, and Security of Distributed Systems  23rd International Symposium, SSS 2021, Virtual Event, November 1720, 2021, Proceedings. Ed. by Colette Johnen, Elad Michael Schiller, and Stefan Schmid. Vol. 13046. Lecture Notes in Computer Science. Springer, 2021, pp. 305–319. doi: 10.1007/9783 030910815\_20.
 [13]

Jared Coleman et al. “The Pony Express Communication Problem”. In: Combinatorial Algorithms  32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 57, 2021, Proceedings. Ed. by Paola Flocchini and Lucia Moura. Vol. 12757. Lecture Notes in Computer Science. Springer, 2021, pp. 208–222. doi: 10.1007/9783030799878\_15.
 [14]

Jared Ray Coleman, Lorand Cheng, and Bhaskar Krishnamachari. “Search and Rescue on the Line”. In: Structural Information and Communication Complexity  30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 69, 2023, Proceedings. Ed. by Sergio Rajsbaum et al. Vol. 13892. Lecture Notes in Computer Science. Springer, 2023, pp. 297–316. doi: 10.1007/978 3031327339\_13. url: https://doi.org/10.1007/9783031327339%5C_13.
 [15]

Jared Ray Coleman et al. “Linear Search for an Escaping Target with Unknown Speed”. In: Combinatorial Algorithms  35th International Workshop, IWOCA 2024, Ischia, Italy, July 13, 2024, Proceedings. Ed. by Adele Anna Rescigno and Ugo Vaccaro. Vol. 14764. Lecture Notes in Computer Science. Springer, 2024, pp. 396–407. doi: 10.1007/9783031630217\_30. url: https://doi.org/10.1007/9783031630217%5C_30.
 [16]

Jared Ray Coleman et al. “Optimal Delivery with a Faulty Drone”. In: CoRR abs/2404.17711 (2024). doi: 10 . 48550 / ARXIV . 2404 . 17711. arXiv: 2404 . 17711. url: https://doi.org/10.48550/arXiv.2404.17711.
 [17]

Jurek Czyzowicz, Kostantinos Georgiou, and Evangelos Kranakis. “Group Search and Evacuation”. In: Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Ed. by Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Vol. 11340. Lecture Notes in Computer Science. Springer, 2019, pp. 335–370. doi: 10.1007/9783030110727\_14.
 [18]

Jurek Czyzowicz et al. “Evacuating Robots from a Disk Using FacetoFace Communication”. In: Discret. Math. Theor. Comput. Sci. 22.4 (2020).
 [19]

Jurek Czyzowicz et al. “Group Evacuation on a Line by Agents with Diﬀerent Communication Abilities”. In: LIPIcs 212 (2021). Ed. by HeeKap Ahn and Kunihiko Sadakane, 57:1–57:24. doi: 10.4230/LIPIcs.ISAAC.2021.57.
 [20]

Jurek Czyzowicz et al. “Search on a line with faulty robots”. In: Distributed Comput. 32.6 (2019), pp. 493–504. doi: 10.1007/s0044601702960.
 [21]

Henri Devillez et al. “TwoAgent Tree Evacuation”. In: Structural Information and Communication Complexity  28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28  July 1, 2021, Proceedings. Ed. by Tomasz Jurdzinski and Stefan Schmid. Vol. 12810. Lecture Notes in Computer Science. Springer, 2021, pp. 204–221. doi: 10.1007/9783030795276\_12.
 [22]

Ofer Feinerman et al. “Collaborative search on the plane without communication”. In: ACM Symposium on Principles of Distributed Computing, PODC ’12, Funchal, Madeira, Portugal, July 1618, 2012. Ed. by Darek Kowalski and Alessandro Panconesi. ACM, 2012, pp. 77–86. doi: 10.1145/2332432. 2332444.
 [23]

Shmuel Gal. “Search games”. In: Wiley encyclopedia of operations research and management science (2010).
 [24]

Konstantinos Georgiou et al. “Optimal Circle Search Despite the Presence of Faulty Robots”. In: Algorithms for Sensor Systems  15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2019, Munich, Germany, September 1213, 2019, Revised Selected Papers. Ed. by Falko Dressler and Christian Scheideler. Vol. 11931. Lecture Notes in Computer Science. Springer, 2019, pp. 192–205. doi: 10.1007/9783030344054\_11.
 [25]

MingYang Kao, John H. Reif, and Stephen R. Tate. “Searching in an Unknown Environment: An Optimal Randomized Algorithm for the CowPath Problem”. In: (1993). Ed. by Vijaya Ramachandran, pp. 441–447.
 [26]

Jon M. Kleinberg. “Online Search in a Simple Polygon”. In: Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 January 1994, Arlington, Virginia, USA. Ed. by Daniel Dominic Sleator. ACM/SIAM, 1994, pp. 8–15.
 [27]

Kevin Spieser and Emilio Frazzoli. “The CowPath Game: A competitive vehicle routing problem”. In: Proceedings of the 51th IEEE Conference on Decision and Control, CDC 2012, December 1013, 2012, Maui, HI, USA. IEEE, 2012, pp. 6513–6520. doi: 10.1109/CDC.2012.6426279.