Types of space

Up: Representing information spatially (AI)
Back: to main list of student notes

## Types of space

The four descriptions above are analogous to the caves one. The caves world and the neural net represent physical space: by analogy, the other three descriptions can be said to represent an abstract space, which contains points (the events, classes, or board states), and their connections (the causal links, taxonomic connection, or moves). When used in applications like game-playing, or other problem-solving, the space is often called a state space, because each point marks a different state of the problem.

If the caves world were part of this universe, each connection would have a length. We don't represent these lengths in our exercises, because all we are concerned with is the structure of the network. Using mathematical terminology, we can say that we are only interested in the topological properties - those to which distance is irrelevent - and not the metric properties - those concerned with distance. Like the people who make London Underground maps, we ignore distance.

In some types of space, we don't just ignore distance; it has no meaning in the first place. You can see that this is true of the classification example, for instance; it makes no sense to say that one of the `includes` is longer than another.

```includes( dicotelydon, crucifer ).
includes( composite, daisy ).```
So watch out when you use Prolog to represent such structures in the way that I have done. If your predicates don't say anything about distance, is it because it has no meaning, or because you have ignored it? The same can be asked of other properties, of course. If your program doesn't mention some property of a situation, is it because the property doesn't exist, or because you have ignored it?

The caves world and these four examples differ in other ways. The caves world and economic model are potentially cyclic or looped, because one point can be linked through a chain of paths or causes back to itself. The classification and noughts-and-crosses are acyclic or unlooped. We can also say that they are tree-structured, because there is a natural way to draw them as a tree. When writing Prolog programs, watch out for cyclic spaces: you will need to use special techniques to write route-finders and other predicates, otherwise they may get into an infinite loop.

In the economic model, classification, neural net, and noughts-and-crosses, the links are directed: one end is somehow different from the other. To traverse a causal link backwards is not the same as following it forwards. The caves world is not directed. If you are writing a predicate that describes a directed space, then take care that you get its arguments the right way round:

`includes( dicotelydon, crucifer ).`
does not mean the same as
`includes( crucifer, dicotelydon ).`

Finally, in the classification and noughts-and-crosses, the points themselves can be ordered: it is natural to say of one class of animals that it includes another; it is natural to say of one state of the noughts-and-crosses game that it is later in the game than another. There is no analogue of this with the other examples. In general, spaces which are both acyclic and directed can be ordered in this way. Intuitively, there is one overriding direction, and once you've followed it, you can't get back.

You will not be expected to remember these terms in the rest of the course. The point of this section, apart from trying to make you visualise abstract problems, and to show how they can be represented by Prolog, was to give a taste of the considerations that A.I. people face when representing knowledge. A rich vocabulary has been developed for describing information structures; the examples above are but a small part of it.