next up previous contents
Next: Geometric Objects and Relations Up: PARTIAL FORMALIZATIONS AND THE Previous: The Problem of Formalization

Objects in Space in the Lemming World

Space in the lemming world is two dimensional. Nevertheless, an epistemologically adequate representation of space and objects for the Lemmings world requires features that go beyond what has been treated in the AI literature.

The screen in the Lemmings world is a pixel map. Like all modern computer games it uses colors, but the literature says Lemmings is playable on a gray scale display. We suppose this pixel map is accessible to a program that plays the game. To play the game it also needs the ability to imitate moving and depressing the mouse. There are keyboard shortcuts for some of the mouse actions, but we ignore them, because we are not trying to formalize human speed of action.

The problem for AI is that a human player does not decide what to do operating directly from the pixel map. Instead the human considers the screen as divided into regions, some of which are chambers consisting of empty space that can contain lemmings and possibly other objects and some of which are solid material. Some of the solid material can be turned into space by digging. Separated regions are sometimes combined when lemmings build bridges.

Human players do not convert the picture into an internal form from which all decisions are made without further reference to the picture. Information from the picture is put into mental forms that are not well understood physiologically or psychologically, and decisions about what to do involve repeated reference to the picture. In particular, one often looks at the details of particular areas of the scene or puts newly relevant global features into the mental model. On the other hand, important facts about the picture can be internalized well enough so that I player can get a new idea about how to win while out of sight of the game.

We claim that these aspects of the human way of handling visual information are not just peculiarities of humans. Their main aspects are features of what we have called the common sense informatic situation [McCarthy, 1989]. Computer programs operating in the real world, e.g. controlling mobile robots, also face the common sense informatic situation. This is characterized by incomplete information about the situation itself and incomplete information about the laws that determine the effects of actions.

Therefore, we plan that a Lemmings program will parse the scene into a collection of regions and relations among them. The initial parsing will be later extendable by further reference to the pixel map. Like the human the program will use the scene as its own most comprehensive model, although not always its most intelligible or useful model.

The parsing therefore has two unusual aspects.

  1. The parsing is not intended to be conclusive. The parser may be asked to get more detail about something it returned previously.
  2. The parser looks for common simple regions which it may have to elaborate later rather than having a universally applicable scheme for parsing anything.
  3. The parser gives names to features it finds and generates sentences characterizing them. These sentences are later used by reasoning programs that decide what to do.

    The simplest kind of region may be called a chamber. The simplest kind of chamber has an essentially horizontal floor and walls at each end that reflect walkers.gif

In section 8, page gif, we will discuss actions and events using situation calculus. S0 stands for the situation when a particular game called Game0 starts. Game0 is a simplification of the first game in Lemmings Jr. There is only one lemming. See figure [].

A simple chamber will be rectangular on the screen with walls at both ends. We make tex2html_wrap652 a simple chamber in tex2html_wrap653 and can rely on persistence to keep it a simple chamber in tex2html_wrap654 and beyond. This would be used in planning to solve Game0. Alternatively, if we are actually playing Game0, we can observe that tex2html_wrap652 is a simple chamber in tex2html_wrap654. This requires a mechanism for associating names with features of the picture and with situations depicted on the screen. We haven't decided how to do this yet.

Consider chambers which confine lemmings until something is done about it. They are bounded by simple closed curves, but that high level of generality isn't the common sense way of thinking about them. One could suppose that chambers in the lemming world are a subclass of the interiors of simple closed curves and try to formalize a suitable subclass. This is a bad idea, because we haven't seen all the chambers Psygnosis Ltd. has chosen to use, and they are likely to invent new ones with each new lemming variant they market. Their artists draw the chambers and the regions that surround them according to the requirements of the game designers and their artistic taste. These drawings are then digitized. No human player can represent a digitized screen pixel by pixel, and our formalism can't do this either.

Instead we start with simple figures and elaborate them. The simple chamber is one of these starts. A program that reasoned about the game would observe the screen of Game0 and recognize the upper chamber as a simple chamber and give it a name. In Game0, the floor of tex2html_wrap652 is not entirely even, but these surface rills make no difference. It doesn't matter where tex2html_wrap658 digs its hole. In other lemming games it does make a difference. For example, it might have been necessary in Game0 to dig in a low place in order that the lemmings should not fall too far.

We propose to handle unevenness by allowing additional statements about chambers that have been identified as simple chambers. Complete descriptions of surfaces are not required, but relevant observations may be expressed. Perhaps this is a form of belief revision, e.g. the player formerly believed the chamber was simple and has changed hsi mind; some of the considerations advanced in the study of belief revision might then apply. Another way of handling this idea is to say that c0 is a certain kind of simple chamber and express the unevenness in describing what kind.

We also will handle the chamber with the digger's hole by elaborating the simple chamber description. This will be belief update rather than belief revision.

We can implement the above using a notion of chamber type, or more generally, type of lemming region. tex2html_wrap659 would be the type that is instantiated by tex2html_wrap652. tex2html_wrap661 is is instantiated by tex2html_wrap662. (We are not committed to this particular notation for elaborating simple figures.) We need types in the formalism and not just individual regions, because we need to make new types by elaborating simpler ones, e.g. we make a chamber with the lemming sink at one end by elaborating simple chambers.

next up previous contents
Next: Geometric Objects and Relations Up: PARTIAL FORMALIZATIONS AND THE Previous: The Problem of Formalization

John McCarthy
Mon Mar 2 16:21:50 PDT 1998