Chases and Escapes: The Mathematics of Pursuit and Evasion

By Paul Nahin

We all played tag when we were kids. What most of us don't realize is that this simple chase game is in fact an application of pursuit theory, and that the same principles of games like tag, dodgeball, and hide-and-seek are also at play in military strategy, high-seas chases by the Coast Guard, and even romantic pursuits. In Chases and Escapes, Paul Nahin gives us the first complete history of this fascinating area of mathematics, from its classical analytical beginnings to the present day.


Drawing on game theory, geometry, linear algebra, target-tracking algorithms, and much more, Nahin also offers an array of challenging puzzles with their historical background and broader applications. Chases and Escapes includes solutions to all problems and provides computer programs that readers can use for their own cutting-edge analysis.


Now with a gripping new preface on how the Enola Gay escaped the shock wave from the atomic bomb dropped on Hiroshima, this book will appeal to anyone interested in the mathematics that underlie pursuit and evasion.

Some images inside the book are unavailable due to digital copyright restrictions.

• Language: English
• Publisher: Princeton University Press
• Release date: Jul 22, 2012
• ISBN: 9781400842063

Book preview

Frontispiece - Screenshot from the author's computer display,* captured while playing the World War II first-person shooter Call of Duty™: United Offensive™, showing what a defending tail machine gunner on a B-17 bomber saw in his gun sight when under attack over Europe by German fighters flying on ‘pure pursuit’ trajectories (see figure 2.6.3). The B-17 used an optical gunsight to help the gunner aim his two .50-caliber machine guns so their bullets would arrive at where the fighter would be, rather than where it was. Some gunners took a more direct approach; as one B-24 gunner who flew against the Japanese in the Pacific war put it, My own feeling about it was, you just filled the sky full of lead and let them run into it. In this book, of course, we prefer to be just a bit more analytical than that! During World War II many classified theoretical studies of pursuit trajectories in air-to-air combat were made by the Applied Mathematics Panel (AMP), which was part of the U.S. government National Defense Research Committee (NDRC). The NDRC was created by presidential order in 1940, and the AMP was formed in 1942, again by written order of President Franklin D. Roosevelt. You can find an example of AMP's pursuit work, in the open literature, in Handelman (1949), and more on AMP's work, in general, in Rees (1980).

---

* For readers who also enjoy computer gaming, the author's old system was a DELL Inspiron 5150 laptop with 512 megabytes of RAM, a 3.06 GHz Pentium 4 Processor, and an Nvidia FX5200 graphics card with 64 megabytes of video memory, all running under Windows XPPro/ DirectX 9.0c. By the standards of 2006, this was a low-powered gaming machine. The author now performs advanced gaming research on an Xbox360.

CHASES AND ESCAPES

The Mathematics of

     Pursuit and Evasion

With a new preface by the author

Paul J. Nahin

Princeton University Press

Princeton and Oxford

Copyright © 2007 by Princeton University Press

Published by Princeton University Press,

41 William Street,

Princeton, New Jersey 08540

In the United Kingdom:

Princeton University Press,

6 Oxford Street, Woodstock, Oxfordshire OX20 1TW

press.princeton.edu

Cover design by Kathleen Lynch/Black Kat Design

Cover illustration by Selçuk Demirel/Marlena Agency

All Rights Reserved

Third printing, and first paperback printing, with a new preface, for the

Princeton Puzzlers series, 2012

Paperback ISBN: 978-0-691-15501-2

The Library of Congress has cataloged the cloth edition of this book as follows

Nahin, Paul J.

Chases and escapes: the mathematics of pursuit and evasion/Paul J. Nahin.

p.  cm.

Includes bibliographical references and index.

ISBN-13: 978-0-691-12514-5 (acid-free paper)

ISBN-10: 0-691-12514-7 (acid-free paper)

1. Differential games. I. Title.

QA272.N34 2007

519.3'2–dc22 2006051392

British Library Cataloging-in-Publication Data is available

This book has been composed in ITC New Baskerville

Printed on acid-free paper.∞

Printed in the United States of America

10 9 8 7 6 5 4 3

For Patricia Ann

Who chased whom?

It was fifty years ago,

so who's to know?

Today it wouldn't matter,

we're both too slow!

