Generating Causal Networks for Mobile Multi-Agent Systems with Qualitative Regions

1 Introduction

Methods for automatically generating underly­ ing causal relations for mobile multi-agent sys­ tems, e.g., traffic system, industry flow system, are indispensable to reorganize the system's be­ havior and achieve the system's goals efficiently. Scientific questions on the complex behavior of the multi-agent systems arise in connection to the system's emergent property, i.e., the sys­ tem's behavior can be very complex in spite of the simple behavior of each agent. Although we have no way to control such properties com­ pletely, we can understand and explain the be­ havior with an underlying mathematical model, by observing the system's behavior and verify­ ing assumptions about the target system.

In this paper, we propose a method for gen­ erating causal networks among the parameters which describe the target multi-agent system. By causal networks, we mean the qualitative arithmetic and differential relations of parameters. All of the parameters needed to de­ scribe the target system are not given explicitly. There exist implicit parameters, embedded in the target system, which must be salvaged.

Our method consists of three components: 1) A macro-behavior rule generator, which prepares implicit parameters and the macro-behavior rules. 2) A causal network constructor. 3) An explanation generator. In the course of this process, spatial extents are represented and reasoned with qualitative regions.

In the following section, we illustrate an ex­ ample to demonstrate our method, the forag­ ing behavior of ant colonies, which are typical mobile multi-agent systems with a local com­ munication method by means of the chemical pheromone.

2 Problem

2.1 Foraging Behavior of Ant

Colonies

We selected an ant colony as an example for the causal network construction because it is a typical example of a mobile multi-agent system. It has macro-goals at the colony level which must be achieved by the cooperative behaviors of the micro-agents. The micro-agents have a local communication method with the chemical pheromone, but the colony itself has no global

communication methods.

It is difficult for the target system to have a centralized controlling mechanism (headquar­ ters) because it lacks a global communication method. The target system must therefore achieve its macro-goals by coordinating or tun­ ing the individual micro-agent behavior.

The foraging behavior of an ant colony is the organized behavior of the ant society. This is a typical example of the complex behavior of a biological multi-agent system [Assad and Packard, 1992] [Drogoul et al., 1992]. Although the behavior (algorithm) of each ant is quite simple, the colony shows complex foraging be­ haviors, which maximize the bait transport ratio and mm1m1ze the risk caused by environ­ mental disturbance, i.e., climate, food competi­ tion, and so on [Hoelldobler and Wilson, 1990]. In this paper, the model for the foraging be­ havior of each ant is assumed to be as follows , shown in Figure 1. 1

[The foraging behavior system of ant colonies]

1. At any time, an ant is in one of these modes: search, attracted, trace, or trans­ port .
2. Search is the default mode. The ant moves randomly in search mode.
3. When an ant in any mode finds a bait-site, it turns into transport mode, in which it carries a bit of bait back to the colony's nest. Bait can exist at several bait­ sites. Ants in transport mode secrete re­ cruitment pheromone on their transporta­ tion path, which becomes the pheromone 'trail.' An ant in transport mode turns into search mode when it reaches the nest .
4. The trail evaporates and diffuses, which produces a pheromone atmosphere (We call the pheromone atmosphere just 'pheromone').
5. When an ant in search mode comes across a pheromone atmosphere, it turns into at­ tracted mode, in which it is induced by the pheromone and moves toward a posi­ tion of higher pheromone density. If the pheromone disappears before the ant in attracted mode find a trail, it turns into search mode.
6. When an ant in search or attracted mode finds a trail, it turns into trace mode, in which it traces the trail in the reverse di­ rection of the nest . If the ant in trace mode cannot find a bait at the end of trail , it turns into search mode.

An ant in trace or transport mode must be able to recognize the direction of the nest. There are two assumptions about the ability. The first one is that ants can remember the path from the nest to the current position. The sec­ ond one is that 'nest pheromone' is being se­ creted at the nest and each ant can recognize the direction of the nest by the gradient of the pheromone density.

This simple algorithm of the ant (agent) imple­ ments the foraging behavior of the ant colony (multi-agent system), i.e.,

1. to find the bait-site(s),
2. to mobilize ants in the colony in order to carry bait on a large scale, therefore,
3. to maximize the bait transport ratio.

1 The model is not entirely faithful to real ant behavior. It represents common aspects of many kinds of ant colonies.

