Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 67–70___________________________________________________________________________________________________________Efficient collective search by agents that remember failures
Masao Kubo

Department of Computer Science, National Defense Academy
Hashirimizu 1-10-20, Yokosuka, Kanagawa,239-8686, Japan
Nhuhai Phung

Department of Computer Science, National Defense Academy
Hashirimizu 1-10-20, Yokosuka, Kanagawa,239-8686, Japan
Hiroshi Sato

Department of Computer Science, National Defense Academy
Hashirimizu 1-10-20, Yokosuka, Kanagawa,239-8686, Japan
E-mail: masaok@nda.ac.jp, ed17006@nda.ac.jp, hsato@nda.ac.jp
http://www.nda.ac.jp/cs/stuff/masaok.html

Abstract
The BRT agent is an algorithm that can find appropriate collective behavior by changing the agreement contents ina trial and error manner. Computer experiments show that it is necessary to change the agreement contents thenumber of times that is proportional to the square of the number of choices. In this paper, we attempted to shorten
this search time by introducing an agent that memorizes actions that were not able to achieve the expected effect ofwhat they executed. As a result, we found that search time can be improved by just mixing a few this proposed
taboo list agents.
Keywords: Swarm intelligence, Machine learning, Complex systems, Best-of-n problem

swarm and no general models as to whether to discover,memorize, and learn new micro interactions leading
have not been proposed. It has become a bottleneck inthe construction of a more advanced self-organizing
swarm system [4].
To this problem, a voting model (BRT model, Biasand Rising Threshold model) has been proposed thatemerges a trial and error process at the macro level by
momentary change of agreement of an agent group [6].
Every agent chooses one action from among the actions
and notifies all of them. The agent changes its action inview of the number of supporters of each action. Theykeep voting until actions of the all members are same.
This is a model that expands the 2-option consensus

1. Introduction
Roughly speaking, if a set of required roles (forexample, collecting foods and resting) and therelationship between these elements are embedded inindividual behavior beforehand, for example they cankeep energy of them constant [1]. On the other hand, itis anticipated that it will not be able to lead to somereasonable macro states of the swarm by the above
division of labor methods such as when a newenvironment is encountered. They need methods how toemerge the swarm in a better macro state against such asituation [2]. To solve this issue we have to discuss
individual's learning but also learning capability as

Copyright © 2018, the Authors. Published by Atlantis Press.
This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
67

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 67–70___________________________________________________________________________________________________________building model against the agreement of [3] and others
so that it can be used even in the case of multiple
options and incorporates the passage of time. By
appropriately designing the bias value θ which
expresses the degree of preference of the behavior
selected by itself, this algorithm has the feature ofreaching consensus in almost constant time regardlessof the number of agents in the group. A series ofcomputer experiments shows that it is possible to findsuitable consensus actions in a time proportional toapproximately M2 for the number of actions M.
This is inefficient in cases other than dynamic
environments where the environment and tasks
frequently change. Here, we introduce a derivation
agent of BRT that memorizes a set of behavior that wereonce executed but not appropriate, and removes themfrom their own action selection. In the following, thisfunction is called UEM (unsuitable experience memory),
and an agent having this function is called an UEM
agent. The memory used here is a short term, and it
forgets probabilistically. As will be described later, if allagents have UEM they can expect to discover a good
macroscopic behavior in proportion to M.
This paper is organized as follows. First, we will
explain the BRT and its characteristics. Next we
propose an UEM agent and estimate its characteristics.
Finally, we verify the characteristics of the proposed
method by computer experiment. As a result, we foundthat it is possible to reduce the time required for solution
search even if all agents do not have UEM function.

At this time, the agent Pi decides the behavior
Ai(t+1) at the time t as follows. Ifn(A i (t))
  i + c (t-t i,last )N(1)is satisfied, Ai(t+1)=Ai(t). Otherwise, behavior otherthan Ai(t) is stochastically chosen and becomes Ai(t+1)∈A\Ai. Here,τis a constant representing the incrementof proponents number.
