betaFeedback

WorksMathematics

Optimal Patrol Widths in the Infinite-Corridor Barrier-Guarding Game

Abstract

A guard of speed at most one and capture radius rr patrols an infinite corridor. An intruder knows the patrol and can follow any path of speed at most qq from one end to the other. We determine where the maximum width permitted by straight wall runners can be guarded against all such paths. Write Wopt(q)W_{\mathrm{opt}}(q) for the supremum over patrols with bounded longitudinal excursion and F(q)=2r1+(3q2+2q−1)−1F(q)=2r\sqrt{1+(3q^2+2q-1)^{-1}} for the wall ceiling on 1/3<q<11/3 < q < 1. A four-leg bowtie attains F(q)F(q) exactly for qa≤q<1q_a\le q < 1, where 0.457892036651<qa<0.4578920366520.457892036651 < q_a < 0.457892036652. For every 1/3<q<qa1/3 < q < q_a the supremum is strictly smaller. As qq approaches qaq_a from below, F(q)−Wopt(q)F(q)-W_{\mathrm{opt}}(q) is bounded above and below by positive constant multiples of r(qa−q)2r(q_a-q)^2. The lower estimate controls near-optimal patrols uniformly in their period. A rescaled bowtie gives the matching upper estimate. We also prove that periodic patrols give the same supremum as bounded-excursion patrols. For q≥1q\ge1 the one-way optimum is r4+q−2r\sqrt{4+q^{-2}}, a transverse sweep. This sweep is optimal against transit in both directions for q≥1/2q\ge1/2. At low speeds, qWopt(q)/rqW_{\mathrm{opt}}(q)/r tends to two, and an explicit ten-leg patrol guards width greater than (2/q−1.235353)r(2/q-1.235353)r throughout 0<q≤1/400 < q\le1/40. Rational spacetime and flux certificates give finite-speed bounds, including 6.944691333740r<Wopt(1/4)≤8.10r6.944691333740r < W_{\mathrm{opt}}(1/4)\le8.10r.

Introduction

The channel patrol problem

A searcher who commits to a patrol can block a channel only if an evader who knows its schedule cannot time a crossing. Washburn posed this question for a single searcher and compared it with two solvable restrictions: joining the walls into a tube, and imposing a transverse back-and-forth patrol [7 Sec. 2.C.], [8 pp. 36–37]. In the latter case the critical width and the optimal transverse half-amplitude are

Wbf(q)=r4+q−2,a0=r2q1+4q2,(1)W_{\mathrm{bf}}(q)=r\sqrt{4+q^{-2}}, \qquad a_0=\frac{r}{2q\sqrt{1+4q^2}}, \tag*{(1)}

where qq is the ratio of the intruder’s speed to the guard’s. In the tube approximation the critical width for q<1q<1 is 2r/q2r/q. Even the transverse value in (1) exceeds this when 3/2<q<1\sqrt{3}/2<q<1, giving a counterexample to the conjecture that joining the walls always favors the searcher [7 Sec. 2.C.].

Bowtie patrols have a longer history. Koopman’s crossover patrol uses a lead angle chosen for a target traveling on a straight course [1 Sec. 7.1 and Fig. 6], [4 pp. 200–203]. Balinski, Lucas, Owen, and Sand [2 App. I–II] and Washburn [3] optimize detection probabilities for straight transitors. Galyaev and Maslov [9] also study fixed-course intruders. Hew [10, 11] studies prescribed patrols against maneuvering evaders, and Rowling [12] treats effective sweep width with counter-detection. In the present game every admissible transit must be intercepted, at any starting phase.

Washburn’s area estimate for closed search paths against straight targets [5 eqs. (2)–(3)] gives

Wopt(q)≤Warea(q):=2r1+q−2.(2)W_{\mathrm{opt}}(q)\le W_{\mathrm{area}}(q):=2r\sqrt{1+q^{-2}}. \tag*{(2)}

For completeness, set the guard speed to one. In the straight runners’ coordinates (x,qt−y)(x,qt-y), the swept disk on [0,L][0,L] has area at most πr2+2r∫0LX′2+(q−Y′)2 dt\pi r^2+2r\int_0^L\sqrt{X'^2+(q-Y')^2}\,\mathrm{d}t by polygonal approximation.

The integrand is at most 1+q2−qY′/1+q2\sqrt{1+q^2}-qY'/\sqrt{1+q^2} by the speed bound and concavity of the square root. If ∣Y∣≤H|Y|\le H, all straight phases in [H+r,qL−H−r][H+r,qL-H-r] on every lane must be detected in this window. Comparing areas, dividing by LL, and sending LL to infinity proves (2).

Exact Mathematical Model and Conventions