Notice that this simple agent's algorithm (and the colony's strategy) can be easily influenced by an environmental disturbance. When more than one bait-site exists and all the ants in the colony gather to a bait-site simultaneously, en­ emy animals can easily att ack the colony. The colony might also miss other bait-sites which have more bait than the bait-site currently un­ der attack.

Figure 1. The foraging behavior system.

2.2 Numerical Simulations

We have carried out numerical simulations of the foraging behavior with several sets of pa­ rameters [Nakamura and Kurumatani, 1995]. Part of the results of the simulations is shown in Figure 2.

In these simulations, a nest exists in the center of the environment, and there are eight bait­ sites equidistant from the nest . The only dif­ ference between the two is the number of ants in the colony.

Figure 2. Numerical simulation of the foraging behavior for 60 (a) and 600 (b) ants.

Other important parameters are as follows:

Expansion of simulated space 0 ::; x < 100L:lx, 0 ::; y < 100L:ly, 0 ::; z < 3llz Length of a grid and a step llx =fly= llz = 0(0.01,..., 0.1m) , llt = 0(1 ,..., 10sec) Moving speed of ants in all mode 2 ,..., 3 (llx/ llt) Evaporation and diffusion factors 'Yeva = 0.24 L:lt, 'Ydif = 0.42 (llx 2 / llt) Minimum sensitive trail strength 0.0001 Minimum sensitive pheromone density 0.001 Pheromone secreted by an ant for a step 0.001

In Figure 2(a), there are 60 ants searching for 8 bait-sites. Some ants actually find a bait­ site and generate a pheromone trail between the bait-site and the nest. Since the trail evap­ orates more quickly than the other ants gather to the trail, continuous growth of the trail and continuous large-scale transport are not achieved. In Figure 2(b), there are 600 ants. They are able to gather to the trail, and large­ scale transport is achieved. The results indicate that there must be a large enough number of ants in the colony to overcome the time-delay between the gathering speed of the ants and the evaporation/diffusion speed of the pheromone. In Figure 2(b), almost all of the ants gather to bait-site number 5. The colony basically "for­ gets" the other bait-sites. Actually the same phenomenon that all the ants gather to only one bait-site is observed under almost all pa­ rameters whenever large-scale transport is re­ alized. The reason is that there is a positive feedback in the differential relations of the sys­ tem parameters, i.e., the number of ants gath­ ering to a bait-site, the amount of secreted pheromone by the ants, and the amount of evaporated pheromone atmosphere which at­ tracts the ants.

In the following section, we present a method for generating causal networks, which can be used to explain such phenomena.

3 Generating Causal Networks

Our approach is to prepare fragments of knowl­ edge about the system's behavior at macro level, called macro-behavior rules, and then to generate causal networks using the rules. A part of macro-behavior rules are generated from the description of the problem, with salvaging implicit parameters.

Our method has the advantages that 1) spatial extents can be represented and reasoned sym­ bolically, therefore partial differential equations (e.g., diffusion) can be handled in qualitative (symbolic) manner, 2) implicit parameters can be found and used to generate causal networks, and 3) the generated causal networks can be used to generate explanation or reorganize the target multi-agent system, e.g., suppressing the exponential amplification in the foraging be­ havior which is found in the causal networks of ant colonies.

3.1 Qualitative Region

A qualitative region represents a spatial extent describing an attribute of the target system and its changes, e.g., how the pheromone trail or at­ mosphere spreads, or how ants in search mode are distributed.

Mathematically, when a function f(x, y) and a meaningful value I (a landmark) are given, a qualitative region of r = region(f, 1) de­ notes a closed line on an x-y plane which is represented by f(x , y) =I. Usually we use the notation, r = region(f, 1, +) , which repre­ sents the closed region f(x , y) > I on the x-y plane, shown in Figure 3. 2

Since our aim is not to represent such regions precisely (it can be done by numerical simula­ tions), we represent their characteristic proper­ ties symbolically, to reason about the behavior of the target systems.

Although one method for representing the char­ acteristic properties is to describe the bound­ aries of a region qualitatively [Kurumatani, 1990], in this paper, we use only the area of a region, the amount of entity included in a region, and their qualitative changes, in addi­ tion to describing the topological relationships among regions. From the computational point of view, defining a new qualitative region pro­ ceeds as follows:

• Define a symbol (atom) for the region.
• Define the class of the region. The class has the descriptions about instance re­ gions, including the changing manner of the region (equation type), i.e., diffusion, evaporation, constant, and so on.
• The characteristic properties (qualitative variables) of the region, i.e.,

