Logical Agents for Language and Action

In the following presentation you will see some concrete examples of logical reasoning in game scenarios involving planning, language understanding, and dealing with inconsistency. Then we will take a look at the middleware architecture that equips game characters with a reasoning engine to actually carry out the reasoning in practice.

Problem

The smarts in computer game non-player characters (NPCs) often work something like this - game developers tell NPCs what to do while NPCs just do what they have been told to do.

The problem with that is that NPCs don't do any thinking of their own. The developers have to use their intelligence to make up for the NPCs' lack of intelligence. They consider all the situations that the NPC might encounter and figure out what the NPC should do in each situation. That's a lot of work and the resulting behavior is inflexible since it doesn't apply to new situations.

Solution

In this presentation we will find out how logic-based artificial intelligence can provide a solution.

Logic can be used to express knowledge, e.g. about actions and their effects, in a way that isn't specific to one particular situation. A reasoning mechanism can then apply that knowledge to many different particular situations, e.g. to find actions that satisfy a specific goal.

This makes it possible for game developers to create more open-ended games with less work. Every piece of knowledge they enter can be reused in many different situations. And the NPCs' behavior becomes more flexible since they can adapt that knowledge to new situations.

Action

Imagine a large game world in an adventure or a role playing game. This world is inhabited by non-player characters that think and act by themselves. They have their own independent needs and goals that they proactively act to satisfy.

Suppose that NPCs get hungry as time passes. This particular NPC is currently perceiving hunger and adopts the goal of being not hungry. He needs to search for a plan to achieve this goal given his current situation. What this slide shows is a classic planning problem where an out of reach piece of food is at tree height while our character is down on the ground.

Logic for Action

We can formulate such planning problems in logic as deductive planning.

The NPC has knowledge about actions and their effects, expressed by the axioms in the blue boxes. He knows e.g. that you can move an object if you are at the same location and height as that object, and that if you do move it then it will end up in the new location. Similarly, you can take an object that is at the same location and height, after which you will be holding the object. Finally, if you are next to an object at ground level you can climb that object to reach higher.

The reasoning process starts with the NPCs goal of having the apple. It proceeds in a goal-directed fashion, adding the arrows that represent logical inferences between the axioms. The end result is the construction of a proof that some set of actions will achieve the goal. In this case these actions were to move the rock over to the apple, climb the rock, and finally take the apple.

Language

Next, suppose we allow people to explore this game world using avatars. When players meet the intelligent game characters they can interact with them through dialog. The traditional approach would be to script the entire dialog in advance, giving the player a few choices of what to say and writing the NPCs' responses to each possible question. But we are going to express some general knowledge of language in logic and have the NPCs apply that knowledge to whatever the player says. Instead of scripted dialog we will generate dialog on the fly.

E.g., a player meets our NPC and asks "Who are you?". At this point the only input available is a string of characters. How can the NPC reason with that?

Logic for Language Parsing

He will use general knowledge of English to parse the string into a logical formula. And, just as with actions, we can express that knowledge in logic as a definite clause grammar. This means that the NPC can use the same reasoning engine that he used for planning to understand natural language.

These boxes are axioms from the grammar, which relate strings of characters to logical forms. We see e.g. that the string "you" is associated with a logical constant you, and that a sentence starting with "who" asks for the name of someone.

Our NPC proves that the English sentence corresponds to a logical formula, and the arrows illustrate the inference he carried out. He is now free to continue the reasoning process and derive an answer to the logical representation of the question. However, the answer will also be a logical formula, while we would prefer the answer to be in English!

Logic for Language Generation

Fortunately, nothing in the definite clause grammar says that we have to start with a string and derive a logical form. We can just as well start with the logical form of the question's answer and derive the corresponding English response!

The reasoning involves a slightly different set of axioms, taken from the same grammar, but works in exactly the same way. After a couple of inference steps the NPC arrives at his English reply, "I am Smith".

Trust

Giving players more freedom in what they can do and say is associated with some risk. What if they, by accident or by intent, try to fool NPCs into believing things that are not true? This is particularly troublesome in classical logic where anything follows from contradiction. If NPCs believed a player's lie they might go "mad" and start to believe anything!