Fix capture radius r>0r>0, maximum guard speed V>0V>0, maximum intruder speed U>0U>0, and dimensionless speed ratio q:=U/V>0q:=U/V>0. By rescaling space by rr and time by r/Vr/V, we often work in normalized units r=1r=1, V=1V=1, U=qU=q, restoring explicit factors of rr in theorem statements. In these units a unit-speed patrol means a patrol with speed bounded by one; waiting is allowed.

Definition 1.1 (Corridor, Patrols, and Evasion). For half-width b>0b>0 (corridor width W=2bW=2b), let Cb:=[−b,b]×RC_b:=[-b,b]\times\mathbb{R}.

  1. A prescribed patrol is an absolutely continuous trajectory g=(X,Y):R→Cbg=(X,Y):\mathbb{R}\to C_b satisfying the speed bound ess sup⁡t∈RX′(t)2+Y′(t)2≤V\operatorname*{ess\,sup}_{t\in\mathbb{R}}\sqrt{X'(t)^2+Y'(t)^2}\le V. We say gg has bounded longitudinal excursion if H(g):=sup⁡t∈R∣Y(t)∣<∞H(g):=\sup_{t\in\mathbb{R}}|Y(t)|<\infty, and is TT-periodic if g(t+T)=g(t)g(t+T)=g(t) for all t∈Rt\in\mathbb{R} (which implies H(g)<∞H(g)<\infty).

  1. A (one-way upward) transit trajectory is an absolutely continuous path p=(x,y):R→Cbp=(x,y):\mathbb{R}\to C_b satisfying ess sup⁡tx′(t)2+y′(t)2≤U\operatorname*{ess\,sup}_{t}\sqrt{x'(t)^2+y'(t)^2}\le U that traverses the corridor upward in Lab coordinates: lim⁡t→−∞y(t)=−∞\lim_{t\to-\infty}y(t)=-\infty and lim⁡t→+∞y(t)=+∞\lim_{t\to+\infty}y(t)=+\infty. (When H(g)≤H<∞H(g)\le H<\infty, any finite-horizon segment p:[t0,t1]→Cbp:[t_0,t_1]\to C_b with y(t0)≤−H−2ry(t_0)\le-H-2r and y(t1)≥+H+2ry(t_1)\ge+H+2r extends outside [t0,t1][t_0,t_1] at velocity (0,+U)(0,+U) without meeting Br‾(g(t))\overline{B_r}(g(t)), so finite-zone and full Lab transit are equivalent.)

  1. Closed-disk capture: The patrol gg captures pp if there exists t∈Rt\in\mathbb{R} such that

∥p(t)−g(t)∥2=(x(t)−X(t))2+(y(t)−Y(t))2≤r.\|p(t)-g(t)\|_2=\sqrt{(x(t)-X(t))^2+(y(t)-Y(t))^2}\le r.

The patrol gg successfully guards CbC_b if it captures every admissible upward transit trajectory pp.

Definition 1.2 (Minimax Guarded Corridor Widths). For q=U/V>0q=U/V>0 and H≥0H\ge0, define the excursion-constrained minimax width

Wopt(q,H):=sup⁡{2b>0:∃ patrol g on Cb with sup⁡t∈R∣Y(t)∣≤H guarding Cb},W_{\mathrm{opt}}(q,H):=\sup\{2b>0:\exists\text{ patrol }g\text{ on }C_b\text{ with }\sup_{t\in\mathbb{R}}|Y(t)|\le H\text{ guarding }C_b\},

and the global bounded-excursion minimax width Wopt(q):=sup⁡H≥0Wopt(q,H)W_{\mathrm{opt}}(q):=\sup_{H\ge0}W_{\mathrm{opt}}(q,H). Define W2way(q,H)W_{\mathrm{2way}}(q,H) and W2way(q)W_{\mathrm{2way}}(q) analogously when gg must simultaneously block both upward (y(∓∞)=∓∞)(y(\mp\infty)=\mp\infty) and downward (y(∓∞)=±∞)(y(\mp\infty)=\pm\infty) speed-UU intruders. Because any speed-q2q_2 trajectory is admissible at speed q1≥q2q_1\ge q_2, Wopt(q)W_{\mathrm{opt}}(q) is nonincreasing in qq; Wopt(q,H)W_{\mathrm{opt}}(q,H) is nondecreasing in HH. The feasible widths are downward closed: projecting a wider patrol horizontally onto a narrower strip preserves the speed bound and decreases its distance from every point of that strip.

