# Research on Multirobot Pursuit Task Allocation Algorithm Based on Emotional Cooperation Factor

Authors: Baofu Fang; Lu Chen; Hao Wang; Shuanglu Dai; Qiubo Zhong
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Multirobot task allocation is a hot issue in the field of robot research. A new emotional model is used with the self-interested robot, which gives a new way to measure self-interested robots’ individual cooperative willingness in the problem of multirobot task allocation. Emotional cooperation factor is introduced into self-interested robot; it is updated based on emotional attenuation and external stimuli. Then a multirobot pursuit task allocation algorithm is proposed, which is based on emotional cooperation factor. Combined with the two-step auction algorithm recruiting team leaders and team collaborators, set up pursuit teams, and finally use certain strategies to complete the pursuit task. In order to verify the effectiveness of this algorithm, some comparing experiments have been done with the instantaneous greedy optimal auction algorithm; the results of experiments show that the total pursuit time and total team revenue can be optimized by using this algorithm.


---

## Body

## 1. Introduction

In recent years, multirobot task allocation problem has attracted widespread attention, which is widely used in robotic soccer, robotic rescue, intelligent warehouse, and other issues [1–3]. In order to solve the multirobot task allocation problem, Elango develops a simulation model involving task priority and the utilization of robots and refers to it as a balance multirobot prioritized task allocation (BMRPTA) problem [4]. This simulation model tries to find a balanced exploration path for each robot which is so constituted that the average waiting time and total completion time of all tasks are minimized. This allocation method assumes that robots are completely rational, so it does not consider the benefits of the individual robot. Auction [5, 6] is a fast and effective method of negotiation; when applying it into multirobot task allocation, robots can ensure the maximization of the overall benefits, at the same time considering their own benefits. Eric and Ofear [7] give up the ideas from traditional auction methods to pursue optimal task allocation strategy, so this paper focuses on the study of how to use robots efficiently in each team and how to prevent robots interfering with each other in the process of task execution, as well as how to execute the allocated tasks efficiently based on auction. Nanjanath and Gini [8] take more attention to the impact of robotic failures and environmental uncertainties in auction, so they aim at finding a compromise between computational complexity and quality of allocations and ability to adapt. If a robot finds an unexpected obstacle, experiences any other delay, loses communication, or is otherwise disabled, the rest of the team continues to operate. Above literatures take into account the self-interest of robot, but they do not have a deep research about self-interested robots such as the ability of self-interested robots, the individual cooperative willingness of robots in different situations, and the changes of individual cooperative willingness during executing tasks.Psychology shows that emotion plays a very essential role in the process of work, where negative emotions may cause people’s action to be slow and insensitive for the work while positive emotions can be conducive to the work [9]. Delgado-Mata and Ibanez-Martinez [10] add emotional mechanism to robots and use emotion to reflect the self-interest features of robots. When robots have negative emotions, such as sadness and fear, they are trended to keep the status quo and do not participate in the task; while robots have the positive emotion, they choose to participate in the task.In order to measure individual cooperative willingness of self-interested robot in multirobot task allocation problem, a multirobot pursuit task allocation algorithm which is based on emotional cooperation factor is proposed. We build emotional cooperation factor for self-interested robots, then use it to measure the individual cooperative willingness of self-interested robots, and determine whether the robots are suited to participate in the pursuit task or not. Emotional cooperation factor is updated based on emotional attenuation and external stimuli. Combined with the two-step auction algorithm recruiting team leaders and team collaborators, set up pursuit teams and finally use certain strategies to complete the pursuit task.


## 2. Emotional Cooperation Factor

### 2.1. Definition

