Analysis of the appropriate behavior of various types of automata in the conditions of the placement game

Dimitrichenko Dmitriy Petrovich PhD in Technical Science Researcher, Institute of Applied Mathematics and Automation 89a Shortanova str., Nalchik, 360000, Russia, Republic of Kbr dimdp@rambler.ru Other publications by this author

Introduction

The organization of complex behavior of decentralized systems built on the basis of simple elements is reflected in such a section of machine learning as "Collective behavior of automata" ^[1], which has wide applied significance from solving problems of automatic optimization, intelligent control, building robotic systems ^[2], and to issues of psychology ^[3].

At the same time, the connection between neural network and automaton approaches is quite close ^{[4, 5]}.Due to the growth of computing capabilities of multi-user and multithreaded systems, there is an objective need for analysis and management ^{[6, 7]} of a set of agents acting in a decentralized manner, in accordance with their own goal-setting and interacting with each other and a given environment.

At the same time, there are often situations when the same action selected by several agents can be physically performed at a particular time by only one of them.

For example, only one of the threads processing the current data can perform a read (or write) operation. All other applicants are blocked from accessing this data.

Only one robot at the intersection, out of two approaching along different paths, can cross the opposite highway. Both robots cannot move at the same time (there will be a collision), or simultaneously wait for the passage of another robot, thereby creating a situation of deadlock in the passage of the intersection for an indefinite period not only by the current, but also by the following robots.

In the biological interpretation, certain areas of the ecological niche, shared by several animals, correspond to the jointly selected actions of agents. Then the amount of actual resource on the site is divided (not necessarily equally) among all the animals present on it.

A similar situation occurs when multiple applications actively use Internet traffic.

These are the simplest cases illustrating the rules of behavior within the framework of the placement game, when an action chosen by several agents can be performed at a given time (in our case, receive encouragement) by only one of them (in our case, one of the automata that chose this action).

All of the above makes it possible to involve probability theory, game theory, and automata theory in the analysis of the behavior of multi-agent systems (a finite set of agents in an artificial environment) in order to obtain theoretically justified and confirmed results using simulation methods.

The automaton approach used in this work provides the researcher with a formalized (within the framework of discrete mathematics) method that allows to perform a formal statement of the problem and analyze the behavior of agents and the given habitat itself in terms of an automaton model (a collective of automata), input, output and internal alphabets, as well as transition rules and selection results.

The purpose of this work is to obtain quantitative estimates of the influence of inertial properties (manifested in various ways) of certain types of automata and different values of memory depth on the effectiveness of the functioning of a collective of automata in a stochastic environment organized according to the rules of the placement game.

The novelty of the conducted research is the following:

1. 1. The rationale (theoretical proof of the corresponding statement and its confirmation when performing computational experiments) that in the stochastic environment of the placement game, it is sufficient to take the operating time of a separate (reference) automaton as a confidence interval for the functioning of a collective of automata. This made it possible to minimize the time of conducting computational experiments for the studied types of automata, which is especially important with an increase in memory depth values and, as a result, an increase in the amount of computing time.
   2. Such an estimate of the confidence interval turns out to be invariant with respect to a given type of automata. At the same time, the larger the team of automata, the more accurate the estimate of the current time interval obtained in this way turns out to be.
   3. The use of the integral value of the mathematical expectations of all automata to assess the effectiveness of a collective of automata, which in conditions of actions that are not equivalent in price, is especially informative and allows you to accurately interpret the approximation of a collective of automata to a statistically optimal state, since due to the stochasticity of the environment, automata are actually always in motion.
   4. It was possible to observe that the integral value of the efficiency of the functioning of a collective of automata obtained in this way not only quantitatively strives to maximize the aggregate of incentives from the environment, but also informs about the desire of the collective to minimize the level of intra-collective competition.

One of the traditional methods of analyzing the behavior of automata is the use of the apparatus of game theory ^[8]. This choice is due to the fact that game theory makes it easy to create formalizable systems of rules (environment) and behavioral strategies (available actions) that determine the nature of interaction between an individual automaton (or a set of automata) and the environment ^[9].

This circumstance makes it possible to form a closed circuit Environment-Automaton, in which the actions of the automaton determine the reaction of the environment, which in turn, through feedback, influences the choice of the subsequent action of the automaton.

The first interesting models of this type were created by Mikhail Lvovich Tsetlin ^[9]. He was the creator of a whole line of research called "collective behavior of automata" ^[9-12]. He formulated the basic principles underlying such models and ways to implement them.

The formalization of the concept of purposeful behavior allowed M. L. Tsetlin to formulate the basic principle of organizing complex behavior of a set of decentralized systems forming collectives of automata.

The main provisions of this approach are as follows:

1) the principle of superposition;

2) the principle of commensurability;

3) the principle of universality of the automaton structure.

The principle of superposition. Any sufficiently complex behavior consists of a set of simple behavioral acts. The joint implementation of such simple behavioral acts and the simplest interaction result in very complex behavioral processes.

