Future Current

Benjamin Johnston and Martin Magnusson at the AGI-08 post-conference workshop

Inhabiting the complex and dynamic environments of modern computer games with autonomous agents capable of intelligent timely behavior is a significant research challenge. Martin Magnusson illustrates this point speaking on the topic of his paper with Patrick Doherty using their own attempts to build a practical agent architecture on a logicist foundation.

The following transcript of Martin Magnusson’s AGI-08 presentation on the paper “Temporal Action Logic for Question Answering in an Adventure Game” has been corrected and approved by the speaker. Video is also available.

Temporal Action Logic for Question Answering in an Adventure Game

Hi, I am Martin Magnusson. I am a PhD student at Linköping University, Sweden, where I work at the AI department with my adviser Patrick Doherty. This talk is about a paper called “Temporal Action Logic for Question Answering in an Adventure Game”. I’ll concentrate on what I think is the message of the paper and then have the obligatory video demonstration .

The paper is about applying logic in computer games. I believe that logic will be fundamentally important in building an AGI. You might question why I believe that? Well, the key aspect of an AGI is that it can be applied to any (intellectual) problem. Logic has a number of features that makes it seem suitable. For example it has at least these three features I have listed in the slide.

First, if we express knowledge in logical form, then we can apply theorem proving. Theorem proving is an entirely general algorithm that can be applied to any problem. Secondly, logic is domain independent, so we can try to express any type of knowledge in logic. Thirdly, we want the AGI to learn from books, for example, using natural language, and you can potentially translate between natural language and logic.

If this sounds like logic is the solution to all of our problems, and it sounds a little bit too easy to be true, you are probably right. If we try to put this vision into practice, we will find that there are some stumbling blocks.

First, when we are considering theorem proving we think of a type of black box algorithm where we put things in and hope that the solution will pop out. That does not really work. I know that it does not really work because that’s the first thing I tried. I formalized common sense reasoning problems and put them in an off-the-shelf theorem prover. The performance was simply not acceptable.

What I do now is that I use a natural deduction theorem prover, which makes it very easy to add special purpose rules. For example, I use temporal action logic, where time is the integers. Then I integrate constraint solvers, and this makes reasoning about time reasonably efficient. But there’s still a general purpose algorithm, so whenever the special purpose rules fail, you can always fall back on the more general theorem proving algorithms.

Given that logic is universally applicable, we might be able to formalize a giant knowledge base with all the things an AGI would need to know. But doing so will probably be extremely difficult and take decades. What do we do until then, with only a half finished knowledge base? What is a half finished knowledge base useful for?

Well, I believe that computer games provide one application where you can actually use a knowledge base that is not fully developed but still have it do useful things. I believe that, because there are so many different kinds of games. Some of them are extremely simple, where even today’s technologies would be enough to do useful things. Others are these giant virtual worlds where we would need a lot of common sense reasoning to do anything useful.

Finally, the translation into natural language, while it is possible in principle, no one has yet been able to create a grammar with sufficient coverage. Here I think there is a way to maybe circumvent this stumbling block. What I have in my application is an interactive parser. It works somewhat like this T9 system that you might have in your cellphones, but instead of suggesting word completions it suggests sentence completions. What happens is that it guides the input into a sentence it is guaranteed to parse.

Let’s look at a simple prototype game demonstration that makes use of these very general technologies in quite a limited way. The guy running around in the video is a human-controlled avatar and he meets up with a virtual game character. At the bottom of the screen you see the interactive parser guiding the user’s input sentences. It uses a really simple bi-directional grammar, which makes it possible to use the same grammar both for parsing and generating the replies to the questions. The questions are answered using the natural deduction theorem prover.

As we explore this virtual environment, we find this other game character. This guy is actually proactive and he takes the initiative in the dialog by asking for the owner of the axe and his location. We happen to know the answer to his question because we just visited the Keypr character, we know he owns the axe, and we also know where he is. The game character can take this new information that we provided him and use it to carry out this plan. His goal is to obtain some lumber. Part of his plan was to buy an axe. As we see, this plan involves several agents. As a demonstration of the generality of the method, the same theorem prover was used both for generating the plan and for answering the questions.

Here the question being asked requires memory of past events. The game character hasn’t yet satisfied his goal of getting lumber, so he needs to carry on with his plan, which involves chopping down a tree. He knows the effects of actions and can reason with those, using the theorem prover to come up with complex plans.

Now let us try to buy the lumber from the game character. We can do that by issuing commands, not just asking questions. Our own avatar will form a very simple plan to carry out this command. We are free to do anything we want in this environment, but let’s go back to the first game character, try to sell the lumber, and maybe make some money in the process. This character charges 6 gold instead of 3, which our avatar detects as an inconsistency. But it does not matter since, if we sell it to him, we will get the 6 gold and make money in the process. Perhaps by doing this we have solved a simple game puzzle.

To conclude, while logic has the features required for AGI, there are stumbling blocks in applying it. What I’m saying here is not that we have solved all these stumbling blocks. What we’ve done is to figure out a couple of techniques to get around the stumbling blocks, and we have chosen this computer games application as one possible avenue of incremental progress towards a logical AGI system. Thank you.

This entry was posted on Tuesday, June 24th, 2008 at 12:19 am and is filed under AGIRI, Artificial Intelligence, Games. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.