If E is an evader with speed 1 and P is a pursuer with speed s > 1, then Of course P can catch E [no matter what E does], at least by going to his [E's] initial position and [simply] following his path.

— from Isbell (1967), showing that not all pursuit problems have complicated answers

Contents

Preface to the Paperback Edition

What You Need to Know to Read This Book (and How I Learned What I Needed to Know to Write It)

Introduction

Chapter 1.

The Classic Pursuit Problem

1.1 Pierre Bouguer's Pirate Ship Analysis

1.2 A Modern Twist on Bouguer

1.3 Before Bouguer: The Tractrix

1.4 The Myth of Leonardo da Vinci

1.5 Apollonius Pursuit and Ramchundra's Intercept Problem

Chapter 2.

Pursuit of (Mostly) Maneuvering Targets

2.1 Hathaway's Dog-and-Duck Circular Pursuit Problem

2.2 Computer Solution of Hathaway's Pursuit Problem

2.3 Velocity and Acceleration Calculations for a Moving Body

2.4 Houghton's Problem: A Circular Pursuit That Is Solvable in Closed Form

2.5 Pursuit of Invisible Targets

2.6 Proportional Navigation

Chapter 3.

Cyclic Pursuit

3.1 A Brief History of the n-Bug Problem, and Why It Is of Practical Interest

3.2 The Symmetrical n-Bug Problem

3.3 Morley's Nonsymmetrical 3-Bug Problem

Chapter 4.

Seven Classic Evasion Problems

4.1 The Lady-in-the-Lake Problem

4.2 Isaacs's Guarding-the-Target Problem

4.3 The Hiding Path Problem

4.4 The Hidden Object Problem: Pursuit and Evasion as a Simple Two-Person, Zero-Sum Game of Attack-and-Defend

4.5 The Discrete Search Game for a Stationary Evader — Hunting for Hiding Submarines

4.6 A Discrete Search Game with a Mobile Evader —Isaacs's Princess-and-Monster Problem

4.7 Rado's Lion-and-Man Problem and Besicovitch's Astonishing Solution

Appendix A

Solution to the Challenge Problems of Section 1.1

Appendix B

Solutions to the Challenge Problems of Section 1.2

Appendix C

Solution to the Challenge Problem of Section 1.5

Appendix D

Solution to the Challenge Problem of Section 2.2

Appendix E

Solution to the Challenge Problem of Section 2.3

Appendix F

Solution to the Challenge Problem of Section 2.5

Appendix G

Solution to the Challenge Problem of Section 3.2

Appendix H

Solution to the Challenge Problem of Section 4.3

Appendix I

Solution to the Challenge Problem of Section 4.4

Appendix J

Solution to the Challenge Problem of Section 4.7

Appendix K

Guelman's Proof

Notes

Bibliography

Acknowledgments

Index

Preface to the Paperback Edition

How will you escape it?

—a character in Dostoevsky's The Brothers

Karamazov asks the same question that the

crewmen of the B-29 Enola Gay must have

asked their pilot, concerning the shock wave

from the world's first atomic-bomb drop

The appearance of the hardcover edition of this book in 2007 prompted numerous letters and e-mails from readers all around the world. That surprised me at first, but after a little thought I think I know what might have prompted that response. In the introduction I mention a number of pursuit-and-evasion movies—including Cornel Wilde's 1966 The Naked Prey—that I think exactly catch the spirit in which I wrote, and the appearance of this book just after Mel Gibson's remake of Prey (the 2006 Apocalypto) is what perhaps sparked the imaginations of readers. In any case, I was of course pleased to learn that the book was being read. Since writing this book I have learned some new things.

In February 2008 I received a very nice note from Steve Strogatz, professor of theoretical and applied mechanics at Cornell, commenting on the n-bug cyclic pursuit problem of chapter 3. In particular, he wrote to tell me of his generalization (done when he was in high school!) of Martin Gardner's n = 4 analysis, to directly derive this book's equation (3.2.7) on p. 115. The following year Steve included an expanded discussion of his note to me in his book The Calculus of Friendship (Princeton University Press 2009), and you can find it there on pp. 15–22.

On p. 119 of this book you'll find the curious trigonometric identity

where the symbols are defined in figure 3.3.1 on p. 117 (A, B, and C are the interior vertex angles of an arbitrary triangle, and a, b, and c are the lengths of the sides opposite the similarly labeled angles). This identity is vital to completing an analysis in chapter 3. After reading the book's proof of the identity (see pp. 239–240), however, Peter Milner (a retired professor of mechanical engineering at the University of Auckland, New Zealand) wrote in March 2008 to tell me that he thought there must be a better way. In fact, he found two (!) quite short, elementary derivations. Here's the one I particularly like. Rearrange the claimed identity to read

From the well-known identity

and from the fact that for any triangle

the LHS of the rearranged identity becomes

From the law of cosines we have

and so

Thus,

where … stands for a little bit of routine algebra. Next, turning to the RHS of the rearranged identity, and using the law of cosines again, twice, for cos(A) and cos(B), we have

Obviously LHS = RHS, and since all of the above steps are reversible, we are done.

Thanks, Peter!

Since the original publication of this book five additional journal papers have come to my attention that I think particularly pertinent. They are

(1) F. Behroozi and R. Gagnon, The Goose Chase, American Journal of Physics, March 1979, pp. 237–238;

(2) Carl E. Mungan, A Classic Chase Problem Solved from a Physics Perspective, European Journal of Physics, November 2005, pp. 985–990;

(3) James O'Connell, Pursuit and Evasion Strategies in Football, Physics Teacher, November 1995, pp. 516–518;

(4) Nick Lord, An Interception Problem, The Mathematical Gazette, December 1990, pp. 351–354;

(5) Andrew J. Simoson, Pursuit Curves for the Man in the Moone, College Mathematics Journal, November 2007, pp. 330–338.

The absence of the first four from the hardcover edition was an oversight on my part. The fifth paper appeared shortly after the original publication of this book.

That last paper is particularly interesting from an historical point of view, because it strongly hints at an appreciation of pure pursuit problems that dates back to at least 1638. That's the year Francis Godwin's story The Man in the Moone was posthumously published, almost a century before Pierre Bouguer's 1732 analysis, the analysis that opens chapter 1 of this book. Godwin (1562–1633), an Anglican bishop, actually wrote his tale decades earlier (in 1599), but limited himself to circulating it privately among friends. First editions of the 1638 book are now extremely rare, but you can find the story reprinted in the anthology by Faith K. Pizor and T. Allan Comp, The Man in the Moone and Other Lunar Fantasies (introduction by Isaac Asimov), Praeger 1971.

Godwin's tale is a fantastic voyage that tells of a journey from the Earth to the Moon and then back, a journey powered by twenty-five swans (!) flying pure pursuit trajectories at a constant speed. What makes this story particularly interesting to a mathematical mind is that Godwin states specific numerical times for each part of the round trip: twelve days to the Moon, and eight days back to the Earth. Professor Simoson's paper describes how he used a computer, Mathematica software, and Euler's method (see pp. 206–208 in this book) to experimentally study the fictional trip to see if those travel durations make sense. The general conclusion seems to be that, if one makes certain reasonable assumptions (or at least as reasonable as one can be starting with the premise that twenty-five swans are pulling you through space), then Godwin's numbers are not too bad.

There is nothing in the historical record, however, to indicate that Godwin had any special mathematical training, and so we are left with the puzzle of just how he arrived at his numbers. Did he simply guess? Was he an unappreciated genius? I don't know. Read Simoson, read Godwin, and make up your own mind. Mention of Godwin's work is also made in Simoson's book Voltaire's Riddle (The Mathematical Association of America 2009), as well as Bouguer's pirate ship analysis (with the pursued and the pursuer changed into a rabbit and a fox, respectively). Simoson also discusses Ash's problem of the spider and the fly, which I mention in passing on p. 42, and sketches a computer approach to solving it.

Another paper I should have discussed is one I am embarrassed to admit I simply forgot to include—embarrassed because I wrote it (thirty-five years ago)! I was reminded of that paper when I received an e-mail from a reader, an e-mail I'll tell you about in just a moment. In the mid-1970s there was a high-level policy debate about the proposed replacement of the U.S. strategic (that is, nuclear) B-52 bomber fleet with the B-1. Part of that debate concerned the vulnerability (or not) of land-based bombers, of any kind, to a surprise attack by offshore Soviet nuclear-tipped submarine-launched ballistic missiles (SLBMs). In 1977 the Brookings Institution released a study on that issue, and I wrote a response to it that took exception to part of the analysis (see my paper Can Land-Based Strategic Bombers Survive an SLBM Attack? IEEE Transactions on Aerospace and Electronic Systems, March 1977, pp. 216–219).

At the end of my paper I presented the following mathematical model as an alternative to the Brookings model for an initially parked bomber attempting to escape from a single incoming SLBM nuclear warhead detonation (a model easily extended to include multiple warheads):

Let the origin of a rectangular coordinate system be the location of a bomber base. At time t = 0 a bomber begins its escape attempt by flying out along a radius vector whose angle with the positive x-axis is a uniform random variate between the limits ±θ. At time t = t0, the SLBM warhead detonates and the bomber is somewhere along an arc of uncertainty with radius Ru(t0) [in my paper, I derived a formula for Ru(t) as a function of the bomber's mass, thrust per engine, number of engines, and maximum low-level flight speed]. The location of the warhead detonation is described by a bivariate normal distribution with zero means and variances related to the SLBM CEP [circular error probable]. Given the warhead size and the bomber's hardness to blast overpressure, there then exists a circle of lethality with radius RL centered on the detonation point. The probability the bomber is destroyed is the probability the bomber is on that portion of its arc of uncertainty that lies within the circle of lethality.

I concluded my paper with this challenge: This is certainly a nontrivial problem… and, as far as I know, it remains an open problem in chases and escapes. It is really only of mathematical interest, I should tell you, as the likelihood of an actual SLBM attack on U.S. bomber bases is quite improbable, for reasons given in Kosta Tsipis's 1983 book, Arsenal: Understanding Weapons in the Nuclear Age.

In December 2010 I received an e-mail from Rob Cook (who operates the very interesting website pcgamingtips.blogspot.com), asking if I knew anything about the historic escape of the B-29 bomber Enola Gay from the blast wave produced by the nine-thousand-pound uranium-gun atomic bomb—dubbed Little Boy—that was dropped on Hiroshima, Japan, the morning of August 6, 1945. (It was Rob's email that reminded me of my SLBM paper.) Rob had just seen a BBC documentary on that event, in which the bomber's pilot (Paul Tibbets) described the extreme escape maneuver he had executed immediately after release of the bomb. His description bothered Rob; details of that maneuver, as remembered by Tibbets, didn't seem to make any physical sense. I wrote back to Rob to say that I had not seen any analytical treatments of that event, but his query certainly made me wish I had thought to include some discussion of the escape in this book. So, with this new preface in mind, I decided to look into the matter of the Enola Gay.

Some details of the mission were easy to find. The 1962 book Now It Can Be Told, by Leslie Groves (the commanding general of the Manhattan Engineer District, the cover name for the American atomic-bomb project), states that the escape maneuver was worked out by the Ballistics Group of the Los Alamos Ordnance Division, that it involved a sharp diving turn, the sharpest possible consistent with safety, and that bomb release occurred at an altitude of 31,600 feet.

In the 1977 book Enola Gay, by Gordon Thomas and Max Morgan Witts, we are told—numerous times—that the turn-angle (I'll elaborate on just what that is in a moment) was to be 155 degrees, after which the bomber should stop turning and then simply flat-out run for it. There is some uncertainty in the precise value; in a Saturday Evening Post article (How to Drop an Atom Bomb, June 8, 1946) Tibbets is quoted as saying it was 150 degrees, and in the BBC documentary he said it was 159 degrees. It was Tibbets's explanation in the documentary of where this angle comes from that seemed to Rob to be incorrect. In just a moment I'll show you how to calculate the turn-angle.

In the 2005 book Shockwave: Countdown to Hiroshima, by Stephen Walker, we learn a bit more about the escape maneuver. At the instant of the drop "Tibbets disengaged the autopilot, grabbed the yoke, and did exactly what he had trained so long to do: he slammed the bomber straight into the right-hand diving turn, sixty degrees of bank [my emphasis, a value also found in the Post article], the massive bomber almost standing on its wingtip, the g-forces pinning every man to his seat." The reason for that was, of course, to quickly reverse the bomber's flight path and put as much distance as possible between the Enola Gay and the bomb detonation. That would maximize the probability of the bomber remaining intact when the massive supersonic explosion's shock wave eventually overtook the fleeing bomber.

Just what the safe distance might be was, however, pretty much a mystery. In mid-September 1944, just two weeks after learning of the bombing missions (code-named Silverplate) he would command as head of the top-secret 509th Composite Group (Composite because, unlike any other bomb group, its operational needs were totally supported within the group, with no outside support required), Tibbets met with J. Robert Oppenheimer, the