Behavior Networks for Continuous Domains using Situation-Dependent Motivations

1 Introduction

Agents in a complex dynamic domain need to take mul­ tiple goals into account, which may be of different type (as exemplified in the RoboCup soccer environment):

• maintenance goals, which should be less demanding the more the goal is satisfied (e.g. 'have stamina').
• achievement goals, which should be more demand­ ing the closer the agent is to the goal (e.g. 'score a goal').

Maes [1989; 1990; 1992] suggested a mechanism for action selection (MASM - Maes Action Selection Mech­ anism [Tyrrell, 1994]) in dynamic and unpredictable do­ mains based on so-called behavior networks. Although MASM-networks do work in continuous domains, they do not exploit the additional information provided by continuous states. Similarly, though there are mecha­ nisms to distinguish different types of goals in MASM, there are no means to support goals with a continuous truth state (like 'battery charged') to become increas­ ingly demanding the less they are satisfied.

·The work reported here has been funded by the German Research Association (DFG, Graduiertenkolleg Menschliche und maschinelle lntelligenz). I would like to thank Gerhard Strube and Bernhard Nebel for important comments and sug­ gestions during the preparation of this research.

We propose a revised and extended version (REASM) of Maes' action selection mechanism, that takes the step from discrete to continuous domains by introducing real­ valued propositions. It also allows for advanced motiva­ tional control by situation-dependent goals, and retains the advantages of MASM, such as reactivity, planning capabilities, robustness, accountance of multiple goals and the cheap and distributed calculation.

We give a formal definition of extended behavior ~et­ works and describe the activation spreading and actwn selection algorithm in section 2. In section 3 we show some domain independent properties such as activation spreading always reaching a stable state. Among other empirical results, we show in section 4 that the exten­ sions proposed show significantly better success in the RoboCup domain.

2 REASM Formalism

In this section we give a formal description of the re­ vised and extended behavior networks followed by the algorithms for activation spreading used to calculate the utility of a behavior and for action selection, which de­ cides on the behavior to execute.

2.1 Behavior Network Description

Let S be a set of worldstates, p+ a set of atoms, and r : p+ x S -+ (0 .. 1] a function assigning a truth value to each atom in each worldstate. P is a set of atoms and negated atoms where r(·p,s) := 1- r(p,s) . £"is a propositional language over P and the logical c~nnec­ tive 1\, where r(pl\q, s) := r(p, s) ®r(q, s) and® 1s a~y continuous triangular norm (e.g. min(p, q), pq) . £ ts a propositional language over P and the logical connec­ tives 1\ and V , where r(p V q, s) := r(p, s) EB r(q, s) and EB is any continuous triangular conorm (e.g. max(p, q), x + y- xy) [Saffiotti et al., 1995].

REASM behavior networks B are described by a tuple (9, M, II), where

• g denotes the set of goals characterized as tuples ( GCon, t, RCon) with

