John David Funge
SDxWiki

John David Funge is the author of "AI for Games and Animation" (see Books).

(Following commentary by DWM.)

Funge's work is about putting applying current AI theory to practical applications in computer graphics, particularly games. His focus is on the cognitive modeling subfield of AI, because this sort of modeling works at a higher level of abstraction than, e.g., neural networks, making it easier to formulate and understand programs, and thus making them easier to maintain (debug and extend). However, the mathematical logic notation is dense, and unfamiliar to most readers. It seems to derive mainly from logic programming theory.

His Cognitive Modelling Language (CML) is based on the mathematical logic notation. The compiler generates Prolog as output. I have only a very bare understanding of the precepts of Prolog, but I'd have to say that this approach seems to make sense. This has gotten me interested enough to start a new page on Logic Programming, where I can gather some resources on this topic.

An attempt to summarize main concepts "AI for Games and Animation"

The concepts are not necessarily discussed in the same order here as in the book, and I'm ignoring some stuff that I didn't think was particularly relevant to cognitive modelling per se. (Some of it was provided as background material, I think.)

The author's focus is on characters interacting in real time with a physical model of the environment, but the concepts can be adapted more broadly.

Funge is looking for emergent complex behavior from relatively simple cognitive models. To keep the cognitive model simple enough to be practical (in terms of execution time, and complexity to write and maintain), actions should not be controlled in detail by the cognitive model. For instance, "go to x,y", is a primitive operation from this model's point of view, even though it may be a fairly complex action in itself, involving collision avoidance, etc. A scripting system can be useful for specifying low level actions, provided it executes fast enough.

For similar reasons, the cognitive model works with a simplified view of the world, rather than with full access to the world model. This also has the effect of making characters behave more believably. Funge gives a great example: Imagine a character that pushes over a tall stack of heavy blocks. With perfect knowledge of the world model, the character's AI could precompute where every block is going to fall, rush to a nearby safe spot, and calmly watch all the blocks fall around it without getting a single bruise. Definitely not realistic!

A large part of the book focuses on the modelling of domain knowledge. Mathematical logic is used for precision; this is often dense and unfamiliar, so it take a while to unravel it. (Sometimes it's worthwhile.) Specifically, Funge borrows from prior work on "situation calculus", a means of describing changing worlds in a mathematical logic.

A "situation" is a snapshot of the state of the world. The notation s' = do(a,s) means that performing action a when in situation s leads to a new situation s' .

Any property of the world that changes over time is called a fluent. Although Funge's notation doesn't quite put it this way, I think you can consider a situation as being defined by the values of all the fluents (including a time fluent?). The notation is kind of backwards from this, though -- it treats fluents as functions on situations, so that temperature(s) would represent, for example, the value of the temperature in situation s. For a boolean-valued (0 or 1) fluent gunLoaded(s), the shorthand GunLoaded(s) is equivalent to the assertion gunLoaded(s) == 1.

Precondition axioms are statements of what actions are possible in given situation. The function "Poss" is used to express these. Examples from the book: ;Poss(Load,s): The gun can always be loaded. ;Poss(aim,s): The gun can always be aimed. (The target is implied in the book's example.) ;Poss(shoot,s) => Loaded(s): The arrow means "implies", in the logical sense. The gun can only be shot if it's loaded.

We use a "closed-world" assumption. Absent additional axioms, having the gun loaded is the only precondition for shooting it.

Effect axioms make statements about how the world is expected to change when an action is taken: ;Loaded(do(load,s)): The gun is loaded after loading it. Seems trivial, but it's important for the AI to know this if it's trying to plan a sequence of actions! The notation is actually pretty logical. do(load,s) returns a new situation s' . Loaded(s') asserts that the gun is loaded in state s' . ;Aimed(do(aim,s)): The gun is aimed after aiming it. ;Poss(shoot,s) && Aimed(s) => !Alive(do(shoot,s)): If the gun is aimed at the target and it can be shot then he is dead after shooting. (I adapted the notation using C operators, I don't have fancy symbols available here!)

Now, under the "closed-world" assumption, we work on the premise that our rules describe everything that can happen in the world. That's obviously not true, but planning becomes intractable otherwise. (This is an assumption that is worth challenging, someday!) This lets us replace the effect axioms with successor state axioms. This is where the logic notation starts to get really dense, so I'll spare you. It's not important anyway, since the successor state axioms can be derived from the effect axioms, but it is important to note the closed-world assumption.

Additional state constraints are used to reason about side-effects of actions. If you have the fluents nearBomb, and fire, an action detonate, and an effect axiom Fire(do(detonate,s)) (there is a fire after detonation), then you might have a state constraint that says Fire(s) && NearBomb(s) => ! Alive(s) (if you're near a fire, you're dead). Now if you detonate the bomb when you're next to it, you get the implicit side-effect of dying.

Sensing is an important topic. Sometimes, you don't know the value of a fluent, but you know that you can take an action to acquire the knowledge. When you don't know the value of a fluent, then you don't know what situation you're in; but you know all the possible situations that you might be in, based on the fluents that you do know. Sensing the value of an undetermined fluent reduces the set of possible situations that you might be in. (This is where one of the most impressive-sounding terms of the book appears: an "epistemic fluent" is a fluent whose value is the set of possible situations!)

Well, anyway, this goes on for a while with ever more complex logic equations. It doesn't take too many fluents before you get systems with lots and lots of possible situations, making practical computation difficult. The next interesting idea is the use of interval arithmetic to avoid the explosion of possibilities you get with real-valued fluents. This just means that, for example, instead of having a temperature in Kelvin as a fluent, you replace it with a fluent that takes on a smaller set of discrete values ranging from "wicked cold" to "liquifying heat". That also sits well with someone who has to write these rules, because it's how people tend to think about things. It also harmonizes well, I believe, with finite domain analysis, a type of computation for which the Mozart implementation of the Oz Language is particularly well suited. (Funge uses a custom language of his own design, which is based on Prolog. He has an implementation available on his Web site which 'compiles' to Prolog.)

More to come...