In the early 2000s, USC Viterbi Computer Science Professor Milind Tambe and a graduate student began working on a game-theory algorithm to optimize interactions among robots. They found that randomized interactions resulted in the most effective coordination.
“We were really just playing around with some concepts,” Tambe said. “Really, what could you do with this stuff?”
A couple years later, Tambe found out. At the inaugural meeting of CREATE (Center for Risk and Economic Analysis of Terrorism Events), USC’s Department of Homeland Security-funded national research counterterrorism center, one of the speakers suggested that the 9/11 terrorists succeeded partly because American security operations had become so predictable. “Suddenly, a light bulb went off,” Tambe said. “Maybe intelligent randomization could be of some value.”
In the years since, Tambe and his research team have created ARMOR, a sophisticated software program that greatly enhances security around the world in a variety of settings, ranging from American ports and airports to Asian wildlife sanctuaries to African forests. The software and its many iterations use algorithms to randomize patrols to confuse would-be terrorists, poachers and other malefactors by making it impossible for them to identify exploitable patterns. Through machine learning, the software also continuously improves with the input of new data, such as when and where past attacks have occurred and the identification and ranking of high-value targets.
ARMOR provides additional protection to high-value assets through what Tambe calls “intelligent randomization.” That means important targets receive extra protection while others receive less oversight. Taken together, the software optimizes the use of limited resources to provide the greatest possible security.
Tambe’s research is rooted in mathematical game theory, which tries to predict how conflict might play out between adversaries. According to the Bavesian Stackelberg game theory, the offense (the bad guys) observes the defense (counterterrorism forces, park rangers and others) to identify and exploit any security weaknesses. ARMOR, through the creation of intelligently randomized schedules, aims to thwart attacks by keeping the potential criminals guessing.
“I think Milind’s work is very important,” said Ariel Procaccia, a Tambe collaborator and assistant professor of computer science at Carnegie Mellon University. “I believe it’s one of the most important applications of algorithmic or computational game theory out there.”
It’s certainly among the most widely used.
In 2007, Los Angeles International Airport counterterrorism experts began using ARMOR to randomize the scheduling of police checkpoints for the six inbound roads to LAX. That project’s success led to the creation of a new version of the software, IRIS, to randomize the flight schedules of federal air marshals. In 2011, the U.S. Coast Guard began using a version of Tambe’s software, called PROTECT, to help protect the Port of Boston. Today, the system operates at four major American ports, including Los Angeles and Long Beach, which together rank No. 9 in the world by container traffic.
That’s not all. Last year, the Coast Guard successfully tested the system to thwart illegal fishing of red snapper and sharks off Texas in the Gulf of Mexico. Conservationists in Malaysia, Indonesia, Uganda, Nepal and elsewhere have tested or expressed interest in prototyping it to save endangered rhinos, tigers and other animals. The U.S. Navy, according to published reports, has expressed interest in using it for anti-piracy patrols.
With a missionary’s zeal, Tambe travels the globe to spread the word. His peregrinations have taken him from the Pentagon to national parks in Uganda. Tambe, a native of India with fluency in both Western and Eastern cultures, treads carefully when discussing the software, always listening and learning while diplomatically building consensus.
Tambe exudes deep-seated confidence about ARMOR’s potential to make a difference.
“I expect it to spread like wildfire throughout the world, including applications I can’t even think of,” he said. “I mean it’s absolutely fantastic. Wherever there’s an adversarial component involved, wow, we can be right there.”
Different iterations of USC Viterbi Professor Milind Tambe’s ARMOR game-theory systems are in use, undergoing beta testing or being considered for future uses around the globe.
U.S. Ports — PROTECT
U.S. Coast Guard officials Joe DiRenzo and David Boyd visited Milind Tambe at his USC office in 2010 to discuss his game-theoretical software and how he might modify it to optimize Coast Guard patrols of American ports.
DiRenzo, the Coast Guard Atlantic Area’s senior adviser for science, technology innovation and research, and Boyd, senior operations analyst at Coast Guard Pacific Area, both went away impressed. They were even more impressed when the police stopped them at a checkpoint on their way to LAX. Officers searched their car while dogs sniffed for drugs.
DiRenzo and Boyd knew that LAX police had employed Tambe’s system on roads leading in and out of the airport. Seeing it in action, though, brought home the value of intelligently randomizing scheduled patrols.
In 2011, Boston Harbor became the first U.S. port to use Tambe’s PROTECT system to secure crowded piers, bridges and ferry terminals. The Port of New York came next, followed by Los Angeles-Long Beach and Houston.
“Dr. Tambe’s research is both innovative and relevant in how we approach today’s port security problem set,” Boyd said. “It is very exciting to see how it is being applied to the maritime domain.”
Borrowing a page from Tambe, the Coast Guard randomizes scheduled patrols at most of its 361 ports. Still, PROTECT earns high marks for its effectiveness and ease of use. Perhaps that’s why senior Coast Guard officials have considered deploying it at other ports.
“We think it’s reduced the likelihood of an attack, because now we have randomized patrols,” said Craig Baldwin, program manager at the Coast Guard Research and Development Center. “From a mathematical sense, I believe it achieves the best resource allocation.”
The hijacking of four planes on Sept. 11, 2001, underscored America’s vulnerability to terrorists.
As part of its multipronged strategy to prevent future attacks, the Transportation Security Administration (TSA) has deployed Milind Tambe’s IRIS software since 2009. IRIS intelligently randomizes federal air marshals’ flight schedules to make their air patrols unpredictable to would-be malefactors.
For obvious reasons, TSA refuses to reveal when, where and on what flights it deploys IRIS. However, the agency uses the software at unnamed airports around the country and often on international flights, Tambe said.
“In some cases, when [TSA] have had to increase the number of air marshals, they’ve really exercised IRIS a lot more,” he said.
TSA appears quite satisfied with the software and is in ongoing talks about upgrading it and expanding its use, Tambe added.
In 2011, the Military Operations Research Society (MORS) awarded a TSA and USC team the prestigious RIST award for developing the intelligently randomized software. The university, former Federal Air Marshal Service Director Robert Bray said in testimony before the U.S. Congress, was “the first non–Department of Defense winner in history.”
In 2006, the RAND Corp. released a report stating that some terrorist groups viewed Los Angeles International Airport as an “attractive target.” Unlike many other airports, LAX has several roads leading into it, giving potential terrorists many possible routes for curbside bombings or other attacks.
RAND recommended round-the-clock security checkpoints along the five thoroughfares to LAX. However, the estimated cost proved prohibitive. Erroll G. Southers, then chief of homeland security and intelligence for LAX Police, had a different idea.
Through his affiliation with CREATE, USC’s Center for Risk and Economic Analysis of Terrorism Events, Southers knew Milind Tambe and was impressed by his work on intelligently randomized scheduling.
The LAX Police successfully tested the software in 2007. After “tweaking it based on officer feedback,” Southers said, officials deployed it in 2008.
“Weapons seizures went up. Narcotics seizures went up. And let’s just say our ability to identify persons of interest went up,” Southers said.
In January 2009, for instance, a random inspection of a truck on its way to the airport near Century and Sepulveda boulevards netted 10 handguns, five rifles, an antique musket and nearly 1,000 rounds of ammunition. One handgun was loaded.
ARMOR proved so effective at keeping the bad guys guessing that Southers could deploy fewer officers at roadside checkpoints and deploy them in the terminal and elsewhere.
Today, Southers, CREATE’s director of transition and research deployment, serves on the board of advisers of ARMORWAY, a new company created to commercialize Tambe’s “highly effective” software.
Staten Island — PROTECT
Up to 4,000 passengers take the Staten Island Ferry to and from Manhattan during rush hour. That makes it a potentially inviting target to would-be malefactors, especially given New York City’s status as America’s cultural and financial center.
The U.S. Coast Guard’s positive experience at several major ports with Milind Tambe’s security game-theory approach to optimize security asset allocation led the agency in 2013 to employ it at the Staten Island Ferry, according to Craig Baldwin, the program manager at the Coast Guard Research and Development Center.
“Anywhere it’s identified that escorts or some sort of protection is necessary for a ferry system, we’d like to consider utilizing the PROTECT game- theory approach to optimize the limited resources we have,” said Baldwin, who for the past four years has collaborated with Tambe on the system.
Tambe said he is proud of the growing acceptance of his game-theoretical randomizing software.
“When I saw the Coast Guard boats executing our algorithms from the top of the Staten Island Ferry, I was absolutely thrilled, goose bumps everywhere,” he said.
Fare evasion is a challenging and costly problem facing subway systems around the world. And the LA Metro is no different.
In an attempt to catch fare jumpers, the Los Angeles County Sheriff’s Department, which LA Metro subcontracts for security, began experimenting with Milind Tambe’s TRUSTS software in 2011. The game-theoretical approach appeared to work, said Sheriff’s Lt. John Sullivan, former operations manager for transit, North Bureau.
“I think [TRUSTS] is a good thing,” he said. “I think it helps us more effectively employ police resources.”
In 2013, a controlled two-month study compared the number of fare jumpers police caught using schedules created by usual means versus those made by TRUSTS. The result: Metro police apprehended 66 percent more evaders with the intelligently randomized software, Tambe said.
“The problem with schedules made by humans is that humans tend to fall into simple, predictable patterns,” he said.
The Sheriff’s Department also ran experiments to ascertain TRUSTS’ effectiveness in deploying scarce police personnel to deter crime and terrorism on LA Metro, Sullivan said. Preliminary results were good, although more extensive testing is needed to draw any definitive conclusions, he added.
Tambe said ARMORWAY, his new company, and the Sheriff’s Department are in discussions about the long-term deployment of his software for LA Metro.
Sullivan is optimistic about TRUSTS’ future. “If the research continues to show its viability,” he said, “I think it will be embraced by LA Metro, the Sheriff’s Department and transit systems nationwide.”
Gulf of Mexico — ARMOR-FISH
In the Gulf of Mexico off Corpus Christi, Texas, illegal fishing has decimated the shark and red snapper populations. Additionally, drug traffickers use the coastal waters to ply their trade.
Surface and aerial patrols have slowed illicit activities in the Gulf of Mexico, but there are simply not enough assets to cover the entire area. That’s why U.S. Coast Guard officials asked Milind Tambe and his research team to develop randomized scheduling software to help address this issue.
From the end of August until mid-October, the Game Theoretic Fish Patrol Schedule Model was deployed in the Gulf of Mexico in support of Coast Guard activities. During the 2014 testing, the Coast Guard interrupted two major illegal fishing operations—which impressed Sam Cheung, the Coast Guard’s Research and Development Center (RDC) project manager in game theory, along with his colleagues.
“Based on the results and feedback provided by relevant USCG officials, Dr. Milind Tambe and I think the Game Theoretic Fish Patrol Schedule Model supports operational effectiveness,” Cheung said.
Cheung has recommended that the Coast Guard and other government agencies consider employing it in the Gulf of Mexico and elsewhere to protect fish stocks and hamper other illegal activities, such as drug smuggling. However, Cheung added, “the challenge is finding the funds needed for long-term support and the required training needed for the software.”
Uganda — PAWS
In Uganda, poachers win all too often, much to the detriment of local animal populations. Poachers exploit the country’s porous security network to slaughter Cape buffalo, waterbuck and giant forest hogs, which are served up locally and exported as “bush meat.” They target elephants for ivory.
In an effort to thwart the country’s poachers, Milind Tambe and Ugandan partners including park rangers and NGO officials are working on PAWS-Uganda, an iteration of the ARMOR software. In November, Tambe visited the country for a series of meetings to answer questions, listen and garner support. Among others, he talked to a high-ranking Uganda Wildlife Authority official to obtain new data that would allow Tambe and his team to fine-tune PAWS-Uganda.
In April 2014, Ugandan rangers tested PAWS at Queen Elizabeth National Park. Overall, the field tests went well. However, a few of the suggested patrol routes were less than optimal because they had been based on incomplete or outdated information, said Andrew Lemieux, a criminology researcher and Tambe associate who works closely with the Ugandan national park.
Tambe has vowed to make the necessary fixes. He also plans to continue discussions with potential Ugandan partners to increase their comfort level with software created by American academic researchers thousands of miles away.
“Overall, I am hopeful PAWS will be deployed in Uganda,” Tambe said, “but to make it official will require some effort.”
Malaysia — PAWS
Throughout Southeast Asia, experienced poachers wage war on the continent’s dwindling tiger population. Using leg snares and baited poison, they ruthlessly and efficiently kill the animals for their fur, meat and bones, which are often used in Chinese medicine. The systematic slaughter of tigers has reduced the worldwide population in the wild to as few as 3,200, a 97 percent drop in just over a century, according to the World Wildlife Fund.
Illegal tiger trappers in Asia can operate undetected in forests for long periods of time, making them difficult to locate and arrest, said Rob Pickles, monitoring specialist in Panthera’s Tiger Program, an NGO committed to ensuring the survival of tigers and other wild cats. That’s why Panthera has partnered with Milind Tambe and his research team to test PAWS in Malaysia.
In November, Panthera, in conjunction with the nonprofit group Rimba, began testing the software in forests in northeast Malaysia. They evaluated its ability to generate effective patrols in the challenging, hilly terrain, Pickles said. Tambe hopes to visit Malaysia this spring to oversee additional beta testing and to forge closer links with nonprofit and governmental conservation agencies.
“Panthera currently operates in 14 tiger sites across Asia, and each one of these requires guidance on patrol strategy,” Pickles said, “so PAWS might be an excellent tool to use at all of our sites.”
For the Pentagon, there is no greater duty than protecting U.S. troops, whether in transport, training or combat. With terrorists throughout the world targeting the United States and its military assets, the threat of sabotage and terrorism is a real and present danger.
After reading how the U.S. Coast Guard uses Milind Tambe’s ARMOR software to protect some American ports, “it was pretty easy to envision using it for force protection around military bases and facilities,” said U.S. Army Col. Jeffery Hannon.
Hannon said that the military faces the large challenge of how to deploy a shrinking number of ships, aircraft and troops to address a growing list of global and domestic needs. He thought a game-theoretic model application structured like ARMOR could be modified to meet users’ specifications and to identify and test different ways to assign and allocate military forces on a global scale. With that in mind, Tambe and Hannon met last summer with officers from the U.S. military to discuss the approach behind the ARMOR software.
While there is no commitment yet, Hannon said he thought ARMOR is “a useful tool that could be a significant jump forward for how the military tackles scarcity, whether the challenge is local force protection or the global problem of allocating forces to U.S. Combatant Commands.”
Madagascar — PAWS
In Madagascar, lush forests support the multitude of animal and plant life that contributes to the island country’s rich biodiversity. The forests sequester carbon, prevent erosion, promote ecotourism and serve as a source of malaria medicine and other plant-based medicines.
They also attract illegal loggers in search of money. In eastern Madagascar, they have cut down rosewood, ebony and other trees used in the production of musical instruments and furniture. It is believed that organized crime, some with ties to terrorist organizations, oversees the deforestation.
Meredith Gore, an associate professor of conservation social sciences at Michigan State University, believes that Milind Tambe’s ARMOR software might help turn the tide. She, Tambe and a Malagasy civil society group called Alliance Voahary Gasy (AVG) hope to eventually employ the software to randomize patrol schedules for rangers, police and national park officials to reduce environmental crimes.
In August, Gore and AVG officials visited eastern Madagascar to gather data from local people about where illegal logging takes place, the routes used to transport the stolen wood and the types of trees most at risk—information that Tambe can incorporate into the software. She and Tambe hope field-testing could begin by the end of this year.
“Everybody in Madagascar has been incredibly excited about collaborating with Milind, learning about the technology and science, and making a difference on the ground,” Gore said.
Singapore — STREETS
As a USC Viterbi computer science graduate student, Pradeep Varakantham worked closely with Milind Tambe, one his Ph.D. advisers. When he graduated in 2007, Varakantham was well aware of Tambe’s ARMOR software and its potential.
Today, the assistant professor of information systems at Singapore Management University is collaborating with Tambe on new software that would intelligently randomize traffic police patrols to reduce the growing problem of reckless driving in the Asian city-state.
In Singapore, the number of traffic violations for speeding, running red lights and other infractions has increased, according to a 2013 report by the Singapore Police Force. The problem of reckless driving has become so acute that in 2012 the government created a multipronged program called Safer Roads Singapore.
Varakantham, Tambe and other researchers are working on a software program called STREETS that would intelligently randomize patrols and enhance roadside safety.
The duo has met several times with officials from Singapore’s Ministry of Home Affairs about it and hopes to secure funding for large-scale testing and deployment. Varakantham and Tambe are confident STREETS would make a difference.
“To the best of our knowledge, existing methods of traffic patrolling rely solely on the intuition of traffic officers on the ground,” Varakantham said. “STREETS not only incorporates information about driver driving patterns on different roads, but it also projects a perception of omnipresence through strategic randomization.”