The Influence Of Nonuniformity in The Models Of Automate Collective Behaviour

Introduction

In mid-fifties Lll. Gel.'fam am M.L. Tsetlin have :Lormulated a b1Pothes1s that complex forms af behaviour observed may be explained by the integrated ac­ tivity or a set af sybsyste~~~s, each be­ ing local by its nature and havil6 limi­ ted information on the task of the whole system. This hypothesis has served as a core for a number af collective behavi­ our models in which the role of local subsystems was played by deterministic or nonprobabilistic finite automata. The choice of such subsystems was dictated by the results obtained by M.L. Tsetlin am his school. They have shown that in a stationary random array such automata provide purposeful behaviour and that umer unrestricted increase of their me­ mory depth the behaviour of each subsys­ tem bc~omes asymptotically optimal [i] . In many cases of nonstationary random ar­ ray the probabilistic automata with re­ organising structure also provide good behaviour with a priori ignorance of the array properties [2.]. In [ 1] and [ 2] desjgns ot numerous automata providing purposeful behaviour and models of coloverall task.

''i'ishiilfi" model

N devoted f'..ishing fans live in a town · .l!.:ach :..>unday they take their fish­ ing-tackle and go out fishing. The nea­ rest environs of the town have 14 fish­ ing placos but to all fishermen's reg­ ret M is much less than N. Therefore they can never cou11t on loneliness. This makes them hold on to a certain "code of honour": have n people gathered at one place, all of their catch is devided equally among them. The local task of each fisherman is evident, to max:imise the amount oi' his catch in a certain t i­ me interval T (his SWIDier vacation sea­ son, for example). The town has its own task which is to maximise the total amount of all fi!lhermen' s catch :in a season. In this case the tcr.vn populatioz$ needs for fresh fish are met especially well.

