--- title: "Multi-robot Task Allocation in the Environment with Functional Tasks" authors: - "Fuhan Yan" - "Kai Di" doi: "10.24963/ijcai.2022/653" url: "https://ijcai.org/proceedings/2022/653" pdf: "https://ijcai.org/proceedings/2022/0653.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "4710-4716" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Agent-Based Simulation and Emergence" - "Agent-based and Multi-agent Systems: Coordination and Cooperation" - "Robotics: Multi-Robot Systems" --- # Multi-robot Task Allocation in the Environment with Functional Tasks Fuhan Yan, Kai Di *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 4710-4716. DOI: [10.24963/ijcai.2022/653](https://doi.org/10.24963/ijcai.2022/653) ## Abstract Multi-robot task allocation (MRTA) problem has long been a key issue in multi-robot systems. Previous studies usually assumed that the robots must complete all tasks with minimum time cost. However, in many real situations, some tasks can be selectively performed by robots and will not limit the achievement of the goal. Instead, completing these tasks will cause some functional effects, such as decreasing the time cost of completing other tasks. This kind of task can be called “functional task”. This paper studies the multi-robot task allocation in the environment with functional tasks. In the problem, neither allocating all functional tasks nor allocating no functional task is always optimal. Previous algorithms usually allocate all tasks and cannot suitably select the functional tasks. Because of the interaction and sequential influence, the total effects of the functional tasks are too complex to exactly calculate. We fully analyze this problem and then design a heuristic algorithm. The heuristic algorithm scores the functional tasks referring to linear threshold model (used to analyze the sequential influence of a functional task). The simulated experiments demonstrate that the heuristic algorithm can outperform the benchmark algorithms. ## Full text ## 1 Introduction Multi-robot task allocation (MRTA) is one of the most crucial problems in multi-robot systems and is also fundamental for many other robotic problems such as search, rescue, and patrol. Therefore, multi-robot task allocation problems have been widely studied in previous works [Wei et al., 2020; Koenig et al., 2008; Sullivan et al., 2019; Suslova and Fazli, 2020; Yan et al., 2019]. In previous studies of MRTA, it is usually assumed that all the tasks must be completed, and the allocation algorithms allocate all these tasks to robots. However, in many real situations, some tasks can be selectively performed by robots and will not limit the achievement of the goal. In other words, even if the robots perform none of these tasks, the robots can also achieve the goal. Nevertheless, after these tasks are completed, some effects can be generated. This kind of task can be called "functional task". Meanwhile, the tasks that must be completed by robots can be called "compulsory task". The motivation is described as the following example. ∗Co-corresponding Authors - Multi-robot real-time information collection: Some robots need to collect the real-time information of some locations. A robot needs to visit a target location and then upload the real-time information (obtained by camera or other sensors) to the base by wireless communication. Uploading the real-time information of the target locations are the "compulsory tasks", and the optimization objective is to minimize the time cost. In this case, the robots can selectively set up the simple communication enhancement facilities (such as deployable antenna). Then, the robots can upload the data faster. These are the "functional tasks". If the data size of a target location is quite small, the robot needs not to perform functional task. If the data size is quite large, the robot can save more time than the time cost of setting up a simple communication enhancement facility. This paper studies the multi-robot task allocation with functional tasks. In most cases, neither allocating all functional tasks nor allocating no functional task is always optimal. Previous algorithms cannot suitably allocate the functional tasks and may lead to large time costs. We fully analyze this problem and design a heuristic algorithm. The functional tasks are firstly scored respectively based on linear threshold model. According to the individual scores, the combination of functional tasks is selected. The robots allocate the selected functional tasks, and then allocate the compulsory tasks assuming the selected functional tasks have been completed. The simulated experiments are presented to test the performance of the proposed algorithm. The experimental data demonstrate that the proposed heuristic algorithm can outperform the benchmark algorithms when functional tasks exist in the environment. The rest of this paper is organized as follows. In Section 2, we briefly introduce the related works. Section 3 presents the problem formulation. Section 4 shows the problem analyses and benchmark algorithms. The heuristic algorithm is shown in Section 5. The experiments are provided in Section 6. Finally, we conclude this paper in Section 7. ## 2 RelatedWorks ## 2.1 Multi-robot Task Allocation Problems The multi-robot task allocation (MRTA) problem is one of the core issues in multi-robot systems. In some studies, the robots just need to visit various locations that represent tasks, and a task is completed after being visited [Wei et al., 2020; Koenig et al., 2008; Sullivan et al., 2019]. Besides, some studies analyze this kind of model with some extra complex restrictions, such as time windows [Suslova and Fazli, 2020], heterogeneous skill requirements [Emam et al., 2020], etc. Some studies analyze the factors related to the performing processes (completing task is not just visiting). For instance, a single robot is not able to complete a task because the skill requirement set of this task is a superset of the skill set of the robot [Lee, 2018]. In this case, several robots need to perform a task simultaneously. Besides, some studies analyze the multi-robot task allocation with precedence constrained (PC-MRTA) [McIntire et al., 2016; Bischoff et al., 2020]. Some tasks cannot be performed until certain tasks are completed. ## 2.2 The Classical Algorithms Used inMRTA The time complexity of the algorithm exactly solving MRTA is not acceptable. Even if the tasks are completed after being visited, MRTA is still np-hard [McIntire et al., 2016]. Therefore, most allocation algorithms are approximate or heuristic. Many metaheuristics can be used in MRTA, and they are problem independent frameworks that can also be used in other optimization problems. The metaheuristics that have been used for task allocation include Genetic Algorithms [Yuan et al., 2013], Simulated Annealing [Behnck et al., 2015], and Ant Colony Optimisation [Chen et al., 2018]. They can be tuned to converge within certain time limits. However, when the solution space is quite large or there are some complex restrictions, they may converge slowly. The auction-based algorithms are usually faster and widely used to allocate tasks. Among these, the most popular frame is the sequential single-item (SSI) auction [Koenig et al., 2008; Sullivan et al., 2019; McIntire et al., 2016]. Although there are many auction-based algorithms, they cannot effectively solve the proposed problem. The reason is that functional tasks are optional, and which functional tasks should be allocated has not been analyzed. Nevertheless, SSI can still be selected as an important basic technology in this paper. Then, we concretely introduce the version of SSI auction [Koenig et al., 2008; Sullivan et al., 2019] that will be used in this paper: - Sequential Single-Item (SSI) Auction. During each round of SSI, all robots bid on all unassigned tasks and the auctioneer then assigns one additional (previously unassigned) task to robots. The bidding rule is: each robot tries to insert the task being bid on into the task sequence consisting of the currently allocated tasks to it, and the bid is the minimum time cost of the new sequence. The winner determination rule is: allocates the task which has the largest difference between the lowest bid and second lowest bid (in the event of a tie, the task with the lowest bid is assigned). ## 3 ProblemFormalization This paper studies the multi-robot task allocation with functional tasks (FT-MRTA). In this section, we first introduce the basic settings of MRTA. Then, the functional tasks and optimization objective are introduced. ## 3.1 Basic Settings - Environment: the environment is modeled as a twodimensional grid world, and the size is X × Y . Some robots are initially located at a waiting area that is at the center of the world. Let R = {r1, r2, ...} denote the set of robots. There can be more than one robot in a same cell of the grid world. Some tasks are distributed in the world, and let T = {t1, t2, ...} denote the set of tasks. There can be at most one task in a cell of the grid world. Let d(ti, tj ) denote the Manhattan distance between task ti and task tj , and let d(ri, tj) denote the Manhattan distance between robot ri and task tj. - Robots: all the robots are initially at the center of the world, i.e., ( X2 , Y2 ). Let d(O, tj) denote the Manhattan distance between ( X2 , Y2 ) and task tj. In each time step, each robot can move up, down, left or right to the adjacent cell. Certainly, the robot can also stay in a cell. - Tasks: each task ti ∈ T is associated with a requirement parameter νi ∈ (0,+∞) that determines how hard to complete ti. A task can be performed only by one robot. When a robot and a task are in the same cell, the robot can begin to perform the task. If the robot begins to perform, it cannot stop until completing this task. When performing task ti, the robot can make νi ←max(0, νi - 1) in each time step. When νi = 0, task ti is completed. Therefore, the time cost of completing ti is ⌈νi⌉. ## 3.2 Compulsory Tasks and Functional Tasks The tasks can be divided into two sub-sets. Let Tc denote the set of compulsory tasks and Tf denote the set of functional tasks. |T| = |Tc| + |Tf |. For the sake of simplification, it is assumed that Tc = {t1, t2, ..., t|Tc|} and Tf = {t1+|Tc|, t2+|Tc|, ..., t|T |}. - Compulsory tasks: task ti(1 ≤ i ≤ |Tc|) must be completed and can directly limit the achievement of the goal. - Functional Tasks: if a functional task is completed, the time cost of completing other tasks will be decreased. Besides, each functional task ti is associated with an influence parameter fi ∈ (1,+∞) and can only influence the tasks in a limited range. Only the functional tasks that are completed before tj begins to be performed can influence tj. Therefore, let ti << tj denote that ti can be completed before tj begins to be performed. Overall, after some functional tasks are completed, the time cost of completing task tj is ⌈g(T j f )νj⌉. Here, T j f = {tk|tk ∈ Tf , d(tk, tj) ≤ ε, tk << tj}. The parameter ε denotes the influence range. Without loss of generality, g(x) can be set as different functions while g(x) ∈ (0, 1] and g(∅) = 1 should be satisfied. For instance, g(T j f ) = 1 1+ln ∏tk∈T j f fk . ## 3.3 Optimization Objective The robots must complete all the tasks in set Tc. The optimization objective is the time cost of completing all the tasks in set Tc. Let Si = {ti1 , ti2 , ..., tiw } denote the task sequence allocated to robot ri. Si ∩ Sj = ∅ for any ri, rj ∈ R. If ∪ri∈RSi = Tc, the time cost for robot ri to complete the tasks in Si is As the robots take one time step to move to the neighbouring cell, d(..., ...) can also denote the moving time. If the robots select to perform some tasks in Tf , the sequence Si needs to satisfy Tc ⊆ ∪ri∈RSi. As the functional tasks can influence the time cost of completing other tasks, the time cost for robot ri to complete the tasks in Si becomes: Thus, the final objective of FT-MRTA is defined as: minimize maxri∈RC ′ (Si, ∪rj ∈RSj ), subject to: ## 4 ProblemAnalyses and Benchmark Algorithms The essential objective of the robots is to complete all compulsory tasks. All the compulsory tasks can be allocated based on the SSI algorithm (See also section 2.2). The first baseline can be set as allocating all compulsory tasks without any functional task based on the SSI algorithm. Nevertheless, if the effect of functional tasks is large enough, this baseline is easy to outperform. We present a simple case in figure 1. In figure 1, |R| = 1, |Tc| = 1, |Tf | = 1 and ε = 10. The difference between figure 1 (a) and (b) is ν2. In this simple case, the effect of functional task t2 is easy to analyze: - In (a), if robot r1 only performs the compulsory task t1, the time cost is d(r1, t1) + ν1 = 10 + 50 = 60. This is the baseline. If robot r1 first performs t2 and then performs t1, the time cost is d(r1, t1)+ν2 +d(t1, t2)+ ν1g({t2}) = 5+5+5+25 = 40. Therefore, allocating functional task t2 is better. - In (b), if allocating t2, the time cost is 5+40+5+25 = 75. Ignoring functional task t2 becomes better. In the above case, it is easy to know whether the robot should allocate the functional task. However, if |R|, |Tc| and Figure 1: Case study one. ![Image](https://ijcai.org/proceedings/2022/fulltext/653/image_000000_fc0c547f13621a59754e7660463c6bfc087ec445615987bec770b8901565a651.png) ![Image](https://ijcai.org/proceedings/2022/fulltext/653/image_000001_3908c7d975a6419da20eb0210e1f6e0f8ee92b55e94d9b4713d223e7ef97d15b.png) Figure 2: Case study two. ![Image](https://ijcai.org/proceedings/2022/fulltext/653/image_000002_c6da39cf7de46d3cb619ba8d02aff448d0daca4bd2a61cd59078de6329d1003c.png) |Tf | become quite large, exactly analyze each functional task is infeasible. In this case, the greedy algorithm frame can be used. The robots firstly allocate all compulsory tasks based on the SSI algorithm and obtain the task sequences. Then, the robots try to insert the functional tasks into the sequences and select the best location greedily. This method is inspired by [McIntire et al., 2016]. Figure 2 shows this process: - |R| = 1, |Tc| = 5 and |Tf | = 1. Robot r1 obtains sequence S1 based on SSI algorithm. Then, r1 tries to insert t6 into S1 at different locations. For instance, r1 inserts t6 after t1 to get S′1 . If C ′ (S′1 , (∪rj∈R\r1 Sj) ∪ {S′1 }) < C ′ (S1, ∪rj∈RSj), r1 updates the task sequence (S1 is replaced by S′1 ). Finally, t6 will be inserted at the best location or not be inserted. When |R| > 1 and |Tf | > 1, two greedy allocation algorithms can be presented. One is a fast version while the other is a slow version. In the fast version, C ′ (Si, ∪rj∈RSj) is replaced by a easily estimated value because calculating C ′ (Si, ∪rj∈RSj) is time-consuming. In detail, EC(Si) is the estimated time cost that can be calculated easily: Here, EC(Si) is calculated only based on Si without considering other sequences. Then, if rj =argmaxri∈REC(Si), the functional tasks will be inserted in Sj . The fast greedy allocation algorithm is shown in Algorithm 1. In Algorithm 1, line 2 selects Su that is associated with largest EC(Si). Line 4-8 select the functional tasks that may influence Su. Line 9-16 try to insert the functional tasks into Su. The time complexity of calculating EC(Si) is about O( |Tc| |R| ). The time complexity of analyzing all positions is about O( |Tc| |R| × |Tc| |R| ). Then, the worst time complexity of ## Algorithm 1 Greedy task allocation (fast) ``` Input: Task sequences S1, S2. . . S|R| based on SSI Output: S1, S2. . . S|R| 1: while True do 2: ru ←argmaxri∈REC(Si) (See also equation 3) 3: Tr ← ∅, b ←EC(Su), pbest ← ∅, tbest ← ∅ 4: for all ti ∈ Tf do 5: if ∃tj ∈ Su satisfies d(ti, tj) ≤ ε and i ̸= j then 6: Tr ← Tr ∩ {ti}. 7: end if 8: end for 9: for all ti ∈ Tr do 10: for all positions p in current schedule Su do 11: Insert ti in Su at p to get S′u 12: if EC(S′u ) < b then 13: b ← EC(S′u ), pbest ← p, tbest ← ti 14: end if 15: end for 16: end for 17: if pbest ̸= ∅ then 18: Insert tbest in Su at best position pbest 19: Tf ← Tf \tbest 20: else 21: return S1, S2. . . S|R| 22: end if 23: end while ``` In the slow version, all the sequences and functional tasks are analyzed iteratively. The slow greedy allocation algorithm is shown in Algorithm 2. In line 7 of Algorithm 2, ti is inserted in Sj at p to get S′j . Then, in line 8, When a functional task is inserted into any sequence, ck of all robots will be updated. Then, if the expected maximum time cost decreases, the corresponding parameters are recorded. In line 17, the recorded functional task is truly inserted into the recorded task sequence. The time complexity of calculating ck for all sequences is O(|R|×|Tc|). Then, the worst time complexity of Algorithm 2 is O(|Tf |×|Tf |×|R|× |Tc| |R| × |R| × |Tc|) = O(|Tf |2 |Tc|2 |R|). It means that Algorithm 2 runs much more slowly than Algorithm 1. Therefore, Algorithm 2 runs too slowly to be practical, but can be used as a benchmark algorithm to measure other algorithms. ## 5 The Heuristic Algorithm based on Scoring the Functional Tasks In Algorithm 2, each functional task tries to be inserted in each task sequence. The robot causing maximum time cost can be influenced by the functional task completed by another robot. Thus, Algorithm 2 can make the maximum time cost decrease more than Algorithm 1. Nevertheless, the time complexity of Algorithm 2 is unacceptable. In this case, we try to ## Algorithm 2 Greedy task allocation (slow) ``` Input: Task sequences S1, S2. . . S|R| based on SSI Output: S1, S2. . . S|R| 1: while True do 2: b ←maxri∈RC ′ (Si, ∪rj∈RSj) (See also equation 2) 3: pbest ← ∅, tbest ← ∅, u ← ∅ 4: for all ti ∈ Tf do 5: for all Sj ∈ {S1, S2...S|R|} do 6: for all positions p in current schedule Sj do 7: Insert ti in Sj at p to get S′j 8: Estimate time cost of each sequence as ck for all rk ∈ R (See also equation 4) 9: b′ ← maxrk∈Rck 10: if b′ < b then 11: b ← b′ , pbest ← p, u ← j, tbest ← ti 12: end if 13: end for 14: end for 15: end for 16: if pbest ̸= ∅ then 17: Insert tbest in Su at best position pbest 18: Tf ← Tf \tbest 19: else 20: return S1, S2. . . S|R| 21: end if 22: end while ``` design a heuristic algorithm, which simultaneously satisfies: 1) runs fast; 2) the functional task can also be inserted into any other task sequence while influencing the task sequence associated with the maximum time cost. ## 5.1 Scoring the Functional Tasks In the heuristic algorithm, the first step is scoring all functional tasks. The direct effect of a functional task on compulsory tasks can be easily calculated. However, there may be an indirect effect of a functional task. Figure 3 shows an instance: - In figure 3, |R| = 1, |Tc| = 1, |Tf | = 2 and ε = 10. It is assumed that robot r1 is initially at the position of task t2 but has not yet perform t2. If r1 only performs t1, the time cost is 8+8+50 = 66. This is the baseline. If r1 selects task sequence {t3, t1}, the time cost is 8 + 50 + 8 + 0.5 × 50 = 91. If r1 selects task sequence {t2, t1}, the time cost is 5 + 8 + 8 + 50 = 71. Here, t2 cannot directly influence t1 because d(t2, t1) > ε. Neither {t3, t1} nor {t2, t1} is suitable. However, if r1 selects task sequence {t2, t3, t1}, the time cost is 5+8+ 0.2 × 50 + 8 + 0.5 × 50 = 56. In this case, t2 directly influences t3 and then t3 influences t1. Based on the above instance, it can be known: 1) the indirect effect of each functional task should not be ignored; 2) only if the subsequent functional task is completed, the preceding functional task can indirectly influence the compulsory tasks out of range. This sequential influence process is quite similar to the influence diffusion models in social networks. Therefore, when |R|, |Tc| and |Tf | become large, the functional tasks can be scored referring to the influence dif- Figure 3: Case study three. ![Image](https://ijcai.org/proceedings/2022/fulltext/653/image_000003_7265b7957b63a8cae76abe49a34f8d7200b97bc898415c83a012f6d2d6da05ab.png) ## Algorithm 3 Scoring algorithm ``` Input: Active task set Ta Output: Score 1: Score ← 0, n← 0 2: Inactive task set Tina = T\Ta 3: while True do 4: for all ti ∈ Tina do 5: EGi = g({tk|tk ∈ Ta, tk ∈ Tf , d(tk, ti) ≤ ε}) 6: end for 7: for all ti ∈ Tina do 8: if EGi < TS then 9: Move ti : Tina → Ta 10: if ti ∈ Tc then 11: Score ← Score + γ n νi(1 - EGi) 12: end if 13: end if 14: end for 15: n←n+1 16: if Tina and Ta do not change in this loop then 17: return Score 18: end if 19: end while ``` fusion models. Influence diffusion models in social networks have been widely studied and are usually used to model the diffusion of virus, information, opinion, etc [Yan et al., 2014; Yan et al., 2016; Yang et al., 2019]. In these models, some nodes in the network are initially active while others are inactive. Then, the inactive nodes may be activated according to some rules. The two most classical models are the independent cascade model [Yan et al., 2014; Yan et al., 2016] and linear threshold model [Yang et al., 2019]. Most influence diffusion models are variants of the two classical models. In the independent cascade model, active nodes try to independently activate other nodes with some probabilities. In the linear threshold model, a node is activated if the (weighted) number of active neighbors exceeds a threshold. If the thresholds are deterministic, the linear threshold model is deterministic. Therefore, we select the linear threshold model to score the functional tasks. Algorithm 3 shows this process. In line 5, EGi is used to quantize the influence of the active functional tasks. Smaller EGi means larger influence. In line 8, TS is the threshold of the linear threshold model. In line 11, γ is a discount parameter and is used to decrease the score of indirect influence. The score is the decrement of the time cost of completing compulsory tasks. In line 16-17, if there is no new activated node, the ## Algorithm 4 Task set selecting algorithm ``` Input: Task set Tc and Tf Output: Task set Ts 1: for all ti ∈ Tf do 2: Scorei = Scoring(ti) vi+d(O,ti) (See also Algorithm 3) 3: end for 4: Sorting the scores of each functional task from largest to smallest to get Scoreo1 , Scoreo2 ...Scoreo|Tf | 5: Ts = {to1 },Cost ← νo1 +d(O, to1 ) 6: if Scoreo1 > 1 then 7: for k ← o2 to o|Tf | do 8: Scorebest ←Scoring(Ts) 9: if Scoring(Ts ∪ {tk}) - Scorebest >max(0, νk + d(O, tk) - Cost) then 10: Ts ← Ts ∪ {tk}, Cost ← Cost+vk+d(O,tk) 2 11: end if 12: end for 13: if |Ts| < |R| then 14: for k ← o2 to o|Tf | & |Ts| < |R| do 15: if Scorek > 1 then 16: Ts ← Ts ∪ {tk} 17: end if 18: end for 19: end if 20: end if 21: return Ts ``` diffusion process ends. All the tasks have the same threshold and discount. In the experiments, the two parameters are set heuristically: TS = 0.5, γ = 0.5. The time complexity of calculating EGi is at most O(|Tf |). Then, the worst time complexity of Algorithm 3 is O(|Tf ||T |). ## 5.2 Selecting the Combination of Functional Tasks The input of Algorithm 3 is a task set. It means Algorithm 3 can score the combination of tasks instead of only scoring a single functional task. However, analyzing all combinations of functional tasks is not feasible. Therefore, we firstly score each functional task singly. The effects of different functional tasks may overlap. Directly selecting several functional tasks associated with high scores is not necessarily suitable. In this case, we can gradually add the functional tasks to a set according to the score ranking and use Algorithm 3 to analyze whether the score of the set increases. This process is shown in Algorithm 4. In Algorithm 4, if the score of a single functional task is larger than the time cost of completing this task, the task is considered "useful". Line 1-4 sort the functional tasks according to the scores and time costs. In line 6, if the best functional task is still not "useful", none of the functional tasks will be selected. Otherwise, in line 7-12, the functional tasks are gradually added to a set according to the score ranking. In line 13-19, if the number of selected functional tasks is smaller than |R|, some "useful" tasks can be extra selected to seek the load balance. This is a heuristic setting. The time complexity of line 1-3 is O(|Tf | × |Tf | × |T |). The time complexity of line 4 is at most O(|Tf | × |Tf |). The time complexity of line 5-16 is at most O(|Tf | × |Tf | × |T | + |Tf |) = O(|Tf |2 |T|). Therefore, the worst time complexity of Algorithm 4 is O(|Tf |2 |T|). If |Tf | = 40, |Tc| = 40, |R| = 10, it is known that O(|Tf |2 |T|) = 128000, O( |Tf |2 |Tc|2 |R|2 ) = 25600, O(|Tf |2 |Tc|2 |R|) = 25600000. Algorithm 4 runs slowly than Algorithm 1 but much faster than Algorithm 2. Finally, the heuristic algorithm can be summarized as: 1) select a set of functional tasks based on Algorithm 4; 2) Allocate the selected functional tasks based on the SSI algorithm and obtain the task sequences; 3) assuming the selected functional tasks have been completed (the time costs of completing other tasks have decreased), insert all compulsory tasks into the sequences based on the SSI algorithm. In the full algorithm, Algorithm 4 is performed once, and SSI is performed twice. The worse complexity of SSI is about O(|R||T|). O(|R||T|) is much smaller than the complexity O(|Tf |2 |T|) of Algorithm 4. In addition, O(|Tf |2 |T|) has already included the complexity of Algorithm 3. Therefore, the complexity of the full algorithm can also be represented by O(|Tf |2 |T|). In the two greedy algorithms, O(|R||T|) is also relatively small. ## 6 Simulated Experiments Our experiments were conducted via simulation. Some parameters are fixed: XY = 100 × 100; |Tc| = 40; fi is randomly set in [1,5]; νi is randomly set in [1, νmax]; g(T j f ) = 1 1+ln ∏tk ∈T j f fk . All tasks are randomly uniformly distributed in the grid world. Each experiment is performed with 1000 replications, and the average data are shown in the experimental figures. In each replication, the random values are reset. As shown in figure 4, compared with basic SSI, all other algorithms can greatly decrease the time costs. In figure 4 (a), (b) and (c), when the abscissa value is small but not the smallest 1 , SSI+Greedy (slow) outperforms all other algorithms. Along with the increase of the abscissa value, the heuristic algorithm becomes the best. It means that the advantage of the heuristic algorithm is more obvious when the influence of the functional tasks is greater (i.e. when the parameters ε, νmax, |Tf | are larger). In figure 4 (d), larger |R| is slightly equivalent to smaller |Tf |. When |R| increases, the advantage of the heuristic algorithm becomes less obvious. As the greedy algorithms can only be used after the sequences of the compulsory tasks are fixed, it may lead to the locally optimal solution. When ε, νmax and |Tf | are small, the functional task may just be able to influence very few task sequences. In this case, local optimal solution is very close to global optimal solution. The heuristic algorithm allocates compulsory tasks after functional tasks; thus, the sequences of the compulsory tasks may be different from those obtained by directly allocating compulsory tasks. Therefore, if ε, νmax and |Tf | are large, the heuristic algorithm further decreases the maximum time cost than SSI+Greedy (slow). 1 It must be explained that the leftmost data points in figure 4 (b) are obtained with νmax = 1 instead of νmax = 0. Figure 4: The experimental data. Except the variable parameter (abscissa axis), the other parameters are set as: ε = 50, νmax = 50, |Tf | = 40, |R| = 10. ![Image](https://ijcai.org/proceedings/2022/fulltext/653/image_000004_02b9ca5dbe8e7db2b7d7ff45677f86b5c86a72ce3c3b25d15c2c469cf35a5055.png) Note that the time complexity of SSI+Greedy (slow) is too large to make this algorithm practical. Although SSI+Greedy (slow) outperforms the heuristic algorithm in a few cases, it can also be concluded that the heuristic algorithm is the best of the tested algorithms. ## 7 Conclusion and FutureWorks This paper studies the multi-robot task allocation with functional tasks. Previous algorithms cannot suitably allocate the functional tasks. In most cases, neither allocating all functional tasks nor allocating no functional task is always optimal. We fully analyze this problem and modify the previous classical algorithm based on the greedy algorithm frame. The modified algorithms are used as the benchmark algorithms. Considering the shortages of the greedy algorithms, we design a heuristic algorithm mainly based on scoring the functional tasks. The simulated experiments are presented to test the proposed algorithms. It can be concluded that the heuristic algorithm outperforms all benchmark algorithms. In the future work, we will study this problem in a communication-constrained and distributed environment. If the robots are initially distributed in different areas and are under communication-constrained, suitably allocating the compulsory tasks and functional tasks will be more difficult. ## Acknowledgments This work was supported by the National Natural Science Foundation of China (61936001, 61932007 and 62076060), the Natural Science Foundation of Chongqing (cstc2019jcyjcxttX0002), the Key Cooperation Project of Chongqing Municipal Education Commission (HZ2021008). ## References 1. [Behnck et al., 2015] Lucas P Behnck, Dionisio Doering, Carlos Eduardo Pereira, and Achim Rettberg. A mod- ified simulated annealing algorithm for suavs path plan- ning. Ifac-Papersonline, 48(10):63-68, 2015. 2. [Bischoff et al., 2020] Esther Bischoff, Fabian Meyer, Jairo Inga, and Sören Hohmann. Multi-robot task allocation and scheduling considering cooperative tasks and precedence constraints. In 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 3949-3956. IEEE, 2020. 3. [Chen et al., 2018] Xinye Chen, Ping Zhang, Guanglong Du, and Fang Li. Ant colony optimization based memetic al- gorithm to solve bi-objective multiple traveling salesmen problem for multi-robot systems. IEEE Access, 6:21745- 21757, 2018. 4. [Emam et al., 2020] Yousef Emam, Siddharth Mayya, Gen- naro Notomista, Addison Bohannon, and Magnus Egerst- edt. Adaptive task allocation for heterogeneous multi- robot teams with evolving and unknown robot capabilities. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 7719-7725. IEEE, 2020. 5. [Koenig et al., 2008] Sven Koenig, Xiaoming Zheng, Craig Tovey, Richard Borie, Philip Kilby, Vangelis Markakis, and Pinar Keskinocak. Agent coordination with regret clearing. In Proceedings of the AAAI Conference on Ar- tificial Intelligence, AAAI Press, page 101, 2008. 6. [Lee, 2018] Dong-Hyun Lee. Resource-based task alloca- tion for multi-robot systems. Robotics and Autonomous Systems, 103:151-161, 2018. 7. [McIntire et al., 2016] Mitchell McIntire, Ernesto Nunes, and Maria Gini. Iterated multi-robot auctions for precedence-constrained task scheduling. In Proceedings of the 2016 International Conference on Autonomous A- gents & Multiagent Systems, pages 1078-1086, 2016. 8. [Sullivan et al., 2019] Nick Sullivan, Steven Grainger, and Ben Cazzolato. Sequential single-item auction improve- ments for heterogeneous multi-robot routing. Robotics and Autonomous Systems, 115:130-142, 2019. 9. [Suslova and Fazli, 2020] Elina Suslova and Pooyan Fazli. Multi-robot task allocation with time window and ordering constraints. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 6909- 6916. IEEE, 2020. 10. [Wei et al., 2020] Changyun Wei, Ze Ji, and Boliang Cai. Particle swarm optimization for cooperative multi-robot task allocation: a multi-objective approach. IEEE Robotics and Automation Letters, 5(2):2530-2537, 2020. 11. [Yan et al., 2014] Fuhan Yan, Zhaofeng Li, and Yichuan Jiang. Noised diffusion dynamics with individual biased opinion. In Proceedings of the Twenty-first European Con- ference on Artificial Intelligence, pages 1129-1130, 2014. 12. [Yan et al., 2016] Fuhan Yan, Zhaofeng Li, and Yichuan Jiang. Controllable uncertain opinion diffusion under con- fidence bound and unpredicted diffusion probability. Phys- ica A: Statistical Mechanics and its Applications, 449:85- 100, 2016. 13. [Yan et al., 2019] Fuhan Yan, Kai Di, Jiuchuan Jiang, Yichuan Jiang, and Hui Fan. Efficient decision-making for multiagent target searching and occupancy in an un- known environment. Robotics and Autonomous Systems, 114:41-56, 2019. 14. [Yang et al., 2019] Lan Yang, Zhiwu Li, and Alessandro Giua. Influence minimization in linear threshold networks. Automatica, 100:10-16, 2019. 15. [Yuan et al., 2013] Shuai Yuan, Bradley Skinner, Shoudong Huang, and Dikai Liu. A new crossover approach for solv- ing the multiple travelling salesmen problem using genet- ic algorithms. European journal of operational research, 228(1):72-82, 2013.