Rich computer simulations or quantitative models can enable an agent to realistically predict real-world behavior with precision and performance that is difficult to emulate in logical formalisms. Unfortunately, such simulations lack the deductive flexibility of techniques such as formal logics and so do not find natural application in the deductive machinery of commonsense or general purpose reasoning systems.

This dilemma can, however, be resolved via a hybrid architecture that combines tableaux-based reasoning with a framework for generic simulation based on the concept of ‘molecular’ models. Benjamin Johnston in a presentation on his paper with Mary-Anne Williams delivered at the AGI-08 Conference, argues that this combination exploits the complementary strengths of logic and simulation, allowing an agent to build and reason with automatically constructed simulations in a problem-sensitive manner.

The following transcript of Benjamin Johnston’s AGI-08 presentation on the paper “Comirit: Commonsense Reasoning by Integrating Simulation and Logic” has not been approved by the speaker. Video is also available.

Comirit: Commonsense Reasoning by Integrating Simulation and Logic

I’m Ben, and my supervisor Mary-Anne, we are based at the University of Technology in Sydney. It is pronounced “com-eer-it.” I want to use this talk not to go into the technical details of my paper, but really just to relate the high-level reasoning behind my work. I’m going to start off by talking about what it is I am trying to do. My long-term goal is really to build, not intelligent agents, but to build intelligent middleware an infrastructure, build a platform upon which intelligent systems can be built in weeks or months as opposed to years or decades.

The kind of intelligence I am focusing on at first is how to interact with the world, how to navigate, how to deal with a novel object, as opposed to more factual or other kinds of intelligence. In the long-term, I want to look at using this intuition about the real world and apply this in purely symbolic systems, so that the symbols have a deeper meaning.

What inspired me to go down this path was actually a paper in the logical commonsense world, where the author tried to describe using logic what happens when an egg is cracked. It is a simple problem, but the paper was this long, complex paper with sixty axioms that really are quite complex. This one here says, “If the container contains an object at a given time, and that container is facing downwards at that time, and the object in the container at that time is a liquid, or the objects are shapes which are smaller than the shape of the lid of the container…” to me this is ridiculous. It’s not natural, and I really wanted to find a better way.

I think we as computer scientists understand computers really well. We have all the parts we need. The trick is really in bringing them together in the right ways, and reinterpreting old techniques and putting them in new applications.

This brings me to Comirit, which is our project. My very first step is integrating two simple techniques. The first is graph-based simulation, which provides for iconic, visual, imaginative forms of reasoning. Tableaux-based logical deduction complements this iconic representation with more abstract and symbolic reasoning–it allows for reasoning backwards. The two techniques are intended to complement each other. What I am going to for the rest of this talk is briefly introduce each, and I will finish off by explaining how to put them together. The full details are in my paper.

I chose graph-based simulation because graphs are very general. You can use graphs to represent really any structure from 3D objects, to social networks, to document structures. On these graphs I apply annotations and use those annotations to simulate a wide variety of problems.

This egg example that inspired me to go down the path–we could build a simulation of an egg using a graph by having nodes that represent (sort of molecules), connect them with edges (the bonds), and then each node and edge has properties. They have x, y, z coordinates, they have local mass, they have local rigidity and strength.

We can use this graph representation to simulate what would happen over time. If we dropped the egg onto a table, it will fall, it will crack, and the goo on the inside will make the table wet. The advantage of this approach is that it is a very natural way of expressing it. Rather than these sixty rules that do not really say much and they are hard to encode, you have nine rather common sense rules. These are rules that are taken stright from a high school physics textbook. They’re not hard, and they are largely orthogonal. Gravity works on everything. You do not have to worry about the rigidity of a solid to apply gravity–it is just combined additively.

I think this is a more natural way of capturing a lot of real-world type of knowledge. It is a lot easier than expressing things in logic. There are things that are not very well expressed in graphical simulations, but work fantastic in logic. We have seen many, many successes of logic in the past, though it has not given us true intelligence, yet. It allows us to do the high-level symbolic reasoning, the abstract reasoning. We can use logic to infer possible causes and then simulate to see whether causes match the reality.

To do this logical deduction, I have chosen a method of analytic tableaux. You’ll see why in a moment. The advantage of an analytic tableaux is that it is a very efficient form of reasoning on typical problems. Its worst case complexity, depending on the logic, may not be fantastic but its average case complexity is pretty good on practical problems. It has achieved great success on the semantic web on massive databases. The basic way that this method works, it uses simple rules and operates on a syntactic structural formula. It does syntactic manipulation on the formula to divide the space of worlds. It analyzes the space of all possible worlds to try and find the worlds that satisfy a formula.

There is a fairly technical explanation for it, but the way I intuitively see it is we start off with the formula and we set up this space of all possible worlds. That is the blue box up here. You have this formula, which is asking whether it is possible to move a cup of coffee without making a mess. We have a space of all possible worlds and we want to see if this formula can be satisfied. The method of analytic tableaux breaks down this formula and uses it to guide the separation of this space into subspaces. As it analyzes the formula, breaking it down into its components, we are also narrowing down the space of possibilities until we cannot go any further with syntax alone.

This brings me to a key insight. We have two methods here. The method of analytic tableaux, which really is a search over space of possible worlds, searches over space of scenarios. We have simulation, which takes these possible worlds, takes these scenarios, and basically deduces consequences and predicts the outcomes of these worlds.

These two methods are talking about the same thing. They are talking about these possible worlds. That is the insight which I think leads to a more natural integration between these two methods.

Reverting back to our worlds model, we have those two branches left and we can now load into those branches 3D simulations of our cup of coffee. We can see whether one cup of coffee, moving slowly, was able to successfully move without making a mess. The other cup of coffee, under the faster move, ended up making a mess.

That is the basic idea and I go through all the details in my paper. I think the real elegance of this approach is that it leads to a really nice implementation. The trick to making this work well is to make it absolutely simple, and you can do that by putting absolutely everything in the tableaux–not just the logical formulas, the logical terms in a traditional tableaux, but the simulations themselves, the data structures of the simulation to the tableaux. Even go so far as meta-programming: I load the tableaux algorithm itself into the tableaux. This means that the tableaux can use different logics in different parts of its reasoning. It can use different heuristics, it can use different rules in different parts of the problem.

That is my paper in ten minutes. In the future I am looking towards more general forms of intelligence. At the moment I am looking at integrating other forms of logic into this. I have been trying to learn these 3D models, how the system automatically acquires these 3D models and acquire an understanding of the parameters that drive these models just from experience. Finally, I have been working with a cognitive scientist, trying to rap this up and draw insight from biologically inspired cognitive architectures to make this richer. Thank you.