area( region) total ...amount( region) a verage_amount( region)

2 If more than one such region exists, region(f, 1, +) denotes separated regions r1, r2, ... , rn.

are prepared and can be used in the re­ maining reasoning process.

• Topological relations between two regions and the dynamically changing status of a regwn, I.e.,

identical(ra, rb), isolated(ra, rb), intersect(ra, rb), include(ra, rb), no_change(r), expanding(r), shrinking(r) will be used in the remaining process.

3.2 Macro-Behavior Rules (1) - about Agents

A causal network is a graph representing the causal relations among the variables, on which qualitative values ( +, 0, -) are propagated to generate explanations. A part of the variables are included in the definition of the problem, and the rest of them are introduced by the rea­ soner.

The nodes of the graph represent parameters and characteristic properties at "macro-level," i.e., at the description level of the whole target system, rather than each agent (the behavior of each agent is described at "micro-level") . The arcs are labeled by the qualitative relation of adjacent nodes.

For instance, in a situation where ants in search mode come across a pheromone atmosphere and they switch to attracted mode, the tran­ sition ratio (frequency) of the ants from search mode to attracted mode is qualitatively propor­ tional to the density (population) of the ants in search mode, and also to the area of the pheromone atmosphere, described by, 3

MO+(trans_rate(search, attracted), population(search)). MO+(trans_rate(search, attracted), area(phero)).

These notations are a part of the causal net­ work, which is generated by a macro-behavior rule. The rule is a fragment of knowledge about the macro-behavior, describing the situation in which the rule is activated, and the effect of the activation. For instance, the rule about tran­ sition from search mode to attracted mode is written in the form of predicate:

transit(search, attracted) :- 1* condition for activation *I region(Search, search_region), region(Phero, phero_region), intersect(Search, Phero),

3 MO+ is a 'monotonic' function. MO+(a, b) means that a is qualitatively proportional to b, i.e., 8a/ 8b is positive, and a = 0 when b = 0. I+(a, b) means that a is qualitatively influenced by b, i.e., [da/dt] = ... + [b] ... , where [x] is the sign of x.

I* region relations *I gensym(attracted_, Attracted), assertz( region(Attracted, attracted_region)), assertz(include(Phero, Attracted)), I* quantity relations *I assertz(m_zero_plus( trans_rate(Search, Attracted), population(Search))), assertz(m_zero_plus( trans_rate(Search, Attracted), area(Phero))) .

Since search in this rule is a qualita­ tive region representing the spatial distribu­ tion of search mode ants in the environ­ ment, population(search) is equivalent to totaLamount(search) . The former is an alias of the latter, just for distinguishing the distri­ bution of agents from the physical entity.

3.3 Rule Generation

The macro-behavior rules about agents are gen­ erated at the beginning of the whole reason­ ing process. In the "course, the implicitly exist­ ing variables in the system needed to generate causal networks are defined.

The rule generator receives an automaton con­ sisting of the set of modes and the conditions of mode transition. It processes each condition of mode transition from X to Y, written in prolog predicate form, such as:

trans_condition(X, Y) :- in(position(X), region(Z)),

where Z is a name of class region appeared in the problem description, e.g., physical entity (trail, phero, ... ) or mode name (search, .. . ). The corresponding macro-behavior rule is gen­ erated by rewriting the above form. This pro­ cess includes:

• Introducing predicates for defining a new region and topological relations, e.g.,
• Defining implicit variables, e.g., trans_rate(X, Y)
• Adding qualitative relations, e.g.,

region(Y, class_region_name). include(Z, Y).

MO+(trans_rate(X, Y), population(X)). MO+(trans_rate(X, Y), area(Z)).

Although this part can be regarded as an ab­ stracted version of the translation technique discussed in [Rajamoney and Koo, 1990], spa­ tial extents and implicit parameters can be han­ dled by our method.

Because our targets are limited to 'mobile' multi-agent systems, our translation technique can exploit the metric of Euclidean spaces. In other words, there is a simple mapping between position (point) at micro-level and spatial ex­ tent (region) at macro-level. That's why the above procedure can be applied to each condi­ tion of mode transition.

3.4 Macro-Behavior Rules (2) - about Physical Entity

All physical entities appearing in our problem (pheromone, trail) are described at the macro­ level, i.e.,

region(phero_l, phero_region). equation_type(phero_region, diffusion).

