Mission Oriented Robust Multi-Team Formation and Its Application to Robot Rescue Simulation

1 Introduction

Team formation [Liemhetcharat and Veloso, 2012; Nair and Tambe, 2005; Vidal, 2004] is an important aspect of multiagent systems. In many application problems, e.g., RoboCup Rescue [Kitano and Tadokoro, 2001; James et al., 2015], unmanned aerial vehicles operations [George et al., 2010], and team formation in social networks [Lappas et al., 2009], the groups of agents must coordinate to solve them e↵ectively. In a dynamic environment that o↵ers the possibility of losing agents during a mission, e.g., an agent is injured in a rescue mission, the robustness of a team is crucial. How to form the robust teams that can continue to perform their missions (even if some agents break down) is the main purpose of this work.

In this paper, a novel framework called a mission-oriented robust multi-team formation problem is defined. In this problem, a set of agents and a set of missions are given, and the aim is to form robust teams which can achieve the given missions even if some agents break down, minimize the total cost and maximize the robustness of the teams.

Furthermore, two algorithms are provided to tackle this problem, namely a complete and an approximate algorithms, and also some heuristics are developed that exploit the specificities of the problem. The complete algorithm is based on a branch and bound technique [Lawler and Wood, 1966] and can guarantee to find all Pareto optimal teams, i.e., trade-o↵ between the cost and robustness of the teams. However, since the number of Pareto optimal teams is often exponential, finding all Pareto optimal teams becomes easily intractable [Okimoto et al., 2012]. Thus, a local search based approximate algorithm is also provided [Aarts and Lenstra, 2013].

In the experiments, the performances of two algorithms are evaluated in RMASBench [Kleiner et al., 2013], a testbed for multi-agent coordination algorithms based on the existing RoboCup Rescue simulation platform (RSP) [Skinner and Ramchurn, 2010]. RMASBench provides a library of implementations of state-of-the-art distributed constraint optimization solvers such as DSA [Fitzpatrick and Meertens, 2003] and MaxSum [Farinelli et al., 2008] and facilities to compare coordination algorithms. Our local search based approximate algorithm is then compared with those existing solvers.

As an application domain, we believe that forming rescue teams is promising. Consider the problem of forming rescue teams in a disaster area. There are a set of missions to be accomplished which changes dynamically and a set of rescue robots, where each robot has di↵erent skills to achieve the tasks of a mission, e.g., providing medical treatment, acting as a firefighter and driving a vehicle. Assume that their current positions are di↵erent. Forming robust and costly rescue teams by considering the distance to the disaster area, amounts to a robust multi-team formation problem.

Compared to [Okimoto et al., 2015], the aim of our framework is to form multiple robust teams. Also, this paper proposes efficient algorithms and evaluates them on RoboCup Rescue simulations, while [Okimoto et al., 2015] provides a standard algorithm and evaluates it with random problems. Our framework is similar to the multi-set multi-cover problem [Hua et al., 2009] where the authors proposed an algorithm in which multiple sets can cover a multi-set. If we consider a mission as a set of tasks, finding a robust team to achieve the mission is equivalent to trying to cover the set of tasks multiple times. Compared to [Hua et al., 2009], this paper considers the robustness and the cost of each team simultaneously (i.e. bi-objective optimization).

2 Mission-Oriented Robust Multi-Team Formation

In this section, a formal framework for mission-oriented robust multi-team formation is defined. Furthermore, the biobjective optimization problem for this framework is pointed out, i.e., finding out every multi-team, which is optimally robust and/or cheap. The following definitions are similar to the definitions provided in [Okimoto et al., 2015].

Definition 1 (Multi-TeamFormation Problem) A multiteam formation problem description is defined by a tuple MTF = hA, S, M, cost, skilli, where A = {a1, ..., an} is a set of agents, S = {s1, ..., sm} is a set of skills (of agents), M = {m1, ...,mg} is a set of missions where mi ✓ 2 S for 1  i  g, cost : 2 A ⇥ M ! N is a cost function, and skill is a mapping from A to 2 S . A set of agents T ✓ A is said to be a team and a pair (T, m) is called a mission team where m 2 M.

In the following, two standard properties and the robustness of a mission team are defined.

Definition 2 (Mission TeamCost) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description. Given a mission team (T,m) and a non-negative integer c, (T,m) is called c-costly, if the cost of (T,m) is less than c :

Definition 3 (Mission TeamValidity) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description. Given a mission team (T, m), the mission team is said to be valid w.r.t. m, if (T, m) can accomplish m :

Definition 4 (Mission TeamRobustness) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description. Given a mission team (T, m) and a non-negative integer k, (T,m) is said to be k-robust w.r.t. m, if for every set of agents T 0 ✓ T, such that |T 0 |  k, (T \ T 0 ,m) is valid w.r.t. m.

Now, a mission multi-team for multi-team formation and its properties are defined, i.e., cost, validity and robustness.

Definition 5 (MissionMulti-Team) Let MTF = hA, S, M, cost, skilli be a multi-team formation problem description. A set of mission teams is said to be a mission multi-team denoted MMT .

Definition 6 (MissionMulti-TeamCost) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description. Given a mission multi-team MMT and a non-negative integer cM, MMT is said to be cM-costly if the sum of the costs of all (Ti,mi) 2 MMT, (1  i  g), is less than cM :

Definition 7 (MissionMulti-TeamValidity) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description. Given a mission multi-team MMT, MMT is said to be valid w.r.t. M, if each mission team (Ti, mi) of MMT is valid w.r.t. mi where 1  i  g.

Definition 8 (MissionMulti-TeamRobustness) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description. Given a mission multi-team MMT and a nonnegative integer kM, MMT is said to be kM-robust w.r.t. M, if for every mission team (Ti,mi) 2 MMT where 1  i  g, (Ti,mi) is at least kM-robust w.r.t. mi, i.e., for every ki-robust mission team (Ti, mi) of MMT ,

When we consider the cost and the robustness of a mission multi-team together, we can view a multi-team formation as a bi-objective optimization problem. In this problem, generally, since trade-o↵s exists between two objectives, there does not exists an ideal mission multi-team which minimizes the cost cM and maximizes the robustness kM simultaneously. Therefore, the "optimal" mission multi-team of this problem is characterized by using the concept of Pareto optimality.

Definition 9 (Dominance) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description and MMT and MMT 0 be two mission multi-teams, where MMT is cM-costly and kM-robust and MMT 0 is c 0 M -costly and k 0 M - robust. MMT dominates MMT 0 if and only if kM ≥ k 0 M and cM < c 0 M , or kM > k 0 M and cM  c 0 M .

Definition 10 (Pareto optimality) Let MTF = hA, S , M, cost, skilli be a multi-team formation problem description and MMT be a mission multi-team. MMT is said to be a Pareto optimal mission multi-team if there exists no mission multi-team MMT 0 that dominates MMT.

Definition 11 (Bi-objective optimization problem)

Input: A multi-team formation problem description MTF = hA, S , M, cost, skilli.

Output: Find all Pareto optimal mission multi-teams (T, m).

3 Algorithms for Mission-Oriented Robust Multi-Team Formation

In this section, two algorithms for solving a mission oriented robust multi-team formation problem are proposed, namely complete and approximate algorithms. The former can guarantee to find all Pareto optimal mission multi-teams, while the latter can find good mission multi-teams very quickly.

3.1 Complete Algorithm

The complete algorithm is based on a branch and bound technique [Lawler and Wood, 1966] and can guarantee to find all Pareto optimal teams, i.e., trade-o↵ between the cost and robustness of the teams. In this algorithm, we exploited the specificities of the multi-team formation problem MT F to design dedicated heuristics and consider each agent as a variable whose each domain value corresponds to a mission. Algorithm 1 shows the initialization of this algorithm. In the pseudo-code, S and As are initialized (i.e., we set them as empty), where S is a set of MMT s and As represents an MMT (line 3-6). At the beginning, agents are not assigned to any mission, i.e., each mission multi-team is the empty set (line 8). In this algorithm, in order to create a search-tree, we assume that the ordering among agents is lexicographically

Algorithm 1 Multi-Teams Formation Branch & Bound

• 1: INPUT : A multi-team formation problem MTF =

<A, P, M, cost, skill>. 2: OUTPUT : the set of all Pareto optimal mission multi-teams S 3: S : a set of MMTs // All Pareto optimal solutions 4: S ; 5: As: a MMT // Current assignments 6: As ; 7: for each mission m of M do 8: As As [ {(;,m)} // All missions are added to As 9: end for 10: solve(1, As, S, MTF) 11: Return S

given. The solving starts with the first agent of the ordering among agents, i.e., root node in the search tree (line 10).

Algorithm 2 shows the details of the solving part. It takes an integer N as a parameter and tries to assign the N-th agent of A to each possible mission M (line 11,12). When an agent cannot perform any task of the mission m, this mission is ignored. Otherwise, the agent is added to the team T of (T,m) 2 As (line 13-16). If the team cost of As is larger than the cost bound by adding the agent in T, the next mission is considered (line 17-20). Then, it checks the validity of As (line 21-32). In this part, the basic idea is to detect the case when the current partial team assignment As cannot lead to a valid completion. To form a k-robust mission team for a mission, we need at least k + 1 agents. Thus, it can compute the minimal number of agents required to obtain a valid mission team for each remaining missions (line 22-29). When the number of remaining unassigned agents is lower than this minimal value, it is not possible to find a mission team with the current partial assignment. (|A| - N) is the maximal number of agents that can still be added in a mission team. If this number is less than the minimal required MinAgent, it is useless to continue with the current mission teams. It cancels the last choice of adding agent (T T \ {a}), and continues with the next agent (line 30-32). This allows us to branch before assigning all agents and reduces the search space. If the current assignment passed all checks, it continues to solve with the next agent (line 34). When the last agent of A has been assigned in As, it provides a complete assignment. If As is valid and not (Pareto) dominated, As is added to S (line 2-9). When the previous mission teams of S are dominated by the current mission team As, they are removed from S . Finally, it backtracks (line 9 and 35) and continues the search (line 12).

Theorem 1 For the proposed complete algorithm, it holds (i) the required memory belongs to O(n(m + 1) n ) and (ii) the required computation time belongs to O(n(m + 1) n+2 ), where m is the number of missions and n is the number of agents.

Let us proof (i). In the worst case, all possible mission multi-teams are Pareto optimal, i.e., there exists (m + 1) n Pareto optimal mission multi-teams: each agent can belong to every possible teams or no team. A mission multi-team is composed by an assignment and a pair of integers: the cost and the robustness of it. Since an agent can only belong to one mission team, an assignment can be represented by a vector of integers of size n were each component encodes the team

Algorithm 2 solve(N, As, S , MTF)

1: INPUT : An integer N, As an MMT, a set of mission multi-teams T and a multi-teams formation problem MTF = <A, P, M, cost, skill>. 2: // 1) All agents have been assigned 3: if N > |A| then 4: if As is not valid then 5: Return 6: if As is not dominated by any element of S then // Check As is dominated by the elements of S 7: Remove all MMT from S which are dominated by As // Check As dominates the elements of S 8: S S [ {As} 9: Return 10: a: the N th agent of A 11: // 2) Assign agent N to a mission 12: for each (T,m) of As do 13: // 3) Check if a can accomplish a task of m 14: if skill(a) \ m == ; then 15: Continue 16: T T [ {a} 17: // 4) Check the cost bound 18: if cost(As) > maxCost then 19: T T \ {a} 20: Continue 21: // 5) Check the validity 22: MinAgent : 0 23: for each pair (Ti,mi) of As do 24: k : the required robustness for mi 25: if Ti is not valid w.r.t. m then 26: MinAgent MinAgent + k + 1 27: if Ti is k 0 -robust w.r.t. m and k 0 < k then 28: MinAgent MinAgent + (k - k 0 ) 29: end for 30: if (|A| - N) < MinAgent then 31: T T \ {a} 32: Continue 33: // 6) Continue the search with the next agent 34: solve(N + 1,As, S , MTF) 35: T T \ {a} 36: end for 37: Return

of one agent. In order to compute the robustness, for each pair (T, m 0 ) 2 As, we store a vector where each component corresponds to a skill s of m 0 and the value of the component is the number of agents a 0 of T such that s 2 skill(a 0 ). The memory size of the Pareto optimal mission multi-teams is then bound by O((2 + 2n)(m + 1) n ) = O(n(m + 1) n ). Since the complete algorithm only requires to store them during the solving, the required memory is bound by O(n(m + 1) n ).

Next, let us proof (ii). Let ST be the number of partial assignments of MTF and j be a non-negative integer (1  j  n). Consider that only one agent can change its mission team at a given time. When no pruning occurs, and since there are (m + 1) j possible assignments for the first j agents in the ordering, the number of partial assignments is given by P n j=1 (m + 1) j = (m+ 1) n+1 - 1 m+ 1 - 1 - 1 = (m+ 1) n+1 - 1 m - 1 that is bound by O((m + 1) n+1 ). In each time, a new mission team (T,m 0 ) is assigned to an agent a in the current partial assignment As, the complete algorithm:

Algorithm 3 Multi-Teams Formation Local Search

1: INPUT: A multi-teams formation problem MTF = <A, P, M, cost, skill> and MaxNeighbor a non-negative integer 2: OUTPUT : the best MMT found 3: try 0 4: Create a MMT As randomly until As is valid 5: // Phase 1: Random search 6: do 7: As 0 As 8: do// 1.1) Generate a neighbor of As 9: Select an agent a randomly 10: m1 the mission of a 11: Remove a from T1 in (T1, m1) 2 As 0 12: Select a mission m2 randomly 13: Add a to T2 in (T2,m2) 2 As 0 14: while As 0 is not valid 15: if As 0 dominates As then // 1.2) Better solution 16: As As 0 17: try 0 18: else// 1.3) Try another neighbor 19: try try + 1 20: while try < MaxNeighbor 21: // Phase 2: Systematic search 22: do 23: As 0 As 24: improvement False 25: for each agent a of A do 26: m1 the mission of a 27: Remove a from T1 in (T1, m1) 2 As 0 28: for each mission m in M do 29: Add a to T in (T, m) 2 As 0 30: if As 0 dominates As then 31: As As 0 32: improvement True 33: Break 34: end for 35: if improvement == True then 36: Break 37: end for 38: while improvement == True 39: return As

• checks if the agent a can accomplish m 0 . This operation is linear and only requires to check if skill(a) \m 0 , ;, i.e., it has a cost of the number of skills in the worst case.
• computes the new cost cost (As). This operation is constant and just removes the cost of the previous team assigned to a and add one of the new assigned team.
• updates the robustness of T. This operation is linear. As stated before, T has a vector where each component corresponds to a skill s of m 0 and the component value is the number of agents a 0 of T such that s 2 skill (a 0 ), i.e. this requires at most s operations.
• checks the cost bound. This operation is constant.
• checks the validity of As. This operation requires to compute the minimum number of agents needed to make T valid for each mission team (T, m 0 ).

This number is the di↵erence between the current robustness k 0 of T and the required robustness k. Both k 0 and k are known, so that the whole operation has a linear complexity, i.e., O(m). In case no pruning occurs, ST represents the maximal occurrences of the five above operations. Solving a MTF with this complete algorithm is then bound by

|ST| ⇥ (t + 1 + s + 1 + m) = O((m + 1) n+1 ⇥ (t + s + m)) where t is the number of skills. Finally, when As is a complete assignment, the algorithm checks if As is dominated by the current Pareto optimal mission multi-teams. This operation is linear in the size of them, i.e., it compares the pair (cost (As), k) with all elements of them, which has a complexity of O(2n(m + 1) n ). Thus, the runtime complexity is bounded by O((m + 1) n+1 ⇥ (t + s + m)) + 2n(m + 1) n ) which belongs to O(n(m + 1) n+2 ).

3.2 Approximate Algorithm

Since the complexity of the complete algorithm is exponential in the number of agents (in the worst case), an approximate algorithm is also provided that is based on local search technique. Algorithm 3 shows the pseudo-code of it. The input is a multi-teams formation problem MTF and a non-negative integer MaxNeighbor which is used to limit the search. First, it generates a MMT randomly until a valid one is found (line 4). Then, a neighbor MMT is computed by randomly switching the mission team of an agent (line 9-13). If the selected MMT is not valid, another neighbor is generated. When a valid neighbor dominates the current candidate, i.e., both its cost and its robustness are better, it becomes the new candidate (line 15-17) and the search continues. Otherwise, another neighbor MMT is considered (line 18-19). The phase 1 terminates after MaxNeighbor improvement failures (line 520). The phase 2 is a systematic search which ensures to reach a local optimal (line 21-38). It avoids to miss a good mission multi-team that will happen to be near the current candidate. In this phase, every neighbors assignments is checked and the current candidate is changed to its neighbor when a better candidate is found. The search continues until the current candidate is not dominated by any of its direct neighbor. Finally, it outputs the local optimal mission multi-team.

4 Evaluation

In this section, the complete and approximate algorithms are evaluated with RMASBench [Kleiner et al., 2013], benchmarking platforms for agent-based system. RMASBench is a testbed for multi-agent coordination algorithms based on the existing RoboCup Rescue simulation platform (RSP) [Skinner and Ramchurn, 2010]. It simulates urban searches and rescue scenarios using real city maps. Figure 1 shows one of the representative scenarios, where Paris is the playground. In fig. 1, the 18 red points are the firemen agents and the 5 black crosses locate the initial ignition points where the fire start to spread. The RMASBench simulation platform introduces a generic API for multi-agent coordination, which essentially provides facilities for exchanging messages among agents and decisions making. It provides a library of implementation of state-of-the-art solvers, e.g., DSA [Fitzpatrick and Meertens, 2003] and MaxSum [Farinelli et al., 2008], as well as facilities to compare coordination algorithms.

4.1 Context

In RMASBench, the coordination problem is about assigning fire brigades to fires in order to mitigate damages on buildings and try to stop fires propagation. The benchmark poses crucial challenges for coordination. The agents evolve in a dynamic environment where a set of fires to be extinguished varies over the time. Fires may spread to neighboring buildings and grow in intensity as time goes, making them harder to extinguish and more likely to spread. The simulation is turn based (i.e. in each turn, the complete state of the world is known). It includes the positions of agents, the fires locations and the blockades places. Given the information, in each turn, the solver has to assign a target to each agent, i.e., a fire for each fireman and a blockade for each policeman. It has a strong spacial aspects: a fire brigade agent can operate on a given fire only if it is physically located in the proximity of that fire, hence agents must consider their travel time when coordinating. Moving to a distant location takes several turns, during which the state of the world changes. Agents have to change target because of the blockades appearance or buildings destruction. It includes the coalitional e↵ects: several agents can work on the same fire, and the more agents work on the same fire the faster the fire can be extinguished. However, if too many units are allocated to the same fire, they might hinder each other or ignore other fires. The optimal mission teams of firemen have to be balanced, i.e., enough agents to fight the fire but not too many to avoid hinder.

An instance of the RMASBench can be modeled as a multiteam formation problem as follows. The set of agents contains only two kinds of agents, namely firemen and policemen. For each fireman agent ai, skill (ai) = { f ire} and for each policeman agent aj, skill (aj) = {blockades}. Each building on fire is represented by a mission mf = { f ire} and each blockade by a mission mb = {blockade}. For each mission, the required k-robustness is the fire intensity. The cost of a team is the sum of the distances that its members need to travel in order to reach the target. Since the number of missions explodes because of fire spread, it appends quickly that there is more missions than agents. In this case, it is not possible to assign a valid mission multi-team to each mission. To tackle this problem, we consider the number of unsatisfied missions during solving. For each turn, our two algorithms compute the mission multi-team so that the travel of team members is minimized and the fire fighting is maximized.

4.2 Experimental results

To evaluates the performances of complete and approximate algorithms, we focused on the benchmark scenario provided by RMASBench. Each experiment has been run on a computer Macbook Pro 13-inch mid 2010 (Intel(R) Core(TM) 2 Duo 2.4 GHz P8600). The scenario takes place on the map of Paris with 5 ignition points at start and 18 fire brigade agents (see Figure 1). The results show the simulation run for 300 turns and fire brigades remain idle for 23 turns before they become aware of all fires.

Figure 2 and 3 show the evolution of run time during the simulation. Solving time of our two algorithms are compared regarding the number of missions, i.e., the number of buildings on fire. We can see that the run time of the complete algorithm increases exponentially when the number of missions increases. This is why the number of solutions (mission multi-teams) increases exponentially. Compared to these results in fig.2, the approximate algorithm is more efficient. In this problem, the approximate algorithm re-uses the previous solution to start solving, and it allows us to generate a good solutions quickly 1 . In the simulation, the number of fire increases quickly, thus the complete algorithm is too slow to solve a new problem for each turn. On the other hand, the approximate algorithm is a more realistic approach when it requires to solve the problem in a small amount of time.

