Predicting what the other team will do, by pretending to be them

My PhD viva is done: passed, with minor corrections. It all goes back to my undergraduate days, when Yiannis Demiris’s lectures got me interested in robotics. In October 2006 I started a PhD in his research group, BioART (the Biologically inspired Autonomous Robots Team), and it was there that we came up with the idea for this thesis. Four years on, it’s a strange feeling to have nothing hanging over me.

So it seems a good moment to write down what the thesis is actually about, ideally in fewer than 154 pages. The full title is Operationalising the Simulation Theory for Intent Prediction in a Multi-Agent Adversarial Environment. That’s a mouthful even by thesis standards. In plain English it asks this: if you’re watching the other team move around, can you work out what they’re up to, and do it early enough to be useful?

The idea: simulate, don’t classify

There are broadly two ways to work out what someone intends. One is to learn patterns: “units moving like this usually means an attack”. The other comes from a theory of how people read each other’s minds, called simulation theory. The idea is that you understand someone by putting yourself in their shoes. You run their situation through your own decision-making, and see which of your plans would have made you do what they’re doing.

BioART already had an architecture built on that idea. It’s called HAMMER (Hierarchical Attentive Multiple Models for Execution and Recognition), and it had worked well for a single robot recognising what a single person was doing. It pairs up:

• inverse models: “if my goal were X, here’s what I’d do”;
• forward models: “if I did that, here’s what would happen next”.

You run lots of these pairs in parallel, one per hypothesis. Every so often you check each prediction against what actually happened, and give each hypothesis a confidence score. Whichever hypothesis keeps predicting the world best wins.

My job was to make that work with teams. That’s a lot harder. A team can split up, change formation and chase several goals at once, usually just as you think you’ve worked them out.

Here’s a toy version in 2D. It isn’t the thesis code, but the loop is the same. Every second it forward-simulates “they’re heading for the bridge / the town / the ridge” from the red team’s current position. A second later it marks each prediction against where they actually went. Click an objective to make the red team change their minds, and see how long it takes to catch on.

Building a world to test it in

You can’t test intent prediction without something to predict. So a big chunk of the PhD went into building a real-time strategy game, which I called hammerQt:

• Engine: Delta3D, which glues Open Scene Graph (graphics) to the Open Dynamics Engine (physics).
• Interface: Qt for the UI.
• Units: tanks and soldiers driving around a large outdoor terrain. The terrain is generated from heightmaps, and PNG masks mark out the roads, forests and towns.
• Players: human commanders on each team pick goals for their units over the network.

The physics mattered, because the forward models are the simulator. To test a hypothesis, the system:

1. serialises the state of every relevant unit;
2. sends it to a headless copy of the simulator;
3. runs it faster than real time with the graphics turned off;
4. sends the predicted positions back.

Each copy is single-threaded, so the server launches them over SSH across a list of machines, and queues hypotheses until one is free. It’s basically a small render farm where nothing gets rendered.

A lot of this was hard in thoroughly unglamorous ways. The thesis acknowledgements mention “the tanks are inexplicably falling through the ground!” and a crash deep inside ODE’s quickworldstep. Both were real, and neither was fun at the time. Running the simulation faster than real time is a balancing act too. Push it too far and the physics timestep gets so big that the tanks start doing things tanks really shouldn’t. For my scenarios the limit was about 4x.

The HAMMER simulator in action: an RTS-style engagement, with the system generating intent hypotheses across the 2D tactical map and the 3D view. At the end, line graphs compare how well it predicts targets with threat-based attention against round-robin.

Making it affordable

The first version worked. In the experiments it correctly spotted the manoeuvres and formations a human-controlled team was using, and it noticed when they switched. It was also greedy: only about four hypotheses fitted into each prediction interval. So the last two chapters are about getting away with doing less.

• Fewer hypotheses. Instead of simulating every possible target, I generate lots of candidate paths, cluster the similar ones with spectral clustering, and only simulate one from each cluster. Of the approaches I tried, this gave the best accuracy for the least computing.
• Only look where it matters. In real life you can’t see the whole battlefield at once. So I added partial observability and a threat-based attention mechanism, which points the observers at the scariest areas first. You spot changes slightly later, in exchange for a big saving in computing. It beat a simple round-robin schedule comfortably.

Papers

• Multi-Agent Behaviour Segmentation via Spectral Clustering, AAAI-07 workshop on Plan, Activity and Intent Recognition (with Bálint Takács and Yiannis Demiris)
• Predicting the movements of robot teams using generative models, Distributed Autonomous Robotic Systems 8 (Springer, 2009)
• Using a Cognitive Architecture for Opponent Target Prediction, AI & Games symposium at AISB 2010
• Partial Observability During Predictions of the Opponent’s Movements in an RTS Game, IEEE CIG 2010

The thesis PDF, the simulator source and the clustering library are all on the thesis page, for anyone who fancies building their own tank-based mind reader.