# Modeling of Task Planning for Multirobot System Using Reputation Mechanism

Authors: Zhiguo Shi; Jun Tu; Yuankai Li; Junming Wei
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Modeling of task planning for multirobot system is developed from two parts: task decomposition and task allocation. In the part of task decomposition, the conditions and processes of decomposition are elaborated. In the part of task allocation, the collaboration strategy, the framework of reputation mechanism, and three types of reputations are defined in detail, which include robot individual reputation, robot group reputation, and robot direct reputation. A time calibration function and a group calibration function are designed to improve the effectiveness of the proposed method and proved that they have the characteristics of time attenuation, historical experience related, and newly joined robot reward. Tasks attempt to be assigned to the robot with higher overall reputation, which can help to increase the success rate of the mandate implementation, thereby reducing the time of task recovery and redistribution. Player/Stage is used as the simulation platform, and three biped-robots are established as the experimental apparatus. The experimental results of task planning are compared with the other allocation methods. Simulation and experiment results illustrate the effectiveness of the proposed method for multi-robot collaboration system.


---

## Body

## 1. Introduction

The field of distributed robotics started in the late 1980s, when several researchers began investigating issues in multiple mobile robot systems. Prior to this time, researches had concentrated on either single robot systems or distributed problem-solving systems that did not involve robotic components [1]. In the early distributed robotics work, the topics of particular interest include  (
1
) cellular (or reconfigurable) robot systems, such as cellular robotic system [2] and cyclic swarms [3]; (
2
) multirobot motion planning, such as traffic control [4] and movement in formation [5]; (
3
) architectures for multirobot collaboration, such as ACTRESS [6]. Also, literatures on other particular topics, such as robot colonies [7] and heterogeneous multirobot systems [8], have been published.In recent years, multirobot systems research has made great progress in many areas [9]. Issues of multirobot system [10] include biological inspirations, communication, architectures, localization/mapping/exploration, object transport and manipulation, motion coordination and formation [11, 12], reconfigurable robots, and learning.Collaboration is an important characteristic and a major evaluation indicator for multirobot systems [6]. Multirobot systems can complete the mission through collaboration which a single robot cannot achieve. It is not the linear summation of the role of single robot but includes the individual-based interactively incremental besides the linear summation, which increases the overall performance [13].Task planning includes two aspects [9]: task decomposition and task allocation. Presently, task planning system has been widely used in the space shuttle satellites, pilotless aircraft, and so forth. The research of multirobot systems is closely related to the distributed artificial intelligence, which consists of two main areas of research: distributed problem solving (DPS) and multiagent systems. DPS mainly focuses on how to decompose a particular problem and how to solve the problem among multiple agents, including three main aspects, which are problem decomposition, subproblem solving, and synthesis of the findings.In the task decomposition and distribution research, there are several traditional methods: Contract Net Mechanism [14], Local/Global Planning [15], Distributed Searching, and Joint Intentions. Contract Net Protocol is an important noncentralized task decomposition and distribution model in distributed artificial intelligence.The traditional task allocation is mainly based on contract net protocol (CNP) [14], which can provide the solution for the issues by consulting to avoid conflict. Parker [16] developed a behavior-based distributed multirobot collaboration structure named L-ALLICANCE and the corresponding system with the capability of parameters learning named L2-ALLICANCE [17] in MIT. The system utilizes an incentive-based task allocation mechanism for behavior and enhances the generalization and error tolerance of multirobot system. Parker also proposed a behavior-based task allocation mechanism named ASyMTRe [18].Gerkey applied the market algorithm in multirobot system to deal with dynamic task allocation problem named MURDOCH [19]. The market mechanism in task allocation is based on consultations. The robots complete the task assigned through mutual consultation and negotiation on the basis of certain agreement in multirobot system.However, the task allocation methods have their limitations to some extent. Behavior-based task allocation mechanism does not take into account the influence of collaboration history, while market-mechanism-based task allocation does not fully consider the impact of the time factor, leading to poor robustness.In addition, the topics of multirobot search and rescue, cooperative localization, motion coordination, and formation control attract a lot of researchers in the fields of robot collaboration system [20]. Collaboration optimization method, including linear programming method and the Hungarian algorithm [21], can be applied to solve simple tasks and robot collaboration optimization problems. But when the number of robots and tasks increases in the system, the computational complexity will increase exponentially.In this paper, a task planning method based on reputation mechanism is proposed. Reputation plays an important role in the collaboration among people. In many cases, task allocation is based on someone’s reputation, which is gained from the evaluation of the completion of historical tasks. Reputation theory is attracting interest from industrial and academic research communities and increasingly being integrated with online services and applications, especially in network computing system.Reputation of robots is the overall assessment and the summary of past actions observed from one robot to another through the gradual dynamic capabilities in a continuous interactive process. The assessment can be used to guide further actions of the robot. Reputation includes five attributes:(
1
) the related characteristics of environmental context, (
2
) dynamic characteristics of changing over time, (
3
) time lag characteristics of forming through the continuous learning and historical experience, (
4
) group characteristics of being affected by the group or alliance of the robot, and (
5
) incentive and reward mechanism. The robot with good reputation should be rewarded in task allocation. Otherwise, it should be punished.The rest of the paper is organized into four sections as follows: the system structure and basic concepts are presented in Section2. The modeling of task planning using reputation mechanism is proposed in Section 3. Simulation and experimental results are shown in Section 4, and concluding remarks are in Section 5.


## 2. Basic Concepts and System Structure

Task planning consists of two parts: decomposition and allocation. Task allocation in the multirobot system is divided into two categories: direct allocation and delegation allocation. Direct allocation is to assign a task to robot that can provide collaboration directly. If the robot cannot complete the assigned task, the assigned task can be delegated to other robots. The task can be further delegated if needed.The periodical constraint is utilized to guarantee the time effectiveness of task allocation. (t
b, t
e) is a periodical constraint from t
b to t
e, which means that the task allocation is valid in the period from the time t
b to t
e. If a task cannot be accomplished in the arranged time, it will be withdrawn, which can improve the performance of the system. A typical collaboration system is shown in Figure 1.Figure 1
Robot collaboration system.In Figure1, there are two cooperative groups. Tasks can be assigned by direct allocation or indirect delegation.In the robot reputation system, robot reputation level (RRL) is proposed to quantify the reputation of each robot, which is based on the historical experience and the overall evaluation of the system. “0” and “1” are used to quantize the reputation value. “0” represents the lowest reputation and “1” represents the highest reputation. The symbol of robots group is indicated asD. The value on the line from robot R
1 to robot R
2 is the direct reputation from R
1 to R
2, and the individual reputation value of the robot R
1 is the value on the robot, shown in Figure 2.Figure 2
Reputation of the robot collaboration system.In Figure2, the reputation of the group is the value beside the name of the group; for example, the reputation of group D
1 is 0.5. The reputation of robots in the collaboration system consists of three parts: (
1
) the individual reputation; (
2
) the group’s reputation where the robot belongs to; (
3
) the reputation between the two robots intending to cooperate.


## 3. Task Planning Using Reputation Mechanism

In this section, task planning is divided into two parts: task decomposition and task allocation. Firstly, the condition and process of the task decomposition are presented. Secondly, task allocation using reputation mechanism is defined and presented in detail.


### 3.1. Task Decomposition

