Error on line 60 position 2: Syntax error
Error on line 60 position 2: Syntax error

Search theory and big data: Applying the math that sank U-boats to today's intel problems

Jul. 5, 2013 - 03:45AM   |  
By ROBERT BECKHUSEN   |   Comments
Coast Guardsmen on the deck of the cutter Spencer watch a depth-charge attack on a German U-boat in 1943.
Coast Guardsmen on the deck of the cutter Spencer watch a depth-charge attack on a German U-boat in 1943. (Coast Guard)
  • Filed Under

It was July 13, 1943, and German submarine U-607 sailed from France on a mission to lay mines in the Caribbean against American ships.

Traveling through the Bay of Biscay, the U-boat’s voyage was uneventful as the clock ticked past midnight. Blissfully unaware of danger, the officers popped champagne to celebrate their captain’s birthday. They had no idea they were being hunted by Allied forces incorporating advanced new techniques thought up by some of the best mathematical minds in America. Hours later, patrolling British aircraft swooped down, releasing depth charges. The blast was so great that the hull broke in two and the conning tower flew into the air. Half the crew was killed.

The U-boat had become one more success for an obscure but intriguing branch of mathematics developed to help the war effort. Refined during the Cold War, the field would come to be called simply “search theory.”

“Search theory is about how to distribute your resources to most efficiently find something when you don’t know where it is, but you have some idea about where it might be and how it moves,” said Charles Twardy, a research professor at George Mason University and an expert on the discipline.

In simple language, search theory uses advanced math to help calculate where your target may be. In recent years, the discipline has been revitalized to help hunt insurgents, missile sites and improvised explosive devices. Now the Pentagon is exploring whether it can help sort and simplify the massive volumes of data compiled by modern ISR sensors.

MATHEMATICIANS AT WAR

The feared German U-boat fleet had no shortage of prey in the early years of World War II. Britain was dependent on American supplies shipped across the Atlantic to stay in the fight, and Axis submarines were inflicting severe losses on merchant vessels. The fall of Paris in 1940 opened up new ports, notably at Saint-Nazaire on France’s Atlantic coast, which extended the submarines’ range.

But the U-boats sailing from occupied France had a vulnerability: they had to cross the Bay of Biscay to reach the open ocean. The bay was something of a funnel, forcing the Nazi fleet to a closed space, potentially vulnerable to Allied aircraft. At the time, submarines operated mainly on the surface to conserve fuel, typically submerging only to attack or flee.

In 1942, the U.S. Navy gathered elite mathematicians to form the Operational Evaluations Group. Working with Bernard Koopman, these experts began to refine theories of probability and other mathematical concepts to target, specifically, the location of submarines.

Koopman, a French-born mathematician who would become the Navy’s first prominent search theorist, believed existing submarine search methods had shortcomings. One traditional tactic involved flying a patrol plane at 45-degree angles along suspected U-boat routes while scanning the water for surface wakes. On its face, it made sense. Since it was assumed most U-boats were leaving French ports and heading west in a direct line, this pattern was thought to optimize the territory covered.

But these methods relied on a lot of assumptions. What if a submarine tacked back and forth, changing course unexpectedly? Koopman theorized that sub hunters could do better by attempting to calculate the probability of locating the target in various given areas. He used Bayesian models, mathematical tools for determining likelihood. Once an area was combed through, the search formulas could be refined to find more and more likely target areas.

By 1943, the methods were being used in the Bay of Biscay, along with sonar and radar, to devastating effect. The U-boats took heavy, regular losses, and more American vessels managed to cross the Atlantic unharmed. Search theory by itself wasn’t responsible, but now Allied search aircraft had a working methodology.

FINDING LOST H-BOMBS

After the war, other researchers built on this new branch of mathematics. The anti-submarine operations of the Cold War continued to demand better ways to narrow search parameters, , and other applications were discovered as well.

By the 1960s, search theory was a well-developed field in national security studies.

