Autonomous Concept Formation

1 Introduction

The ability to communicate with others is a manifesta­ tion of our intelligence. An understanding of commu­ nication therefore contributes to the goals of artificial intelligence. A requirement for higher forms of commu­ nication, such as human language, is the development of concepts that are to be communicated. In this paper, a model is proposed that describes the formation of a particular type of concepts.

A situation concept is a part of the state of an environ­ ~ent that determines how the environment will present 1ts~lf to a certain agent in response to (possibly absent) actwns of that agent. Therefore, a situation concept is an agent specific aspect of the complete state of the environment. In many environments, the state of an en­ vironment can not be completely determined from the current sensor inputs. Thus, knowledge about the in­ teraction history with the environment yields extra in­ formation about the current state. Situation concepts can be formed by agents by observing patterns in the sequence of inputs from the environment, actions of the agent, and subsequent evaluative feedback. They allow an age~t to predict some aspect of the future, e.g. the evaluative feedback that will follow a certain action or the next input from the environment given the actio~.

An important characteristic of situation concepts is that they can be developed by autonomous agents, since only evaluative feedback is assumed to be available from the environment. This distinguishes the method from traditional concept learning methods such as decision ~ree lea:ning (see e.g. [Quinlan, 1990]), which require mstruct1ve feedback and thus are a form of supervised learning. 1 Although unsupervised learning methods such as clustering, can also be viewed as methods fo; concept formation, these are less suitable as a basis for an agent that has to adapt itself to an environment, since feed~a:k on how well the agent is performing can by defimtwn not be taken into account.

It is assumed here that an autonomous agent should learn to produce successful . behavior based on evalua­ tive feedback. This feedback may be provided directly by the environment, as is usually assumed in reinforce­ ~ent learning, or it may be determined by the agent 1tself based on its internal state and its interaction with the environment, which seems to correspond better to how humans and animals function. When such an agent ~dapts .its behavior to an environment, its choice of ac­ twns wlil come to depend on its interaction history with that environment. However, the number of possible in­ teraction histories may be large, even if histories of small len?th are considered, so that the exact same history is ~n.hkely to recur frequently. In the interest of learning, 1t 1s therefore necessary to generalize.

Some generalization methods for reinforcement learn­ i~g can be used as a basis for situation concept forma­ tion. A prerequisite is that the representation of the states of the environment is adapted to the learning proble~, and provides a division of the interaction space mto regwns, such that an agent only needs to consider a region within that space, and not the specific interaction history (a point within that region), in order to decide which action to take. A good example of such an al­ gorithm is the U-Tree method [McCallum, 1996], which uses the Kolmogorov-Smirnov test to determine whether the distribution of long-term expected rewards within a region of the state-action space, determined by features on the interaction history, varies or not. However, most generalization methods for reinforcement learning can not be used as a basis, either because the representa­ tion of the interaction space is not adapted to the learning problem (e.g. plain discretization, CMAC [Albus, 1981)), or because no crisp division of the state-action space is used (e.g. neural networks).

For an exposition of the difference between evaluative and 1 instructive feedback, see e.g. [Sutton and Barto, 1998], pp. 31-33.

In cognitive science literature, many models for con­ cepts are discussed, see e.g. [Lakoff, 1987; van Or­ man Quine, 1975; Putnam, 1988]. When viewed as a cognitive model for a specific type of concepts, situation concepts distinguish themselves from other models by the level of detail at which they are specified. Since this level allows direct implemen.tation, their validity can be tested in computational experiments, as testified by this paper. It should be emphasized that situation concepts are an idealized model of a particular class of concepts, and are not claimed to be a general model for the for­ mation of concepts. Nonetheless, the possible forms of situation concepts are diverse, as may be judged from the examples in the paper.

Situation concepts are especially suited to serve as a basis for communication. In the model of language evolution investigated here, concept formation interacts with a process linking concepts to words or signals, see [Steels, 1997; Steels and Vogt, 1997]. In literature on the evolution of language, communication often corresponds directly to actions, which limits communication to the instruction of other agents. Examples include [Werner and Dyer, 1991], where sounds tell agents in a simula­ tion how to move to the emitter of the sound, [Yanco and Stein, 1993], where a leader robot instructs a fol­ lowing robot what way to move, and [Oliphant, 1997], where concepts are abstract and are modeled as having a one to one correspondance with situations. An excep­ tion is [MacLennan, 1991], where the term situation is also used to describe what the symbols that are com­ municated represent. The meaning of those situations is quite different from situation concepts though, since they are equal to the input of the agent, hence no con­ cept formation is involved. In [Billard and Hayes, 1999], an interesting experiment is described where a robot de­ velops concepts as regularities in its own behavior. This is possible because actions. are selected by a process in­ dependent of concept formation, which explains why the problem mentioned above with relation to unsupervised learning plays no role here. Since the meaning of con­ cepts in that work (objects in the environment of the robots) is fixed in advance for one of the robots (the teacher) though, it does not deal with the initial cre­ ation of the concepts, with which we will be concerned here.

