How PopBeast represents its world

Let's start then with the simple Eden of Figure 4.

Here, PopBeast is in a room which contains a key k and a door #. Suppose that I have told PopBeast to open the door. How does it work out what to do? To answer this question, you have to know how the command ``open the door'' is presented, and I'll get on to this later. I will start though by talking about how PopBeast represents the world - how it remembers where it is, and what objects are around it.

It does this in two main ways. The first is by maintaining a kind of internal image. In programming terms (if you know any - don't worry if not), this image is a two-dimensional array of characters which holds a copy of the picture above. Non-programmers can think of it as just a two-dimensional grid on which is drawn a map of the world. This is an analogue representation. PopBeast builds up the map by wandering around the world and superimposing successive retinal images; this is fairly straightforward, and I shan't say any more about it.

The second method is based on logic, and describes the world as a set of propositions. If you look at Figure 5 and compare it with the Eden in Figure 4, you should be able to work out what's going on.

square(me, [4,4])
square(key(1), [5,6])
square(door(2), [8,4])
square(hammer(3), [11,3])
square(rock(4), [14,6])
square(food(5), [16,11])

in(me, 49)
in(key(1), 49)
blocked(49, 50, door(2))
in(hammer(3), 50)
blocked(50, 51, rock(4))
in(food(5), 51)
joins(49, 50)
joins(50, 51)
joins(51, 49)

dir([1,0])

Figure Eden in propositions.

For those who don't know logic, a brief explanation of terminology is in order. A proposition is a statement about an object, or about a relation between objects. It is usually written as a name (the predicate) followed by some things in brackets. These things are the objects that the proposition is talking about, and are called its arguments. If there are more than one argument, they are separated by commas. Note that some authors use variants of this notation: Charniak and McDermott, for instance, use bracketed lists

( predicate argument-1 argument-2 )

Each predicate expresses some fact about an object or set of objects. In this figure, the first group of propositions is all of the form square( _, [_,_] ). These describe the contents of squares. The first argument denotes the object within a square, and the second argument, specifying the position of the square, is a pair of (X,Y) values. These are in PopBeast's internal co-ordinate system, for which (0,0) is at the bottom left.

The second group describe the way the world is divided into regions, and how they're connected. I have made PopBeast describe the world in terms of regions because of their importance in everyday life: they enable you to divide the world into pieces which can be reasoned about in isolation, in that influences are contained, i.e. an event happening in one region has very little effect on events in another.

In this group of propositions, the numbers 49,50,51 refer to the three different regions. The joins propositions tell you which regions are adjacent; the blocked propositions tell you whether you can pass between them, and if not, why not; the in propositions tell you which objects lie within a region.

The third group describes PopBeast's knowledge of the direction it is facing in, by specifying how it would move were it to go forward. At the moment, it would go one place right (X) and none north (Y), so the direction is [1,0].

It goes without saying that I am not asking you to learn the details of these notations, merely to appreciate the kind of information they carry. The propositional representation is very close to how the Prolog programming language works, and you will see it again in the AI practical.

So far, we've seen three different ways of describing where things are. We can use an analogue internal map, or we can use propositions. Within the propositions, we can either give exact co-ordinates, or we can describe the world in terms of regions and their contents. Why do we need all these? The answer is that different representations are good for different jobs. The analogue map is useful when you know the locations of two points, and you want to plot a detailed path between them. It is also easy to build up from retinal images, and serves as a starting point for the propositional representations. The propositions about squares and object co-ordinates are useful when deciding which points we want to plot a path between. The propositions about regions are useful in formulating high-level plans about moving from region to region. If we know that region 1 contains a hammer, and region 2 contains a rock, then to smash the rock in region 2, we have to go into region 1. At this level of detail, the exact co-ordinates of the hammer and rock don't matter, so we can speed up computation by ignoring them. At a lower level, we will eventually need to take them into account: then we descend through the other two representations.