“The next search that came up were the H-bombs that were lost off Palomares,” said Larry Stone, a chief scientist at Virginia defense firm Metron and a leading authority on search theory.

In 1966, a U.S. B-52 bomber broke apart above Spain, losing four of its hydrogen bombs, one of them in the Mediterranean. The bomb was later discovered using search theory — along with some help from a Spanish fisherman who happened to see the plummeting bomb and gave authorities a search heading to apply to their formulas.

Next came the loss of the nuclear attack submarine Scorpion, which sank with 99 men in a catastrophic 1968 accident. Stone was a young analyst for the consultant firm Wagner Associates. After being told about the loss of the submarine, Stone and his colleagues laid out of a series of scenarios with the possible location of the missing ship, based on search theory principles. His colleague, Tony Richardson, was told by the Navy to draw up a probabilistic distribution of the likely locations, and then “pack your bags tomorrow for a flight out to the Azores to help with the search,” Stone recalled. Richardson found the sub southwest of the islands at a depth of about 10,000 feet.

In the 1970s, the Navy invested more in the research, seeking to locate Soviet ballistic missile submarines operating near U.S. coasts. And in 1974, the Coast Guard begin using its first computerized search program based on Bayesian models, called the Computer-Assisted Search Planning system, or CASP.

“You wouldn’t believe the computer they used then,” Stone said. “This was originally a batch program run on a mainframe with very limited capabilities in the Commerce Department building down in Washington, and it was accessed by teletype with extremely limited memory and computational capability.”

THE 'FLAMING DATUM' ThEORY

Search theory works the same way no matter what you are searching for. Commanders may be hunting a submarine in the Pacific, a Scud missile in the desert or an IED on a highway. Or, say you’re looking for your car keys in a giant parking lot or for an Alzheimer’s patient who wandered into the woods. These are all small targets lost somewhere in big spaces.

Most searches are based on grids and depend largely on luck and the number of searchers you can bring to bear on the territory. Try to cover a large territory with a small number of searches, and your success is unlikely.

Search theory tries to improve your odds by showing you which areas are more or less likely to contain your target. Here’s a taste, for the mathematically inclined: The “random search formula,” one of the bedrocks of the doctrine, represents time required to cover an area as l = VW?/A. A is the area of territory to be covered, visualized as a rectangular grid on a map. The reciprocal of lambda (l), seen as VW?, represents the length of time required to cover A once.

Then take the next formula, where your final probability of detecting a target is represented as PD. Plug your values into the formula PD(t)= P(T=t) = 1- exp(- lt). Here the lower-case t represents your time to locate the target. Upper-case T is a random variable.

And theoretically, you’ll have your probability of finding the U-boat, in a particular period of time.

But the random search formula was meant to find targets that were moving in a more or less predictable fashion. As search theory evolved, mathematicians began to explore more variables. What if you’re searching for an object moving at a high speed? Or a thing that doesn’t want to be found?

“That was one of the original problems that motivated search theory during World War II,” Stone said.

Once a submarine realizes it’s being tracked, its behavior will change. That’s a problem for searchers, and all the new variables cause the math to get very complicated, with a whole new set of formulas. Search theorists even have an inside joke for one of the complications: the “flaming datum” problem.

“Torpedoes hit a ship, and boom, there’s a flame,” Stone said. “I know a submarine was over here at the time the torpedo was fired, and he’s submerged, and I want to find him. The assumption then is that the submarine could have taken off in any direction, uniform from zero to 360 heading, at some range and speed, and you don’t know.”

This analogy could also be approximated to a Scud missile launcher that just fired its payload before fleeing from an incoming aerial counterattack, or a triggerman for a remotely detonated bomb. ISR sensors have detected the location of the explosion or rocket launch, but the triggerman — or Scud launcher — could have taken off in any direction.

“You can’t make the simplifying assumptions you make when they’re not reacting to you,” Twardy said.

HUNTING INSURGENTS

After the Soviet Union collapsed, the threat from enemy submarines faded, and search theory lost favor. The 1990s were something of a nadir for work in the field.