Situation concepts are constructed individually by each agept. Since the concepts are based on experi­ ence with the same environment, there should be strong similarities between the conceptual systems of different agents, given that they are of the same type or species. This provides a basis for the development of communica­ tion. When agents link signals they receive and produce to their current situation, a system of communication may result where the individual situation concepts of agents are associated with shared signals. This princi­ ple is demonstrated in a simulated environment. The question that will be investigated here is whether the communication that results from this process is useful.

The structure of the paper is as follows. Section 2 for­ mally defines situation concepts in general and describes how agents form a specific type of situation concepts in the experiments of this paper. Section 3 describes how agents adapt associations between concepts and signals in order to develop a system of communication. Section 4 explains how agents may utilize situation concepts once a system for communicating them has been learned. The setup of the experiments is described in section 5. In sec­ tion 6, the benefit of communicating situation concepts is measured. Finally, section 7 presents conclusions drawn from the experiments.

2 Formation of Situation Concepts

In the most general formulation, a situation concept is a subset of the possible histories of an agent's interaction with its environment with the property that knowing to which situation concept the actual history of interaction corresponds, allows the agent to predict some aspect of the future. As an example, let's consider the advent of a thunder storm. Both seeing a flash of lightning and hearing a roaring sound of thunder are indicators that in a few moments, it may start to rain. Thus, these observations may be grouped together to form a situa­ tion which has the property that a shower is likely to arrive within short, whereas this possible future event will be less likely in the case of a bright blue sky. In this example, the situation is based on observations in the recent past, and the prediction concerns future ob­ servations. Actions of the agent or evaluative feedback played no role. Another example is the schema mech­ anism described in [Drescher, 1991], where the context and an agent's action are used to predict the result of the action. In that framework, a context is specified as a set of conditions and can be viewed as an instantia­ tion of situation concepts, since it defines a subset of the possible histories of interaction (viz. the current input) and has predictive value.

To formally describe interaction histories, time will be discretized here, which is a simplification of situation concepts in general. At time T, the complete interaction history Hmax is defined as the following set of symbols:

where for 0 :::; t :::; T, Xt, At and Rt are symbols rep­ resenting the input, action and reward, an evaluative feedback, at time t. Situation concepts are defined for a subset H of this complete history:

A situation concept Sp is a membership function that accepts a value for each element of an interaction history H within the corresponding domain (Im for Xt, An for At and R for Rt) and yields a boolean value. If and only if this value is true at time T, the situation concept Sp applies; equivalently, it may be said in this case that the agent is in situation Sp .

In the rest of the paper, the interaction history of sit­ uation concepts will consist of the current input from the environment, so that H = {Xr }. They are cho­ sen such as to allow to predict the subsequent reward given an action the agent may choose. In the experi­ ments, the formation of situation concepts is based on the Adaptive Subspace algorithm of [de Jong and Vogt, 1998], which recursively splits a space into two halves in a selected dimension, based on some split criterion. The split criterion here is whether the distribution of rewards over the sensor space differs between the two halves, which yields an algorithm similar in function to the previously mentioned U-tree algorithm and the continuous state generalization algorithms in [Uther and Veloso, 1998]. Initially, the complete sensor space is a single region. Regions have a one to one correspondance with situation concepts, and hence there is a single situ­ ation concept. When the distribution of rewards varies substantially within a region of the sensor space, this region is split in half, thus replacing it with two half­ sized regions. This principle is applied recursively, and terminates when each situation corresponds to a region of the sensor space within which rewards are distributed homogeneously.

The result of concept formation is a tree which divides the sensor space into situations, represented by internal nodes, and for each situation contains a subtree repre­ senting possible actions in that situation, where each leaf stores an estimation of the reward following the selection of the corresponding action in that situation. An exam­ ple of such a tree is shown in figure 1. The actions that are distinguished depend on the situation and are con­ structed based on the same principle as the situations.

Action selection depends solely on the situation, not on the specific input determining the situation. The tree of situations and actions is traversed from left to right , following the conditions in the nodes that apply to the current input. This yields the current situation, rep­ resented as an internal node of the tree. The possible actions are now represented in the leaves of this node's subtree. Greedy action selection would select an action determined by the leaf with the highest estimation of the subsequent reward. For learning though, exploration is necessary. In the experiments here, the choice of explo­ rative actions is based on the estimation error when the action was last selected and the time since it was last selected, and hence combines error based and recency based properties. For an overview of other exploration policies, see [Thrun, 1992].

