15 Individuals and Relations

15.1 Exploiting Relational Structure

One of the main lessons of AI is that successful agents exploit the structure of the world. Previous chapters showed how states can be represented, learned, and reasoned with, in terms of features. Representing domains using features can be much more compact than representing states explicitly, and algorithms that exploit this compactness can be much more efficient. There is, however, usually much more structure that can be exploited beyond features for representation and inference. In particular, this chapter considers reasoning in terms of individuals and relations:

  • •

    Individuals are things in the world, whether they are concrete individuals such as people and buildings, imaginary individuals such as unicorns and programs that can reliably pass the Turing test, processes such as reading a book or going on a holiday, or abstract concepts such as money, a course (such as the course MCS-224 at a particular university), an offering of a course (such as the 2026 Spring offering of MCS-224) and times. Individuals are also called entities, objects, or things.

  • •

    Relations specify what is true about these individuals. This is meant to be as general as possible and includes unary relations that are true or false of single individuals, propositions, which are true or false independently of any individuals, as well as relationships among multiple individuals.

Example 15.1.

In the representation of the electrical domain in Example 5.8, the propositions u⁢p⁢_⁢s2, u⁢p⁢_⁢s3, and o⁢k⁢_⁢s2 have no internal structure. There is no notion that the propositions u⁢p⁢_⁢s2 and u⁢p⁢_⁢s3 are about the same relation, but with different individuals, or that u⁢p⁢_⁢s2 and o⁢k⁢_⁢s2 are about the same switch. There is no notion of individuals and relations.

An alternative is to represent explicitly the individual switches s1, s2, s3, and the properties u⁢p and o⁢k. Using this representation, “switch s2 is up” is represented as u⁢p⁢(s2). By knowing what u⁢p and s1 represent, you do not require a separate definition of u⁢p⁢(s1). A binary relation, like c⁢o⁢n⁢n⁢e⁢c⁢t⁢e⁢d⁢_⁢t⁢o, can be used to relate two individuals, such as c⁢o⁢n⁢n⁢e⁢c⁢t⁢e⁢d⁢_⁢t⁢o⁢(w1,s1).

Modeling in terms of individuals and relations has a number of advantages over just using features:

  • •

    It is often the natural representation. Often features are properties of individuals, and this internal structure is lost in converting to features.

  • •

    An agent may have to model a domain without knowing what the individuals are, or how many there will be, and, thus, without knowing what the features are. When interacting with the environment, the agent can construct the features when it finds out which individuals are in the particular environment.

  • •

    An agent can do some reasoning without caring about the particular individuals. For example, it may be able to derive that something holds for all individuals without identifying any individuals. An agent may be able to derive that some individual exists that has some properties, without caring about other individuals. There may be some queries an agent can answer for which it does not have to distinguish the individuals. For example, a cleaning robot might be able to infer that someone or something created a mess, without knowing which entity did.

  • •

    The existence of individuals could depend on actions or could be uncertain. For example, in planning in a manufacturing context, whether there is a working component may depend on many other subcomponents working and being put together correctly; some of these may depend on the agent’s actions, and some may not be under the agent’s control. Thus, an agent may have to act without knowing what features there are or what features there will be.

  • •

    Often there are infinitely many individuals an agent is reasoning about, and so infinitely many features. For example, if the individuals are sentences, the agent may only have to reason about a very limited set of sentences (e.g., those that could be meant by a person speaking, or those that may be sensible to generate), even though there may be infinitely many possible sentences, and so infinitely many features.