• GCon E £/' the goal condition, i.e. the situa­ tion in which the goal is satisfied,
• L the importance of the goal E (0 .. 1],
• RCon E .C the relevance condition, i.e. the situation-dependent importance of the goal with r = r(RCon, s) the relevance of the goal.
• M is a finite set of competence modules, where m EM is a tuple (Pre, b, Post, a) with
• Pre E .C 11 denoting the precondition with e = r(Pre, s) the degree of executability;
• b the behavior, which is executed once the mod­ ule is selected for execution;
• Post is a tuple (EJJ, ex), where Eff E .C" are the effects of the behavior and exi denotes the expectation E (0 .. 1] of effect proposition Effi to become true after executing this module;
• a the activity E m. indicating the utility of the module with a 9 the vector of activations a 9 , received (directly or indirectly) by goal 9i·
• II is a set of (domain-dependent) parameters used to control activation spreading;
• "' E (0 .. 1( activation of modules,
• {J E (0 .. 1( inhibition of modules,
• {3 E (0 .. 1( inertia of activation,
• () E (0 .. a] activation threshold, with a the upper bound for a module's activation,
• !:!;.() E]O .. O] threshold decay.

The revised activation spreading algorithm of REASM (see next section) made it possible to reduce the number of parameters and to restrict them to the ranges printed above. This simplifies the process of finding best per­ forming parameter values for a domain (see section 4.1).

2.2 Activation Spreading

The competence modules are connected in a network [Maes, 1989] to receive activation from goals and other modules. A competence module k receives activation from a goal 9ii at timestep t

if the module has an effect (with expectation ex i) that is part of the goal condition and both are atoms or both are negated atoms, i.e. the behavior satisfies the goal. f is any continuous triangular norm, that combines the static importance of the goal t 9 , and the dynamic relevance r 9 , (e.g. t 9 , · r 9 .).

A module k is inhibited by a goal i by

if the module has an effect that is part of the goal condi­ tion and exactly one of them is negated, i.e. the behavior would undo an already satisfied goal.

A module receives activation by a so called successor module if it has an effect (with expectation exj) that is part of the preconditions of the successor module (psucc)

and both are atoms or negated atoms. The activations are calculated separately for each goal activation asucc 9, of the successor module and are

where a: m.--+ (0 .. 1( is the transfer function of the mod­ ules activation for which we used a(x) = (1 + e~<(!-'-x))- 1 [Goetz, 1997]. The term (1- r(p8ucc, s)) states that the less the precondition of the successor module is satisfied in situation s the more activation is spread to modules making this precondition true, i.e. the false precondi­ tion becomes an increasingly demanding subgoal of the network.

Finally a module is inhibited by conflictor modules by

if it has an effect that is part of the preconditions of the conflictor module (peon/) and exactly one of them is negated. a~~~/ 9 , is the activation the conflictor module received directly or indirectly by goal 9i at timestep t -1.

The activation akg; of each goal is kept separately by each module and is set to the activation of that link with the highest absolute maximum activation

In other words, only the strongest path from each goal to a module is taken into account. Any confluence of activation within a module from the same goal is pro­ hibited. This leads to some important new properties of the algorithm shown in section 3.

Finally the activation of a module k is

where {3 controls the inertia of the activation and there­ fore the inertia of the agent's behavior.

Activation and inhibition as well as the introduction of relevance conditions allow the modelling of differ­ ent types of goals. Increasingly demanding maintenance goals (e.g. 'have stamina' in the RoboCup soccer envi­ ronment) can be achieved by adding a relevance condi­ tion ('stamina low'). This increases the relevance of the goal and therefore the activation of satisfying behaviors by the goal as the situation diverges from the state to be maintained. Achievement goals (e.g. 'score a goal') can be realized by adding a relevance condition ('close to goal') whose truth value increases on nearing the goal. Modules achieving the goal are increasingly activated, modules conflicting with the goal are inhibited.

2.3 Action Selection

Action selection is done in a cycle containing the follow­ ing steps [Maes, 1990]

1. Calculate activation of each module a} (Eq. 6) .
2. Combine activation and executability of a module by a non-decreasing function h : m. x (0 .. 1] --+ m.. To prevent non-executable modules from being ex­ ecuted, h(a, 0) should be zero.

1. If the highest value h(a, e) lies above(}, execute the corresponding module's behavior, reset(} to its orig­ inal value and go to 1.

4. Otherwise reduce (} by D.(} and go to 1.

Step 2 is necessary because modules have a continous executability e and can therefore not be divided into executable and non-executable as opposed to MASM. All modules have to be considered for execution prefer­ ing modules with higher executability, although modules with high activation may be executed even if their exe­ cutability is low.

3 Domain Independent Properties

In this section we show properties of the algorithm for activation spreading that are domain independent.

3.1 Stability

An important property of activation spreading networks is to reach a stable state of activation. Although this seems to be the case for Maes' behavior networks, to our knowledge it has never been proven. However, variations of Maes' networks (variation four of [Tyrrell, 1994]) oscil­ late under some circumstances. The algorithm proposed here can be proven to reach a stable state.

Lemma 1 The above described algorithm for activation spreading does not allow feedback of activation for u( a) ~ a and t -too.

Proof. Although there possibly are cycles within REASM behavior networks, the activation a module gets from itself a~elf 9 , drops to zero for t -t oo. This holds b I t I n(rm(l t-(n+m)l ( _ t (E ecause aself 9 , < "'( u a self 9 , , - n+m q. 3,4 and u(a) ~a,"'(, 8 < 1 and r(p, s), exi ~ 1). n is the no of excitation links, m the number of inhibition links within the cycle. For t -t oo either 'YnC: (for n > 0) or 8m< (form> 0) and therefore la·elt9fl approaches zero. For m = n = 0 the module is not part of a cycle. 0

Theorem 2 Activation in REASM networks always reaches a stable state (unless the situation changes).

Proof. Activation for each goal is calculated separately by the competence modules. Therefore we can treat each goal separately and look at the connected subgraphs containing one goal. We split the vertices of this sub­ graph into two sets: V 0 contains the vertices which have reached a stable state of activation, V contains all the other nodes of the subgraph. Initially, V 0 only contains the goal. After one step of activation spreading the node with the strongest link to the goal (in terms of maximum absolute activation (Eq. 1, 2)) will receive constant acti­ vation a 9 , and can be removed from V and put into V 0 . This holds because activation decreases along activation paths (proof of lemmal) and because each module re­ ceives activation across a single incoming link (Eq. 5). This can be repeated for all nodes in V, although ac­ tivation of these nodes may take more than one step of activation spreading to reach a stable state, because of previous activation caught in feedback cycles. This activation feedback, however, drops to zero for t -t oo (lemma 1). The main activation of a module m received by all goals am then equals am = (1 - /3)- 1 :L::n amgn (Eq. 6) and D..am = 0. 0

3.2 Problems mentioned by Tyrrell

Tyrrell [1994] pointed out some problems of behavior networks proposed by Maes. We show that none of these problems hold within REASM.

Preference for appetitive behaviors 1

The action selection mechanism proposed by Maes shows some undesirable preference for appetitive nodes over consummatory nodes (see Fig. 1) independent of pa­ rameter settings [Tyrrell, 1994].

In MASM activation of an appetitive node (action2) is a~ = r(a~- 1 )+7+4>+</>ha~- 2 + ... while a consummatory node (action3) receives less activation a~ = r(a;- 1 ) +7+ 4>) . This is undesirable, because action3 directly satisfies the goal while action2 only satisfies a precondition of action! which reaches the same goal.

Figure 1: Preference for appetitive nodes At the top level are the goals with their importance, below are the competence modules and their activation and at the bottom level the situation propositions (perceptions) with their r-values. Only the relations of activation values matter. MASM (left) undesirably prefers appetitive action2, REASM {right) correctly prefers action3 (actionl is non-executable) .

In REASM, activation from a goal always decreases with the distance to that goal (proof of lemma 1) prefer­ ring modules that directly satisfy it. This prevents acti­ vation feedback from occurring (lemma 1) and therefore the preference for appetitive behaviors.

Activation fan

MASM divides activation spread by goals by the number of links connected to the goal (activation fan). Similarly, activation received by a node is divided by the number of incoming links. This penalizes goals with more behav­ iors satisfying it and does not prefer modules satisfying multiple goals at once (see Fig. 2).

Tyrrell shows however that leaving out division by the number of links causes a different problem, namely the confluence of activation in nodes with many successors which may all be alternatives of one goal (see Fig. 3).

1 In contrast to consummatory behaviors that try to satisfy a goal, appetitive behaviors try to prepare consummatory.

Neither problem holds for REASM. Activation is not divided by the number of incoming or outgoing links. Therefore behaviors satisfying multiple goals are pref­ ered (Eq. 6), goals with alternative behaviors satisfying them are not penalized. And there is no confluence of ac­ tivation from the same goal due to the fact that only the strongest path of activation from each goal to a module is taken into account (Eq. 5).

4 Empirical Results

Empirical analysis of behavior networks has been con­ ducted using the RoboCup soccer server program [Noda, 1995]. Agents in this domain are simulated soccer play­ ers getting their (relative) perceptions from the server across a network and sending executed actions to the server which changes its state accordingly. Perception and action are non-deterministic, i.e. perceptions as well as actions are perturbed by some noise, and may be lost in the network. The state of the soccer field is dynamic: It changes whenever any of the agents performs some action. It is continuous: State, perceptions and also actions are described by continuous values. In short, the RoboCup domain is non-deterministic, dynamic and continuous and is therefore a demanding environment for any algorithm for action selection.

The network used contained three goals and eight com­ petence modules (see Fig. 5). The corresponding behav­ iors were implemented using C++ methods that were called once the competence module was selected. r­ functions for perception-propositions were similarly calculated from the agent's perceptions and state informa­ tion using C++ methods.

4.1 Parameter Setting

As stated above, activation spreading and action selec­ tion depend on a set of parameters. These parameters are domain dependent and have to be tuned to obtain best performance from the agents. This was done by playing a series of games with equal teams of two players 2 except for varying one parameter of one team along its definition area. 25 games for each of eleven variations per parameter were conducted to obtain statistically reliable results. The quality of the varied team was measured by the difference between scored goals and those scored by the other team. For the variation of the first parameter, the other parameters were set to 'sensible' values. The following parameter variations used previously found val­ ues, which performed best. Because parameters are not independent of each other, this process was repeated for all parameters, until changes of best values became small ( < 0.1). This led to curves as shown for the activation by goals "' in Figure 4.

Two things should be noted: First, without any moti­ vation by goals ("' = 0) the agents perform very poorly, because all modules have same activation (zero) . Hence, always the first executable module is executed. Second, although differences like "' = 0.4 to "' = 0.5 are signifi­ cant, the score level is high for a wide range of parameter values indicating that finding a 'functional' parameter setting is not too difficult.

4.2 Real-valued Propositions

To evaluate the usage of real-valued propositions we con­ ducted a series of 30 games where one team used realvalued propositions while the other team used discrete propositions ( r-values were truncated to 0 for 0 ~ r < 0.5 and rounded to 1 for 0.5 ~ r ~ 1). No goal relevance was used for these games. The team using real-valued propositions scored significantly higher 3 (Table 6).

20ffside rule was switched off, stamina recovery was in­ creased w.r.t . eleven player games.

One reason for this is that using continuous proposi­ tions, modules with a high utility may be executed even if their executability is low. So even if the likelihood of a successful execution of the behavior is small, the high utility of one or more of its effects makes it worthwhile to try. This is reflected for example by a significantly higher number of shots at the goal by the team using, real-valued propositions, although both teams had al­ most equal ball possessions.

4.3 Situation-Dependent Goal Relevance

In another experiment we introduced situation depen­ dent goal relevances (dynamic goals). The relevance con­ dition for the goal 'score goal' was to be in the opponent's half (true, lOrn behind the midline and false 10m before with linear interpolation), for 'protect own goal' it was not to be in the opponent's half and for 'be unmarked' it was for the teammate to be the nearest player to the ball. Two teams, one team using situation-dependent goals, played a series of 30 games. Although relevance conditions were fairly primitive, the team using dynamic goals scored significantly higher (Table 7).

3 All statistical test are paired samples T-tests for differ­ ences of means with o = 0.01

4.4 Comparison to MASM

We also implemented the original algorithm proposed by Maes [Maes, 1990] to be able to compare both algo­ rithms. After parameter optimization described above for both networks, we played a series of 30 games. The agents of one team were controlled by MASM, the other team's action selection was conducted by REASM. Both teams' agents used the same perceptions 4 and identical behaviors, so the only difference was in action selection.

REASM scored considerably higher than agents using MASM even without the usage of real-valued proposi­ tions and situation-dependent goals (Table 8). This can be explained by the significantly higher rate in behavior switches conducted by MASM. It is caused by resetting the activation of executed competence modules to zero in MASM and by using sigmoidal transfer functions in REASM making behaviors attractors for activation re­ sulting in fewer behavior changes [Goetz, 1997].

4 Using discrete propositions for MASM.

When equipping REASM with real-valued proposi­ tions and situation-dependent goals it scores significantly higher than MASM (Table 9).

5 Limitations

REASM does not allow for multiple behaviors executed concurrently. However, humans are able to perform well trained behaviors in parallel, unless they use the same resources [Gopher and Donchin, 1986]. Assuming knowl­ edge about the resources used by a behavior, the action selection algorithm could be changed to build sets of exe­ cutable behaviors with disjunct resources and execute all behaviors in that set, with the highest sum of utilities.

For the empirical studies, expectations of effects were set manually. Although Maes proposed an algorithm to learn the links of a network and their expectations [Maes, 1992], this work does not extend to continuous domains with delayed effects. Adaptive behavior networks are however inevitable once domains get increasingly com­ plex. Work in the area of reinforcement learning with delayed reward could help to extend the algorithm for learning behavior networks from experience.

6 Discussion

Maes' algorithm contains two further kinds of links spreading activation from perceptions p to competence modules with precondition p (situation links) and from competence modules with effect p to other modules with precondition p (predecessor links). These links account for the reactivity of the system because they insert ac­ tivation from perceptions into the network. However, when dropping the division of activation by the number of links that use a perception, as we proposed, situation activation of all executable modules equals a 8 = ¢ ( ¢ is a parameter that controls the amount of situation acti­ vation) . In that case there is no direct influence of these links to the selection of a behavior. The indirect influ­ ence of having more activation in non-executable mod­ ules with some preconditions satisfied did not turn out to improve action selection as Goetz [1997] and our own studies demonstrated, where parameter variations of ¢ showed best performance for¢= 0.

Decugis and Ferber [1998] introduced a different vari­ ation of Maes' algorithm for which they proved conver­ gence of activation. However, their algorithm does not include inhibition and therefore the ability to take un­ wanted effects into account. Another shortcoming is that goals do not depend on the current situation. Besides showing better success, situation-dependent goals sim­ plify the creation of behavior networks, especially when domains get increasingly large and complex. This is be­ cause relevance conditions of goals can be used to di­ vide up the domain into different contexts. The soccer­ playing agents for example can use goal relevance to easily incorporate different strategies for play-on phases, and for phases when the game has been interrupted by the referee. When using the behaviors' preconditions to produce the same set of strategies, precondition lists of all behaviors grow rapidly, complicating the introduction of new behaviors and new strategies.

In this paper, we have argued that real-valued propo­ sitions can be integrated into an action control algorithm using behavior networks to improve the performance of agents in continous domains. Further the introduction of situation-dependent goals simplifies the creation of large behavior networks and improves agents' performance by focussing on relevant goals as exemplified by studies us­ ing the Robocup domain.