3 Development of Communication

Situation concepts organize the possible inputs an agent may receive into groups such that experience gained with a certain input influences the reward estimation of sim­ ilar inputs. Apart from speeding up learning, this form of generalization provides a basis for the development of communication. Although the specific concepts agents create may differ, they result from a search for patterns in interactions with the same environment. If a rela­ tion between the individual concepts of the agents and a shared set of signals can be found, this would allow the agents to 'speak a common language'. To this end, agents maintain a set of signals for each situation. An association between a signal and a situation has a use score and a success score. When an agent is in situation S, it selects a signal associated with Sand emits it. Af­ ter every agent has produced the signal corrresponding to its situation, every agent receives the collection of sig­ nals produced. Upon receiving these signals, each agent increases its use scores for the associations between these signals and the current situation. Since the conceptual systems of agents may differ, the signals associated with a certain state of the environment may differ from agent to agent .

4 Benefitting from Communication

The ability to communicate enables a capacity of gain­ ing knowledge or information that cannot be attained through use of the ordinary perceptual devices. This advantage explains why so many animals, including hu­ mans, have retained the faculty to develop communica­ tion in the course of evolution once it evolved. An in­ spiring example is the alarm call system of vervet mon­ keys. Ingenious experiments involving playing back the calls produced by these monkeys show that these animals have a warning system with specific calls for different kinds of predators [Seyfarth et al., 1980]. This example demonstrates the principle of how situation concepts can be useful when communicated. When a monkey did not detect the threat of an approaching predator, successful interpretation of the alarm calls produced by other com­ munity members may induce awareness of its perilous situation. Put in abstract terms, the signals an agent receives from the other agents allow it to deduce that its situation is different from what it had observed using ordinary perception. ·

It should be understood that the ultimate meaning of a situation concept is determined by its predictive value, and not by the pattern in interaction history that has been observed to be correlated with this aspect of the future. In terms of the alarm calls example, the situ­ ation corresponds to the presence of a predator, rather than to the observation of the predator by a monkey, even though situation concepts are by necessity initially constructed as correlations between interaction histories and consequences. Therefore, when a significant aspect of an agent's environment cannot be perceived directly through perception, communication may be the only way to determine the actual situation.

The benefit of communication may surface when sen­ sor information is incomplete. The resulting uncertainty may be partially resolved by means of communication. Once a coherent mapping between situations and sig­ nals exists, the likelihood of being in a certain situation given the signals an agent receives can be determined using Bayes' formula:

where CJ is a signal that was perceived, and f..L is a situ­ ation. If the probability of a certain situation given the signals is high enough, the agent may decide that it is in that situation, and not in the situation indicated by its sensors (or, in general, its interaction history) .

The use of Bayes' formula assumes that a coherent mapping between situations ·and signals is already avail­ able. However, since this is initially not the case, agents need to adapt their private associations between situa­ tions and signals. Depending on the process of adapta­ tion, a coherent mapping may or may not emerge. Two sources of information are available as input to this adap­ tation process. Firstly, an agent may use its sensors to determine its situation and update the use scores of the associations between that situation and the signals it receives from the other agents. Secondly, the situa­ tion may be determined from the signals emitted by the other agents. To calculate the probability of being in a situation given the signals using Bayes' formula, a lin­ ear combination of the use and success scores is filled in for P(CJ I J..L) in the above formula; the remaining two values are obtained from counts of the occurence of sit­ uations and signals. This second source of information indicates more directly whether the link between a sig­ nal and a situ.ation can increase the performance of the agent. Concretely, the estimated value of the action and the actual reward following the action are compared to decide whether the determination of the situation was correct or not. If the magnitude of the difference is small, the success scores of the associations between the signals and the situation should be increased. Conversely, if the absolute difference exceeds a threshold, they should be decreased. Sending signals is not followed by evaluation, and hence does not influence scores.

Figure 2 shows an outline of the algorithm specifying when the situation is determined based on signals, and how association use and success are updated.

x := receive-input() sensor-situation := determine-situation-from-sensors(x) produce-signal (sensor-situation) signals := receive-signals() signal-situation := determine-situation-from-signals( signals) if (P(signal-situation I signals) > random(l.O)) action := choose-action(signal-situation) act (action) R := receive-reward() if (IR- value( action) I < threshold) increase-association-success(signal-situation, signals) for ((sin situations) and (not (s =signal-situation))) decrease-association-success( s, signals) else decrease-association-success(signal-situation, signals) update-value( action) e lse all-signals := signals(sensor-situation) decrease-association-use(sensor-situation, all-signals) increase-association-use(sensor-situation, signals) action : = choose-action (sensor-situation) act (action) R := receive-reward() update-value( action)