The principle of commensurability. The degree of expedient behavior of the analyzed cybernetic system is considered as the value of the mathematical expectation of a set of fines and rewards received by this system from the environment over the observed period of time t. This value is in the range with the following boundaries:

The left boundary is the value of the mathematical expectation of the number of fines and rewards received by the simplest system implementing a strategy of randomly selecting actions available in a given environment from the set D=d1,..., dm, m>=2.

The right boundary is the value of the mathematical expectation of fines and rewards received by the system, which at any given time t, t>>1, always implements the obviously optimal action in this environment di= d*, i=1, ..., m.

Obviously, the closer the value of the mathematical expectation of the incentives of the analyzed system is to the left boundary of the interval defined in this way, the more precisely its behavior corresponds to the strategy of "random selection". And the closer this value is to the right boundary of the interval, the closer the behavior pattern is "to a system aware of the best possible strategy."

Such a definition of appropriate behavior does not depend on the structure of the analyzed system, but is based only on the statistical result of interaction with the environment.

The principle of universality. The design of the analyzed system should not contain empirical data on optimal (or non-optimal) actions in a given environment, i.e. the system identifies such actions during its operation for some time t.

The first automatic implementation of such a system was proposed by M. L. Tsetlin.

Automatic implementation

Here is a formal description of the machine:

X = x1, ..., xk – the set of input signals coming from the environment to the input of the automaton (input alphabet).

D = d1, ..., dm is a finite set of actions available to the automaton, (output alphabet).

S = s1,…,sn, 2 <= m <= n is a finite set of internal states of the automaton (internal alphabet).

The rules of operation of the automaton at discrete moments of time t are unambiguously set by two functions:

The function of transitions of internal states: st+1 = F(st, xt), and the initial internal state at zero time t=t0: s0 = S(t0).

The function of dependence of output signals (actions) from internal states: dt = G(st).

General statement of the problem

Let's define some environment E in which automata of the studied types will function.

Let there also be types of automata for which it is possible to establish the degree of appropriate behavior in the environment E in a certain way above.

Is required:

- to determine the degree of influence of the memory depth q of each of the considered types of automata on the change in the degree of expediency of behavior in the specified environment E;

- based on the results obtained, determine the type of machine design that reaches a given level of expediency with the lowest possible memory depth q =q*;

- if there are several equivalent designs, specify the simplest design to implement.

Biological background

The results from experimental biology required the formulation of a cybernetic "white box" with appropriate behavior.

The experiment was as follows ^[9]:

The experimental animal was placed at the base of a T-shaped maze with the possibility of choosing one of two actions:

"Turn left";

"Turn right."

According to the experimental conditions, at the end of each of the two branches, favorable (or unfavorable) conditions unknown to the experimental animal were realized with independent probabilities for each of the two events (branches).

It was necessary to establish the ability of experimental animals to distinguish between environmental properties of a probabilistic nature.

It turned out that, despite the selection errors at the beginning of the series of experiments, the animals subsequently correctly associated the turn they chose (the action they performed) with the one for which the probability of a fine (the probability of getting into an unfavorable situation) was minimal.

Stationary environment

The stationary environment E is a mathematical description of the conditions of a T-shaped maze.

In the T-shaped maze, there were only two actions available for the experimental animals to perform: "turn left" and "turn right". Each of the selected branches was expected to have its own probability of encouraging Pl and Pr.

A generalization of this situation is a stationary environment with m outcomes (actions).

For each of the m actions, a set of probability values is set: either reward pi or penalty 1 – pi, i=1, ..., m.

Choosing the optimal action in such an environment boils down to determining the action with the maximum probability of reward (minimum probability of penalty).

At the same time, neither the experimental animal in biological experiments, nor the automaton corresponding to it in behavior, have knowledge of the initial values of probabilities, but are forced to receive this information in an indirect form through reward and penalty signals received from the environment.

Types of automata designs

The first design of an automaton capable of behaving expediently in the stationary environment E described above is an automaton with linear tactics proposed by M. L. Tsetlin.

The L1 automaton (with memory depth q=1) consists of m states S=s1,.., sm.

Each of the m states of si is assigned an action di, i=1, ..., m.

The L1 automaton functions as follows:

At some point in time t=t*, being in the si state, the L1 automaton performs the output action di, i=1, ..., m.

In response to this action, the environment generates a signal that takes the value "Reward" in accordance with probability pi (or "Penalty" with probability 1 – pi).

This signal is sent to the input of the l1 machine.

If the L1 automaton receives a "Penalty" signal at the input, then it switches to the si+1 state and, therefore, switches the external action from di to di+1.

Upon receiving the "encouragement" signal, the L1 automaton remains in the initial state of si, while there is no change of action.

Thus, at the next moment of time t*+1, the L1 automaton will perform an action in accordance with its internal state, and the process of interaction of the automaton with the environment will repeat in the manner described above.

By assigning q consecutive states to each of the m actions di, we obtain a sequence of linear automata with monotonously increasing memory depth q.