In order to describe the willingness intensity of the robot to participate in the pursuit, this paper enhances an emotion model constructed in our work before [11]. At first, the emotional cooperation factor f, representing the robots’ emotional cooperative willingness, can be defined as follows:
(1)f=I×Mt×(w1,w2,w3),
where the basic emotion status is described by a set E={ei∣i=1,2,…,N} and ei is corresponding to happiness, anger, sadness, and joy; I is an emotional intensity vector; I=[I1,I2,…,IN]; Ii is the emotional intensity of basic emotion status ei. Mt is the exchanging matrix from basic emotion to PAD model where pleasure-arousal-dominance (PAD), three-dimensional model of emotion, is proposed by Chen and Long [12]. The value of f is decided by the type of the basic emotion status ei; wi(i=1,2,3) are the weights of PAD in each dimension where ∑i=13wi=1.Definition 1.
f
c is a justice factor for robot cooperation, which is calculated to judge whether the robot is willing to attend pursuit task allocation:
(2)fc={1,f>ξ0,f≤ξ,
where ξ is a justice parameter of the emotional cooperation factor. If the value of emotional cooperation factor is above ξ, the robots’ emotion will be pleased and stable, whereas if the value of emotional cooperation factor is below ξ, the robot will be variable and unstable.


### 2.2. Several Impacts on Emotional Cooperation Factor

#### 2.2.1. Emotional Decay

Emotional intensity will decrease with the time passing by which directly causes the change of emotional intensity vectorI and then influence the value of emotional cooperation factor. Based on the 3rd law of emotional intensity in psychophysics, the emotional decay curves comply with an exponential function y=e-x. In order to simplify the process of emotional decay, we only consider previous emotional decay impact on the emotion of current moment. So the function of emotional decay can be expressed as follows:
(3)φ(ki)=e-kiT,It=It-1×φ(ki),
where It-1 is emotional intensity vector at t-1; T is the checking period for emotional status; and ki is an emotional decay factor.


#### 2.2.2. Emotional Stimuli

External stimulation is another important factor affecting the emotional status. Pursuing different evader can get different rewards. The higher reward given, the greater stimulation intensity produced. During the pursuit, if the robot is in depressed mood or emotion decay for pursuit unwilling to complete the task, we need to impose different stimulation intensity for different types of robots to ensure that the robot will complete its pursuit.By using a stimuli vectors1s2,…,sr to represent a real world stimulation, a stimuli with the kind of i and the intensity of r can be written as Sir=si1si2,…,sir=sisi,…,sis,r=1,2,…,rmax⁡, where rmax⁡ is the maximum emotional intensity. By simulating robot’s emotions and personality, Wang and Teng [13] define the matrix of stimulation B, assuming that stimulation is instantaneous without considering time; the emotional intensity can be expressed as follows:
(4)Φ(Ii,t)=Ii,t×B.In summary, the value of emotional cooperation factor is influenced by the emotional decay and emotional stimuli. It can be transformed to the change of emotional intensity vectorI, which can be defined as follows:
(5)Ii,t=g(∑i=1Nφ(Ii,t-1)+βΦ(Ii,t)),
where g is a limiting function [14] that confines the value of emotional intensity within [0,1]; we set g(x)=1/(1+e-x); β is the active threshold of stimuli and the value of β corresponds to the type of robot for stimulus; the fact that a different type of stimuli gives different effects of emotion changes can be expressed.


## 2.1. Definition

In order to describe the willingness intensity of the robot to participate in the pursuit, this paper enhances an emotion model constructed in our work before [11]. At first, the emotional cooperation factor f, representing the robots’ emotional cooperative willingness, can be defined as follows:
(1)f=I×Mt×(w1,w2,w3),
where the basic emotion status is described by a set E={ei∣i=1,2,…,N} and ei is corresponding to happiness, anger, sadness, and joy; I is an emotional intensity vector; I=[I1,I2,…,IN]; Ii is the emotional intensity of basic emotion status ei. Mt is the exchanging matrix from basic emotion to PAD model where pleasure-arousal-dominance (PAD), three-dimensional model of emotion, is proposed by Chen and Long [12]. The value of f is decided by the type of the basic emotion status ei; wi(i=1,2,3) are the weights of PAD in each dimension where ∑i=13wi=1.Definition 1.
f
c is a justice factor for robot cooperation, which is calculated to judge whether the robot is willing to attend pursuit task allocation:
(2)fc={1,f>ξ0,f≤ξ,
where ξ is a justice parameter of the emotional cooperation factor. If the value of emotional cooperation factor is above ξ, the robots’ emotion will be pleased and stable, whereas if the value of emotional cooperation factor is below ξ, the robot will be variable and unstable.


## 2.2. Several Impacts on Emotional Cooperation Factor

### 2.2.1. Emotional Decay

Emotional intensity will decrease with the time passing by which directly causes the change of emotional intensity vectorI and then influence the value of emotional cooperation factor. Based on the 3rd law of emotional intensity in psychophysics, the emotional decay curves comply with an exponential function y=e-x. In order to simplify the process of emotional decay, we only consider previous emotional decay impact on the emotion of current moment. So the function of emotional decay can be expressed as follows:
(3)φ(ki)=e-kiT,It=It-1×φ(ki),
where It-1 is emotional intensity vector at t-1; T is the checking period for emotional status; and ki is an emotional decay factor.


### 2.2.2. Emotional Stimuli

External stimulation is another important factor affecting the emotional status. Pursuing different evader can get different rewards. The higher reward given, the greater stimulation intensity produced. During the pursuit, if the robot is in depressed mood or emotion decay for pursuit unwilling to complete the task, we need to impose different stimulation intensity for different types of robots to ensure that the robot will complete its pursuit.By using a stimuli vectors1s2,…,sr to represent a real world stimulation, a stimuli with the kind of i and the intensity of r can be written as Sir=si1si2,…,sir=sisi,…,sis,r=1,2,…,rmax⁡, where rmax⁡ is the maximum emotional intensity. By simulating robot’s emotions and personality, Wang and Teng [13] define the matrix of stimulation B, assuming that stimulation is instantaneous without considering time; the emotional intensity can be expressed as follows:
(4)Φ(Ii,t)=Ii,t×B.In summary, the value of emotional cooperation factor is influenced by the emotional decay and emotional stimuli. It can be transformed to the change of emotional intensity vectorI, which can be defined as follows:
(5)Ii,t=g(∑i=1Nφ(Ii,t-1)+βΦ(Ii,t)),
where g is a limiting function [14] that confines the value of emotional intensity within [0,1]; we set g(x)=1/(1+e-x); β is the active threshold of stimuli and the value of β corresponds to the type of robot for stimulus; the fact that a different type of stimuli gives different effects of emotion changes can be expressed.


## 2.2.1. Emotional Decay

Emotional intensity will decrease with the time passing by which directly causes the change of emotional intensity vectorI and then influence the value of emotional cooperation factor. Based on the 3rd law of emotional intensity in psychophysics, the emotional decay curves comply with an exponential function y=e-x. In order to simplify the process of emotional decay, we only consider previous emotional decay impact on the emotion of current moment. So the function of emotional decay can be expressed as follows:
(3)φ(ki)=e-kiT,It=It-1×φ(ki),
where It-1 is emotional intensity vector at t-1; T is the checking period for emotional status; and ki is an emotional decay factor.


## 2.2.2. Emotional Stimuli

External stimulation is another important factor affecting the emotional status. Pursuing different evader can get different rewards. The higher reward given, the greater stimulation intensity produced. During the pursuit, if the robot is in depressed mood or emotion decay for pursuit unwilling to complete the task, we need to impose different stimulation intensity for different types of robots to ensure that the robot will complete its pursuit.By using a stimuli vectors1s2,…,sr to represent a real world stimulation, a stimuli with the kind of i and the intensity of r can be written as Sir=si1si2,…,sir=sisi,…,sis,r=1,2,…,rmax⁡, where rmax⁡ is the maximum emotional intensity. By simulating robot’s emotions and personality, Wang and Teng [13] define the matrix of stimulation B, assuming that stimulation is instantaneous without considering time; the emotional intensity can be expressed as follows:
(4)Φ(Ii,t)=Ii,t×B.In summary, the value of emotional cooperation factor is influenced by the emotional decay and emotional stimuli. It can be transformed to the change of emotional intensity vectorI, which can be defined as follows:
(5)Ii,t=g(∑i=1Nφ(Ii,t-1)+βΦ(Ii,t)),
where g is a limiting function [14] that confines the value of emotional intensity within [0,1]; we set g(x)=1/(1+e-x); β is the active threshold of stimuli and the value of β corresponds to the type of robot for stimulus; the fact that a different type of stimuli gives different effects of emotion changes can be expressed.


## 3. Multirobot Pursuit Task Allocation Algorithm

The contract net protocol is proposed by Smith [15] in 1980 at first and it is a typical market method which origins from the contractual mechanisms in the business activity. In the pursuit task allocation problems, emotional robots choose the appropriate evaders to pursue using contract net protocol. This paper provides a multirobot pursuit task allocation algorithm based on emotional cooperation factor to get appropriate pursuers and form the optimized cooperation teams at last.


### 3.1. Basic Definition

Definition 2.
DefineE={E1,E2,…,Em} as a set of evaders, where Ei is represented by four elements Ei=〈Pe,Te,Ce,Re〉, where Pe indicates the position of the evaders, represented by (ex,ey); Te={ti∣i=1,2,…} is the type’s set of the evader, which may have various types; set Ce={ci∣Te=ti,i=1,2,…} indicates the capability of each evader needed. Since the evaders have different types, and this means that catching evaders needs different type and different number of robots. Therefore, the key point to construct a pursuit team is to decide the number and the relative types of the pursuers. Define the reward after completing a pursuit task, Re={ri∣Te=ti,i=1,2,…}. The pursuer can gain different reward to capture a different type of evaders.Definition 3.
Define the pursuers setP={P1,P2,…,Pn}. Pj has five elements Pj=〈Pp,Tp,Cp,Ep,f〉, where Pp is the position of the pursuer, indicated by (px,py); set Tp={ti∣i=1,2,…} represents the different type of the pursuer; set Cp indicates the capability of each pursuer, Cp={ci∣Tp=ti,i=1,2,…}, which embodies the characteristics of heterogeneous of different kinds of pursuers; Ep indicates the emotional intensity of the pursuers, which is a N dimensional vector Ep=(I1,I2,…,IN); f represents the value of emotional cooperation factor introduced before, which shows the willingness of the pursuer to complete its task.Definition 4.
UseG to represent the team gain after capturing an evader. After evader Ei is captured, the gain Gi of team Gpi can be calculated by the cost of pursuit Costi and reward of the task Rei, as follows:
(6)Gi=Rei-Costi.
During the pursuit, the cost of the team is mainly reflected on cost of distanceCostdi and emotional cost Costei:
(7)Costi=Costdi+Costei,
where Costdi is the sum of the distance between each team’s robots of Gpi and the target evader Ei. Supposing m is the number of the pursuers in team Gpi, the cost of distance Costdi can be written as follows:
(8)Costdi=∑j=1m(pxj-exi)2+(pyj-eyi)2.
The emotional costCostei is carried out by its mood swings. In the stage of allocation, we need to predict the number of pursuers who may have emotional risk. Firstly calculate the time tj that pursuer Pj needs to move to the evader, then estimate its emotional status after tj, and calculate the value of fj in that time; if fj<ξ, it means that this pursuer may have emotional risk; otherwise it does not. So the emotional risk of each pursuer can be represented to be as follows:
(9)Coste=a×re,
where a is the number of robots who may have emotional risk and re is the emotional risk cost.


### 3.2. Each Pursuit Team Leader Confirmed

In this paper, hybrid architecture is used to assign the pursuit task. There is a central administrator and some distributed robots in the system. The functions of central administrator include collecting information of evaders, publishing evaders’ information, receiving the bid, and authorizing contracts. The first auction is to recruit a leader for each pursuit team, who likes a practical project contractor. When the pursuers in the team are not enough, administrator takes charge of recruiting pursuers. The algorithm of recruiting team leader is as follows:(a)
The central administrator sends a recruiting message to robots, also giving them leaders’ numberNe that the central administrator needs, and then publishes the detailed information of all evaders.(b)
PursuerPj receives the message, calculates its own fj, and sends it to the central administrator.(c)
The central administrator will count the numberNp of the robots which fit fj≥ξ and then publish the leader they will recruit. After that, if Np<Ne, the administrator will send a stimulation command to each robot to update their fj. Pursuit robot Pj will accept the command and recalculate its fj and then send it to the central administrator and then back to step b; if Np≥Ne, just continue.(d)
PursuerPj checks the evader information of each pursuit task and calculates its gain, then uses each gain as a bid value, and sends it back to the central administrator.(e)
Central administrator views the tenders submitted by pursuers and selects the most appropriate pursuer based on bid values for each task, so that all team leaders have the shortest total distance to the evaders. The problem can be transformed into a classic assignment problem; the Hungarian algorithm [16] is the most appropriate.(f)
The contract was awarded to the successful pursuing robots. After the pursuers receive the contract, the contract becomes effective. So it becomes the teamGpi’s leader, and then the team is formally established.According to Definition2, different capability is needed to capture each evader. If the leader is fully capable to catch the evader, it will do it alone. Otherwise, leader with insufficient capability needs other cooperators, so it should recruit other pursuers.


### 3.3. Recruiting Cooperators

At first, each insufficient leader sends its team’s message to other free pursuers. Leader will choose appropriate members to join its team. The relative algorithm is listed below.(a)
Leaders will check whether their team’s capability meets the requirement. If not, the leader will publish team’s information to recruit collaborators including the evaders position, the capability value they still need, the reward, and the leader’s information.(b)
Free pursuerPj receives the recruitment information, calculates its fj, and sends it to the leaders with corresponding recruitment information.(c)
If the value offj is greater than ξ, which shows pursuer Pj is willing to cooperate with other robots, then the pursuer Pj count its gain as a bid value send to the leader.(d)
Leader views the tenders received and selects the most appropriate cooperators based on bid values for each team, so that all pursuit teams have the biggest total gains. The problem can also be transformed into a classic assignment problem, solved by the Hungarian algorithm [16].(e)
Each leader counts the total capabilityCgi after new cooperator attends in its team, if Cgi≥Cei, where Cei is an total capability to complete the task, the team can be established; whereas it not meet the capability requirement, the leader sends a emotional stimuli to the pursuer, then jump to step a.(f)
When all of the teams have enough capability as the task required, an allocation matrixQ will be generated and contracts will be sent from the leader to its cooperators. If some teams still need more cooperators to complete the task while there are no free robots, they must wait until the eligible robot completes its task.After the contracts are received by cooperators, the pursuit teamGp will be established.


### 3.4. Pursuit Strategy

In order to verify the effectiveness of multirobot task allocation algorithm proposed by this paper, we combine this multirobot task allocation algorithm with some pursuit algorithm to complete the pursuit task. We use the pursuit algorithm as follows.Assume that there is a virtual force field in the pursuing process. The force from pursuers to the evader is repulsion, whereas that from evader to pursuers is an attraction. The pursuers will move according to the attraction and the evader will run depending on the repulsion. We assume that the size of attraction and repulsion is related to distance. AttractionFa and repulsion Fr can be defined as follows:
(10)Fa=γ1Edi,Fr=γ(1Pd1+1Pd2+⋯+1Pdn),
where γ is scale factor; Edi is the distance from the pursuer to the evader Ei; Pdi is the distance from each pursuer in pursuit team to its own evader. Draw a unit circle which uses the position of evader to be the center of the circle and then split the circle into h parts on the circumference; the direction of the evader will be chosen from the h directions which come from the center to the h dividing points. Calculate the repulsion Fr of the evader to get to each of the divisions; choose the direction with the least repulsion Fr as the motion direction. In the same way, choose the direction with the maximum attraction Fa as the motion direction for pursuit.Definition 5.
Usefd as the capturing distance judgment factor which can predict whether evader is captured or not:
(11)fd={1,∃Edi≤κ0,∀Edi>κ,
where κ is the available distance for capture; when the distance between pursuer and evader is below κ in the same pursuit team, it means that this evader is captured.


## 3.1. Basic Definition

Definition 2.
DefineE={E1,E2,…,Em} as a set of evaders, where Ei is represented by four elements Ei=〈Pe,Te,Ce,Re〉, where Pe indicates the position of the evaders, represented by (ex,ey); Te={ti∣i=1,2,…} is the type’s set of the evader, which may have various types; set Ce={ci∣Te=ti,i=1,2,…} indicates the capability of each evader needed. Since the evaders have different types, and this means that catching evaders needs different type and different number of robots. Therefore, the key point to construct a pursuit team is to decide the number and the relative types of the pursuers. Define the reward after completing a pursuit task, Re={ri∣Te=ti,i=1,2,…}. The pursuer can gain different reward to capture a different type of evaders.Definition 3.
Define the pursuers setP={P1,P2,…,Pn}. Pj has five elements Pj=〈Pp,Tp,Cp,Ep,f〉, where Pp is the position of the pursuer, indicated by (px,py); set Tp={ti∣i=1,2,…} represents the different type of the pursuer; set Cp indicates the capability of each pursuer, Cp={ci∣Tp=ti,i=1,2,…}, which embodies the characteristics of heterogeneous of different kinds of pursuers; Ep indicates the emotional intensity of the pursuers, which is a N dimensional vector Ep=(I1,I2,…,IN); f represents the value of emotional cooperation factor introduced before, which shows the willingness of the pursuer to complete its task.Definition 4.
UseG to represent the team gain after capturing an evader. After evader Ei is captured, the gain Gi of team Gpi can be calculated by the cost of pursuit Costi and reward of the task Rei, as follows:
(6)Gi=Rei-Costi.
During the pursuit, the cost of the team is mainly reflected on cost of distanceCostdi and emotional cost Costei:
(7)Costi=Costdi+Costei,
where Costdi is the sum of the distance between each team’s robots of Gpi and the target evader Ei. Supposing m is the number of the pursuers in team Gpi, the cost of distance Costdi can be written as follows:
(8)Costdi=∑j=1m(pxj-exi)2+(pyj-eyi)2.
The emotional costCostei is carried out by its mood swings. In the stage of allocation, we need to predict the number of pursuers who may have emotional risk. Firstly calculate the time tj that pursuer Pj needs to move to the evader, then estimate its emotional status after tj, and calculate the value of fj in that time; if fj<ξ, it means that this pursuer may have emotional risk; otherwise it does not. So the emotional risk of each pursuer can be represented to be as follows:
(9)Coste=a×re,
where a is the number of robots who may have emotional risk and re is the emotional risk cost.


## 3.2. Each Pursuit Team Leader Confirmed

In this paper, hybrid architecture is used to assign the pursuit task. There is a central administrator and some distributed robots in the system. The functions of central administrator include collecting information of evaders, publishing evaders’ information, receiving the bid, and authorizing contracts. The first auction is to recruit a leader for each pursuit team, who likes a practical project contractor. When the pursuers in the team are not enough, administrator takes charge of recruiting pursuers. The algorithm of recruiting team leader is as follows:(a)
The central administrator sends a recruiting message to robots, also giving them leaders’ numberNe that the central administrator needs, and then publishes the detailed information of all evaders.(b)
PursuerPj receives the message, calculates its own fj, and sends it to the central administrator.(c)
The central administrator will count the numberNp of the robots which fit fj≥ξ and then publish the leader they will recruit. After that, if Np<Ne, the administrator will send a stimulation command to each robot to update their fj. Pursuit robot Pj will accept the command and recalculate its fj and then send it to the central administrator and then back to step b; if Np≥Ne, just continue.(d)
PursuerPj checks the evader information of each pursuit task and calculates its gain, then uses each gain as a bid value, and sends it back to the central administrator.(e)
Central administrator views the tenders submitted by pursuers and selects the most appropriate pursuer based on bid values for each task, so that all team leaders have the shortest total distance to the evaders. The problem can be transformed into a classic assignment problem; the Hungarian algorithm [16] is the most appropriate.(f)
The contract was awarded to the successful pursuing robots. After the pursuers receive the contract, the contract becomes effective. So it becomes the teamGpi’s leader, and then the team is formally established.According to Definition2, different capability is needed to capture each evader. If the leader is fully capable to catch the evader, it will do it alone. Otherwise, leader with insufficient capability needs other cooperators, so it should recruit other pursuers.


## 3.3. Recruiting Cooperators

At first, each insufficient leader sends its team’s message to other free pursuers. Leader will choose appropriate members to join its team. The relative algorithm is listed below.(a)
Leaders will check whether their team’s capability meets the requirement. If not, the leader will publish team’s information to recruit collaborators including the evaders position, the capability value they still need, the reward, and the leader’s information.(b)
Free pursuerPj receives the recruitment information, calculates its fj, and sends it to the leaders with corresponding recruitment information.(c)
If the value offj is greater than ξ, which shows pursuer Pj is willing to cooperate with other robots, then the pursuer Pj count its gain as a bid value send to the leader.(d)
Leader views the tenders received and selects the most appropriate cooperators based on bid values for each team, so that all pursuit teams have the biggest total gains. The problem can also be transformed into a classic assignment problem, solved by the Hungarian algorithm [16].(e)
Each leader counts the total capabilityCgi after new cooperator attends in its team, if Cgi≥Cei, where Cei is an total capability to complete the task, the team can be established; whereas it not meet the capability requirement, the leader sends a emotional stimuli to the pursuer, then jump to step a.(f)
When all of the teams have enough capability as the task required, an allocation matrixQ will be generated and contracts will be sent from the leader to its cooperators. If some teams still need more cooperators to complete the task while there are no free robots, they must wait until the eligible robot completes its task.After the contracts are received by cooperators, the pursuit teamGp will be established.


## 3.4. Pursuit Strategy

In order to verify the effectiveness of multirobot task allocation algorithm proposed by this paper, we combine this multirobot task allocation algorithm with some pursuit algorithm to complete the pursuit task. We use the pursuit algorithm as follows.Assume that there is a virtual force field in the pursuing process. The force from pursuers to the evader is repulsion, whereas that from evader to pursuers is an attraction. The pursuers will move according to the attraction and the evader will run depending on the repulsion. We assume that the size of attraction and repulsion is related to distance. AttractionFa and repulsion Fr can be defined as follows:
(10)Fa=γ1Edi,Fr=γ(1Pd1+1Pd2+⋯+1Pdn),
where γ is scale factor; Edi is the distance from the pursuer to the evader Ei; Pdi is the distance from each pursuer in pursuit team to its own evader. Draw a unit circle which uses the position of evader to be the center of the circle and then split the circle into h parts on the circumference; the direction of the evader will be chosen from the h directions which come from the center to the h dividing points. Calculate the repulsion Fr of the evader to get to each of the divisions; choose the direction with the least repulsion Fr as the motion direction. In the same way, choose the direction with the maximum attraction Fa as the motion direction for pursuit.Definition 5.
Usefd as the capturing distance judgment factor which can predict whether evader is captured or not:
(11)fd={1,∃Edi≤κ0,∀Edi>κ,
where κ is the available distance for capture; when the distance between pursuer and evader is below κ in the same pursuit team, it means that this evader is captured.


## 4. Experiments

### 4.1. Relevant Parameters Setting

In the experiments, we letN=3 and select dread, anger, and joy as three kinds of emotion as a basic emotion. According to the paper [11], we get the transformation matrix from basic emotion to PAD emotion model which showed the following:
(12)Mt=[-0.640.60-0.43-0.510.590.250.400.200.15].From the paper [14], we find that “dominance” in the PAD model has the maximum impact on emotional cooperation factor, “pleasure” follows, and “arousal” has the minimal impact. Therefore, respectively, set w1=0.2, w2=0.1, w3=0.7. With the passage of time, emotional intensity infinitely tends to zero, so we select ξ=0.001. The pursuer is not willing to participate in pursuit, when f<0.001. On the contrary (f>0.001), it means the pursuer is willing to finish the task.Definen=12, m=4, so 12 pursuers pursue 4 evaders and produce the initial position of evaders and pursuers t in the 100×100 square area. In order to determine the influence of emotional decay factor k experiments, we have randomly done 1200 sets of experiments without emotional decay; the experimental results are shown in Figure 1.Figure 1
1200 sets of experiments without emotional decay.From Figure1, the total cost time of pursuit from 20 to 30 seconds is more intensive, so we randomly select 100 sets of data from the 1200 sets of initial data which obtained from above experiments, then use the 100 sets of data for the next experiments. For the following experiment, suppose emotional decay types of robots were the same in all experiments; namely, emotion decay factor k was the same. Set T=0.1, so check the emotional status of pursuit robot every 0.1 second. When the value of φ(k) is too small, emotional decay will be too fast, not conducive to experiment, so the value of φ(k) is fixed between 0.5 and 1. Using the 100 groups’ initial data, experiments are carried out under different values of k; then obtain the total cost time of pursuit; finally, calculate the average time to finish all pursuits by different φ(k). Result is shown in Figure 2.Figure 2
The effect ofφ(k) on pursuing time.Figure2 shows that when the value of φ(k) is between 0.5 and 0.85, average time has larger effect by φ(k). With the increase of φ(k), average time shows a trend of increase, but it has greater volatility. When φ(k) is between 0.85 and 0.93, pursuit time decreases and φ(k) decays obviously. When the value of φ(k) is between 0.93 and 1, it has little effect on pursuit time. To ensure the stability of experiment and reflect the impact of φ(k) to pursuit time, we control the value of φ(k) between 0.85 and 0.93, so set φ(k)=0.87, so emotional decay factor k=1.39.In the pursuit strategy, the forces of attraction and repulsion are just the parameter to determine the motion direction for evaders and pursuers, whose value is too large or too small having no effect on determining the actual motion direction. In order to simplify the experiment we setγ=1. Choose h=36; evaders select the direction that will produce the smallest repulsive force. Take κ=0.8; when the distance between pursuit robot and evader is less than or equal to 0.8 m, that means the evader has been captured.


### 4.2. Experiment and Data Analysis

To verify the effectiveness of the algorithm in this paper, we have made a comparison with the method of instantaneous greedy optimal auction algorithm [17]. The 200 experiments are designed under the same scene. As Figures 3 and 4 show, comparing with instantaneous optimal auction greedy algorithm in the same scenario, 86.5% total time of pursuit can be shortened and 77.5% total gain is higher. When use instantaneous greedy optimal auction algorithm to establish the pursuit teams, all robots are self-interested, so every robot would like to choose joining the team which gives itself the greatest gain, thus self-interested robots may lead to part of teams’ capacity excess and another part of teams lack of capacity, it is not conducive to pursuit task allocation. In our algorithm, all pursuers have emotions, and they consider personal gain while taking into account the global gain for pursuit team. At the stage of pursuit task allocation, when pursuers meet conflict between global gain and their own gain, in order to obtain greater global gain they will sacrifice their own gain. So our algorithm can optimize the total pursuing time and global gains. Analyzing the experiments with poor total pursuit time or global gains, we found that the initial position of robots is very favorable to instantaneous greedy optimal auction algorithm.Figure 3
The comparison chart of total cost time of pursuit.Figure 4
The comparison chart of total gain for pursuing teams.


## 4.1. Relevant Parameters Setting

In the experiments, we letN=3 and select dread, anger, and joy as three kinds of emotion as a basic emotion. According to the paper [11], we get the transformation matrix from basic emotion to PAD emotion model which showed the following:
(12)Mt=[-0.640.60-0.43-0.510.590.250.400.200.15].From the paper [14], we find that “dominance” in the PAD model has the maximum impact on emotional cooperation factor, “pleasure” follows, and “arousal” has the minimal impact. Therefore, respectively, set w1=0.2, w2=0.1, w3=0.7. With the passage of time, emotional intensity infinitely tends to zero, so we select ξ=0.001. The pursuer is not willing to participate in pursuit, when f<0.001. On the contrary (f>0.001), it means the pursuer is willing to finish the task.Definen=12, m=4, so 12 pursuers pursue 4 evaders and produce the initial position of evaders and pursuers t in the 100×100 square area. In order to determine the influence of emotional decay factor k experiments, we have randomly done 1200 sets of experiments without emotional decay; the experimental results are shown in Figure 1.Figure 1
1200 sets of experiments without emotional decay.From Figure1, the total cost time of pursuit from 20 to 30 seconds is more intensive, so we randomly select 100 sets of data from the 1200 sets of initial data which obtained from above experiments, then use the 100 sets of data for the next experiments. For the following experiment, suppose emotional decay types of robots were the same in all experiments; namely, emotion decay factor k was the same. Set T=0.1, so check the emotional status of pursuit robot every 0.1 second. When the value of φ(k) is too small, emotional decay will be too fast, not conducive to experiment, so the value of φ(k) is fixed between 0.5 and 1. Using the 100 groups’ initial data, experiments are carried out under different values of k; then obtain the total cost time of pursuit; finally, calculate the average time to finish all pursuits by different φ(k). Result is shown in Figure 2.Figure 2
The effect ofφ(k) on pursuing time.Figure2 shows that when the value of φ(k) is between 0.5 and 0.85, average time has larger effect by φ(k). With the increase of φ(k), average time shows a trend of increase, but it has greater volatility. When φ(k) is between 0.85 and 0.93, pursuit time decreases and φ(k) decays obviously. When the value of φ(k) is between 0.93 and 1, it has little effect on pursuit time. To ensure the stability of experiment and reflect the impact of φ(k) to pursuit time, we control the value of φ(k) between 0.85 and 0.93, so set φ(k)=0.87, so emotional decay factor k=1.39.In the pursuit strategy, the forces of attraction and repulsion are just the parameter to determine the motion direction for evaders and pursuers, whose value is too large or too small having no effect on determining the actual motion direction. In order to simplify the experiment we setγ=1. Choose h=36; evaders select the direction that will produce the smallest repulsive force. Take κ=0.8; when the distance between pursuit robot and evader is less than or equal to 0.8 m, that means the evader has been captured.


## 4.2. Experiment and Data Analysis

To verify the effectiveness of the algorithm in this paper, we have made a comparison with the method of instantaneous greedy optimal auction algorithm [17]. The 200 experiments are designed under the same scene. As Figures 3 and 4 show, comparing with instantaneous optimal auction greedy algorithm in the same scenario, 86.5% total time of pursuit can be shortened and 77.5% total gain is higher. When use instantaneous greedy optimal auction algorithm to establish the pursuit teams, all robots are self-interested, so every robot would like to choose joining the team which gives itself the greatest gain, thus self-interested robots may lead to part of teams’ capacity excess and another part of teams lack of capacity, it is not conducive to pursuit task allocation. In our algorithm, all pursuers have emotions, and they consider personal gain while taking into account the global gain for pursuit team. At the stage of pursuit task allocation, when pursuers meet conflict between global gain and their own gain, in order to obtain greater global gain they will sacrifice their own gain. So our algorithm can optimize the total pursuing time and global gains. Analyzing the experiments with poor total pursuit time or global gains, we found that the initial position of robots is very favorable to instantaneous greedy optimal auction algorithm.Figure 3
The comparison chart of total cost time of pursuit.Figure 4
The comparison chart of total gain for pursuing teams.


## 5. Conclusions

In this paper we have a deep research about self-interested robots, such as the ability of self-interested robots, the individual cooperative willingness of robots in different situations, and the changes of individual cooperative willingness during executing tasks. We proposed a multirobot pursuit task allocation algorithm based on emotional cooperation factor. In order to measure individual cooperative willingness of self-interested robot in multirobot task allocation problem, emotional cooperation factor, a value updated based on emotional attenuation and external stimuli in the process of pursuit is introduced into emotional robot. By using two steps of auction for allocation, several subteams and their leaders and cooperators are selected and then choose a certain pursuit strategy to complete pursuit task. As the experiment shows, our algorithm optimizes the cost of pursuit time and total team’s gain, as well as proving the effectiveness.



---

*Source: 864180-2014-07-23.xml*