But the conflicts in Iraq and Afghanistan renewed interest in the discipline. Mathematicians saw how it could have new applications in national security, pinpointing threats. After all, commanders were now focusing on finding IEDs on roadways, traveling insurgents in valleys and routes for enemy supply lines.

“A lot of it is applying the existing search theory to land detection,” said Twardy, who has contributed research on search theory to the Pentagon’s Joint Improvised Explosive Device Defeat Organization. Some of that research included trying to locate insurgents planting IEDs.

In 2010, U.S. Special Operations Command sponsored field exercises at Camp Roberts, Calif. Operators of an RQ-11 Raven drone used Bayesian search models to find vehicle-borne improvised explosives in transit before they detonate. The exercise pitted a forward-operating base positioned along an intersecting network of roads against several civilian cars with drivers posing as suicide attackers. The Raven’s job was to locate the VBIEDs before they moved into blast range.

The exercise didn’t go as well as hoped. The Raven only detected the VBIEDs two times out of 12 simulated attacks. A summary from the Naval Postgraduate School concluded that the Raven “proved to be an inadequate platform for this task,” owing to its limited range. But there was a note of optimism: The theory could work, and it could potentially work better with a bigger drone.

In 2011, researchers at the Naval Postgraduate School surveyed recent efforts to adapt search theory in mobile ground robots for locating missing persons and pursuing fleeing targets. One exercise involved two single-wheeled Rotundus GroundBots equipped with GPS systems made to navigate an obstacle course. The robots “were able to guarantee detection of any potential adversary.” But it’s an open question whether they’d succeed in more complex terrain.

“You need to know how good your sensors are,” Twardy said. If you do, and you’re aware of the environment and the target you’re looking for — such as its speed and likely route — you can narrow down a measure of certainty as to what your high-priority areas should be. “Your sensors might be eyeballs, they might be sonar, they might (be) a UAV flying overhead,” he added, warning that success can’t be always guaranteed.

In 2011, the Defense Advanced Research Projects Agency sponsored a team of researchers who used search theory algorithms to analyze satellite images of surface-to-air missile sites. Analysts were shown brief — less than a second — flashes of satellite images and were tasked with identifying which ones were showing missiles, according to a paper about the study. Algorithms based in search theory then found the “optimal” interval of time to present the images to analysts. It was 200 milliseconds.

SEARCHING BIG DATA

The next challenge for this venerable branch of mathematics is no less than one of the biggest challenges faced by modern militaries: big data. The intelligence community has made no secret of its need for methods to work with the deluge of data produced worldwide.

“There’s really two veins of search theory. There’s the classic random search and then there’s the large data search, or large problem search, which is really what’s getting the lion’s share of attention,” said Jeffrey Cares, president of Alidade, a Rhode Island company that has developed search theory games for the Navy. “We have all of this data in centrally located databases, and we have to figure out how that all goes together. We have these huge search problems that we force upon ourselves by centrally locating data.”

Cares doesn’t believe search theory is a panacea for global databases and the truly massive volumes of information, but the discipline could be a solution on a case-by-case basis. One example where it could be a game changer: video feeds from wide-area surveillance systems, such as an aerostat or drone.

Twardy, the researcher who worked with JIEDDO, also believes that search theory may not single-handedly solve problems in big data or intelligence analysis, but he believes that the discipline will be part of the answer. The complexity of the mathematical formulas may have increased since the days of World War II, but the fundamentals are the same.

More In C4ISR Journal

Start your day with a roundup of top defense news.

More Headlines

Shutdown undermines cybersecurity

Shutdown undermines cybersecurity

With fewer eyeballs monitoring the government's networks for malicious activities and an increasing number of federal systems sitting idle during the shutdown, security experts fear it could create a perfect storm for insiders and hackers looking to do ag

Exclusive Events Coverage

In-depth news and multimedia coverage of industry trade shows and conferences.

TRADE SHOWS:

CONFERENCES: