Adaptive Fault Tolerant Execution of
Multi-Robot Missions using Behavior Trees
Michele Colledanchise,† Alejandro Marzinotto,† Dimos V. Dimarogonas,‡ and Petter ¨Ogren†
Abstract— Multi-robot teams offer possibilities of improved
performance and fault tolerance, compared to single robot
solutions. In this paper, we show how to realize those possi-
bilities when starting from a single robot system controlled by
a Behavior Tree (BT). By extending the single robot BT to
a multi-robot BT, we are able to combine the fault tolerant
properties of the BT, in terms of built-in fallbacks, with the
fault tolerance inherent in multi-robot approaches, in terms of
a faulty robot being replaced by another one. Furthermore, we
improve performance by identifying and taking advantage of
the opportunities of parallel task execution, that are present
in the single robot BT. Analyzing the proposed approach, we
present results regarding how mission performance is affected
by minor faults (a robot losing one capability) as well as major
faults (a robot losing all its capabilities). Finally, a detailed
example is provided to illustrate the approach.
I. INTRODUCTION
Imagine a robot that is designed to perform maintenance
on a given machine. The robot can open and close the
cover, do fault detection and replace broken hardware (HW)
components. However, this robot is fairly complex and easily
breaks down. Thus, it is desirable to replace this big versatile
robot with a team of smaller specialized robots, as shown
in Figure 1. This paper shows how to modify the single
robot Behavior Tree (BT) controlling the original robot, to
a multi-robot BT, to be run in parallel on all new robots,
thereby improving both fault tolerance and performance of
the original BT.
The fault tolerance of the single robot BT, in terms of
fallbacks, is improved by also adding the tolerance afforded
by the redundancy achieved through having multiple robots,
and the performance of the single robot BT is improved
by executing the right tasks in parallel. In detail, the BT
includes both so-called sequence and fallback compositions,
as explained below. Some tasks that were earlier done in
sequence, such as diagnosing different HW components, are
now done in parallel, while other tasks that were also done
in sequence, such as opening the cover and then diagnosing
HW, are still done in a sequence. Similarly, some tasks that
were earlier done as fallbacks, such as searching in storage 2
if no tools were found in storage 1, are now done in parallel,
while other fallbacks, such as using the small screwdriver if
the large one does not ﬁt, are not done in parallel. Thus fault
tolerance as well as performance is improved.
†The author is with the Centre for Autonomous Systems, Computer
Vision and Active Perception Lab, School of Computer Science and Com-
munication, The Royal Institute of Technology - KTH, Stockholm, Sweden.
‡The author is with the Centre for Autonomous Systems, Automatic
Control Lab, School of Electrical Engineering, The Royal Institute of
Technology - KTH, Stockholm, Sweden.
C
REST
C
REST
HW1
A
REPLACE
HW
A
FAULT
B
REPLACE
HW
B
REST
HW1
HW2
HW3
HW4
HW5
Fig. 1.
Snapshot of a multi-robot mission execution. Two robots are
replacing the broken parts, HW2 and HW4, (bottom) of a machine. One
robot is out of order (top left), and tree robots are resting (top right).
The contribution of this paper is that we show how fault
tolerance and performance can be improved in a single robot
BT, by adding more robots to the team and extending the BT
into a multi-robot BT, using two important modiﬁcations.
First we add a task assignment functionality, and then we
identify and adapt the sequences and fall back compositions
of the BT that are possible to execute in parallel.
The outline of this paper is as follows. First, in Section II
we review related work. Then, in Section III we give an
overview of the classical formulation of BTs. The main
problem is stated in Section IV and the proposed solution
is given in Section V. An extensive example illustrating
the proposed approach is presented in Section VI, and we
conclude the paper in Section VII.
II. RELATED WORK
BTs are a recent alternative to Controlled Hybrid Systems
(CHSs) for reactive fault tolerant execution of robot tasks,
and they were ﬁrst introduced in the computer gaming
industry [1]–[3], to meet their needs of modularity, ﬂex-
ibility and reusability in artiﬁcial intelligence for in-game
opponents. Their popularity lies in its ease of understanding,
its recursive structure, and its usability, creating a growing
attention in academia [4]–[11]. In most cases, CHSs have
memoryless transitions, i.e. there is no information where
the transition took place from, a so-called one way control
transfer. In BTs the equivalent of state transitions are gov-
erned by calls and return values being sent by parent/children
in the tree structure, this information passing is called a
two way control transfers. In programming languages, the
replacement of a one way (e.g., GOTO statement) with
a two way control transfer (i.e., Function Calls) made an
improvement in readability and reusability [12]. Thus, BTs
exhibit similar advantages as gained moving from GOTO to
Function Calls in programming in the 1980s. Note however,
arXiv:1502.02960v1  [cs.RO]  10 Feb 2015
we do not claim that BTs are better than CHSs from a purely
theoretical standpoint. Instead, the main advantage of using
BTs lies is in its ease of use, in terms of modularity and
reusability, [8]. BTs were ﬁrst used in [1], [2], in high proﬁle
computer games, such as the HALO series. Later work
merged machine learning techniques with BTs’ logic [4],
[5], making them more ﬂexible in terms of parameter passing
[6]. The advantage of BTs as compared to a general Finite
State Machines (FSMs) was also the reason for extending the
JADE agent Behavior Model with BTs in [7], and the beneﬁts
of using BTs to control complex missions of Unmanned
Areal Vehicles (UAVs) was described in [8]. In [10] the
modular structure of BTs addressed the formal veriﬁcation
of mission plans.
In this work, we show how a plan for a multi-robot
system can be addressed in a BT fashion, gaining all the
advantages aforementioned in addition to the scalability that
distinguishes a general multiagent system. Many existing
works [13]–[15] stressed the problem of deﬁning local tasks
to achieve a global speciﬁcation emphasizing the advantages
of having a team of robots working towards a global goal.
Moreover, [16], [17] introduce the concept of task delega-
tion among agents in a multi-agent system, dividing task
speciﬁcation in closed delegation, where goal and plan are
predeﬁned, and open delegation where either only the goal
is speciﬁed while the plan can be chosen by the agent, or
the speciﬁed plan describes abstractly what actions have to
be taken, giving to the agent some freedom in terms of
how to perform the delegated task. In [18], it is shown
how verifying the truth of preconditions on single agents
becomes equivalent to checking the fulﬁllment of a global
robot network through recursive calls, using a tree structure
called Task Speciﬁcation Trees.
Recent works present some advantages of implementing
BTs in robotics applications [8], [19] making comparisons
with the CHSs, highlighting their modularity and reusabil-
ity. In [9], BTs were used to perform autonomous robotic
grasping. In particular, it was shown how BTs enabled the
easy composition of primitive actions into complex and
robust manipulation programs. Finally, in [20] performance
measures, such as success/failure probabilities and execution
times, were estimated for plans using BTs. However, BTs
are mostly used to design single agent behavior and, to the
best of our knowledge, there is no rigorous framework in
academia using the classical formulation of BTs for multi-
robot systems.
III. BACKGROUND: FORMULATION OF BTS
Here, we brieﬂy introduce an overview of BTs, the reader
can ﬁnd a detailed description in [8].
A BT is deﬁned as a directed rooted tree where nodes are
grouped into control ﬂow nodes, execution nodes, and a root
node. In a pair of connected nodes we call the outgoing node
parent and the incoming node child. Then, the root node has
no parents and only one child, the control ﬂow nodes have
one parent and at least one child, and the execution nodes
are the leaves of the tree (i.e. they have no children and one
parent). Graphically, the children of a control ﬂow node are
sorted from its bottom left to its bottom right, as depicted
in Figures 2-4. The execution of a BT starts from the root
node. It sends ticks 1 to its child. When a generic node in a
BT receives a tick from its parent, its execution starts and it
returns to its parent a status running if its execution has not
ﬁnished yet, success if its execution is accomplished (i.e. the
execution ends without failures), or failure otherwise.
Here we draw a distinction between three types of control
ﬂow nodes (selector, sequence, and parallel) and between
two types of execution nodes (action and condition). Their
execution is explained below.
Selector (also known as Fallback): When the execution
of a selector node starts (i.e. the node receives a tick from its
parent), then the node’s children are executed in succession
from left to right, until a child returning success or running
is found. Then this message is returned to the parent of the
selector. It returns failure only when all the children return a
status failure. The purpose of the selector node is to robustly
carry out a task that can be performed using several different
approaches (e.g. a motion tracking task can be made using
either a 3D camera or a 2D camera) by performing each
of them in succession until one succeeds. The graphical
representation of a selector node is a box with a “?”, as
in Fig. 2.
A ﬁnite number of BTs T1,T2,...,TN can be composed into
a more complex BT, with them as children, using the selector
composition: T0 = Selector(T1,T2,...,TN).
?
Child 1
Child 2
· · ·
Child N
Fig. 2.
Graphical representation of a selector node with N children.
Sequence: When the execution of a sequence node
starts, then the node’s children are executed in succession
from left to right, returning to its parent a status failure
(running) as soon as the a child that returns failure (running)
is found. It returns success only when all the children return
success. The purpose of the sequence node is to carry out
the tasks that are deﬁned by a strict sequence of sub-tasks,
in which all have to succeed (e.g. a mobile robot that has
to move to a region “A” and then to a region “B”). The
graphical representation of a sequence node is a box with a
“→”, as in Fig. 3.
A ﬁnite number of BTs T1,T2,...,TN can be composed
into a more complex BT, with them as children, using the
sequence composition: T0 = Sequence(T1,T2,...,TN).
Parallel: When the execution of a parallel node starts,
then the node’s children are executed in succession from
left to right without waiting for a return status from any
child before ticking the next one. It returns success if a
given number of children M ∈N return success, it returns
1A tick is a signal that enables the execution of a child.
→
Child 1
Child 2
· · ·
Child N
1
Fig. 3.
Graphical representation of a sequence node with N children.
failure when the children that return running and success
are not enough to reach the given number, even if they
would all return success. It returns running otherwise. The
purpose of the parallel node is to model those tasks separable
in independent sub-tasks performing non conﬂicting actions
(e.g. a multi object tracking can be performed using several
cameras). The parallel node is graphically represented by a
box with “⇉” with the number M on top left, as in Fig. 4. A
ﬁnite number of BTs T1,T2,...,TN can be composed into a
more complex BT, with them as children, using the parallel
composition: T0 = Parallel(T1,T2,...,TN,M).
⇒
M
Child 1
Child 2
· · ·
Child N
Fig. 4.
Graphical representation of a parallel node with N children.
Action
(a) Action node.
Condition
(b) Condition node.
Fig. 5.
Graphical representation of action and condition nodes.
Action: When an action node starts its execution, then
it returns success if the action is completed and failure if the
action cannot be completed. Otherwise it returns running.
The action node is represented in Fig. 5(a)
Condition: The condition node checks if a condition
is satisﬁed or not. The return status is success or failure
accordingly and it is never running. The condition node is
represented in Fig. 5(b).
Root: The root node is the node that generates ticks. It
is graphically represented by a box labeled with “∅”.
IV. PROBLEM FORMULATION
The problem considered in this work is to deﬁne identical
decentralized local BT controllers for the single robots of a
multi-robot system to achieve a global goal. We ﬁrst give
some assumptions used throughout the paper, we then state
the main problem.
Let S be a set of symbols describing atomic actions (e.g.
perform grasp, go to position) and let R ∈N be the set of
robots in a multi-robot system, each of which can perform
a ﬁnite collection of local tasks Li ⊆S, i ∈R and n = ∣R∣
and let ¯L = ⋃i∈R Li be the set of all the local tasks. Now
let G = {g1,g2,...,gv} be a ﬁnite collection of global tasks
executable by the multi-robot system and Pk be the set of
global tasks running in parallel with gk. We deﬁne ψ(gk) as
the ﬁnite set of local tasks which have to return success for
the global task gk to succeed.
Finally, let ν ∶G × ¯L →N and µ ∶G × ¯L →N respectively be
functions that give the minimum number of robots needed,
and the maximum number of robots assignable, to perform a
local task, in order to accomplish a global task. Given these,
we state the following assumptions:
Assumption 1: The
minimum
number
of
robots
re-
quired to execute global tasks running in parallel does
not exceed the total number of robots in the system:
∑gk∈Ph ∑lj∈ψ(gk) ν(gk,lj) ≤n ∀gh ∈G.
Assumption 2: Each global task in G can be performed
by assigning to some robots in R one of their local tasks:
ψ(gk) ⊆2 ¯
L ∀gk ∈G.
Problem 1: Given a multi-robot system deﬁned as above
and a global goal that satisﬁes Assumptions 1-2, design a
local BT controller for each single robot to achieve this goal.
V. PROPOSED SOLUTION
In this section, we will ﬁrst give an informal description
of the proposed solution, involving the three subtrees TG
(global tasks), TA (task assignment) and TLi(local tasks).
Then, we describe the design of these subtrees in detail. To
illustrate the approach we give a brief example, followed
by a description of how to create a multi agent BT from a
single agent BT. Finally, we analyze the fault tolerance of
the proposed approach.
The multi agent BT is composed of three subtrees running
in parallel, returning success only if all three subtrees return
success.
Ti = Parallel(TA,TG,TLi,3)
(1)
Remark 1: Note that all robots run identical copies of
this tree, including computing assignments of all robots
in the team, but each robot only executes the task that
they themselves are assigned to, according to their own
computation.
The ﬁrst subtree, TA is doing task assignment. Parts of the
performance and fault tolerance of the proposed approach
comes from this feature, making sure that a broken robot is
replaced and that robots are assigned to the tasks they do
best.
The second subtree, TG takes care of the overall mission
progression. This tree includes information on task that needs
to be done in sequence (using sequence composition), tasks
that could either be done in sequence or in parallel (using
parallel M = N compositions), fallback tasks that should
be tried in sequence (using selector compositions), and
fallbacks that can be tried in parallel (using parallel M = 1
compositions). The execution of TG provides information to
the assignment in TA. The fault tolerance of the proposed
approach is improved by the fallbacks encoded in TG, and the
performance is improved by parallelizing actions whenever
possible, as described above.
The third subtree, TLi uses output from the task assign-
ment to actually execute the proper actions. We will now
deﬁne the three subtrees in more detail.
a) Deﬁnition of TA: This tree is responsible for the
reactive optimal task assignment, deploying robots to dif-
ferent local tasks according to the required scenario. The
reactiveness lies in changes of constraints’ parameters in the
optimization problem, depicting the fact that the number of
robots needed to perform a given task changes during its
execution.
The assignment problem is solved using any other method
used in optimization problem. Here we suggest the following,
however the user can replace the solver without changing the
BT structure:
minimize
- ∑
i∈R
∑
lj∈¯
L
p(i,lj)r(i,lj)
subject to:
aj ≤∑
i∈R
r(i,lj) ≤bj ∀lj ∈Li
∑
lj∈¯
L
r(i,lj) ≤1 ∀i ∈R
r(i,j) ∈{0,1}
(2)
where r ∶R × ¯L →{0,1} is a function that represents the
assignment of robot i to a local task lj, taking value 1 if
the assignment is done and 0 otherwise; p ∶R × ¯L →¯R is
a function assigning a performance to robot i at executing
the task lj (if the robot i cannot perform the task lj i.e.,
lj ∉Li then p(i,lj) = -∞). aj,bj ∈N are respectively the
minimum and the maximum number of robots assignable to
the task lj and they change during the execution of (1) and
aj ∈N is set to a positive value upon requests from TG. At
the beginning they are initialized to 0, since no assignment
is needed. When the execution of a global task gk starts,
aj and bj are set respectively to ν(gk,lj) and µ(gk,lj)
∀lj ∈ψ(gk). Then when a local task lj ﬁnishes its execution
(i.e., it returns either success or failure), aj and bj decrease
by 1 until aj = 0, since the robot executing lj can be assigned
to another task while the other robots are still executing their
local task. When the task gk ﬁnishes, both aj and bj are set
back to zero.
The tree TA is shown in Fig. 6(a). The condition “Local Task
Finished” returns success if a robot has succeeded or failed
a local task, failure otherwise. For ease of implementation
a robot can communicate to all the other when has ﬁnished
a local task. The condition “New Global Task Executed”
returns success if it is satisﬁed, failure otherwise.
The condition “Check Consistency” checks if the constraints
of the optimization problem are consistent with each other,
since such constraints change their parameters during the
tree execution. The addition of a constraint in (2) effects the
system only if a solution exists. This condition is crucial to
run a number of global tasks in parallel according to the
number of available robots (see Example 1 below).
The action “Assign Agents” is responsible for the task
assignment, it returns running while the assignment routine
is executing, it returns success when the assignment problem
is solved and it returns failure if the optimal value is ∞.
b) Deﬁnition of TG: This tree is designed to achieve
the global goal deﬁned in Problem 1 (i.e., the global goal is
achieved if the tree returns success) executing a set of global
tasks.
An example of TG is depicted in Fig. 6(b). The execution
→
∅
?
Assign
Agents
Check
Consistency
Local
Task
Finished
New Global
Task
Executed
1
(a) Task Assignment tree
?
∅
→
Perform
Global
Task g4
Perform
Global
Task g1
Perform
Global
Task g2
Perform
Global
Task g3
1
(b) Global tasks tree
Fig. 6.
Example of BT modeling a global task
of the action “Perform Global Task gk” requires that some
robots have to be assigned, then it sets bj = µ(gk,lj) ∀lj ∈
ψ(gk). In the tree TA the condition “New Global Task
Executed” is now satisﬁed, making a new assignment if
the constraints are consistent with each other. Finally action
“Perform Global Task gk” returns success if the number of
local tasks lj ∈ψ(gk) that return success is greater than
ν(gk,lj) (i.e the minimum amount of robots needed have
succeeded) it returns failure if the number of local tasks
in ψ(gk) that return failure is greater than ∑i∈R r(i,j) −
ν(gk,lj) (i.e., some robots have failed to perform the task,
the remaining ones are not enough to succeed), it returns
running otherwise. The case of translating a single robot BT
to a multi robot BT is described in Section V-A below.
c) Deﬁnition of TLi: This tree comprises the planner
of a single agent. Basically it executes one of its subtrees
upon request from the TA, the request is made by executing
the action “Assign Agents”.
?
∅
→
This Agent
Assigned to
Local Task 1
Perform
Local
Task 1
→
This Agent
Assigned to
Local Task 2
Perform
Local
Task 2
. . .
→
This Agent
is not
Assigned
Rest
Fig. 7.
Example of BT modeling a local task on a single agent
Example 1: By way of example, we consider a system
that is to explore 2 different areas. Intuitively, different areas
can be explored by different robots at the same time but
if only a single robot is available those areas can only be
explored in a sequence. The local trees TLi are as depicted
in Fig. 8(b) and the global task tree TG as in Fig. 8(a).
Considering ﬁrst the case in which there is only one robot
available. When the execution of Explore Area A in TG starts,
in (2) the constraint that one robot has to be assigned to
explore area A is added (i.e. the related aj and bj are both
set to 1). The optimization problem is feasible hence the
assignment takes place. When the execution of Explore Area
B starts, the related constraint is not consistent with the other
constraints, since the only available robot cannot be assigned
to two tasks, hence the assignment does not take place.
Considering now the case where a new robot is introduced
in the system, it is possible to assign two robots. Both
constraints: the one related to Explore Area A and the
one related to Explore Area B, can be introduced in the
optimization problem without jeopardizing its consistency.
Those two tasks can be executed in parallel.
Note that the two different executions (i.e. Explore Area A
ﬁrst, then Explore Area B; Explore Area A and Explore Area
B in parallel) depend only on the number of available robots,
the designed tree does not change.
⇒
∅
2
Explore
Area A
Explore
Area B
1
(a) TG of example 1
?
∅
→
This Agent
Assigned to
Explore A
Go To
Area A
→
This Agent
Assigned to
Explore B
Go To
Area B
→
This Agent
is not
Assigned
Rest
1
(b) TLi of example 1
Fig. 8.
Trees of example 1
A. From single robot BT to multi-robots BT
Here we present how one can design a BT for a multi-robot
system reusing the BT designed to control a single robot. Let
TS be the tree designed for the single robot execution with
AS = {α1,α2,⋯} being the set of action nodes, each robot in
the multi-robot system will have as TG a tree with the same
structure of TS changing the meaning of the action nodes and
replacing the control ﬂow nodes with parallel nodes where
possible.
The action nodes of TG are the global tasks G of the tree (i.e.
tasks that the entire system has to perform). Their execution
has the same effect on the multi-robot system as the effect
of the actions AS in TS. The execution of tasks in G adds
constraints in the optimization problem of the tree TA deﬁned
by the sets ψ(gk), ∀gk ∈G. Those sets, in this case, have
all cardinality 1 (i.e., only one robot is assigned to perform
a task in G) since it is a translation from a single robot
execution to a multi-robot execution.
The main advantage of having a team of robots lies in fault
tolerance and the possibility of parallel execution of some
tasks. In the tree TG the user can replace sequence and
selector nodes with parallel nodes and M = N and M = 1
respectively (i.e., if the children of a selector node can be
executed in parallel, the correspondent parallel node returns
success as soon as one child returns success; on the other
hand if the N children of a sequence node can be executed
in parallel, the correspondent parallel node returns success
only when all of them return success). The trees TLi have
the same structure of the one deﬁned in section V, deﬁning
as “Perform Local Task k” the action αk.
Then to construct TG, ﬁrst each action node of TS is replaced
by a global task gk with ψ(gk) = αk and then the control
ﬂow nodes are replaced with parallel nodes where possible.
The tree TA is always the one deﬁned in section V.
Finally, each robot i in a multi-robot system runs the tree Ti
deﬁned in (1).
Here we observe that if the multi-robot system is heteroge-
neous the trees TLi are such that they hold the condition
¯L ⊆AS (i.e. the multi-robot system can perform the tasks
performed by the original single robot).
B. Fault Tolerance
The fault tolerance capabilities of a multi-robot system are
due to the redundancy of tasks executable by different robots.
In particular, a local task lj can be executed by every robot
i ∈R satisfying the condition lj ∈Li. Here we make the
distinction between minor faults and major faults of a robot
according to their severity. A minor fault involves a single
local task lj, i.e. the robot is no longer capable to perform
the task lj, here the level of a minor fault is the number of
local tasks involved. A major fault of a robot implies that
the robot can no longer perform any of its local task.
Remark 2: A minor fault of level λ is different from λ
minor faults, since the latter might involve different robots.
Remark 3: A major fault involving a robot i ∈R is
equivalent to a minor fault of level ∣Li∣involving every task
in Li.
Deﬁnition 1: A multi-robot system is said to be weakly
fault tolerant if it can tolerate any minor fault.
Deﬁnition 2: A multi-robot system is said to be strongly
fault tolerant if it can tolerate any major fault.
Lemma 1: A multi-robot system is weakly fault tolerant
if and only if for each robot i ∈R and for each local task
lj
∈Li there exists another robot h ∈R such that lj ∈
Li∩Lh and the problem (2) is consistent under the constraint
r(i,j) ⋅r(h,j) = 0.
Proof: (if) When r(i,j) ⋅r(h,j) = 0 either robot i or
h is not deployed. Assume that the robot i is involved in a
minor fault, related to the local tasks lj. Since lj ∈Li ∩Lh,
lj ∈Lh then the robot h can perform the local task lj in
place of robot i, since it is not deployed.
(only if) if the system can tolerate a minor fault then for
each robot i there exists another robot h such that the local
task related to the fault can be performed by both of them
since one took over the other. Hence lj ∈Li and lj ∈Lh, this
implies that lj ∈Li ∩Lh holds. Moreover, if the fault can be
tolerated it means that when lj is performed either the robot i
or robot h is not deployed otherwise the reassignment would
not be possible. Hence the condition r(i,j) ⋅r(h,j) = 0
holds.
Corollary 1: A multi-robot system can tolerate a minor
fault of level λ if Lemma 1 holds for the local tasks involved
in the fault.
Lemma 2: A multi-robot system is strongly fault tolerant
if and only if for each robot i there exists a set of robots I
such that Li ⊆∪n
h∈I,h≠iLh and the problem (2) is consistent
under the constraints r(i,j) ⋅r(h,j) = 0 ∀j ∶lj ∈Li,h ∈I.
Proof: (if) Since Li ⊆∪h∈I,h≠iLh all the local task of
the robot i can be performed by some other robots in the
system. Then when the robot i is asked to perform a local
task lj, exists at least another robot that can perform such
task, this robot is not deployed since r(i,j) ⋅r(h,j) = 0
∀j ∶lj ∈Li,h ∈I.
(only if) if the system can tolerate a major fault then exists
a robot i that is redundant, i.e. its tasks can be performed by
other robots. Hence there exists a set of robots I, in which
i is not contained, such that Li ⊆∪h∈I,h≠iLh, moreover
since each local task lj of the robot i can be performed
by a robot h ∈I, robot h is not deployed when i is
performing lj otherwise it could not take over robot i, hence
r(i,j) ⋅r(h,j) = 0 ∀j ∶lj ∈Li,h ∈I.
VI. MOTIVATING EXAMPLE
In this section we expand upon the example that was
brieﬂy mentioned in Section I, and involves a multi-robot
system that is to replace damaged parts of the electronic
hardware of a vehicle. Let us assume that to repair the
vehicle, the system has to open the metal cover ﬁrst, then
it has to check which parts have been damaged, replace
the damaged parts, solder the connecting wires, and ﬁnally
close the metal cover. In this example the setup is given by
a team composed by robots of type A, B and C. Robots
of type A are small mobile dual arm robots that can carry
spare hardware pieces, place them and remove the damaged
part from the vehicles, and do diagnosis. Robots of type
B are also small mobile dual arm robots with a gripper and
soldering iron as end effectors. Robots of type C are big dual
arm robots that can remove and fasten the vehicle cover. We
consider the general case in which the vehicle’s electronic
hardware consists of p parts, all of them replaceable. The
global tasks set is deﬁned as:
G ={Normal Operating Condition,Open Metal Cover,
Close Metal Cover,Fix Part 1,Fix Part 2,...,Fix Part p,
Diagnose Part 1,Diagnose Part 2,...,Diagnose Part p}.
(3)
where:
Open Metal Cover ={Remove Screws,Remove Cover}
Close Metal Cover ={Place Screws,Place Cover}
Fix Part k
={Fix HW k,Fix Wires k,
Solder k} k = {1,2,...,p}.
(4)
The local tasks for robots of type A set are:
Li ={Replace HW,Replace Wires,Do Diagnosis on k}
i = {1,2}.
(5)
The local tasks for robots of type B set are:
Li ={Replace HW,Replace Wires,
Do Diagnosis on k,Solder} i = {3,4}.
(6)
Task
Robots A
Robots B
Robots C
Use Screwdriver
-∞
-∞
1
Move Frame
-∞
-∞
1
Do Diagnosis on k
3
1
-∞
Replace HW k
1.5
1
-∞
Replace Wires k
1.5
1
-∞
Use Soldering Iron on k
-∞
1
-∞
TABLE I.
Robot performances values
Patameter
Value
ν(Remove Screws, Use Screwdriver)
1
µ(Remove Screws, Use Screwdriver)
2
ν(Place Screws, Use Screwdriver)
1
µ(Place Screws, Use Screwdriver)
2
ν(Remove Cover, Move Frame)
2
µ(Remove Cover, Move Frame)
2
ν(Place Screws, Remove Cover)
1
µ(Place Screws, Remove Cover)
2
ν(Place Cover, Move Frame)
2
µ(Place Cover, Move Frame)
2
ν(Diagnose Part k, Do Diagnosis on k)
1
µ(Diagnose Part k, Do Diagnosis on k)
1
ν(Fix HW k, Replace HW k)
1
µ(Fix HW k, Replace HW k)
1
ν(Fix Wires k, Replace Wires k)
1
µ(Fix Wires k, Replace Wires k)
2
ν(Solder k, Use Soldering Iron on k)
1
µ(Solder k, Use Soldering Iron on k)
3
TABLE II.
Scenario parameters. Note that when ν = µ, as in the case of
(Remove Cover, Move Frame) we have that the number of required robots
for a task is equal to the maximal number of robots that can participate in
executing the task.
The global tasks for robots of type C set are:
Li ={Use Screwdriver,Move Frame i = {5,6}.
(7)
The map from global tasks to local tasks ψ are as follows:
ψ(Remove Screws)
= Use Screwdriver
ψ(Place Screws)
= Use Screwdriver
ψ(Remove Cover)
= Move frame
ψ(Place Cover)
= Move frame
ψ(Diagnose Part k)
= Do Diagnosis on k
ψ(Fix HW k)
= Replace HW k
ψ(Fix Wires k)
= Replace Wires k
ψ(Solder k)
= Use Soldering Iron on k
(8)
The tree TG deﬁned is showed in Fig. 9.
A. Execution
Here we describe the execution of the above mission using
the proposed framework.
Consider a team of 2 robots of type A, 2 robots of type B,
and 2 robots of type C designate to diagnose and ﬁx a vehicle
composed by 5 critical parts as depicted in Fig. 10(a). The
robots’ performances p(i,lj) are related to how fast tasks
are accomplished. They are collected in Table I, and the
scenario’s parameters are in Table II.
When the vehicle is running on nominal operating con-
ditions, the assignment tree TA of each robot has aj =
bj = 0 since no assignments are needed. When a fault
on the vehicle takes place, the condition “Nominal Op-
erating Conditions” is no longer true in all the robots’
BTs, then the “Remove Screws” action has to be executed.
According to ψ(Remove Screws) this global task requires
the local task “Use Screwdriver” to be accomplished. The
constraints related to this task have to be added in (2) after
checking the feasibility of the optimization problem. The
parameter aj and bj for “Use Screwdriver” are changed
into: aj = ν(Remove Screws, Use Screwdriver) = 1 and
bj = µ(Remove Screws, Use Screwdriver) = 2 with j ∶
lj = {Use Screwdriver}. Solving (2) both robots C are
assigned to “Use Screwdriver”, while the other are not
deployed (Fig. 10(b)). When a robot accomplishes its local
task, then the corresponding bj is decreased by 1 until
bj = 0 and the robot can be deployed for a new task if
needed. A similar assignment is then made to accomplish
the global task “Remove Cover”. After removing the metal
cover, all the vehicle hardware have to be diagnosed, and
the global task “Diagnose Part 1” will change the pa-
rameters in aj = ν(Diagnose Part 1, Do Diagnosis on 1) =
1 and bj
=
µ(Diagnose Part 1, Do Diagnosis on 1)
=
1
with
j
∶
lj
=
Do Diagnosis on 1,
in
a
similar
way “Diagnose Part 2” will change the parameters in
aj
= ν(Diagnose Part 2, Do Diagnosis) = 1 and bj
=
µ(Diagnose Part 2, Do Diagnosis)
=
1 with j
∶
lj
=
Do Diagnosis and so forth until “Diagnose Part 4”. When
the system changes the parameters related to “Diagnose Part
5” the optimization problem is not feasible since there are
not enough agents, then the assignment for “Diagnose Part
5” does not take place (Fig. 10(c)).
Here we show the reactive functionality of the proposed
framework. Note that the robots of type A have higher perfor-
mance than the robots of type B in doing diagnosis according
to Table I, i.e., they are faster. While the robots of type B
are still doing diagnosis on HW3 and HW4, the robots
of type A can be deployed for new tasks without waiting
for the slower robots (Fig. 10(d)). After diagnosis, HW2
and HW4 must be replaced, robots of type A have higher
performance in “Replace HW” therefore, they are deployed
to minimize the objective function of (2), robots of type B
are not deployed since µ(Fix HW k, Replace HW k) = 1
i.e. the replacing of an electronic HW is made by a single
robot (Fig. 10(e)).
If a robot of type A has a major fault, all its performance
parameters are set to -∞and a robot of type B can take over
since it can execute all the task of a robot A, this situation is
depicted in Fig. 10(f). Here two robots of type B are replac-
ing wires on HW1, since µ(Fix Part i, Replace Wires) = 2
and a robot of type A is replacing wires on HW2. The ﬁnal
part of the repair is the soldering of the new wires, executable
only by robots of type B (Fig. 10(g)). Finally the metal cover
is put back (Fig. 10(h)) and the tree TG returns success.
B. Fault Tolerance Analysis
Analyzing the system, it is neither weakly nor strongly
fault tolerant. A minor fault on the local task “Move Frame”
→
Remove
Screws
Remove
Cover
Place
Screws
Place Cover
∅
?
Nominal
Operating
Conditions
⇒
p
?
Diagnose
Part 1
?
Diagnose
Part 2
· · ·
?
Diagnose
Part p
→
Fix
HW 1
Fix
Wires 1
Solder
1
→
Fix
HW 2
Fix
Wires 2
Solder
2
→
Fix
HW p
Fix
Wires p
Solder
p
1
Fig. 9.
TG of Example VI-A
can not be tolerated since ν(Remove Cover, Move Frame) =
2 as well as ν(Place Cover, Move Frame) = 2 thus a single
robot cannot perform the task. However, some faults can be
tolerated. The multi-robot system can tolerate up to 3 major
faults (2 faults involving both robots A, and 1 fault involving
a robot B) and up to 11 minor faults (1 fault involving “Use
Screwdriver”, 3 faults involving “Replace HW k”, 3 faults
involving “Replace Wires k”, and 3 faults involving “Do
diagnosis on k” ), as long as at least one robot of type B
and 2 robots of type C are operating. Note that the local task
“Use soldering iron on k” can be performed by a robot of
type B only.
VII. CONCLUSIONS
We have shown a possible use of BTs as a distributed
controller for multi-robot systems working towards global
goals. This extends the ﬁelds where BTs can be used, with
a strong application in robotic systems. We have also shown
how using BTs as a framework for robot control becomes
natural going from a plan meant to be executed by a single
robot to a multi-robot plan.
ACKNOWLEDGMENT
This work has been supported by the Swedish Research
Council (VR) and the European Union Project RECONFIG,
(FP7-ICT-2011-9), the authors gratefully acknowledge the
support.
REFERENCES
[1] D. Isla, “Handling Complexity in the Halo 2 AI,” in Game Developers
Conference, 2005.
[2] A. Champandard, “Understanding Behavior Trees,” AiGameDev. com,
vol. 6, 2007.
[3] D. Isla, “Halo 3-building a Better Battle,” in Game Developers
Conference, 2008.
[4] C. Lim, R. Baumgarten, and S. Colton, “Evolving Behaviour Trees
for the Commercial Game DEFCON,” Applications of Evolutionary
Computation, pp. 100–110, 2010.
[5] D. Perez, M. Nicolau, M. O’Neill, and A. Brabazon, “Evolving
Behaviour Trees for the Mario AI Competition Using Grammatical
Evolution,” Applications of Evolutionary Computation, 2011.
[6] A. Shoulson, F. M. Garcia, M. Jones, R. Mead, and N. I. Badler,
“Parameterizing Behavior Trees,” in Motion in Games.
Springer,
2011.
[7] I. Bojic, T. Lipic, M. Kusek, and G. Jezic, “Extending the JADE
Agent Behaviour Model with JBehaviourtrees Framework,” in Agent
and Multi-Agent Systems: Technologies and Applications.
Springer,
2011, pp. 159–168.
A
REST
A
REST
B
REST
B
REST
C
REST
C
REST
HW1
HW1
HW2
HW3
HW4
HW5
(a) Screenshot I
A
REST
A
REST
B
REST
B
REST
HW1
C
USE
SCREW-
DRIVER
C
USE
SCREW-
DRIVER
HW1
HW2
HW3
HW4
HW5
(b) Screenshot II
C
REST
C
REST
HW1
A
DIAGNOSE
A
DIAGNOSE
B
DIAGNOSE
B
DIAGNOSE
HW1
HW2
HW3
HW4
HW5
(c) Screenshot III
C
REST
C
REST
HW1
A
DIAGNOSE
A
REPLACE
HW
B
DIAGNOSE
B
DIAGNOSE
HW1
HW2
HW3
HW4
HW5
(d) Screenshot IV
[8] P. ¨Ogren, “Increasing Modularity of UAV Control Systems using
Computer Game Behavior Trees,” in AIAA Guidance, Navigation and
Control Conference, Minneapolis, MN, 2012.
[9] J. A. D. Bagnell, F. Cavalcanti, L. Cui, T. Galluzzo, M. Hebert,
M. Kazemi, M. Klingensmith, J. Libby, T. Y. Liu, N. Pollard,
M. Pivtoraiko, J.-S. Valois, and R. Zhu, “An Integrated System
for Autonomous Robotics Manipulation,” in IEEE/RSJ International
Conference on Intelligent Robots and Systems, October 2012, pp.
2955–2962.
[10] A. Kl¨okner, “Interfacing Behavior Trees with the World Using De-
scription Logic,” in AIAA conference on Guidance, Navigation and
Control, Boston, 2013.
[11] M. Colledanchise and P. Ogren, “How Behavior Trees Modularize
Robustness and Safety in Hybrid Systems,” in Intelligent Robots and
Systems (IROS 2014), 2014 IEEE/RSJ International Conference on,
Sept 2014, pp. 1482–1488.
[12] E. W. Dijkstra, “Letters to the editor: go to statement considered
harmful,” Commun. ACM, vol. 11, pp. 147–148, March 1968.
[13] X. C. Ding, M. Kloetzer, Y. Chen, and C. Belta, “Automatic deploy-
ment of robotic teams,” Robotics Automation Magazine, IEEE, vol. 18,
no. 3, pp. 75–86, 2011.
[14] S. Karaman and E. Frazzoli, “Vehicle routing problem with metric
temporal logic speciﬁcations,” in Decision and Control, 2008. CDC
2008. 47th IEEE Conference on, 2008, pp. 3953–3958.
C
REST
C
REST
HW1
A
REPLACE
HW
A
REPLACE
HW
B
REST
B
REST
HW5
HW2
HW3
HW4
HW5
(e) Screenshot V
C
REST
C
REST
HW1
A
REPLACE
HW
A
FAULT
B
REPLACE
HW
B
REST
HW1
HW2
HW3
HW4
HW5
(f) Screenshot VI
C
REST
C
REST
HW1
A
REST
A
FAULT
B
USE
SOLDERING
IRON
B
USE
SOLDERING
IRON
HW1
HW2
HW3
HW4
HW5
(g) Screenshot VII
HW1
A
REST
A
FAULT
B
REST
B
REST
HW1
HW2
HW3
HW4
HW5
C
USE
SCREW-
DRIVER
C
USE
SCREW-
DRIVER
(h) Screenshot VIII
Fig. 10.
Plan Execution. HW components are either un-diagnosed (grey),
checked and OK (green) or broken (red)
[15] A. Ulusoy, S. L. Smith, and C. Belta, “Optimal multi-robot path
planning with ltl constraints: Guaranteeing correctness through syn-
chronization,” CoRR, vol. abs/1207.2415, 2012.
[16] C. Castelfranchi and R. Falcone, “Towards a Theory of Delegation for
Agent-based Systems,” Robotics and Autonomous Systems, vol. 24, pp.
141–157, 1998.
[17] R. Falcone and C. Castelfranchi, “C.: The human in the loop of a
delegated agent: The theory of adjustable social autonomy,” IEEE
Transactions on Systems, Man and CyberneticsPart A: Systems and
Humans, pp. 406–418, 2001.
[18] P. Doherty, D. Landn, and F. Heintz, “A distributed task speciﬁcation
language for mixed-initiative delegation,” 2012.
[19] A. Marzinotto, M. Colledanchise, C. Smith, and P. ¨Ogren, “Towards
a Uniﬁed Behavior Trees Framework for Robot Control,” in Robotics
and Automation (ICRA), 2014 IEEE International Conference on, June
2014.
[20] M. Colledanchise, A. Marzinotto, and P. ¨Ogren, “Performance Analy-
sis of Stochastic Behavior Trees,” in Robotics and Automation (ICRA),
2014 IEEE International Conference on, June 2014.