USC News

Menu Search

Computers learn to match wits with humans

Simulated battle scene: Soar helicopter-pilot agents engage “enemy” fighting vehicles.

Last week’s hard-fought chess match between world chess champion Gary Kasparov and the Deep Blue computer system is one illustration of how far software has come in reproducing complex, human decision-making ability. Other dramatic examples can be observed at the School of Engineering’s Information Sciences Institute (ISI), which has created computer “agents” that can match wits with top human jet-fighter pilots in simulated dogfights conducted in virtual computer environments.

The project that created these silicon sky warriors and other programs – including ones that reproduce the skills of helicopter pilots engaging enemy fighting vehicles, Navy firemen trying to control shipboard blazes and even soccer players working together as a team – is called “Soar.” The goal is to develop what project leader Paul S. Rosenbloom calls “a basic architecture for intelligent systems.”

Rosenbloom began working on this architecture in the early 1980s, as a student of artificial intelligence-pioneer Allen Newell at Carnegie-Mellon University. He started Soar (the name is not an acronym) in 1983, in cooperation with Newell and University of Michigan researcher John Laird, who currently co-directs the project with Rosenbloom and Carnegie-Mellon researcher Jill Fain Lehman.

The project, which is funded by the U.S. government’s Advanced Research Projects Agency, has explored military modes of decision-making. However, it is unclassified and has potential applications for endless civilian uses, including entertainment. USC-based Soar researcher Milind Tambe, for example, is preparing a team of silicon soccer players to compete in a virtual tournament, “RoboCup ’97,” to be held next year in Japan.

While the abilities of the systems are still limited, they are genuine, as Soar computer fighter-pilot agents proved in a 1994 war game, “STOW-E” (for “Simulated Theater of War – Europe”).

The Soar agents performed at what Rosenbloom described as a “Third-World pilot” level against real-life top guns. They were able to post some victories, particularly in multiplane environments, where human pilots could be more easily distracted.

This is notable because modern high-performance aircraft combat – conducted at long distance by missiles and sensors – is more than a simple test of reflexes, a task at which the computer might be expected to excel. Rather, it is a chess-like game of cat-and-mouse, in which success depends on thinking one’s way through conflicting and ambiguous clues and deciding – in time – what an adversary is doing, and how best to counter it.u0000

In some ways, the agent creations of Soar might be thought of as supersophisticated relatives of the arcade-game kick-boxers and kung-fu fighters ready to do battle with teenagers at the drop of a quarter.

But according to W. Lewis Johnson, a Soar project leader, arcade-game gladiators “have a very limited repertoire of heavily scripted behavior. They have little or no adaptability.” Instead, the figures are – rather like insects – pre-programmed to react to specific situations in specific ways. When they ‘see’ a figure answering a certain description, for example, they always attack, if and only if an adversary comes within a certain distance. If a situation falls outside a scripted scenario, such a character is unable to respond.

Agents of Soar, on the other hand, behave in a more autonomous, more complicated way. In conflict situations, agents watch the behavior of their adversary, attempting to understand it the way a human would – as actions aimed at accomplishing a goal. Similarly, they themselves act in order to accomplish a mission with specific goals. However, they have great flexibility in how they go about achieving those goals – a basic requirement for any intelligent system, according to Newell.

Johnson’s particular specialization adds a further wrinkle to this process: he focuses on “debriefability” – the agents’ ability to describe and explain their problem-solving activities. This feature allows a computer operator to stop an agent at any point during a conflict situation to get a status report and review the agent’s plan for accomplishing its mission.u0000

The amount of computation necessary to create such agent behavior is formidable – far more complex than that needed to program arcade-game kind of behavior. Such programs must run fast enough to mimic the speed of human thought, because even the best decision is worthless if it comes too late.

Years ago, when the concept of “artificial intelligence” was first put forward, programming experts were only beginning to grasp how to create complicated, autonomous, goal-oriented behavior – and the machines that existed to run such programs were large and slow. Now, both machines and programs are better, “and the technology is starting to catch up with the hype,” Johnson said.