Logic for Trust

But NPCs don't have to believe everything the player tells them. Instead they have an axiom that expresses the policy - if someone tells me something, then if I trust that person I will believe what they told me.

By default our NPC will trust new people he meets, as long as there is no reason not to trust them. Suppose then that one player claims that Smith is holding an apple. Smith will at first believe this claim. However, when he sees that he is not holding anything, this results in an inconsistency. The inconsistency is a reason not to trust the player since it was the player's claim that led to the inconsistency. So Smith retracts the default assumption of trust, and the inconsistency as well. This mechanism successfully avoids "insanity" and ensures a consistent belief state.

Middleware

By now we have seen some examples of how logic can be used to enable intelligent behavior in a couple of computer game scenarios. But so far we have only been looking at theory. For this to be useful we need a concrete reasoning architecture with a practical implementation. Such as system would act as middleware between the logical theory and the game world.

This slide shows the Logical Agents architecture that is the "brain" of our NPCs. Percepts from the game world enters the brain, where the reasoning engine carries out "thinking", e.g. parsing language or planning actions. Scheduled actions are then executed in the game world, e.g. speaking a sentence or grabbing an apple.

Getting logic to work in a real time computer game setting, however, is not entirely trivial. Each part of this architecture is really designed to deal with a specific challenge that the logical approach faces.

Some Objections

Let us look in more detail at each component and how it deals with potential objections to the use of logic in games.

Progress in artificial intelligence has been slower than some optimistic predictions. But since logic has been part of AI since its beginnings we now have accumulated over 50 years of logic-based AI research (not counting, of course, the two thousand years of developments in logic before anyone had the idea to build an intelligent machine using logic). One of the most important inventions is nonmonotonic logic, like the Temporal Action Logic (TAL) that we use. Nonmonotonic logic can perform non-deductive reasoning such as jumping to conclusions or drawing abductive inferences. This meets the objection that thinking is not just deduction.

The reasoning is carried out by a pattern-directed inference system (PDIS). It stores the state of the proof search explicitly in the knowledge base. You can interrupt its reasoning at any time and later resume reasoning from the same point. This makes it possible to adapt the number of inference steps to fit the time constraints of a single game frame. You can also time share the reasoning between NPCs by running a few reasoning steps for each one. This meets the requirement that the system has to work in real time.

A related concern is the efficiency of the inference steps themselves. There are many ways to optimize theorem provers. One thing that the architecture currently does is to formulate certain reasoning problems as constraint satisfaction problems (CSP) and apply efficient reasoning algorithms. You could also plug in other efficient special purpose reasoning modules, e.g. a path finding algorithm. But probably the only way to convince you that logical reasoning in games is feasible is by asking you to go to www.logicagents.com and try the game prototype. While it is a very small demo, it shows that it is possible to use a theorem prover in a computer game without noticeable delays.

Finally, we saw earlier how game characters will have to deal with false information. An assumption-based truth maintenance system (ATMS) is a well-known algorithm for tracking dependencies between formulas in a knowledge base. Using an ATMS the NPCs know which formulas were derived from inconsistent information and are able to retract them. This mechanism meets the need for NPCs to robustly deal with inconsistency.

Conclusions

To summarize - most existing NPCs do only what they have been told. We try to improve upon this by applying some of the research in logic-based artificial intelligence, which has been going on for at least 50 years, to create NPCs that "think" for themselves.

This presentation illustrated how one and the same logic and reasoning engine can be applied to many different problems, such as goal-oriented action planning and natural language understanding. We also discussed the Logical Agents middleware architecture that implements a practical reasoning engine, and how it deals with some objections to the use of logic in games.

Finally, let us remind ourselves of what we hope to gain by adopting a logic-based approach. There are two main benefits. First, game developers can create more open-ended games with less work without having to specify the NPCs' reactions in every conceivable situation. Instead, the NPCs apply knowledge about the game world to figure out what to do by themselves. Second, this means that NPCs can figure out what to do in new situations, possibly even situations that were not even foreseen by the game developers. What new kinds of games could this ability make possible?