5 Experimental Setup

In the experiments, five agents can move horizontally and vertically on a grid, see figure 3. Input consists of the agent's own horizontal and vertical coordinates, and an input indicating the type of a predator that is present or the absence of predators. Actions consist of moving one step left or right or staying, and selecting a vertical position.

A predator of random type is created in 10% of the timesteps at a random horizontal position, provided no predator is present yet. Three different types of preda­ tors exist. The vertical position of an agent determines whether it is safe from the predator or not, and since the number of vertical positions is three, each position corresponds to a single type of predator. The horizontal position of an agent determines whether it can see the predator. The scope of the agents' perception amounts to 90% of the field; hence, for each agent, 10% of the predators are expected to be invisible. When a predator is invisible to an agent at creation time it will remain so until it is removed again, i.e. until the end of the situation.

6 Measuring the Benefit of Communication

The previous section demonstrated how communication may be of benefit to an agent. Our current purpose will be to investigate whether this benefit does indeed arise. If such a benefit can be measured convincingly, this would indicate that an effective system of commu­ nication has emerged.

If the predator is invisible to an agent, there is a chance of 1 in 3 that the agent can randomly select the right vertical position. But if the agent has the right vertical position in significantly more than a third of all cases where a predator is present and invisible to the agent, this is an indication that the agent benefits from the sig­ nals it receives from other agents. However, this way of measurement has a possible problem. If a predator ar­ rives and is invisible to an agent, the agent will receive a low success. Since the processes of learning and adap­ tation are active continuously, the agent's estimation of the position's attractiveness will slowly bm surely de­ crease. When the value of the action corresponding to the position has decreased below another action's value, and the agent will start to choose that other action, and move to another position. The speed of this process may be increased by the exploration mechanism, which will at times select the action of moving to another position upon which the value of that action increases, since its reward is higher than the original estimation. Because the number of positions is limited, the agent will even­ tually hit the position where it's safe from the predator.

The problem can be circumvented in the following way. At the first timestep after the creation of a predator, the only information available to an agent for which the predator is invisible consists of the signals that are pro­ duced by other agents that can see the predator. Thus, if the agent moves to the correct position at this timestep more often than in a third of the cases, it must have extracted information from .communication. Since the event that a predator is created and is invisible to an agent that uses the signals to determine its situation at that same moment is rather infrequent, the number of measurements is scarce. Therefore, this information is measured over a period of 50.000 timesteps.

There are numerous factors that influence the course of the experiment, including the increase and decrease of association strengths, removal of infrequent signals, and selection of the signal an agent produces. However, a single factor has been found to be very strongly related to the development of successful communication. This factor is the duration of a situation, and the relationship can, besides the feasibility of learned communication of situation concepts, be seen as a general result of this research.

Experiments have been performed where the duration t of the intervals during which a predator is present var­ ied from a single timestep up to 50 timesteps. To visu­ alise the information, a histogram has been made where the fraction of correct situation determinations is cal­ culated over bins of 5.000 timesteps. In order to get a more reliable estimate, the experiment has been re­ peated a number of times for each parameter setting. Because of the duration of the experiments, the number of runs per parameter setting was limited to 5. In the graph in figure 4, each line represents the average of five runs with different random seeds for a chosen duration of situations.

The graph shows how the benefit of communication depends on the duration of the interval. When predators stay for only a single timestep, the fraction of successful determinations of the situation based on signals in case of an invisible predator stays well under one third, which means that the agent is doing worse than when it would randomly choose its position. However, as the duration of the intervals increases, so do performance and speed of convergence. For intervals of 3 or more timesteps, the fraction of successful guesses is already higher than a third, and for intervals of 10 or more steps the agents reach perfection in determining which predator is present based on communication.

7 Conclusions

A model for the formation pf a particular type of con­ cepts, called situation concepts, has been described. Sit­ uation concepts capture information about how the envi­ ronment of an agent will respond to its actions. They can be constructed by analysing patterns in the history of in­ teraction between the agent and its environment. Apart from providing a particularly detailed model of concept formation, situation concepts are especially suited to serve as a basis for communication. Since agents interact with the same environment, successful communication of the situation allows agents to be better informed about their environment than their sensors alone would permit, which improves the ability to select appropriate actions.

Both the formation of situation concepts and the subsequent development of learned communication have been demonstrated in a simulation experiment. More­ over, the possible benefit of communication as an extra information source has been observed in the experiment by monitoring the actions of agents at moments when the sensors provided incomplete information. Finally, a strong relationship was found between the duration of situations and the development of successful communi­ cation.