Fishing places are not all of the same value and characterised by some ob­ jective and t i.me invariant parameter Pi · This parameter can be treated as the pro­ babil.ity of fish being found in the i-th fishizl5 place. But the values of p i are unknown a priori to fishermen. During the season all fishermen accumulate information on the fishing places. This personal individual experience of each of t~em leadj to two individual esti.JIIat­ es 1ft and \)i. Where i is the nwaber Of a fishing place and j the ordinal num­ ber of a fisl:erman. The estimate of fi[ serves for approximation of the unknown parameter Pi and represents the mean frequency of fish to ~e found in the i-th fishing place. vt approximates the math~matical expectation or the n~ber of f J.Shermen at the i-th place. V,. is . l pract~cally calculated as the mean number Of fishermen during j-th fisherman's visits to the i-th place.

To llake a decision on the choice of the f ishicg place the fishermen are apt to use the estimates of their estimates rather than the estimates themselves. One can consider, f'or instance that the J · J l' four numbers aj ) a~, b 4 and b2. are given such that with rtt >a~ the j-th fisherman takes the value of 7i~ for favourable ~j ; J .. · with Jl,< a, takes 1ii. for unfavourable and with a[ 6.Ttft.a~takes it for uncertain. (l'or rn .f. j it would be natural to consider the o'fer four threshold numbers). b~ and bl are used to estimate v~ With~~< b~ the value of ~~ is tak~n for ' ~ J . c. favourable_, wi~ \).:.>h~ for unfavourable and with h~ ~ \), ~ b~ for uncertain. :r:r the value of 1 is assi8ned to the favourable estimate, o, to unfavourable am 1/2 - to uncertain, then each fishing place can be estimated by the j-th fisherman as a set. of two components <.. ~ J. fl~) where ~J J '5,,-c, s i and Yl i can take their values from the set L 3 = { 0, 1/tJ., 1 J . Time and ex­ perience can change this set of estimat­ es :for a certain fishing place.

To make his de cis ion a fisherman should choose among the fishing places with a given set of estimates for all fishing places in the form of ( ~!· , 'q~·) . It is natural to sUppose that all entire fishing places are estimated by the fish­ ermen on a thre&-stage scale as well: a good place, a poor place and an uncertain place. Presenting these estimates in the form of L3 a set elements the fisherman can estimate the 1-th fishing place from a the mapping ~ 3 ___. L 3 · On obtaining the estimates for all the fishing places the choice of the next place to go fish­ ing can take into account all the places having the highest est i.mate with equal probabilities. The fUDCtion which imple­ ments the ma.~>ping of L~ onto L 3 is a usual ternary logical :function.

It is difficult to imagine that with a l~g.er graduation of estimates for ff! ~J l and Yi or :for the :fishing places nothing principally changes but the mapping of L; onto ~ which is implemented by a ~ -nary logical function. With the increase of the number of parameters fat' fishing place estimate (for instance the dist­ ance to a fishing place from the town) the logical function will only have a different number of arguments because with ~ estimating parameters it will be necessary to organise the mapping of ~onto~.

To describe the individual differen­ ces of the fishermen one can use the threshold values a~ , a~ , b~ and b~ and the form of the function :i.t,aplement. ing the mapping of L~ onto L} · It can be shOiin that varying these thresholds is in a certain sence equivalent to vary­ ~ the form of the mappirlg function. Therefore we shall further assume that the thresholds do not depend on a fisher­ man but reflect their consensus on "what's good and what's bad". Their in­ dividual differences will therefore be determined only by tbe form of the mapp­ ing function.

For a ''F JSH:mG" model it is natural to consider the mapping function to be of conjunctive nature since the fishing place estimate depends.simultaneously on the estimate o:t rrt and that of

~~ · The follOii ing. table shows several functions \Vhich can be used as the esti­ mating ones.

The function 'f corresponds to the usual ternary conjunction. Such functi­ on is characteristic of an objective fisherman who estimates f ishi.ng places with no emotions or assumptions. The functions 'fd and 'f!can be called opti­ mistic. The fishermen using them are apt to consider that "the world is good". With lack of information on something and thus no chance to estimate it the optimists consider such estimate to be a ~avourable one. The function 'fl is cha­ racteristic of a careful optjmist inclin­ ed to change just one value of 1/2 for 1. Under complete uncertainty considers that "every thing will be alright". On the contrary, the functions ~ t and YJ( are characteristic of the .fessemis­ t ic fishermen. They always think that the ''world does not love them" and "what good they would see from it"?

A first-rank pessimist, or a care­ ful one with one uncertain estimate in the set still dare not substitute it for unfavourable but he does it for the set ( 1/2,%-'>without hesitation. Whereas a fran­ tic pessimist replaces all estimates of 1/2 by o.

In computer simulation of the fisher­ men behaviour a uniform collective was first considered with the common estima­ ting functiom for all the members of the collective. UDder these conditions the "l'lSH:mG" problem turned into an insignif icant modification of the well known problem of distribution of automata among feeding-racks. As in the cl~sical approach the process of redistribution of automata among the feed~-racks (fishing places) was established but the rate of reaching the stationary mode of redistribution was greater because of complication of automata behaviour due to the d.ti:ferences of their iDiividual experience. ''1!' lBH:lliG" is a Goor game where tne payoffs or the participants depend not on the strategy chosen by some participant (in our case not on the choise or the place for fishing) but on participants' dil;;tribution over the pos­ s:llile strategies. Introducing into the Goor' s game the coiiDDon bank according to which the payoffs of all participants are being added up am divided equally among them at each step of the game may help to obtain the maximum or the over­ all payoff for the whole of the collec­ tive (in our case to obtain the over-all towns' goal).

The disadvantage of common the com­ mon bank is the system's central distri­ bution, to :i.llplement which there shoUld be a special clearing house. For the "P'lBHING" model this means that all the fishermen should deliver their catch of the day to one center wherefrom they re­ ceive an N -th part of t~ . overall catch in return.

Introduction of nonuniformity has helped to do, without such central dis­ tribution body. Let us consider the re­ sults of a simulation experiment. Duri~ it an additional assumption was made that the choice o:f the fishing place with no fish gives a fisherman a constant loss reduci05 his mean income collected on the previous days of the season. Besides a certain threshold was assumed to exist. ~ceedine this by the amount or catch Gives a fisherman some income proportional to this excess. With the catch lower than this threshold a fisher­ man has neither loss hor income. A case waiJ cons i.d.ered with Ill = 4, N = 32, a= 0,25, ~ = 0,?5, b 1 : 8 and b 2 :24. The simUlation variants differed in the fishermen collective structure.

For a uniform collective consisting exclusive~ of objective fishermen or frantic optimists the mean input of each member was 118 conditional units after the setting of redistribution process. The uniform collective consisting of frantic pessimists managed to get an in­ come of 134 units. All other uni!orm col­ lectives obtained worse resUlts in com­ parison with these first. Mixed collec­ tives in a number of cases showed much better results. An experimentally compos­ ed collective of 8 first-rank pessimists (carefUl ones) am 24 objectivists coUld gain a mean income of 1.58 units which corresponds to the maximal possible mean input in this game.

Study with different parameters and estillating functions (e.g. disjunctive) has shown that a nonuniform collective providing a global income with the help of a common bank procedure can always be composed.

The "i' lBH :WG" model is eas :Uy trans­ formed into various models or decentra­ lised resource allocation or into the models of the bulk service or queueing theory.

The "NElGHBOURS" ·odel

In a droughty place some country cottages are located roul¥1 the boot of a hill. There is a water source on the hlll which can be quite sufficient with rea­ sonable distribution of watering time among the cottage tenants. But in this problem the tenants do not wish or just cannot arrange such a reas on.abl e t !me­ table. They simply do not seek arzy kind of contacts most probably considering it to be the best way of keeping ne:ighbourly. The low fences between cot ta.Ges allow each tenant to watch the others and thus adjust his o.vn watering activity. ~·or purposeful use of the water supply it is necessary that only one half of the cot­ tage ground be watered at a tilDe. When­ ever more than a half the tenants open the water a certain number of grounds are being automatically switched off from water supply.

To put things in order the water sup­ ply service has decided that all the te­ nants whose cottages have even numbers should water their grounds before the noon, and all the rest, after the noon. But the cottage tenants would not obey this order of the water supply service. Then it WaJl des ided that all the tenants violating the order should be fined with switching off their grounds from water supply for a certain tilDe period. After several fines they stopped supplying such cottage ground with water at all.

A natural question is: can these con-.. dit ions and such a technique enforce or­ der in water supply and not ruin arr:T of the cottage t:,'Tounds by leaving it with­ out water.

Let us f ormulate the problems in a more formal way. There is a chain of 2N automata connected in a ring. Each auto­ maton has information on its closer neighbours' states. There are only two such states, 0 and 1. The collective's task is to transform the automata into the states, forming a sequence of ~'

~' a 3 , ·· ~, a2N' a 1 of the form of o, I, o, ... , r, o on this ring. The task of any of them is to minimise the overall fine for exceeding a certain fine threshold with its overall fine re­ sults in the automaton.

At each cycle the automaton may choose one of the two possible actions corresponding to the choise of this or that state. In the simplest case this choice is made through the analysis of the neighbour automata states at a t illle neglecting the past history of the auto­ maton. '.rhis choice is made using the &low following table. When the choice is not single-valued the automaton chooses either state with equal probabUity. The initial state distribution is given at random. The question of setting the ne­ cessary order in such a collective may be aDSwered analytically through the analysis of the initial situation. In order to avoid bulky computations of the corresponding Markov system states one can simulate the problem on a computer. As a result not a very consoling fact would emerge that the system . ot this kind almost never settle in a desired way. The model may be slightly improved by introduc~ the fines received from the environment (the Water Supply Ser­ vice). If a;tter the automaton has made its choice situation 000 or 111 arises, the automaton is fined. After a certain number of fines it is switched off and its state kept fixed duri~ the subse­ quent cycles. But even after that the whole system does not work very satis­ factory.

Let us introduce the nonuniformity into the automata collective under study using the concept of reflection ranks, thoroughly analysed in ( .n by V.A. Lefevre. Follc. ing this concept let us inductively introduce the reflection ra~f~t~~~~abourmod~.~ shall consider the automaton to have a reflection rank of zero if its function­ ing is completely defined by the above mentioned system state table. The auto­ ·aton' s reflection ra~ is taken for 1 when it works in the following way. First it watches the ne :igbbour ing auto­ mat a change their states and then choos­ es its own state through forecasting its neighbours' behaviour. In general we shall say that the automaton has a ref­ lection rank equal to { if it considers his neighbours to be automata with ref­ lect ion ra~ equal to ( .f. - 1 ) ·

The i!X rea.s e of the refl act ion . rank in our model resUlts from the incre~e or the amount of infomation commi.Qg at the i.Dput or the automaton under study. Tbe automaton with zero reflection is only 1Dformed ar the states of his near­ est neighbours. The aut~aton with a ref­ lect ion rank of 1 shoUld possess the in­ formation on the states of both two of his ri8hthar¥l and two or his lefthand neighbours. The automaton with a reflec­ tion rank af l shoUld use the informa­ tion on the states of ( l + 1 ) neighbour­ ing automata, both righthand and lefthand.

Two models may be studied. The first does not change the automata reflection ranks in the process of their function­ ing. The secooo may change the automata reflection rank by the fining si8nals from the environment. The first model ap­ pears to be greatly dependent on the random reflection rank distribution over the automata collective. To solve our problem of the automata collective's achieving the sequence of states or o,t,o, ... ,o,i it is most desirable to have the reflection ranks of 0 and 1 distributed among the automata in the same order. In this case \vith aey dist­ ribution of the initial states over it the collective still comes into the de­ sired global point.

The second-type mod~ always solves the problem providing that one may use zero and first rank reflections. Use of other reflections does not always bring the desired resUlts to the collective. The collective having automata with zero and secolld rank reflection behaves in a less purposeful way than a uniform col­ lective with zero reflection. For the firSt type mod~ one may show such a ref­ lection rank distribution amo~ the au­ tomata which zeroes the collective into the desired point.

We shall postpone until a little lat­ er the discussion of' the results obtain­ ed from the "NEIGHBOORS" model and now switch over to one which is a direct ge­ neralisation of it.

The ''PATTliRH" model

Let the automata now be located not in the form of a ring, as 1D the "NEIGH­ BOURS" model, but fill in some tore. Let us consider that each of the automata with zero rank reflection ~ eight neigh­ bours the complete information of the states of which is available at aey time. (Again we assume that there are only two states, 0 and 1). The automata collect­ ive's task is to design a certain patt­ ern on the tore defined by its elemen­ tary part being represented by a 3 x 3 matrix. This matrix is known to the au­ tomata. Each automaton's task in to choose a state that would alla.v it and its eight neighbours to design a patt­ ern after the model known. 'rhe initial automata states at the tore are t3ken arbitra;t'ily.

'rhe direct generalisation of the "NEIGHBOURS" model for the tore is the model where the automata should design a chess-board pattern. The algorithm of each automaton's work is defined as fol­ lows. The automaton compares its own state with that of' the central square of the model matrix. After that it counts up the number af its neighbours with the states differing from those of the model matrix. The automaton changes its state with a probabllity proportional to this

overall number.

The computer simulation made by Ye.T. Semionova has shown that the uniformity af a collective led to obtaining only the simplest patterns line those of a chess-board.or of horisontal and verti­ cal stripes. More complicated patterns, for instance, the one given by a matrix

1 1 1

0 1 0

0 1 0 are not obtain-

able. But the introduction of the non­ uDformity over the reflection ranks both in the "NEIGHBOURS" and in the ''P ATTliUl" models has resulted in obtaining practi­ ~ally any kind af patterns given by a

} x } matrix.

Conclusions

All above allows mak~ important conclusions on the advantages of a non­ uniform collective of automata when solv­ illg maey practical problems. The prob­ lems of the ''F lSHDG" 'type were alread;r mentioned. The "NEIGHBOURS" and ''PATTl!RN" t;ype models can easily be transformed into maey models having great importance when applied to constructing the uniform arrays and most probably in biological and microbiological models. Sociological anal~ues af the models cons mered are also easy to be shown.

Another conclusion is that the cont­ rol in nonunil'orm collectives is most ef­

fective when the control over the entire distribution of this nonuniformity is possible. Notice that in performing creative tasks animals and people should adapt to the environment obtaining from it the necessary control for a nonuni­ form collective (see, for· instance,[4] , [5],(6] ).

All this shows the models of col­ lective behaviour of the nonuniform community to be of greater interest for all the scient:Lsts engaded in arr:1 way in solving the problems of artificial intelljgence for a collective of iD:livi­

duals.