Cetlin was able to show that the sequence of such automata L1, L2, ..., Lq, functioning in a stationary environment E, is asymptotically optimal, i.e. the greater the memory depth of a linear automaton Lq, the longer such an automaton performs the most optimal action (with the maximum probability of encouragement), and almost never leaves the associated states.

A complication of the machine with linear tactics is the Krinsky machine.

It is characterized by the fact that when receiving encouragement, this automaton always goes into the deepest state corresponding to the current action performed by it.

When receiving a penalty from the environment, this automaton reacts in the same way as an automaton with linear tactics, lowering the status number of the current (completed) action by one.

For this automaton, the theorem on asymptotic optimality when operating in stationary media is also proved.

The Robbins automaton is the next in terms of the degree of enhancement of the inertia property.

It differs from the Krinsky automaton in that, unlike it, when changing an action, the Robbins automaton immediately goes into the deepest state corresponding to the new action.

Otherwise, it is no different from the Krinsky machine gun.

The theorem on asymptotic optimality in stationary media is also true for him.

Note that for three automata: the automaton with linear tactics, the Krinsky automaton and the Robbins automaton with a memory depth of q = 1, the algorithms of functioning completely coincide, losing the differences between them, which will be illustrated when analyzing their functioning.

A slightly different approach to inertia enhancement is applied in the design of the Krylov automaton.

It combines elements of behavior, both deterministic and stochastic automata.

When receiving a reward, the automaton functions in the same way as an automaton with linear tactics, increasing up to the deepest state number corresponding to the action for which this automaton receives encouragement from the environment E.

When receiving a fine, Krylov's machine "flips a coin."

When an eagle falls, the machine does not change its state, and when a tails falls, it reduces the number of the current state corresponding to the action for which a penalty was received from the environment.

This automaton is also asymptotically optimal in stationary environments.

Dynamic environments

Initially, game theory served as the formal language for describing both stationary and dynamic environments with automata functioning in them.

The actions of the automaton from the set D are mutually unambiguously correlated with the strategies available to the player in the corresponding (given) game with a finite number of strategies.

For example, the set of m actions available to the automaton, together with the values of the probabilities of rewards (penalties) in a stationary environment E, is formulated in the language of game theory as a game with nature:

1) a single-column payment matrix with m non-negative values is specified;

2) the elements of the game matrix are normalized relative to the maximum value of the payment and are considered as the probabilities of rewards from a stationary environment E;

3) the reward value is one, the penalty value is zero;

4) the actions of the machine (player 1) correspond to the row numbers of the specified matrix;

5) Nature (Player 2) has chosen her strategy (single column) and does not change it during all the games of the game;

6) The aim of the game is to maximize the winnings of the slot machine.

Player 1 (automaton), at each moment of time t, plays a game with nature and, depending on the selected action d*=di and the probability p*=pi corresponding to this action, receives a reward (or penalty) signal from the environment I, i= 1, ..., m at the entrance.

Since the optimal strategy of the game with nature is known and corresponds to the player's choice of an action with a maximum price of pi = pmax, it creates an opportunity to compare the effectiveness of the action of an informed player who knows the entire payment matrix with the actions of an automaton who does not know the contents of this matrix.

From the theorems on the asymptotic optimality of the types of automata discussed above, it follows that the greater the memory depth q of an automaton, the more precisely its cumulative actions correspond to the optimal strategy.

Two slot machine games

The case of a two–player zero-sum matrix game is an example of how one machine is able to create an environment for another machine.

In this case, the row numbers are matched to the actions of the first machine, and the column numbers of the payment matrix are matched to the actions of the second machine.

If the first machine with probability p receives a reward, then the second machine receives a penalty, and vice versa, implementing the principle of an antagonistic zero-sum game.

The task of the first machine is to maximize rewards, the task of the second machine is to minimize penalties.

If the game allows a solution in pure strategies, then the automata implement a stationary environment for each other, for which an increase in expediency is associated with an increase in the depth of memory q.

The solution in mixed strategies requires automata to have an optimal memory depth that satisfies the properties of this dynamic environment and the type of automaton.

Similarly, the game of two automata is constructed in the case of non-cooperative, non-antagonistic, bimatric games with a finite number of strategies.

The Placement game

An example of how a collective of automata forms a dynamic environment for an individual automaton is the placement game.

The biological prerequisite for the placement game is the following task:

1) there are a finite number of sites (pastures, or hunting areas) with varying degrees of food productivity. Animals are housed in these areas in some way;

2) if two or more animals are currently on the same site, then the food productivity of the site is divided equally between these animals.

The animal's task is to maximize the amount of food it gets.

The description of the placement game is easily formulated in the language of game theory as follows:

1) let m strategies be given d=d1, ..., dm. The value of each strategy is equal to the mathematical expectation of the "Reward / Penalty" event if it is selected;

2) within the framework of the given strategies, there are n automata: n. The winnings from the strategy di, i=1, ..., m, at any given time t are equally divided among all the machines that have chosen this strategy;