Remark 1.3 (Model conventions). Three modeling conventions merit explicit record:

  1. Stackelberg / zero-visibility commitment: The guard commits to g(t)g(t) without real-time feedback on the intruder’s position outside radius rr, while the intruder has full knowledge of gg and may curve, pause, or reverse longitudinally at any speed ≤U\le U.

  1. Closed vs. open capture disk: Definition 1.1 uses the closed disk {∥p−g∥2≤r}\{\|p-g\|_2\le r\}, so grazing contact at distance rr counts as capture. Under an open capture disk {∥p−g∥2<r}\{\|p-g\|_2<r\},

if gg guards CbC_b with closed disk B‾r\overline{B}_r, then for every ε∈(0,1)\varepsilon\in(0,1) the contracted trajectory gε(t):=(1−ε)g(t/(1−ε))g_\varepsilon(t) := (1-\varepsilon)g(t/(1-\varepsilon)) has speed ≤V\le V and guards C(1−ε)bC_{(1-\varepsilon)b} with closed radius (1−ε)r<r(1-\varepsilon)r < r (hence with open disk BrB_r). Letting ε↓0\varepsilon\downarrow0 shows that open-disk and closed-disk suprema have the exact same numerical value Wopt(q)W_{\mathrm{opt}}(q).

  1. One-way vs. two-way transit: Definition 1.1 specifies known-direction (upward) transit. In the two-way variant (§ 7.1), a single patrol gg blocks both directions; transverse sweeping ((1)) is direction-symmetric, whereas tilted bowties exploit directional asymmetry.

Results

For 1/3<q<11/3 < q < 1, just two families of straight intruders, one along each wall, force the width below or equal to

F(q)=2r1+(3q2+2q−1)−1.F(q) = 2r\sqrt{1 + (3q^2 + 2q - 1)^{-1}}.

The patrol that uses this wall budget most efficiently descends along an inset segment on each side and rises on each diagonal crossing. Its angle with the transverse direction satisfies sin⁡α=(1−q)/(2q)\sin\alpha= (1-q)/(2q). At q=1/2q = 1/2 it guards width 2r7/32r\sqrt{7/3}, exceeding the transverse value 2r22r\sqrt{2}. For qa≤q<1q_a \le q < 1 a moving separator certifies this bowtie against every admissible intruder (Theorem 3.6). For q≥1q \ge1 the transverse value is exact (Theorem 6.1).

References

  1. [1]B. O. Koopman, Search and Screening, Operations Evaluation Group Report No. 56, Office of the Chief of Naval Operations, Navy Department, Washington, D.C., 1946.
  2. [2]M. L. Balinski, W. Lucas, G. Owen, and F. M. Sand, A Study of Optimal Patrol and Transit Strategies in a Rectangular Barrier Zone Using Mathematical Games, Final Report, Mathe-matica, Princeton, NJ, for the Office of Naval Research, Contract Nonr-4937(00), November 4, 1965. DTIC accession no. AD0475962.
  3. [3]A. R. Washburn, Patrolling a Channel Revisited, Technical Report NPS55Ws75121, Naval Postgraduate School, Monterey, CA, January 1976.
  4. [4]B. O. Koopman, Search and Screening: General Principles with Historical Applications, Perga-mon Press, New York, 1980.
  5. [5]A. R. Washburn, “On patrolling a channel,” Naval Research Logistics Quarterly, vol. 29, no. 4, pp. 609–615, 1982, doi:10.1002/nav.3800290408.DOI
  6. [6]L. D. Andersen, A. Bouchet, and B. Jackson, “Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus,” Journal of Combinatorial Theory, Series B, vol. 66, no. 2, pp. 232–246, 1996, doi:10.1006/jctb.1996.0017.DOI
  7. [7]A. R. Washburn, Barrier Games, Technical Report NPS-OR-09-001, Naval Postgraduate School, Monterey, CA, June 2009.DOI
  8. [8]A. Washburn, “Barrier games,” Military Operations Research, vol. 15, no. 3, pp. 31–41, 2010, doi:10.5711/morj.15.3.31. Errata: vol. 21, no. 4, p. 83, 2016.DOI
  9. [9]A. A. Galyaev and E. P. Maslov, “On the border patrolling problem,” Journal of Computer and Systems Sciences International, vol. 50, no. 5, pp. 837–846, 2011, doi:10.1134/S1064230711050091.DOI
  10. [10]P. C. Hew, “Linear and concentric arc patrols against smart evaders,” Military Operations Research, vol. 20, no. 3, pp. 39–48, 2015.
  11. [11]P. C. Hew, “Barriers against smart intruders: Screening the limiting approach angle,” Military Operations Research, vol. 22, no. 1, pp. 5–18, 2017.
  12. [12]S. J. Rowling, “Effective sweep-width for barrier missions against an evasive target,” Journal of Defense Modeling and Simulation, vol. 18, no. 4, pp. 417–428, 2021 (first published online 2019), doi:10.1177/1548512919875524.

Paper details

vlnc:W_7uqej6hz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents