Search Theory: Search & research

Metron software detects a moving submarine in a high false alarm environment. Source: Metron

By Douglas A. Samuelson

Sometimes it takes a while to write up a good piece of work, including the pesky details. Lawrence (“Larry”) Stone knows all about that. He’s been working on optimal search since 1968, and wrote a classic book on search that dealt mostly with stationary targets. He soon found additional results on moving targets. It was just this past year, however, that he and his co-authors Johannes Royset and Alan Washburn finally pulled the new results together into a book, “Optimal Search for Moving Targets,” and into print [1].

Lawrence (“Larry”) Stone

Stone joined Daniel Wagner Associates in July 1967 with a fresh Ph.D. in math, having written a dissertation on stochastic processes used in underwater detection. One reason he joined Wagner Associates was that Tony Richardson, who also worked for the company, told Stone about reporting to an admiral every day during the search for a lost H-bomb that had fallen from a B-52 into the ocean near Palomares, Spain, in 1966. In May 1968, the nuclear submarine USS Scorpion was lost at sea and John Craven (who worked with Richardson on the H-Bomb search) was put in charge of the analysis group for the search. Craven asked Richardson to come to his office in Silver Spring, Md., and Richardson asked Stone to accompany him. During the meeting, Craven and a retired submarine captain, Frank Andrews, described scenarios for the loss of the Scorpion. Richardson was assigned the task of using these scenarios to produce a probability map for the location of the wreck.

Upon ascertaining that Stone had a passport, Craven directed him to fly to the Azores the next evening and to join the scientists aboard the Naval Research Laboratory vessel USNS Mizar, which was searching for the wreck near the Azores. Stone spent the next seven weeks at sea providing advice on where to search. He was relieved by a series of analysts from Wagner Associates as the search dragged on. The sensors were poor, particularly the side-looking sonar, and the team had trouble navigating the search sled. The only sensor that worked well was a camera, but it had limited range. Eventually, though, in October, the team found the wreck within 200 yards of the highest-probability cell in the map prepared by Richardson.

“After the search,” Stone recounts, “Tony obtained an Office of Naval Research (ONR) contract to study search theory. I received about 10 years of support from ONR, became an expert and published a book on search theory [2]. At that time, the available results applied mostly to stationary targets. We could find optimal moving target plans only for two-cell Markovian motion and something called conditionally deterministic motion. People had obtained necessary conditions for targets that moved according to a diffusion process such as Brownian motion, but we were not able to use these conditions to find optimal plans. Alan Washburn, of the Naval Postgraduate School, obtained a different set of necessary conditions for optimality for a simple discrete-time, one-dimensional target motion in a discrete state space.”

Helping to find the USS Scorpion, which was mysteriously lost at sea in 1968, helped launch Larry Stone’s career in search theory. Source: Wikipedia

As a referee, Stone suggested trying to solve the problem for a discrete-time Markov Chain motion model, but Washburn replied that he didn’t see how to do that. Stone next suggested to Scott Brown, at Wagner Associates, that the problem of finding an optimal plan for searching for a moving target over a fixed time period [0, T] in discrete time and space might be approached as a convex programming problem. Brown responded with the idea that the convex program could be made more efficient by, at each time step, allocating search effort so that it is optimal for the stationary target problem obtained by computing the posterior distribution at that time given failure to detect at all other times. Brown suggested that one proceed through time in forward fashion until time T and then return to time 0 and repeat the process. He showed that this forward and backward process converges to the optimal plan for discrete time and space target motions.

Brown submitted these results to the journal Operations Research; more than two years went by without a response from the referees. Meanwhile, Stone co-chaired a NATO search conference in 1979, and Brown presented the results there and discussed them with influential colleagues. Shortly after that the paper was accepted for publication. Washburn added a way to calculate an upper bound on the difference in probability of detection from a plan obtained in Brown’s recursion and the optimal plan. It turned out that it doesn’t take many passes to get close to optimal. Washburn generalized Brown’s result to obtain a class of forward and backward (FAB) algorithms with applications to a number of other problems.

Stone generalized these results to find necessary and sufficient conditions for an optimal plan for any combination of continuous or discrete time and space and also expanded the class of detection functions that could be used beyond the exponential or random search detection function assumed in previous moving target results. One of the major assumptions in all of these results is that search effort can be distributed in space as finely as desired and that the placement of search effort at one time period does not constrain where you can place search at any other period. When such constraints are present one has a much more difficult problem to solve. This is called the constrained searcher path problem. Stone’s coauthor Johannes Royset and his colleagues have made major progress on solving this problem in operationally realistic cases. This progress is reported in two chapters of “Optimal Search for Moving Targets.”

Extensions to Detecting Submarines

“In the 1970s, we and others started looking at applications to anti-submarine warfare (ASW), Stone continues. “For example, searches for Soviet ballistic missile submarines were cued by detections from our long-range underwater sonar system, SOSUS. The Navy would then send out a mission, an aircraft planting a field of sonobuoys, to redetect and localize the submarine. We developed an approach to planning these missions based on computing optimal search plans for a sequence of missions using a variation of the recursion developed by Brown. We implemented this computer planning system for ASW patrol aircraft operating in the Pacific.

“In the process of developing and testing the system, there was a time when both the new computer system and the existing manual planning system were being used. We took advantage of this to compare the effectiveness of searches planned with and without using our program and found that the detection probability was about twice as high when it was used. All this work was done by 1980-81 or so, but we never got around to writing it up in a coherent fashion. We published some papers but never pulled it all together. I thought about pulling these results together for about 30 years, and finally did it starting in 2014.”

The result was the book “Optimal Search for Moving Targets” [1] published in 2016.

Mine Clearance and a Sojourn in Suez

The 1973 Yom Kippur War thrust Stone into a new problem area: clearing unexploded ordnance. One of the sweeteners then Secretary of State Henry Kissinger had thrown into the peace agreement that he negotiated between Israel and Egypt was help for the Egyptians in clearing out the unexploded ordnance that had been dumped into the Suez Canal. In 1974, Wagner Associates got a contract to help the U.S. Navy provide this promised help. Richardson and Tom Corwin, a new Ph.D. from Princeton, tackled this problem, structuring it as first a search problem, then a clearance problem, and then a problem of estimating how well the canal had been cleared. Richardson and Corwin provided the initial on-scene analysis followed by a sequence of analysts from Wagner Associates. Stone was one of the later ones.

“We had to deal with rough conditions,” Stone notes. “Kissinger promised the Egyptians that our people would stay in their hotels and eat at their restaurants . . . while the Russians and French were on ships. We were staying in Port Said, where we had only a couple of hours of water per day. Everyone got sick. Then we got moved to Ismailia, where the Canal Company’s headquarters was located. That was pretty good.”

For the Scorpion search, Stone relied on a handbook of math tables, a slide rule and a small desktop calculator. Just five and a half years later, at Suez, the team had HP-35 hand-held programmable calculators and a programmable (in machine language) Wang desktop calculator. This made possible a major technology change, with most of the heavy computation done onsite.

Detection and Tracking, Search and Rescue, and Corporate Management

In the early 1970s, Richardson, whom Stone credits with teaching him operations research, convinced the U.S. Coast Guard to contract with Wagner Associates to develop a search planning system (Computer Assisted Search Program) to help find people and boats missing at sea. This typically involved modeling the drift of the search object. The approach Richardson developed was to generate Monte Carlo paths from estimates of winds and currents to represent the drift and then allocate search based on the resulting probability map. If a search failed, the system computed the posterior probability map based on failure to detect and drifted the paths to the next search time. It then allocated the next increment of search based on this distribution.

“It was like what’s now called a particle filter,” Stone explains. “We’d done the earliest version around 1974. In applications later developed for the Navy, we used resampling to update the Monte Carlo tracker for detections, such as the ones obtained from the SOSUS system. We think it was the first operational use of a particle filter. In the late 1990s, Neil Gordon, who I believe was in the United Kingdom at the time, rediscovered particle filters and developed and popularized the method with modern computers.”

And why the nearly 30-year wait to write a book on moving targets? Stone joined Metron in 1986 and became absorbed in getting Metron going. Metron, a Wagner Associates spin-off, was founded by Tom Corwin in 1984. There Stone became interested in detection and tracking problems, which are in some ways very similar to search problems but in other ways different. Stone worked on the detection and tracking of submarines and developed a multiple-target tracking system for the Navy’s underwater surveillance system, but the tracker was never implemented because the USSR collapsed and the Navy lost interest in tracking Soviet submarines. Fortunately, Metron obtained a contract from the Office of Naval Research to investigate multiple-target tracking as a Bayesian inference problem. Based on that work, Stone coauthored a book, “Bayesian Multiple Target Tracking,” published in 1999, with a second edition in 2014 [5], that occupied a lot of his time.

Also in the mid- to late- 1980s, Metron was heavily involved in producing the probability map for the search for the S.S. Central America, a ship that sank in a hurricane off South Carolina in 1857, carrying a massive cargo of gold from the California gold rush. The search team discovered the ship in 1987, and in 1988 the team brought more than one ton of gold recovered from the ship into port in Norfolk, Va. This work was named an Edelman Award finalist in 1991 [6]. But, of course, this was a search for a stationary target and did not involve developing new search theory.

Larry Stone was a member of the team that located the sunken steamer SS Central America and its cargo of gold. Source: Wikipedia

About 2005, Metron had a chance to help the U.S. Coast Guard completely redo its search and rescue planning program, now called the Search and Rescue Optimal Planning System (SAROPS). Metron developed the portion of SAROPS that produces probability maps and recommends search plans; other companies provided the user interface and developed the data server that incorporated meteorological data from all over the world. The system was implemented in 2007. It was enabled by computer capability, but also by some theoretical developments: When searching for a person in the water, you want to maximize the probability of detecting the person alive, not just the probability of detection. As an example, suppose that you are searching for a person who maybe in the water or a raft. Initially searching for the raft possibility would likely maximize the probability of detection, but searching first for the person in the water possibility gives a better chance of saving the person’s life.

Stone’s pursuit of his earlier research also suffered from the distraction of his increasing executive involvement in Metron, culminating in serving as CEO from 2004 to 2009.

Back to Moving Targets at Last

Stone has now had a few years to reflect, review and add to his earlier classic work. (The 1975 book won a Lanchester Prize for the best O.R. work published in English.) Asked whether he hoped for another Lanchester Prize this time, and whether he would like a review in Interfaces, Stone says, “You know, you’d have to read it first.” This turned out to be a genuine caution, not a comment on some reviewers’ penchant for sloppy work. It’s definitely not a beach read, even for advanced probability modelers. The math rises to daunting levels, and the assumptions are subject to lively disagreement once you understand enough to recognize them.

“I had lots of disagreements with Bernard Koopman (the founder of search theory who wrote a classic report on search theory in 1946 and several important papers in the 1950s) about the ‘Theory of Optimal Search’ book,” Stone admits. “He said it had too much measure theory and not enough physics and applications, and now looking back, I’d have to agree with him.”

Stone concedes, “My contribution to optimal search was to round out and extend the theory. Koopman was much stronger mathematically. But Koopman objected to the use of subjective probabilities, and it is hard to apply the results in this area without using subjective probabilities!”

Actually, it looks impossible. One would have to have enough observational data to make frequentist inferences, and the absence of such data is pretty much the definition of the problem. But the analyst is left with uncomfortable questions about whether her or she is assuming too much. Probabilists continue to have heated disagreements about this.

“I’ve been lucky many times in my career,” Stone ads. “Getting to work on the Scorpion search, spending a year as an adjunct professor at the Naval War College, which gave me the time to write ‘Theory of Optimal Search.’ And not having Koopman as one of the judges for the 1975 Lanchester Prize.”

New Worlds to Conquer?

Although the new book is the summary and culmination of a lifetime of work, there is still much to be done. There is just one chapter dealing with searches in which the target is either trying to cooperate or trying to evade. Stone refers the interested reader to a book by Alpern and Gal [5] that includes evasion, and one by his co-author, Alan Washburn, on search games [6]. Stone’s longtime friend and later colleague at Metron, John Kettelle, developed a substantial theory on how to hide, but never published it. Nor, apparently, did he pass his notes to anyone else who has since pursued the subject.

And applications abound. The continuing rapid growth of computing capability makes possible amazing transformations of theory into applied inference. No doubt there are interesting ways to do tasks such as detecting intrusions into communications and computer networks, problems that would apply the current theory and then add new facets. Stone’s new book provides a valuable basis and beginning for the work yet to be done.

Doug Samuelson ([email protected]) is president and chief scientist of InfoLogix, Inc., in Annandale, Va.

References

1. Stone, Lawrence D., Johannes O. Royset, and Alan R. Washburn, 2016, “Optimal Search for Moving Targets,” Springer.
2. Stone, Lawrence D., 1975, “The Theory of Optimal Search,” Academic Press; 2nd Ed, 2007, INFORMS.
3. Alpern, Steve, and Shmuel Gal, 2003, “The Theory of Search Games and Rendezvous,” Springer.
4. Washburn, Alan, 2013 (4th Ed.), “Two-Person Zero-Sum Games,” Springer.
5. Stone, Lawrence D., Thomas L. Corwin and Carl A. Barlow, 1999, “Bayesian Multiple Target Tracking,” Artech House; 2nd edition by Lawrence D. Stone, Roy L. Streit, Thomas L. Corwin, and Kristine L. Bell 2014, Artech House.
6. Stone, Lawrence D., 1992, “Search for the SS Central America,” Interfaces, Vol. 22, No. 1, January-February, pp. 32-54.