Figure 4 shows the evolution of the number of buildings on fire during the simulation on the Paris scenario of fig.1. In these experiments, two versions of the approximate algorithms (i.e. k-robust MTF and 0-robust MTF) are compared with the five algorithms provided by RMASBench, namely BMS, DSA, Closest, Greedy and Random. The following is the quick explanations of those algorithms:

• The Random algorithm just assigns each agent to a fire location randomly.
• The Closest algorithm assigns each agent to its nearest fire.
• The Greedy algorithm does the same as Closest but considers the intensity of the fire and avoids to put many agents on the same target, i.e., when there is a fire with an intensity k and k agents assigned to it, it will prefer to assign the next agent to another fire location.
• BMS and DSA are the state-of-the-art solvers. These two algorithms optimize both the distance and the expected efficiency of each agent for each fire regarding its intensity. In those approaches, twometrics are combined into one value (scalarization) and they try to maximize this value.

The k-robust MTF approach uses the fire intensity k as the required robustness for each corresponding mission, as explained before, whereas the 0-robust MTF approach only requires one agent per fire. Both algorithms optimize the distance (i.e. the cost) and the robustness of each mission multi-team simultaneously. At each turn, we compute 100 local optimal solutions (i.e. mission multi-teams) and limit the local search by allowing 100 improvement failures (MaxNeighbor = 100 in Algorithm 3). One of the non dominated mission multi-team we found is randomly selected amount those mission multi-teams.

1 The run time depends on the previous solution and the current situation that is given randomly.

In the experiments, the Random approach is the only one that did not succeed to stop the fire spread. The k-robust MTF succeeds to extinguish all fires after 66 turns, while Closest and Greedy need 92 and 108 turns respectively. The performances of 0-robust MTF are similar to those of Closest which finished in 92 turns, where 0-robust MTF finished in 91. BMS and DSA are the fastest to extinguish all fires, i.e., 63 and 64 turns. However, regarding the control of the fire spread, krobust MTF gives better results. Indeed, the number of buildings on fire at the same time is lower for this algorithm: never exceeds 20 buildings where it reached 25 buildings for BMS and 30 buildings for DSA. Also, the k-robust MTF outperforms 0-robust MTF on both time and fire control. In Summary, these experimental results reveal that (i) our algorithm is more realistic for RMASBench compared to the complete algorithm and (ii) we empirically show that our algorithm can compete with the state-of-the-art solvers provided in RMASBench and considering the robust mission multi-teams (i.e. k-robust MTF) have a better control on the fire spread than the state-of-the-art solvers 2 .

5 Conclusions &FutureWorks

In this paper, a novel framework for mission-oriented robust multi-team formation is introduced. The aim of this problem is to form robust teams which can achieve the given missions even if some agents break down, minimize the total cost and maximize the robustness of the teams. Furthermore, two algorithms for solving this problem is provided, namely, complete and approximate algorithms. Also, the complexity of the complete algorithm is discussed. In the experiments, these two algorithms are evaluated in RMASBench which is a testbed for multi-agent coordination algorithms based on the existing RoboCup Rescue simulation platform. Also, the performances of the approximate algorithm is compared with the existing solvers provided in RMASBench algorithms. We empirically showed that (i) the approximate algorithm is more realistic for RMASBench compared to the complete algorithm and (ii) our algorithm can compete with the state-ofthe-art solvers provided in RMASBench and considering the robust mission multi-teams have a better control on the fire spread than the state-of-the-art solvers.

As a perspective for future research, we will develop efficient heuristics and algorithm which is specialized to the application problems. Also, we intend to apply our approach to some real-world problems, e.g., disaster medical assistance team formation and nurse rescheduling problem [Maenhout and Vanhoucke, 2011]. Moreover, we will consider to extend our framework to incorporate the solving of the job shop scheduling problem induced by the tasks of a mission. Given a limited amount of time for each mission, we could form robust mission multi-teams that can schedule their actions in order to accomplish their missions within the corresponding time limitations.

2 We observed that the essential result does not change in Kobe map scenario.