In addition, ti,last is the clock time at which the agent
Pi last changed its behavior, and (t-ti,last) is the time span,
which the same action continues to be selected.

t i,last (t+1)=t 1 A i (t+1)  A i (t)t i,last

otherwise(2)c(t) is a function that is 1 when not achieving thedesirable macro purpose as follows.


0 i, j, A i (t)  A j (t)  A goal

1c = 

(3)otherwise

If the ratio of agents whom selects the same
behavior as theirs is lower thanθi+τc(t-ti,last), the agent
selects a new behavior from other behavior candidates.

Figure 1. Transition Example (Staring from an agreedstate)

2. Related works
2.1. BRT modelNow, we assumed that there are n agents P1,…,Pn.
A={a1,…,aj,…,aM} is set of agents’s behavior
candidates with M≧2. Ai(t)∈A is the behavior of agent
Pi at time t. The agent Pi has a bias θi (0<θi<1). n(aj)is number of agents selecting behavior aj.
As a result of everyone performing the same action,a macro state of the group occurs. And if this is suitable
for the environment and tasks, this agreement behavior
is assumed to be "suitable".
Agoal is the set of desirable behavior candidates(Agoal⊂A). In advance, the agent does not know Agoal.
Only when all have agreed, it is understood that Agoal
includes that agreed behavior.

2.2. Behavior example of BRT model and its
search time characteristics
Here we illustrate the behavior of the BRT model.
We will introduce its characteristics. Figure 1 isrendition of what was described in our past work [5].
Figure 1 shows a transition process from an agreed state.
In the initial state, all of agents have agreed to a0, buteveryone agreed to another action (a1) in about 65 steps.
Again, 1000 agents agreed to a0 action again in 125steps. From the above it can be seen that agreed
behavior can be switched from either state.

68

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 67–70___________________________________________________________________________________________________________

Here, we show that it is possible to agree with thedesired behavior by computer experiment. The
experimental results are shown in Figure 2. The + markis the average time required for discovery, and the ○mark is the value obtained by dividing it by M2. Since
the ○ mark is almost parallel to the x axis, it ismentioned that the average of the time required todiscover the solution is proportional to M2.

The agent stores it with Eq.5 and select a candidate
with Eq.4. This BRT agent will be referred to as an
UEM (unstable experience memory) agent below.
Table 1 Probability to support one unselected action.
Number of trial
BRT agent
UEM agent
st1
1/M
1/M
2nd
1/(M-1)
1/(M-1)
3rd
1/(M-1)
1/(M-2)x-th
1/(M-1)
1/(M-(x-1))
3.1. Approximation of characteristics of theproposed method
Consider the ratio of UEM agents. Table 1 indicatesthe number of attempts to agree and the probability ofselecting an arbitrary unselected action. When trying anagreement for the first time, the probability of selecting
one action is (1/M) with BRT, UEM agent. Both agentsknow that one action was inappropriate at the secondtime, so both are 1/(M-1). However, in the third andsubsequent times, the behavior selection probabilities ofboth agents will differ. The BRT agent remains 1/(M-1),
but the UEM agent does not select actions that arealready selected as inappropriate, so candidates arereduced step by step. The selection probability of x trial
is 1/(M- (x - 1)). In order to shorten the search time it isnecessary to reduce the number of times they agree withthe action they tried already. This corresponds to thevote of UEM agent.
When the difference between the expected values ofboth at the x-th time is

Figure 2. Characteristics of search time cost by BRT

