How does the hit film Memento, directed by Chris Nolan and released in 2000, relate to artificial intelligence and planning? Surprisingly, understanding the mindset of the main character, played by Guy Pearce, can help you make the most of planners. (It’s an amazing film also! See Amazon U.S., U.K.)
In the games industry in particular, planners have a reputation for being hard to debug. Even once you have your core algorithm fully tested, it’s often time-consuming to figure out exactly how new situations cause the planner to generate a particular solution.
Similarly, the protagonist in Memento has lost the ability to create short term memories since his wife was killed. In effect, he has to rethink everything from scratch every few minutes. Can you see how this quickly becomes a problem?
What is Temporal Coherence?
In this context, temporal coherence is the idea that very few things will change from one moment to another. In a world that respects the laws of physics, this is often the case as objects can’t move that fast. Changes happen incrementally, and life on earth has evolved to be able to deal with this. You don’t have to process the large quantities of information in the world; you just process the changes.
Normally, humans don’t have to rethink everything from scratch every few seconds. Their decisions from one moment to another are also likely to be temporally coherent. This has two benefits:
It’s much easier to make decisions and generally reason in a logical fashion.
It’s much easier for someone watching to understand the reasoning behind particular choices.
The guy in Memento, however, has no contextual memory to store the decisions he’s already made. So he has to “replan” completely every few minutes based on his high-level goals, which he keeps as Polaroids and tattoos on his body. Not only does this make it much harder for him to behave intelligently, but it also takes much more effort to follow what he’s trying to do. (The film plays with this idea brilliantly.)
Photo 1: Having to rethink everything from one minute to another.
How Does This Affect Planners?
The problem is that planning in games is typically done Memento-style. More often than not, the development process for a planner in a virtual actor is structured as follows:
Implement a STRIPS (Stanford Research Institute Problem Solver) or HTN (Hierarchical Task Network) planner.
On a regular basis (around 5Hz is common), run the planner from scratch with the most recent information from the world.
If the new master plan is different than the old plan, then execute it from now on as it must be a better solution.
This approach is typical because writing a planner that can replan to deal with dynamic changes is not trivial, and setting up the whole AI logic to monitor and figure out what changes are relevant takes a lot of work and experience.
However, this approach makes it much harder to debug the actual behaviors, because there’s no temporal coherence. You have to step through the whole decision making process to figure out what changed. No matter how good the tools are, you have to process all the information of the world when debugging the plan rather than monitoring incremental changes.
Photo 2: A scene from Memento with Carrie-Anne Moss.
How to Fix This!
What’s interesting to note is that more reactive forms of AI, such as finite state machines (FSM) don’t suffer from these problems because they operate in control & monitoring mode by default — always checking for changes as failures and successes of the low-level AI actions. Effectively, in this case, you have the advantage of temporal coherence from one second to another in the AI.
Planners in contrast operate primarily in a separate decision-making mode, which means they’re disconnected from the real world by a set of logic symbols. As such, they’re not as well equipped to deal with dynamic changes and adjust the previous plan to the current situation.
In practice, if you don’t want to revert back to plan old FSM, you need to find hybrids systems for both decision-making and control — in particular capable of localized replanning. You have two choices:
The more academic solution would be to use a full planner, and extend its dependency checking abilities to be able to modify the current plan in case of changes in the world.
Game developers seem to be using behavior trees more and more these days, particularly because they use a form of greedy planning that’s simple and adapts plans locally very effectively.
If you’re interested in this topic, then stay tuned to AiGameDev.com for more information from both the theoretical and practical perspectives. Among other things, over the next few days, you’ll be hearing more from the talk at the GDC in Lyon about behavior trees.
Photo 3: Have I been here before?