where the latter predicate indicates that a re­ gion in the class phero..region changes gov­ erned by a diffusion equation.

The macro-behavior rule for such a physical en­ tity depends only on the equation type govern­ ing the entity, e.g., the rule for a diffusing entity is written as follows:

solve(diffusion) :- region(R, Class), equation_type(Class, diffusion), assertz(expanding(R)), assertz(i_minus(total_amount(R), diffusion_rate(R))).

When generating causal networks, such a rule is used to check the equation type of a certain physical entity, and to reason about the change of concerning parameters, after defining im­ plicit variables such as diffusion_rate{phero_l).

3.5 Collecting Qualitative Relations

The reasoner receives 1) behavior of the agents, 2) descriptions of the environment, and 3) the initial state of the target system.

First of all, the reasoner generates macro­ behavior rules about agents.

The environment should be described with qualitative regions. The macro-behavior rules about physical entity check the equation type of an entity in the environment, and reason about the changes of its characteristic properties.

Both typ.es of macro-behavior rules are a collec­ tion of the declaration "how the target system behaves in a certain situation" described at the macro-level. We reason about the target sys­ tem's behavior using the following process:

1. Set the initial state to the currenLstate.
2. Apply the macro-behavior rules to the cur­ renLstate, and determine the rule to be­ come active.
3. If there is no rule which can be activated, stop.
4. Collect the qualitative (causal) relations of parameters in the activated rules , i.e., gen­ erating the causal network corresponding to the current state.
5. Examine the possibility for each param­ eter to cross the landmark, and also ex­ amine the possibility that topological rela­ tions change (spatial version of limit anal­ ysis) .
6. Collect the fragments of the next state in the activated rules , and set it to the cur­ renLstate.
7. Go to 2.

This process resembles one from qualitative process theor-1 [Forbus, 1984] [Falkenhainer and Forbus, 1988j. The differences are that 1) the macro-behavior rule, which corresponds to in­ dividual view and process in qualitative process theory, is generated by the reasoner , in addition to defining implicit parameters, and 2) spatial extents, such as pheromone diffusion , can be represented and reasoned about with qualita­ tive regions.

Main part of a generated causal network is shown in Figure 4. This network corresponds to a state in Figure 2(b) after a large enough number of ants are attracted by the pheromone, trace the trail, and transport the bait while se­ creting recruitment pheromone.

4 Explanation Generation

Once the causal network is obtained, we can generate explanations of the system's behavior by propagating qualitative values in the net­ work [Forbus and Falkenhainer, 1990] [Forbus and Falkenhainer, 1992]. By tracing a loop in the causal network, we obtain an explanation:

pheromone is expanding.

transition from search to attracted is positive.

transition from attracted to trace

is positive.

transition from trace to transport is positive.

pheromone is expanding.

In the generated explanation, the reasoner finds a positive feedback among the parameters. This means that there is a possibility that the pheromone atmosphere and the gathering ant population will grow exponentially.

The fact that the reasoner can find such a causal relation in the target system is impor­ tant , because we can use the results in order to redefine each agent 's behavior.

The system presented in this paper is im­ plemented in SICStus Prolog (ver.2.1) on a SPARCstation20.

5 Discussion

The relationship between the complex behavior of multi-agent systems and each agent 's behav­ ior has been partially investigated [Ray, 1991], but they lack the ability of providing under­ lying mathematical models. Statistical anal­ ysis for system behavior with a fixed simple agent behavior [Axelrod, 1984] can describe the statistic relationship between agent's be­ havior and system's behavior, e.g., distribution of agent in the environment . Since both of them lack causal relations, explanation genera­ tion and reorganization are impossible.

6 Conclusion

A method for generating causal networks for mobile multi-agent systems has been discussed. Our method consists of generating macro­ behavior rules while salvaging implicit parame­ ters, then constructing causal networks among system parameters. Spatial extents are repre­ sented and reasoned with qualitative regions, in the course of the process.

This method was applied to the explanation generation of the foraging behavior of ant colonies.

Since the causal network represents the un­ derlying mathematical structures of the tar­ get system, the reasoner can find the macro properties of the target system, such as posi­ tive/negative feedbacks embedded in the target system, which can be used in redefining each agent's behavior.

Potential applications include cargo-control system, traffic navigation, industry flow con­ trol, and so on.

Acknowledgement

The author would like to thank Mari Nakamura for discussion about modeling ant colonies, and for the implementation of numerical simulators of the foraging behavior.