3. The proposed agent (UEM agent)
The BRT agent remembers the last action that wasagreed but did not suit, and select other behaviors.
Namely this short-term memory is limited to the mostrecent behavior. Then they repeatedly agree on
behaviors that were not suitable a while ago. If theenvironment has not changed since the last execution,
this is not an efficient search. Therefore, we will
introduce an agent that memorizes behavior that agreed
but did not suit for a long time, and tried to makesolution searching more efficient.
The agent has its list Li(t) that remembers actions
that were agreed but not suitable, and adds it to this list
with the probability pin at the time when it is determinedthat it is inappropriate while agreeing.

 L (t) A (t) probability piiinL i (t+1) = L(t)otherwisei
uM  (x 1)

where u (<n) is the number of UEM agents. Thisequation shows that if the population of UEM agents islarge, it is less likely to choose actions that have alreadybeen tried. Also, as the denominator decreases as thenumber of attempts to reach an agreement progresses, itindicates that less agreement on already selected actions
will be reduced. Therefore, even if the population of theUEM agent is small, the effect of shortening the searchtime can be expected.

(4)where Ai(t)={∀j, Ai(t)=Aj(t), Ai(t) ∉ Agoal }.
When selecting a new action, select actions that are
not included in Li(t) stochastically. Namely,A i (t+1) A\L i (t)

(6)

(5)

69

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 1 (June 2018) 67–70___________________________________________________________________________________________________________

composed of UEM agents, we can expect that the searchtime increases linearly with M. However, even in thecase of mixing with the BRT agent, we estimate thateven a small number of UEM agents are effective, andverified the trend in computer experiments. As a result,it turned out to show the behavior as expected.

Figure 3. When changing the ratio of UEM agent.

4. The experimental results
4.1. UEM agent ratio
Figure 3 represents the search time as a cumulative
probability density distribution, and the horizontal axis
is the time required. The vertical axis represents theprobability of finding a solution by this time. The solidline represents the case of pUEM = 0.1. The search time
has been found by 99% trial by 1000 steps. As
estimated by the formula 6, even a small number of
UEM agents can greatly improve search time.
The relationship between the ratio of UEM agent
and the average search time is shown in Figure 4. The
horizontal axis shows the ratio of the UEM agent, andthe vertical axis shows the average search time. pUEM=0.0 requires an average of 834 steps, and pUEM=1.0 took
an average of 462 steps. With pUEM= 0.001 , it is 810
steps, and search time can be improved just by mixing
minute UEM agents. As we increased the proportion ofUEM agents, dramatic improvements were seen up topUEM=0.1 (meaning that pUEM=0.1 required an averageof 486 steps).
From these two experiments, we found that theproposed UEM agent can improve the search time ofBRT agent.

Figure 4. Relation between ratio of UEM agent andsearch time.
References
1.

2.

3.
4.

5.

5. Conclusion

6.

In this paper, in order to improve the efficiency of
the trial and error search behavior that the BRT agent
group emerges, we proposed a derived type of BRT
agent from the candidates by recording the failed
experience called UEM agent. If all flocks are70E. Bonabeau, G. Theraulaz, J. L. Deneubourg, FixedResponse Thresholds and the Regulation of Division ofLabor in Insect Societies, Bulletin of MathematicalBiology, Vol.60(1998)753- 807.
G. Valentini, E. Ferrante, M. Dorigo, The Best-of-n
Problem in Robot Swarms: Formalization, State of theArt, and Novel Perspectives, Frontiers in Robotics andAI, Vol.4, 9(March 2017)1-18.
A. Namatame (In Japanese), Strategic Decision Making,Asakura Publisher (2001)119-149.
M. Kubo, N. H. Phung, H. Sato, A. Namatame,Direction switch behavior to enclose a pack of targets
based on phase transition, Proceedings of swarm
2015(2015)155-161.
N.H. Phung, M. Kubo, H. Sato, S. Iwanaga, Agreement
algorithm with trial and error method at macro level,
Proceedings of Swarm 2017(2017)82-85.
N.H. Phung (In Japanese), A study on extension ofenclosing algorithm for multiple mobile agents, Master’s
thesis at national defense academy of Japan(2017)