In a successful model, all agents must be able to function on three levels.

* They must have a perception mechanism that lets them receive inputs.

* They must be able to take a range of actions to affect the environment – moving, grasping and pointing are typical. This function is closely tied to the previous one. In effect, agents must be able to take actions equivalent to turning the head to bring new objects into view.

* They must be able to analyze tasks and orchestrate actions in purposive behavior, in response to perceptions.

More sophisticated agents can have the ability to remember what they have done, to explain it and even, in new versions, to learn from it.

Johnson said the first two areas are much more difficult than they seem, as roboticists attest. If a human sees a video image of, say, a picnic at a beach, he or she has no trouble identifying objects in it – the picnickers, the basket, the beach ball. But it is surprisingly difficult to train a computer – even a fast, capable one – to do the same. To further train the computer to control devices to interact with this environment involves yet another set of difficulties.

“We finesse problems like this,” said Johnson, by having agents built in the Soar program operate in virtual environments, rather than real-world ones. This way, the first two tasks can be greatly simplified, to allow the agents to concentrate on the third.

This still leaves a highly challenging group of problems. For example, the helicopter agents, created by a group headed by Tambe, must follow terrain (their simulated battles take place on a detailed topographical map) not just to avoid crashing, but for tactical purposes; they must find areas where they can hide from enemy view and pop up at the right moment to attack.

The programming covers “not just flying, but how to attack, how to choose weapons, how to fly in formation, how to break formation, when and how to go to a firing position, all of which have to be dealt with in real time,” Rosenbloom explained.

Creating team behavior is another challenge, said Rosenbloom. “Each agent has to ask itself what its role is in the group, what commitments does it have to the group. We have had dysfunctional behavior by agents.” Tambe is trying to make the agents more cooperative – a project that has obvious bearing on another project, the team of soccer-playing agents.

Soar researchers are also trying to create “command agents” that can coordinate the actions of groups of subordinates. “The command agent gets orders and has to implement them – it has to plan a route, give orders, make sure they are understood, make requests for information, and inform superiors about what he’s doing,” Rosenbloom said. USC-based Soar researchers Jonathan Gratch and Randall Hill are working to develop and program these abilities.

That a computer program is capable of behavior like this is perhaps more surprising than the fact that another program recently competed with the reigning world chess champion on roughly equal terms.u0000u0000

Humans may soon get a chance to watch Soar agents more directly. Johnson is trying to integrate Soar into a “virtual human body,” which will function in computer environments as a trainer for human students. (See graphic, page 7)

Johnson believes that Soar-type agents have many potential uses in training, beyond functioning as simple sparring partners. The “debriefing” capability he is adding to existing programs is one aspect of this potential. “If a pilot trainee can fly against a virtual pilot and then ask it questions afterwards, the trainee can learn more about what are the right and wrong things for a pilot to do,” he said.

Beyond debriefing, Johnson is trying to create a “pedagogical agent,” a programmed professor capable of training humans in a virtual world.

A system he is developing with ISI specialist Jeff Rickel is aimed at training operators of shipboard propulsion systems. Trainees will operate on a virtual mockup of a propulsion system, created using computer graphics and viewed with head-mounted computer displays. The silicon teachers will actually watch students operate the equipment, notice when they are having difficulty, show them how to correct problems and explain their recommendations.

In the meantime, the agent fighter pilots will continue to be tested in war games that link artificial-intelligence laboratories with military computers around the world. Rosenbloom and his team members say they look forward to a full schedule next year, with a major test scheduled for fall of 1997.

It’s not yet clear whether human pilots will again participate in that test, but if they do, they may get a taste of Kasparov’s dismay when Deep Blue achieved the unthinkable, scoring a single victory off the chess master. In light of recent improvements in Soar technology, such an upset is a real possibility.

“But don’t worry,” said Rosenbloom. “We still know how to turn them off.”u0000

Computers learn to match wits with humans

Top stories on USC News