A task can be decomposed if it meets certain conditions. Four task decomposition conditions are given in [22]. If the task can be decomposed and is assignable, the formal definition of automata is as follows.An automata is a tupleA
=
(
Q
,
q
0
,
E
,
δ
,
F
), consisting of a set of states Q; the initial state q
0; a set of events E that causes transitions between the states; a transition relation δ; F is the acceptable states set. s
=
a
0
a
1
⋯
a
n
-
1
∈
E
* is a finite alphabet and a sequence q
0
,
q
1
,
…
,
q
n of n
+
1 states in Q, and q
0
∈
Q
0, q
i
+
1
∈
δ
(
q
i
,
a
i
).The parallel composition ofA
1 and A
2 is the automaton A
1
∥
A
2
=
(
Q
,
q
0
,
E
,
δ
), defined as follows:
(1)
Q
=
Q
1
×
Q
2
;
q
0
=
(
q
1
0
,
q
2
0
)
;
E
=
E
1
∪
E
2
;
∀
(
q
1
,
q
2
)
∈
Q
,
e
∈
E
δ
(
(
q
1
,
q
2
)
,
e
)
=
{
δ
1
(
q
1
,
e
)
,
δ
2
,
(
q
2
,
e
)
if
δ
1
(
q
1
,
e
)
,
δ
2
,
(
q
2
,
e
)
,
e
∈
E
1
∩
E
2
(
δ
1
(
q
1
,
e
)
,
q
2
)
if
δ
1
(
q
1
,
e
)
!
,
e
∈
E
1
∖
E
2
(
q
1
,
δ
2
(
q
2
,
e
)
)
if
δ
2
(
q
2
,
e
)
!
,
e
∈
E
2
∖
E
1
ϕ
otherwise
.The natural projections ofA
S in local event sets E
i is obtained as P
i (A
S), merging the events-related states which belong to the event sets E
/
E
i.(
1) Decomposition Condition 1
(2)
∀
e
1
,
e
2
∈
E
,
q
∈
Q
[
δ
(
q
,
e
1
)
!
∧
δ
(
q
,
e
2
)
!
]
⟹
[
∃
E
i
∈
{
E
1
,
…
,
E
n
}
,
{
e
1
,
e
2
}
⊆
E
i
]
∨
[
δ
(
q
,
e
1
e
2
)
!
∧
δ
(
q
,
e
2
e
1
)
!
]
,
where, e
1, and e
2 are events; E is a set of total events; local event sets E
i; a set of states Q; a transition relation δ; If state q is reachable under events e
1, e
2 that means existing a local events E
i which contains events e
1, e
2, making the state q remain reachable under the event sequence e
1
e
2 and e
2
e
1.(
2) Decomposition Condition 2
(3)
∀
e
1
,
e
2
∈
E
,
q
∈
Q
,
s
∈
E
*
[
δ
(
q
,
e
1
e
2
s
)
!
∨
δ
(
q
,
e
2
e
1
s
)
!
]
⟹
[
∃
E
i
∈
{
E
1
,
…
,
E
n
}
,
{
e
1
,
e
2
}
⊆
E
i
]
∨
[
δ
(
q
,
e
1
e
2
s
)
!
∧
δ
(
q
,
e
2
e
1
s
)
!
]
,
where E
* is sequence of events. If the state q is reachable under the event sequence e
1
e
2 or e
2
e
1, it can launch a local existing events E
i, which contains events e
1, e
2, making the state q remain reachable under the event sequence e
1
e
2
s and e
2
e
1
s.(
3) Decomposition Condition 3
(4)
δ
(
q
0
,
|
i
=
1
n
p
i
(
s
i
)
)
!
,
∀
{
s
1
,
…
,
s
n
}
∈
L
~
(
A
S
)
,
dddddddd
∃
s
i
,
s
j
∈
{
s
1
,
…
,
s
n
}
,
s
i
≠
s
j
,
where L
~
(
A
S
)
⊆
L
(
A
S
) and L
~
(
A
S
) are the biggest subset of L
(
A
S
)  for
all
s
∈
L
~
(
A
S
), ∃
s
′
∈
L
~
(
A
S
), ∃
E
i
,
E
j
∈
{
E
1
,
…
,
E
n
}, i
≠
j can launch p
E
i
∩
E
i
(
s
) and p
E
i
∩
E
i
(
s
′
), beginning with the same event. L
(
A
S
) is the set of all sequences of events of automaton A
S; L
~
(
A
S
) is the set of the sequences of events of automata A
S; the natural projections of the ith local event set in the corresponding sequence of events s
i.(
4) Decomposition Condition 4
(5)
∀
i
∈
{
1
,
…
,
n
}
,
x
·
x
1
·
x
2
∈
Q
i
,
x
1
≠
x
2
,
e
∈
E
i
,
t
∈
E
i
*
,
δ
i
(
x
,
e
)
=
x
1
,
δ
i
(
x
,
e
)
=
x
2
δ
i
(
x
1
,
t
)
!
⟺
δ
i
(
x
2
,
t
)
!
.Formal linear temporal logic language is used to present the whole tasks of the robot system, which is almost the same with the natural language in structure.Several temporal operators of task decomposition are presented as follows [22]:(i)
next state “ο”: requires that a property hold in the next state of the path;
(ii)
until “∪”: used to combine two properties. The combined property holds if there is a state on the path where the second property hold, and at every preceding state on the path, the first property holds;
(iii)
eventually “⋄”: used to assert that a property will hold at some future state on the path;
(iv)
always “□”: specifies that a property holds at every state on the path. Such as: E
=
{
E
1
,
E
2
,
…
,
E
n
}.The reachability while avoiding some events:¬
(
E
1
∨
E
2
)
∪
E
3
Sequence:⋄
(
E
1
∧
⋄
(
E
2
∧
⋄
E
3
)
)
Coverage:⋄
E
1
∧
⋄
E
2
∧
⋄
E
3
Recurrence:□
(
⋄
E
1
∧
⋄
E
2
∧
⋄
E
3
).The equivalent task automataA
S can be transformed from the formula. The natural projections of A
S to local event sets E
i are obtained as P
i (A
S). Linear temporal logic and automata have a close relationship, which can be directly exported from linear temporal logic formula, because every linear temporal logic formula consists of connectors and temporal operators.


### 3.2. Reputation Mechanism

The negotiation process of the robot collaboration system is presented, which mainly is concerned about how to build partnerships between the collaborative robots according to the reputation mechanism.Definition 1 (robot initialization set).
The robot initialization setI is identified as 〈
κ
I
,
E
I
,
CHA
P
I
,
A
C
I
〉, where κ denotes the ontology of collaboration robot, which can get the identification corresponding to κ; E
⊂
ε is an identification set, these identification sets are issued to κ in I. CHAP:
τ
→
P is a partial order function, mapping a finite subset of attributes to the strategy set. The properties of CHAP are called limited properties. For the limited property t, CHAP[t] is called the verification strategy of t. AC:
R
→
P is a partial order function, mapping resources to a finite strategy set.Definition 2 (robot collaboration strategy).
A collaboration strategy is defined as a quintuple〈
Q
,
M
,
ini
t
R
,
star
t
M
,
reply
〉, where Q is the finite set of the collaboration process state, each state denoted by q, and, q
∈
Q; M is the finite set of the collaboration process messages. The massage is denoted by m and usually consists of subscripts. The message sequences can be denoted as m
1
,
…
,
m
n. The function ini
t
R: I
×
k
→
Q defines the initial state of the requester. When the initialization set and requesting robot are given, this state is ini
t
R
(
I
,
K
R
)
=
q, where q
∉
{
success
,
failure
}. star
t
M: I
×
Res
×
k
→
Q
×
M defines that the collaboration is started by a requested robot. The function reply: Q
×
M
→
Q
×
M defines each action of the robot. When the robot initialization set I, current state q and the latest message m from the other side are given, reply
(
q
,
m
)
=
〈
q
′
,
m
′
〉.Definition 3 (framework of reputation mechanism).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to,   t denotes the time of collaboration and l denotes the specific group. The collaboration relationship from R
1 to R
2 is expressed as Γ
(
R
1
,
R
2
,
t
,
c
,
l
):(6)
Γ
(
R
1
,
R
2
,
t
,
l
,
c
)
=
α
×
Θ
(
R
1
,
R
2
,
t
,
l
,
c
)
+
β
×
Ω
(
R
2
,
t
,
l
,
c
)
+
θ
×
Ψ
(
D
1
,
D
2
,
t
,
c
)
,
where Θ
(
R
1
,
R
2
,
t
,
l
,
c
) denotes the direct reputation between robot R
1 and robot R
2. α denotes the direct reputation weight coefficient, 0
≤
α
≤
1. Ω
(
R
2
,
t
,
l
,
c
) denotes the individual reputation value of robot R
2; β is the reputation weight coefficient. 0
≤
β
≤
1. Ψ
(
D
1
,
D
2
,
t
,
c
) denotes the reputation value from the robot group D
1 to the group D
2. θ denotes the group weight coefficient, 0
≤
θ
≤
1, α
+
β
+
θ
=
1, α
,
β
,
θ
≥
0.Definition 4 (direct reputation).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to. The direct reputation from R
1 to R
2 is presented as
(7)
Θ
(
R
1
,
R
2
,
t
,
l
,
c
)
=
DRM
(
R
1
,
R
2
,
t
,
c
)
×
γ
(
t
-
t
a
-
b
,
c
)
×
τ
(
l
a
,
l
b
,
c
)
,
where the definition of DRM (Direct Reputation Matrix) can be seen in Definition 7. t
a
-
b denotes the last collaboration time between R
1 and R
2; γ
(
t
-
t
a
-
b
,
c
) denotes the function of time calibration; τ
(
l
a
,
l
b
,
c
) denotes the function of group calibration function; and γ
(
t
-
t
a
-
b
,
c
) denotes the time calibration function.Definition 5 (individual reputation).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to. The individual reputation of robot R
2 in the collaboration system is presented as
(8)
Ω
(
R
2
,
t
,
l
,
c
)
=
1
n
∑
i
=
1
n
S
(
ρ
i
+
Γ
i
(
R
i
,
R
2
,
t
,
l
,
c
)
)
55555
j
×
γ
(
t
-
t
z
i
-
b
,
c
)
×
τ
(
l
z
i
,
l
b
,
c
)
,
where S
(
ρ
i
+
Γ
i
(
R
i
,
R
2
,
t
,
l
,
c
)
) denotes the function of the reputation calibration; ρ
i denotes the standard deviation of reputation value at the No. i collaboration; λ
(
t
-
t
z
i
-
b
,
c
) denotes the function of time calibration; τ
(
l
z
i
,
l
b
,
c
) denotes the function of group calibration function; and n denotes the number of robots in the collaboration system who is cooperating with robot R
2.Definition 6 (group reputation).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to. Group reputation in the collaboration system is
(9)
Ψ
(
D
1
,
D
2
,
t
,
c
)
=
Ψ
(
D
1
,
D
2
,
t
a
-
b
,
c
)
×
γ
(
t
-
t
a
-
b
,
c
)
,
where Ψ
(
D
1
,
D
2
,
t
a
-
b
,
c
) denotes the group reputation value of the last collaboration between the group D
1 and the group D
2. γ
(
t
-
t
a
-
b
,
c
) denotes the function of time calibration.Definition 7 (direct reputation matrix (DRM)).
If the cooperative system is composed byn robots, DRM will be n
*
n matrix. Direct reputation value Θ
(
R
1
,
R
2
,
t
,
l
,
c
), Θ
∈
[
0,1
]. For example, there are 26 robots in the collaboration system, named from R
A to R
Z, the DRM of which is the following matrix:
(10)

[
1

Θ
(
R
A
,
R
B
,
t
,
l
,
c
)
⋯
Θ
(
R
A
,
R
Z
,
t
,
l
,
c
)

Θ
(
R
B
,
R
A
,
t
,
l
,
c
)

1
⋯
Θ
(
R
B
,
R
Z
,
t
,
l
,
c
)

⋯

⋯
⋯
⋯

Θ
(
R
Z
,
R
A
,
t
,
l
,
c
)

Θ
(
R
Z
,
R
B
,
t
,
l
,
c
)
⋯
1

]


.Definition 8 (time calibration function).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to.   t
a
-
b denotes the last collaboration time between robot R
1 and robot R
2. The time calibration function can be expressed as
(11)
γ
(
t
,
c
)
=
k
0
γ
(
t
a
-
b
,
c
)
+
k
1
e
-
k
(
t
-
t
a
-
b
)
(
t
-
t
a
-
b
T
r
+
)
S
-
k
2
e
-
k
(
t
-
t
a
-
b
)
(
t
-
t
a
-
b
T
r
-
)
(
S
-
1
)
-
k
3
(
1
-
e
-
k
(
t
-
t
a
-
b
)
)
γ
(
t
a
-
b
,
c
)
,
where k
0 denotes the history experience coefficient, generally, k
0
=
1. k
1 denotes the reputation reward coefficient. e
-
k
(
t
-
t
a
-
b
) denotes the correction operator. k
2 denotes the reputation penalty coefficient. r
+ denotes the incentive ratio in time T. r
- denotes the penalty ratio in time T. S denotes validation coefficient of the collaboration, if the assigned task is successfully finished, S
=
1; otherwise S
=
0. k
3 denotes the attenuation coefficient.
If the robot does not take any assigned task, its reputation will diminish as the time went on. The coefficients is satisfied with0
<
k
0
,
k
1
,
k
2
,
k
3
≤
1, k
>
0.
Characteristic 1(time attenuation). With no compensation, the proposition will be proved if γ
(
t
1
)
>
γ
(
t
2
), when t
1
<
t
2
(12)
γ
(
t
1
,
c
)
=
k
0
γ
(
t
0
,
c
)
-
k
3
(
1
-
e
-
k
(
t
1
-
t
0
)
)
γ
(
t
0
,
c
)
,
γ
(
t
2
,
c
)
=
k
0
γ
(
t
0
,
c
)
-
k
3
(
1
-
e
-
k
(
t
2
-
t
0
)
)
γ
(
t
0
,
c
)
,
γ
(
t
1
,
c
)
-
γ
(
t
2
,
c
)
=
k
3
γ
(
t
0
,
c
)
(
e
-
k
(
t
1
-
t
0
)
-
e
-
k
(
t
2
-
t
0
)
)
,
where k
3
γ
(
t
0
)
>
0 and t
1
<
t
2, so the equation above is greater than 0; therefore, the proposition may be established. In the process of collaboration, if no compensation, the value of the function will be decreased.
Characteristic 2 (natural attenuation curve). Generally, k
0 is 1. The value of (11) is related to k and k
3. Taking that k
>
0
,
0
<
k
3
≤
1, a different set of curves will be obtained, which are called the attenuation curves.
The curve, whenk
=
0.2, k
3
=
0.5, is defined as the natural attenuation curve. Assuming that the initial value k
0
γ
(
t
0
,
c
)
=
1, k
3 = 0.5 could be the case, k is 0.1, 0.2, 0.3, and 0.4, respectively.
Characteristic 3 (historical experience related). Assuming that (11) do not have the characteristics of historical relevance, in the absence of natural attenuation as well as under the circumstances of no penalty and award compensation, reputation will have nothing to do with the historical experience. Then k
0
γ
(
t
a
-
b
,
c
)
=
0, because γ
(
t
a
-
b
,
c
) is not equal to zero, so k
0
=
0, which is conflicted with k
0
≠
0. Therefore, the assumption is wrong; that is, (11) is historical experience related.Definition 9 (group calibration function).
Giving thatl
a denotes the group where robot R
1 belongs to, l
b denotes the group where robot R
2 belongs to, c denotes the environment context, the group calibration function is expressed as
(13)
τ
(
l
a
,
l
b
,
c
)
=
{
m
0
1
+
m
1
(
Ω
D
1
+
Ω
D
2
)
/
2
l
a
≠
l
b
1
l
a
=
l
b
.
IfΩ
D
1
=
NULL or Ω
D
2
=
NULL, then τ
(
l
a
,
l
b
,
c
)
∈
[
0.5
–
0.8
]. 0
<
m
0
≤
1, 0
<
m
1
≤
1, m
0 denotes the positive coefficient, m
1 denotes the negative coefficient. The typical parameters of groups are given in Table 1.Table 1
Typical group parameters.
Loyalty
Honesty
Improvement
Randomization
m
1
0–0.1
0.1–0.2
0.2–0.3
0.4–0.6
m
0
0.9–0.99
0.8–0.9
0.7–0.8
0.5–0.7
Concealment
Tricky
Corruption
Deceivement
m
1
0.6–0.7
0.7–0.8
0.8–0.9
0.9–0.99
m
0
0.4–0.5
0.2–0.3
0.1–0.2
0–0.1Characteristic 4 (newly joined robot reward). According to (13), if a robot does not belong to a group or has no collaboration with any robot in the group, the group reputation of the robot is NULL. When cooperating with the other robots, τ
(
l
a
,
l
b
,
c
)
∈
[
0.5
–
0.8
], which stands for relatively high reputation.


## 3.1. Task Decomposition

A task can be decomposed if it meets certain conditions. Four task decomposition conditions are given in [22]. If the task can be decomposed and is assignable, the formal definition of automata is as follows.An automata is a tupleA
=
(
Q
,
q
0
,
E
,
δ
,
F
), consisting of a set of states Q; the initial state q
0; a set of events E that causes transitions between the states; a transition relation δ; F is the acceptable states set. s
=
a
0
a
1
⋯
a
n
-
1
∈
E
* is a finite alphabet and a sequence q
0
,
q
1
,
…
,
q
n of n
+
1 states in Q, and q
0
∈
Q
0, q
i
+
1
∈
δ
(
q
i
,
a
i
).The parallel composition ofA
1 and A
2 is the automaton A
1
∥
A
2
=
(
Q
,
q
0
,
E
,
δ
), defined as follows:
(1)
Q
=
Q
1
×
Q
2
;
q
0
=
(
q
1
0
,
q
2
0
)
;
E
=
E
1
∪
E
2
;
∀
(
q
1
,
q
2
)
∈
Q
,
e
∈
E
δ
(
(
q
1
,
q
2
)
,
e
)
=
{
δ
1
(
q
1
,
e
)
,
δ
2
,
(
q
2
,
e
)
if
δ
1
(
q
1
,
e
)
,
δ
2
,
(
q
2
,
e
)
,
e
∈
E
1
∩
E
2
(
δ
1
(
q
1
,
e
)
,
q
2
)
if
δ
1
(
q
1
,
e
)
!
,
e
∈
E
1
∖
E
2
(
q
1
,
δ
2
(
q
2
,
e
)
)
if
δ
2
(
q
2
,
e
)
!
,
e
∈
E
2
∖
E
1
ϕ
otherwise
.The natural projections ofA
S in local event sets E
i is obtained as P
i (A
S), merging the events-related states which belong to the event sets E
/
E
i.(
1) Decomposition Condition 1
(2)
∀
e
1
,
e
2
∈
E
,
q
∈
Q
[
δ
(
q
,
e
1
)
!
∧
δ
(
q
,
e
2
)
!
]
⟹
[
∃
E
i
∈
{
E
1
,
…
,
E
n
}
,
{
e
1
,
e
2
}
⊆
E
i
]
∨
[
δ
(
q
,
e
1
e
2
)
!
∧
δ
(
q
,
e
2
e
1
)
!
]
,
where, e
1, and e
2 are events; E is a set of total events; local event sets E
i; a set of states Q; a transition relation δ; If state q is reachable under events e
1, e
2 that means existing a local events E
i which contains events e
1, e
2, making the state q remain reachable under the event sequence e
1
e
2 and e
2
e
1.(
2) Decomposition Condition 2
(3)
∀
e
1
,
e
2
∈
E
,
q
∈
Q
,
s
∈
E
*
[
δ
(
q
,
e
1
e
2
s
)
!
∨
δ
(
q
,
e
2
e
1
s
)
!
]
⟹
[
∃
E
i
∈
{
E
1
,
…
,
E
n
}
,
{
e
1
,
e
2
}
⊆
E
i
]
∨
[
δ
(
q
,
e
1
e
2
s
)
!
∧
δ
(
q
,
e
2
e
1
s
)
!
]
,
where E
* is sequence of events. If the state q is reachable under the event sequence e
1
e
2 or e
2
e
1, it can launch a local existing events E
i, which contains events e
1, e
2, making the state q remain reachable under the event sequence e
1
e
2
s and e
2
e
1
s.(
3) Decomposition Condition 3
(4)
δ
(
q
0
,
|
i
=
1
n
p
i
(
s
i
)
)
!
,
∀
{
s
1
,
…
,
s
n
}
∈
L
~
(
A
S
)
,
dddddddd
∃
s
i
,
s
j
∈
{
s
1
,
…
,
s
n
}
,
s
i
≠
s
j
,
where L
~
(
A
S
)
⊆
L
(
A
S
) and L
~
(
A
S
) are the biggest subset of L
(
A
S
)  for
all
s
∈
L
~
(
A
S
), ∃
s
′
∈
L
~
(
A
S
), ∃
E
i
,
E
j
∈
{
E
1
,
…
,
E
n
}, i
≠
j can launch p
E
i
∩
E
i
(
s
) and p
E
i
∩
E
i
(
s
′
), beginning with the same event. L
(
A
S
) is the set of all sequences of events of automaton A
S; L
~
(
A
S
) is the set of the sequences of events of automata A
S; the natural projections of the ith local event set in the corresponding sequence of events s
i.(
4) Decomposition Condition 4
(5)
∀
i
∈
{
1
,
…
,
n
}
,
x
·
x
1
·
x
2
∈
Q
i
,
x
1
≠
x
2
,
e
∈
E
i
,
t
∈
E
i
*
,
δ
i
(
x
,
e
)
=
x
1
,
δ
i
(
x
,
e
)
=
x
2
δ
i
(
x
1
,
t
)
!
⟺
δ
i
(
x
2
,
t
)
!
.Formal linear temporal logic language is used to present the whole tasks of the robot system, which is almost the same with the natural language in structure.Several temporal operators of task decomposition are presented as follows [22]:(i)
next state “ο”: requires that a property hold in the next state of the path;
(ii)
until “∪”: used to combine two properties. The combined property holds if there is a state on the path where the second property hold, and at every preceding state on the path, the first property holds;
(iii)
eventually “⋄”: used to assert that a property will hold at some future state on the path;
(iv)
always “□”: specifies that a property holds at every state on the path. Such as: E
=
{
E
1
,
E
2
,
…
,
E
n
}.The reachability while avoiding some events:¬
(
E
1
∨
E
2
)
∪
E
3
Sequence:⋄
(
E
1
∧
⋄
(
E
2
∧
⋄
E
3
)
)
Coverage:⋄
E
1
∧
⋄
E
2
∧
⋄
E
3
Recurrence:□
(
⋄
E
1
∧
⋄
E
2
∧
⋄
E
3
).The equivalent task automataA
S can be transformed from the formula. The natural projections of A
S to local event sets E
i are obtained as P
i (A
S). Linear temporal logic and automata have a close relationship, which can be directly exported from linear temporal logic formula, because every linear temporal logic formula consists of connectors and temporal operators.


## 3.2. Reputation Mechanism

The negotiation process of the robot collaboration system is presented, which mainly is concerned about how to build partnerships between the collaborative robots according to the reputation mechanism.Definition 1 (robot initialization set).
The robot initialization setI is identified as 〈
κ
I
,
E
I
,
CHA
P
I
,
A
C
I
〉, where κ denotes the ontology of collaboration robot, which can get the identification corresponding to κ; E
⊂
ε is an identification set, these identification sets are issued to κ in I. CHAP:
τ
→
P is a partial order function, mapping a finite subset of attributes to the strategy set. The properties of CHAP are called limited properties. For the limited property t, CHAP[t] is called the verification strategy of t. AC:
R
→
P is a partial order function, mapping resources to a finite strategy set.Definition 2 (robot collaboration strategy).
A collaboration strategy is defined as a quintuple〈
Q
,
M
,
ini
t
R
,
star
t
M
,
reply
〉, where Q is the finite set of the collaboration process state, each state denoted by q, and, q
∈
Q; M is the finite set of the collaboration process messages. The massage is denoted by m and usually consists of subscripts. The message sequences can be denoted as m
1
,
…
,
m
n. The function ini
t
R: I
×
k
→
Q defines the initial state of the requester. When the initialization set and requesting robot are given, this state is ini
t
R
(
I
,
K
R
)
=
q, where q
∉
{
success
,
failure
}. star
t
M: I
×
Res
×
k
→
Q
×
M defines that the collaboration is started by a requested robot. The function reply: Q
×
M
→
Q
×
M defines each action of the robot. When the robot initialization set I, current state q and the latest message m from the other side are given, reply
(
q
,
m
)
=
〈
q
′
,
m
′
〉.Definition 3 (framework of reputation mechanism).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to,   t denotes the time of collaboration and l denotes the specific group. The collaboration relationship from R
1 to R
2 is expressed as Γ
(
R
1
,
R
2
,
t
,
c
,
l
):(6)
Γ
(
R
1
,
R
2
,
t
,
l
,
c
)
=
α
×
Θ
(
R
1
,
R
2
,
t
,
l
,
c
)
+
β
×
Ω
(
R
2
,
t
,
l
,
c
)
+
θ
×
Ψ
(
D
1
,
D
2
,
t
,
c
)
,
where Θ
(
R
1
,
R
2
,
t
,
l
,
c
) denotes the direct reputation between robot R
1 and robot R
2. α denotes the direct reputation weight coefficient, 0
≤
α
≤
1. Ω
(
R
2
,
t
,
l
,
c
) denotes the individual reputation value of robot R
2; β is the reputation weight coefficient. 0
≤
β
≤
1. Ψ
(
D
1
,
D
2
,
t
,
c
) denotes the reputation value from the robot group D
1 to the group D
2. θ denotes the group weight coefficient, 0
≤
θ
≤
1, α
+
β
+
θ
=
1, α
,
β
,
θ
≥
0.Definition 4 (direct reputation).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to. The direct reputation from R
1 to R
2 is presented as
(7)
Θ
(
R
1
,
R
2
,
t
,
l
,
c
)
=
DRM
(
R
1
,
R
2
,
t
,
c
)
×
γ
(
t
-
t
a
-
b
,
c
)
×
τ
(
l
a
,
l
b
,
c
)
,
where the definition of DRM (Direct Reputation Matrix) can be seen in Definition 7. t
a
-
b denotes the last collaboration time between R
1 and R
2; γ
(
t
-
t
a
-
b
,
c
) denotes the function of time calibration; τ
(
l
a
,
l
b
,
c
) denotes the function of group calibration function; and γ
(
t
-
t
a
-
b
,
c
) denotes the time calibration function.Definition 5 (individual reputation).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to. The individual reputation of robot R
2 in the collaboration system is presented as
(8)
Ω
(
R
2
,
t
,
l
,
c
)
=
1
n
∑
i
=
1
n
S
(
ρ
i
+
Γ
i
(
R
i
,
R
2
,
t
,
l
,
c
)
)
55555
j
×
γ
(
t
-
t
z
i
-
b
,
c
)
×
τ
(
l
z
i
,
l
b
,
c
)
,
where S
(
ρ
i
+
Γ
i
(
R
i
,
R
2
,
t
,
l
,
c
)
) denotes the function of the reputation calibration; ρ
i denotes the standard deviation of reputation value at the No. i collaboration; λ
(
t
-
t
z
i
-
b
,
c
) denotes the function of time calibration; τ
(
l
z
i
,
l
b
,
c
) denotes the function of group calibration function; and n denotes the number of robots in the collaboration system who is cooperating with robot R
2.Definition 6 (group reputation).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to. Group reputation in the collaboration system is
(9)
Ψ
(
D
1
,
D
2
,
t
,
c
)
=
Ψ
(
D
1
,
D
2
,
t
a
-
b
,
c
)
×
γ
(
t
-
t
a
-
b
,
c
)
,
where Ψ
(
D
1
,
D
2
,
t
a
-
b
,
c
) denotes the group reputation value of the last collaboration between the group D
1 and the group D
2. γ
(
t
-
t
a
-
b
,
c
) denotes the function of time calibration.Definition 7 (direct reputation matrix (DRM)).
If the cooperative system is composed byn robots, DRM will be n
*
n matrix. Direct reputation value Θ
(
R
1
,
R
2
,
t
,
l
,
c
), Θ
∈
[
0,1
]. For example, there are 26 robots in the collaboration system, named from R
A to R
Z, the DRM of which is the following matrix:
(10)

[
1

Θ
(
R
A
,
R
B
,
t
,
l
,
c
)
⋯
Θ
(
R
A
,
R
Z
,
t
,
l
,
c
)

Θ
(
R
B
,
R
A
,
t
,
l
,
c
)

1
⋯
Θ
(
R
B
,
R
Z
,
t
,
l
,
c
)

⋯

⋯
⋯
⋯

Θ
(
R
Z
,
R
A
,
t
,
l
,
c
)

Θ
(
R
Z
,
R
B
,
t
,
l
,
c
)
⋯
1

]


.Definition 8 (time calibration function).
Giving thatD
1 denotes the domain where R
1 belongs to, D
2 denotes the domain where R
2 belongs to.   t
a
-
b denotes the last collaboration time between robot R
1 and robot R
2. The time calibration function can be expressed as
(11)
γ
(
t
,
c
)
=
k
0
γ
(
t
a
-
b
,
c
)
+
k
1
e
-
k
(
t
-
t
a
-
b
)
(
t
-
t
a
-
b
T
r
+
)
S
-
k
2
e
-
k
(
t
-
t
a
-
b
)
(
t
-
t
a
-
b
T
r
-
)
(
S
-
1
)
-
k
3
(
1
-
e
-
k
(
t
-
t
a
-
b
)
)
γ
(
t
a
-
b
,
c
)
,
where k
0 denotes the history experience coefficient, generally, k
0
=
1. k
1 denotes the reputation reward coefficient. e
-
k
(
t
-
t
a
-
b
) denotes the correction operator. k
2 denotes the reputation penalty coefficient. r
+ denotes the incentive ratio in time T. r
- denotes the penalty ratio in time T. S denotes validation coefficient of the collaboration, if the assigned task is successfully finished, S
=
1; otherwise S
=
0. k
3 denotes the attenuation coefficient.
If the robot does not take any assigned task, its reputation will diminish as the time went on. The coefficients is satisfied with0
<
k
0
,
k
1
,
k
2
,
k
3
≤
1, k
>
0.
Characteristic 1(time attenuation). With no compensation, the proposition will be proved if γ
(
t
1
)
>
γ
(
t
2
), when t
1
<
t
2
(12)
γ
(
t
1
,
c
)
=
k
0
γ
(
t
0
,
c
)
-
k
3
(
1
-
e
-
k
(
t
1
-
t
0
)
)
γ
(
t
0
,
c
)
,
γ
(
t
2
,
c
)
=
k
0
γ
(
t
0
,
c
)
-
k
3
(
1
-
e
-
k
(
t
2
-
t
0
)
)
γ
(
t
0
,
c
)
,
γ
(
t
1
,
c
)
-
γ
(
t
2
,
c
)
=
k
3
γ
(
t
0
,
c
)
(
e
-
k
(
t
1
-
t
0
)
-
e
-
k
(
t
2
-
t
0
)
)
,
where k
3
γ
(
t
0
)
>
0 and t
1
<
t
2, so the equation above is greater than 0; therefore, the proposition may be established. In the process of collaboration, if no compensation, the value of the function will be decreased.
Characteristic 2 (natural attenuation curve). Generally, k
0 is 1. The value of (11) is related to k and k
3. Taking that k
>
0
,
0
<
k
3
≤
1, a different set of curves will be obtained, which are called the attenuation curves.
The curve, whenk
=
0.2, k
3
=
0.5, is defined as the natural attenuation curve. Assuming that the initial value k
0
γ
(
t
0
,
c
)
=
1, k
3 = 0.5 could be the case, k is 0.1, 0.2, 0.3, and 0.4, respectively.
Characteristic 3 (historical experience related). Assuming that (11) do not have the characteristics of historical relevance, in the absence of natural attenuation as well as under the circumstances of no penalty and award compensation, reputation will have nothing to do with the historical experience. Then k
0
γ
(
t
a
-
b
,
c
)
=
0, because γ
(
t
a
-
b
,
c
) is not equal to zero, so k
0
=
0, which is conflicted with k
0
≠
0. Therefore, the assumption is wrong; that is, (11) is historical experience related.Definition 9 (group calibration function).
Giving thatl
a denotes the group where robot R
1 belongs to, l
b denotes the group where robot R
2 belongs to, c denotes the environment context, the group calibration function is expressed as
(13)
τ
(
l
a
,
l
b
,
c
)
=
{
m
0
1
+
m
1
(
Ω
D
1
+
Ω
D
2
)
/
2
l
a
≠
l
b
1
l
a
=
l
b
.
IfΩ
D
1
=
NULL or Ω
D
2
=
NULL, then τ
(
l
a
,
l
b
,
c
)
∈
[
0.5
–
0.8
]. 0
<
m
0
≤
1, 0
<
m
1
≤
1, m
0 denotes the positive coefficient, m
1 denotes the negative coefficient. The typical parameters of groups are given in Table 1.Table 1
Typical group parameters.
Loyalty
Honesty
Improvement
Randomization
m
1
0–0.1
0.1–0.2
0.2–0.3
0.4–0.6
m
0
0.9–0.99
0.8–0.9
0.7–0.8
0.5–0.7
Concealment
Tricky
Corruption
Deceivement
m
1
0.6–0.7
0.7–0.8
0.8–0.9
0.9–0.99
m
0
0.4–0.5
0.2–0.3
0.1–0.2
0–0.1Characteristic 4 (newly joined robot reward). According to (13), if a robot does not belong to a group or has no collaboration with any robot in the group, the group reputation of the robot is NULL. When cooperating with the other robots, τ
(
l
a
,
l
b
,
c
)
∈
[
0.5
–
0.8
], which stands for relatively high reputation.


## 4. Experiments and Results Analysis

Many simulation platforms can be used for multirobot systems [23], for example, Player/Stage, TeamBots, Gazebo, USARSim, Webots, Microsoft Robotics Studio, Swarmbot 3D, Swarmanoid Simulator, and so forth. In this paper, Player/Stage is selected as the simulation platforms because of the simple operability and flexibility. Player/Stage [24] was developed by Robotics Research Lab in University of Southern California in 1999, which is an open-source project that provides internal interface and simulation environment for multirobot system. The platform can be modified and expanded by the researchers worldwide according to their requirements.


### 4.1. Simulation and Performance Analysis

Three robotsR
1, R
2, and R
3 are put in area 1 and with the thrust capability of 2
N, 3
N, and 5
N, respectively. Their initial reputation values are 0.5, 0.9, and 0.7. Three boxes D
1, D
2, and D
3 are put in area 2, which need moving thrust of 2
N, 6
N, and 4
N, respectively. The moving condition is that the thrust provided by the robot is greater than the needed thrust of the box.RobotR
2 is given the highest reputation value who is responsible for sending arranged commands to R
1 and R
3. Assuming that assignment is given to one robot to push the box, the robot moves from area 1 to area 2, and then finds the homologous box and try to push it.However, ifD
2 is too heavy to be pushed and needs cooperation from other robots, R
1 and R
3 are required to cooperate. The robot R
2 goes to push D
1, and after that R
1 and R
2 will go back to area 1. R
3 returns to area 2, and continues pushing D
3 to area 3. All of them return to the initial place waiting for next assignment. The process can be translated into task automata A
s, shown in Figure 3.Figure 3
Task automata.The assigned task is to push the boxes to area 3. The local event set of each robot is presented as follows:(14)
E
1
=
{
h
1
,
R
1
to
D
1
,
R
1
on
D
1
,
FWD
,
R
1
R
3
to
D
2
,
R
1
R
3
on
D
2
,
D
2
to
3
,
r
}
,
E
2
=
{
h
2
,
R
2
to
D
2
,
R
2
on
D
2
,
FWD
,
R
2
to
D
1
,
R
2
on
D
1
,
D
1
to
3
,
r
}
,
E
3
=
{
h
3
,
R
3
to
D
3
,
R
3
on
D
3
,
FWB
,
R
1
R
3
to
D
2
,
R
1
R
3
on
D
2
,
D
2
to
3
,
R
3
to
D
3
,
R
3
on
D
3
,
D
3
to
3
,
r
}
.Checking that the decomposition conditionsE
1, E
2, and E
3, if P
1
(
A
S
)
∥
P
2
(
A
S
)
∥
P
3
(
A
S
)
≅
A
S, which certify that the task is decomposable and decomposed into three subtasks P
1(A
S), P
2(A
S), and P
3(A
S).DTM presents the direct reputation relationships among robots. Three robots in the collaboration system named fromR
1 to R
3, the DTM is shown as
(15)
[
1
0.7
0.4
0.7
1
0.8
0.4
0.8
1
]
.The reputation in the matrix is updated after each step of the collaboration. Box moving is simulated by the approach, shown in Figure4.Simulation process of the approach.
(a)
Initialization
(b)
Taking the assignment
(c)
Pushing boxes
(d)
Waiting for next assignmentTwo typical allocation algorithms are used to make contrast and evaluate the performance of the proposed method, which are sequence allocation and auction allocation. The simulation has seven robots in area 1 and 14 boxes in area 2, without obstacles between them.In the case of the sequence allocations, the results ofN mod 3 may be 1, 2, 3, 4, 5, 6, and 0. Tasks are assigned to the robot R
1
,
R
2
,
…
,
R
7, respectively. The simulation process of sequence allocation is in Figure 5.The simulation of sequence allocation.
(a)
Initialization
(b)
Taking the assignments
(c)
Pushing boxes
(d)
Completing assignmentIn the case of the auction allocation, the bidding is lauched at the beginning by the auctioneer. The best bid is picked out by the predetermined standard. The task will be assigned to the winner of the auction. The winner of the auction is chosen by the auctioneer giving the highest bid.The bid matrix is used to store the value of robot biding for each assignment. A typical bid matrix in the simulation is presented as(16)
01
02
03
04
05
06
07
08
09
10
11
12
13
14
R
1
5
7
13
5
7
10
9
5
7
13
5
7
10
9
R
2
12
8
11
8
9
13
10
12
8
11
8
9
13
10
R
3
10
6
12
10
10
11
15
10
6
12
10
10
11
15
R
4
11
5
10
11
12
10
14
11
5
10
11
12
10
14
R
5
13
10
9
12
11
10
13
13
10
9
12
11
10
13
R
6
10
14
8
17
10
9
12
10
14
8
17
10
9
12
R
7
9
7
7
20
9
8
11
9
7
7
20
9
8
11The tasks are performed in the following sequence:R
5, R
6, R
1, R
7, R
4, R
2, R
3, R
5, R
6, R
1, R
7, R
4, R
2, R
3. The simulation process can be described in Figure 6.Simulation of auction allocation.
(a)
Initialization
(b)
Taking the assignment
(c)
Pushing boxes
(d)
Completing the assignmentIn the case of the task allocation by reputation, the initial reputation value of the system is the following matrix:(17)
[
R
1
R
2
R
3
R
4
R
5
R
6
R
7
]
T
=
[
0.81
0.61
0.55
0.48
0.83
0.46
0.72
]
T
.
The DRM of seven robots is shown as
(18)
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
1
1.00
0.65
0.58
0.86
0.75
0.85
0.87
R
2
0.65
1.00
0.84
0.85
0.77
0.69
0.63
R
3
0.58
0.84
1.00
0.59
0.82
0.79
0.74
R
4
0.86
0.85
0.59
1.00
0.55
0.61
0.85
R
5
0.75
0.77
0.82
0.55
1.00
0.78
0.71
R
6
0.85
0.69
0.79
0.61
0.78
1.00
0.88
R
7
0.87
0.63
0.74
0.85
0.71
0.88
1.00The value of DRM is updated after each process of collaboration. If successfully finished the assigned task, the value of direct reputation between the robots increases by 0.01, otherwise reduces 0.05. In the simulation process, if the assigned task failed, the moving trajectory of the robot is the same to facilitate the performance comparison. The process of performing tasks is shown in Figure7.Figure 7
Process of task allocation by reputation.Every experiment is simulated six times to get a reasonable performance assessment. The ultimate results are the arithmetic average of the six times.The order allocation needs about 635.71s to complete the assigned tasks. The auction allocation needs about 591.63 s to complete the tasks. The reputation-based allocation method needs about 525.15 s. The efficiency of task allocation by reputation is higher than the average of the other two methods, as shown in Figure 8.Figure 8
Comparison of the three allocation method.


### 4.2. Experimental Apparatus and Evaluation

The biped-robot apparatus are utilized as the experimental platform. The shape parameters of the robot are with upright height 33.3 cm, width 9.9 cm, arm length 15.9 cm, arms stretched flat horizontal length 41.7 cm, upper high 13.9 cm, waist high 19.4 cm, and weight 1 kg, as shown in Figure9.Figure 9
Biped-robot experimental apparatus.The wireless sensor module is used to send and receive commands, which are coded as the standard serial data and sent to the assigned robot. The effective transmission distance is about 30 m. The experimental parameters of task allocation are shown in Table2.Table 2
The experimental parameters.
Parameters
Value
〈
κ
,
τ
,
ε
,
Res
〉
κ: four robots’ identity Res: Transport, Movement
〈
R
,
M
,
S
,
T
,
P
〉
R, M: four robots
P: logic set
[
r
b
,
r
e
]
r
b: Time of box picked up
r
e: r
b
+
30 s
own
0
G
G: four robots
m
0, m
1
0.6, 0.5
α, β, θ
1/3, 1/3, 1/3Four task allocation methods are engaged to evaluate the efficiency. In addition to the proposed method, the other three methods are random allocation, order distribution, and simultaneous allocation.A nonnumbered box with the size 8 cm3 is arranged to be moved to the destination. The moving distance is set to be 0.6 m. After receiving the task assignment, the robot moves to the side of the box, pick it up, move it, and put it down at the destination. The processes of picking up and putting down are done manually; other actions are done automatically.For the case of task allocation using order distribution algorithm, the results ofN mod 3 may be 1, 2, and 0. Tasks are allocated to the robot S
1, S
2, and S
3, respectively based on the results, and every task allocation time interval is 30 s. For the simultaneous allocation algorithm, the allocation time interval is 0 s.For the case of task allocation using random distribution, the random number set[
0,1
) is used. When the generated random number R
∈
[
0
–
1
/
3
), the task will be assigned to robot S
1; if R
∈
[
1
/
3
–
2
/
3
), the task will be assigned to robot S
2; if R
∈
[
2
/
3
–
1
), the task will be assigned to robot S
3.The tasks numberedO
1
,
O
2
,
…
,
O
N are generated by the task sequences. N stands for the number of tasks. N
=
9 is taken, respectively, as the arranged tasks and each running time is 7 s. The arithmetic mean value of the maximum time and minimum time is removed to effectively prevent the unexpected result of random events. The results are shown in Figure 10.Figure 10
Comparison of small number of arranged tasks.With the number of tasks increasing toN
=
33, it is taken, respectively, as the arranged tasks (medium number tasks). The arithmetic mean value of the maximum time and minimum time are removed. The experimental results are shown in Figure 11.Figure 11
Comparison of medium number of tasks.According to the practical application, the robots with relatively high-speed capability are allocated more tasks and the efficiency of the task allocation by reputation is 4.35% higher than the second high method.When the number of tasks continues to increase toN
=
180, which are taken, respectively, as the arranged tasks (large number of tasks). The test results are shown in Figure 12.Figure 12
Comparison of large number of tasks.In the case of large number of tasks, the efficiency of task allocation by reputation is 3.57% higher than the second high method.The experimental results show that the task allocation using reputation mechanism can effectively increase the performance and prevent a robot from a delay in the case of the individual robot failure.


## 4.1. Simulation and Performance Analysis

Three robotsR
1, R
2, and R
3 are put in area 1 and with the thrust capability of 2
N, 3
N, and 5
N, respectively. Their initial reputation values are 0.5, 0.9, and 0.7. Three boxes D
1, D
2, and D
3 are put in area 2, which need moving thrust of 2
N, 6
N, and 4
N, respectively. The moving condition is that the thrust provided by the robot is greater than the needed thrust of the box.RobotR
2 is given the highest reputation value who is responsible for sending arranged commands to R
1 and R
3. Assuming that assignment is given to one robot to push the box, the robot moves from area 1 to area 2, and then finds the homologous box and try to push it.However, ifD
2 is too heavy to be pushed and needs cooperation from other robots, R
1 and R
3 are required to cooperate. The robot R
2 goes to push D
1, and after that R
1 and R
2 will go back to area 1. R
3 returns to area 2, and continues pushing D
3 to area 3. All of them return to the initial place waiting for next assignment. The process can be translated into task automata A
s, shown in Figure 3.Figure 3
Task automata.The assigned task is to push the boxes to area 3. The local event set of each robot is presented as follows:(14)
E
1
=
{
h
1
,
R
1
to
D
1
,
R
1
on
D
1
,
FWD
,
R
1
R
3
to
D
2
,
R
1
R
3
on
D
2
,
D
2
to
3
,
r
}
,
E
2
=
{
h
2
,
R
2
to
D
2
,
R
2
on
D
2
,
FWD
,
R
2
to
D
1
,
R
2
on
D
1
,
D
1
to
3
,
r
}
,
E
3
=
{
h
3
,
R
3
to
D
3
,
R
3
on
D
3
,
FWB
,
R
1
R
3
to
D
2
,
R
1
R
3
on
D
2
,
D
2
to
3
,
R
3
to
D
3
,
R
3
on
D
3
,
D
3
to
3
,
r
}
.Checking that the decomposition conditionsE
1, E
2, and E
3, if P
1
(
A
S
)
∥
P
2
(
A
S
)
∥
P
3
(
A
S
)
≅
A
S, which certify that the task is decomposable and decomposed into three subtasks P
1(A
S), P
2(A
S), and P
3(A
S).DTM presents the direct reputation relationships among robots. Three robots in the collaboration system named fromR
1 to R
3, the DTM is shown as
(15)
[
1
0.7
0.4
0.7
1
0.8
0.4
0.8
1
]
.The reputation in the matrix is updated after each step of the collaboration. Box moving is simulated by the approach, shown in Figure4.Simulation process of the approach.
(a)
Initialization
(b)
Taking the assignment
(c)
Pushing boxes
(d)
Waiting for next assignmentTwo typical allocation algorithms are used to make contrast and evaluate the performance of the proposed method, which are sequence allocation and auction allocation. The simulation has seven robots in area 1 and 14 boxes in area 2, without obstacles between them.In the case of the sequence allocations, the results ofN mod 3 may be 1, 2, 3, 4, 5, 6, and 0. Tasks are assigned to the robot R
1
,
R
2
,
…
,
R
7, respectively. The simulation process of sequence allocation is in Figure 5.The simulation of sequence allocation.
(a)
Initialization
(b)
Taking the assignments
(c)
Pushing boxes
(d)
Completing assignmentIn the case of the auction allocation, the bidding is lauched at the beginning by the auctioneer. The best bid is picked out by the predetermined standard. The task will be assigned to the winner of the auction. The winner of the auction is chosen by the auctioneer giving the highest bid.The bid matrix is used to store the value of robot biding for each assignment. A typical bid matrix in the simulation is presented as(16)
01
02
03
04
05
06
07
08
09
10
11
12
13
14
R
1
5
7
13
5
7
10
9
5
7
13
5
7
10
9
R
2
12
8
11
8
9
13
10
12
8
11
8
9
13
10
R
3
10
6
12
10
10
11
15
10
6
12
10
10
11
15
R
4
11
5
10
11
12
10
14
11
5
10
11
12
10
14
R
5
13
10
9
12
11
10
13
13
10
9
12
11
10
13
R
6
10
14
8
17
10
9
12
10
14
8
17
10
9
12
R
7
9
7
7
20
9
8
11
9
7
7
20
9
8
11The tasks are performed in the following sequence:R
5, R
6, R
1, R
7, R
4, R
2, R
3, R
5, R
6, R
1, R
7, R
4, R
2, R
3. The simulation process can be described in Figure 6.Simulation of auction allocation.
(a)
Initialization
(b)
Taking the assignment
(c)
Pushing boxes
(d)
Completing the assignmentIn the case of the task allocation by reputation, the initial reputation value of the system is the following matrix:(17)
[
R
1
R
2
R
3
R
4
R
5
R
6
R
7
]
T
=
[
0.81
0.61
0.55
0.48
0.83
0.46
0.72
]
T
.
The DRM of seven robots is shown as
(18)
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
1
1.00
0.65
0.58
0.86
0.75
0.85
0.87
R
2
0.65
1.00
0.84
0.85
0.77
0.69
0.63
R
3
0.58
0.84
1.00
0.59
0.82
0.79
0.74
R
4
0.86
0.85
0.59
1.00
0.55
0.61
0.85
R
5
0.75
0.77
0.82
0.55
1.00
0.78
0.71
R
6
0.85
0.69
0.79
0.61
0.78
1.00
0.88
R
7
0.87
0.63
0.74
0.85
0.71
0.88
1.00The value of DRM is updated after each process of collaboration. If successfully finished the assigned task, the value of direct reputation between the robots increases by 0.01, otherwise reduces 0.05. In the simulation process, if the assigned task failed, the moving trajectory of the robot is the same to facilitate the performance comparison. The process of performing tasks is shown in Figure7.Figure 7
Process of task allocation by reputation.Every experiment is simulated six times to get a reasonable performance assessment. The ultimate results are the arithmetic average of the six times.The order allocation needs about 635.71s to complete the assigned tasks. The auction allocation needs about 591.63 s to complete the tasks. The reputation-based allocation method needs about 525.15 s. The efficiency of task allocation by reputation is higher than the average of the other two methods, as shown in Figure 8.Figure 8
Comparison of the three allocation method.


## 4.2. Experimental Apparatus and Evaluation

The biped-robot apparatus are utilized as the experimental platform. The shape parameters of the robot are with upright height 33.3 cm, width 9.9 cm, arm length 15.9 cm, arms stretched flat horizontal length 41.7 cm, upper high 13.9 cm, waist high 19.4 cm, and weight 1 kg, as shown in Figure9.Figure 9
Biped-robot experimental apparatus.The wireless sensor module is used to send and receive commands, which are coded as the standard serial data and sent to the assigned robot. The effective transmission distance is about 30 m. The experimental parameters of task allocation are shown in Table2.Table 2
The experimental parameters.
Parameters
Value
〈
κ
,
τ
,
ε
,
Res
〉
κ: four robots’ identity Res: Transport, Movement
〈
R
,
M
,
S
,
T
,
P
〉
R, M: four robots
P: logic set
[
r
b
,
r
e
]
r
b: Time of box picked up
r
e: r
b
+
30 s
own
0
G
G: four robots
m
0, m
1
0.6, 0.5
α, β, θ
1/3, 1/3, 1/3Four task allocation methods are engaged to evaluate the efficiency. In addition to the proposed method, the other three methods are random allocation, order distribution, and simultaneous allocation.A nonnumbered box with the size 8 cm3 is arranged to be moved to the destination. The moving distance is set to be 0.6 m. After receiving the task assignment, the robot moves to the side of the box, pick it up, move it, and put it down at the destination. The processes of picking up and putting down are done manually; other actions are done automatically.For the case of task allocation using order distribution algorithm, the results ofN mod 3 may be 1, 2, and 0. Tasks are allocated to the robot S
1, S
2, and S
3, respectively based on the results, and every task allocation time interval is 30 s. For the simultaneous allocation algorithm, the allocation time interval is 0 s.For the case of task allocation using random distribution, the random number set[
0,1
) is used. When the generated random number R
∈
[
0
–
1
/
3
), the task will be assigned to robot S
1; if R
∈
[
1
/
3
–
2
/
3
), the task will be assigned to robot S
2; if R
∈
[
2
/
3
–
1
), the task will be assigned to robot S
3.The tasks numberedO
1
,
O
2
,
…
,
O
N are generated by the task sequences. N stands for the number of tasks. N
=
9 is taken, respectively, as the arranged tasks and each running time is 7 s. The arithmetic mean value of the maximum time and minimum time is removed to effectively prevent the unexpected result of random events. The results are shown in Figure 10.Figure 10
Comparison of small number of arranged tasks.With the number of tasks increasing toN
=
33, it is taken, respectively, as the arranged tasks (medium number tasks). The arithmetic mean value of the maximum time and minimum time are removed. The experimental results are shown in Figure 11.Figure 11
Comparison of medium number of tasks.According to the practical application, the robots with relatively high-speed capability are allocated more tasks and the efficiency of the task allocation by reputation is 4.35% higher than the second high method.When the number of tasks continues to increase toN
=
180, which are taken, respectively, as the arranged tasks (large number of tasks). The test results are shown in Figure 12.Figure 12
Comparison of large number of tasks.In the case of large number of tasks, the efficiency of task allocation by reputation is 3.57% higher than the second high method.The experimental results show that the task allocation using reputation mechanism can effectively increase the performance and prevent a robot from a delay in the case of the individual robot failure.


## 5. Conclusion

Task planning is developed by two parts: task decomposition and task allocation. The processes of the task decomposition and task allocation using reputation mechanism, are presented. The robot collaboration strategy, the framework of reputation mechanism, and three reputations are defined in detail, which includes robot individual reputation, robot group reputation, and robot direct reputation. Time calibration function and group calibration function are designed to improve the effectiveness of the method, which are proved to be with characteristics of time attenuation, historical experience related, and newly joined robot reward. The success rate of collaboration is enhanced and the time of recovery and redistribution of the task are reduced.Player/Stage is used as the simulation platform, and three biped-robots are established as the experimental apparatus. In the simulation, task decomposition is studied, and the result of task allocation is compared with the sequence and auction allocation methods. The biped-robots are used in the experiments, and four task allocation methods are engaged to evaluate the efficiency. The simulation and experimental results show that the approach can provide an effective performance for multirobot system.



---

*Source: 818701-2014-02-04.xml*