Predictive Receding-Horizon Multi-Robot Task Allocation with Moving Tasks*

This is a repository copy of “Predictive Receding-Horizon Multi-Robot Task Allocation with Moving Tasks” in the Depósito de Investigación de la Universidad de Sevilla. Version: Author Accepted Version Citation: Javier G. Martin, Muhammad Hanif, Takeshi Hatanaka, José M. Maestre & Eduardo F. Camacho. “Predictive Receding-Horizon Multi-Robot Task Allocation with Moving Tasks”. 2022 European Control Conference (ECC), 12-15 Julio 2022 – London (UK). IEEE. ISBN 978-3-9071-4407-7. http://doi.org/10.23919/ECC55457.2022.9838127 To cite this publication, please use the final published version (if applicable). Please check the document version above. Copyright: Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons. Takedown policy: Please contact us ([email protected]) and provide details if you believe this document breaches copyrights. We will remove access to the work immediately and investigate your claim. Predictive Receding-Horizon Multi-Robot Task Allocation with Moving Tasks* Javier G. Martin , Muhammad Hanif, Takeshi Hatanaka , Senior Member, IEEE, Jose M. Maestre , Senior Member, IEEE, and Eduardo F. Camacho , Fellow, IEEE Abstract— This paper addresses a multi-robot task allocation (MRTA) towards moving tasks and presents a novel computationally efficient predictive allocation algorithm that requires solving a linear program (LP) problem. Following the receding horizon control policy, the present algorithm repeats the optimization of future task assignments within an allocation horizon while predicting the evolution of the system. The online optimization is formulated so that the assignment problem is reduced exactly to an LP. The algorithm is also compared with other traditional methods, namely, the greedy approach and a genetic algorithm (GA). Our results show that the algorithm herein proposed outperforms the greedy approach for small prediction horizons and has significantly lower computational load than GA. I. INTRODUCTION Multi-robot systems (MRS) comprise a set of robots that work collaboratively to perform tasks. Among their applications, MRS can be used for mapping [1], [2], surveillance [3]–[5], maintenance [6], and also as robotic sensor networks (RSN), a particular case of wireless sensor networks (WSN) where sensors are mounted on mobile robots [7], [8]. A common challenge in MRS management is the socalled multi-robot task allocation (MRTA) problem [9], [10], where a set of tasks are assigned to the robots in the most efficient way. This problem can be addressed both with decentralized and centralized approaches. While the decentralized approach tends to be more scalable and robust to communication failures, the centralized one benefits from its access to broader information to generate allocations closer to the optimal one. According to the taxonomy proposed in [11], MRTA problems can be classified for the number of simultaneous tasks per robot (single-task robot (ST) vs. multi-task robot (MT)), the number of robots per task (single-robot task (SR) vs. multi-robot task (MR)), and the availability of information to plan future allocations (instantaneous assignment (IA) vs. time-extended assignment (TA)). This taxonomy *This work has been funded by the European Research Council (ERC) under the Advanced Grant OCONTSOLAR (grant agreement number 789051), Grant PID2020-119476RB-I00 funded by MCIN/AEI/ 10.13039/501100011033, and Junta de Andaluc´ ıa (grant P18-HO-4713). Finally, funding from VI PPIT-US is also gratefully acknowledged. J. G. Martin, J. M. Maestre and E. F. Camacho are with the Department of Systems and Automation Engineering, University of Seville, Spain {jgarmar, efcamacho,pepemaestre}@us.es and M. Hanif and T. Hatanaka are with the Dept. of Systems and Control Engineering, Major in Systems and Control Engineering, Tokyo Institute of Technology [email protected], [email protected] has been further developed in [12] by considering the interdependencies between tasks, e.g., for the cases of in-schedule (ID) and cross-schedule (XD) dependencies. TA MRTA problems become more challenging when tasks move as in [13], where an algorithm based on predator dynamics is proposed to deal with this issue, and [14], where manipulators with limited communications must operate over dynamic tasks. In this work, a novel linear approach is presented to address the XD[ST-SR-TA] MRTA problem with moving tasks taking into consideration the order in which robots perform the tasks. To this end, an algorithm that predicts the evolution of the tasks and robots as it is done in the model predictive control (MPC) framework is proposed [15], [16]. MPC is a control technique that uses a model to predict the response of a system and to compute optimal control signals during a certain time horizon. At each time step, the first control action of the sequence of inputs is applied after its corresponding update using the most recent information available. Predictive control methods in the MRS field have been proposed in other works, e.g., [17], where a decentralized model-predictive control strategy is used to address the observation of multiple moving targets; [18], where a non-linear model predictive control strategy is used to dynamically set the formation leader, and [19], where it is used to compute the time to change the assignment of tasks to robots in XD[ST-SR-TA] MRTA problems with static tasks. The rest of this paper is organized as follows. In Section II, the problem formulation is mathematically expressed. In Section III, the proposed algorithm is introduced. Section IV presents the case study where the algorithm is tested and the corresponding results are discussed. Finally, in Section V, the conclusions of this work are detailed and some future research lines are given. Notation: 1a×bdenotes a matrix of ones with arows and bcolumns; 0a×brepresents a matrix of zeros with arows and bcolumns; Iastands for the identity matrix with arows and columns; and diag(x)is employed to denote a diagonal matrix containing vector x as its main diagonal. II. PROBLEM STATEMENT Let us consider a set of Nheterogeneous mobile robots, R={r1, r2, ..., rN}, which must complete a set of M moving tasks, S={s1, s2, ..., sM}, following a given sequence specified by ordinal indixes contained in set K= {1,2, ..., K}. The speed and the position of robot ri∈ R are denoted as vi∈Rand pi∈R2, respectively. On the other hand, the changing location and velocity of each task sj∈ S can be predicted and are denoted by qj∈R2and uj∈R2, respectively. Likewise, task sj∈ S has a relevance quantified by a positive scalar φjand requires an operation time τjto be performed (besides the time employed to reach the task position). For simplicity, τjis considered independent of the robot that performs the task. Likewise, any time spent performing task sjwill be subtracted from τjin further allocations. Finally, we define bi∈[0,100] as the State of Charge (SOC) of robot ri, and wias its discharge rate, which will be used to avoid the assignment of unfeasible tasks from an energetic viewpoint. Moreover, we may want to prioritize some robots over others, e.g., unmanned ground vehicles (UGVs) over unmanned aerial vehicles (UAVs) because UAVs have less autonomy. To this end, we define the penalty λifor the use of robot ri. A. Allocation Variables The allocation, i.e., the assignment of robots to tasks, is described by a set of Boolean variables δijk that are set to 1 when the k−th mission of robot riis to perform task sj(0 otherwise). For convenience, xis defined as the aggregated vector x= [δijk]i∈R,j∈S,k∈K. The following constraints need to be imposed in the optimization N X i=1 K X k=1 δijk = 1 j∈ S,(1) M X j=1 δijk ≤1i∈ R. k ∈ K,(2) to ensure that all tasks are performed (1), and to avoid that robots are simultaneously assigned more than one task per mission slot (2). An example of the described variables can be seen in Fig. 1, where tasks have been considered static. B. Distance and Time Computations The distance between robot riand task sjis defined as dij =||qj−pi||2, and the time for robot rito reach task sj becomes tij =dij vi, as shown in Fig. 2. Fig. 1: r1performs first s1and then s2;r2performs task s3. Let t1,t2and t3be the completion time of s1,s2, and s3 respectively. Then, t1is the time it takes for r1to reach s1 plus τ1;t2is t1plus the time it takes r1to go from s1to s2plus τ2; and t3is the time it takes for r2to reach task s3 plus τ3. Likewise, the distance traveled by r1is the distance from its initial position to s1plus the distance from s1to s2; and the distance traveled by r2is that from its initial position to s3. Let us introduce now the mean time to perform the k−th task as tk=1 M·N· N X i=1 M X j=1 (tijk +τj)k∈ K,(3) where tijk is the time it takes for robot rito perform task sjas its k−th mission. The computation of the time to complete a task sj, say tj, requires to know all the previous tasks carried out by the robot that performs sj. To overcome this issue, we approximate the accumulated time before the beginning of the k−th mission as tk a= k−1 X µ=1 tµk∈ K.(4) Thus, an estimation of tjcan be calculated as tj= N X i=1 K X k=1 δijk ·tE ijk j∈ S, tE ijk =tk a+tijk +τji∈ R, j ∈ S, k ∈ K, (5) with tE ijk as the estimated time if task sjis allocated to robot rias its k−th mission. Finally, we can estimate the distance traveled by the robot rias di= N X i=1 M X j=1 K X k=1 dijk ·δijk i∈ R.(6) where dijk is the estimated distance traveled for robot riif allocated with task sjas its k−th mission. C. Energetic Feasibility Using (5), it is possible to define a family of functions βijk =1if bi−wi·tE ijk ≥0 −1if bi−wi·tE ijk <0(7) Fig. 2: Example with 2robots and 2tasks. Distances from robots to task s1are in red, and to task s2in blue. Task trajectories can be seen in green. to assess whether it will be feasible from an energetic viewpoint for robot rito perform task sjas its k−th mission. This allows us to formulate a new constraint to ensure that tasks will only be assigned to robots with enough SOC: βijk ·δijk ≥0i∈ R j∈ S, k ∈ K,(8) D. Optimization Goals The core of the multi-criteria objective function employed by our algorithm takes into account both the time in which tasks are performed and the distance traveled by the robots and it is defined as Jc= M X j=1 φj·tj(x) + N X i=1 λi·di(x),(9) where λi∈Ris the penalty for the use of robot ri;diis the distance traveled by the robot ri, which can be estimated by means of (6); φj∈Ris the penalty for the time employed to complete task sj; and tjis the completion time in which task sjis finished, which can be estimated by means of (5). Then, the cost function (9) can be transformed into Js= N X i=1 M X j=1 K X k=1 k·δijk ·(λi·dijk +φj·tE ijk),(10) where the multiplication by kenforces that a robot can only be assigned a task as its k−th mission if it already has another task allocated in its (k−1)−th mission slot. Considering the feasibility of the fulfillment of all tasks, we can find two possible cases: 1) All the tasks can be performed. When N·K≥M, there are enough robots to complete the tasks in the allocation horizon and the MRTA problem can be formulated as: min δijk ∈{0,1}Js s.t. (1), (2), (8). (11) Note that if K = M all allocations can be explored (including those using the same robot to perform all the tasks). Thus, if K<Moptimality can be lost, although the computational cost of the problem decreases (the number of decision variables in the problem is N·M·K). 2) Some tasks cannot be completed when N·K<M, the problem must be changed considering the following constraints N X i=1 K X k=1 δijk ≤1j∈ S,(12)            M X j=1 δijk = 1 if maxi,k(βijk)=1 M X j=1 δijk = 0 if maxi,k(βijk) = −1 i∈ R k∈ K ,(13) to ensure that not all tasks need to be fulfilled in the allocation horizon (maintaining that they can be performed only once) and that robots are not idle (unless they do not have enough battery to perform any of the remaining missions). The problem can be then formulated as min δijk ∈{0,1}Js s.t. (12), (13), (8), (14) III. RECEDING HORIZON TASK ALLOCATION ALGORITHM In this section, the LP relaxation of the problem presented in Section II is detailed and the proposed predictive multirobot task allocation algorithm is presented. A. LP relaxation Both (11) and (14) can be transformed into an equivalent LP problem to reduce the computational cost. The equivalent LP problem is as follows: min x≥0c·x s.t. A·x=b(15) where c= [ci]i∈R and xT= [xT i]i∈R, with cT i=                           1·(λi·di11 +φ1·tE i11) 2·(λi·di12 +φ1·tE i12) . . . K·(λi·di1K +φ1·tE i1K) 1·(λi·di21 +φ2·tE i21) 2·(λi·di22 +φ2·tE i22) . . . K·(λi·di2K +φ2·tE i2K) . . . 1·(λi·diM1 +φM·tE iM1) 2·(λi·diM2 +φM·tE iM2) . . . K·(λi·diMK +φM·tE iMK)                           ,xi=                           δi11 δi12 . . . δi1K δi21 δi22 . . . δi2K . . . δiM1 δiM2 . . . δiMK                           . and the matrixes Aand bcontain the corresponding constraints. For simplicity, we consider only the problem expressed in (11) because problem (14) can be relaxed in the same manner. Then, these matrixes Aand bcan be written as A=R0 V I , b =1M+N·K×1 0N·M·K×1,(16) with R=R1R2· · · RN, Ri=     11×K01×K· · · 01×K 01×K11×K· · · 01×K . . .. . ..... . . 01×K01×K· · · 11×K      , V=V1V2· · · VN diag([β111 · · · βNMK]) , Vi=         0K×K0K×K· · · 0K×K . . .. . .. . . IKIK· · · IK . . .. . .. . . 0K×K0K×K· · · 0K×K         . 1 . . . i . . . N Note that the i−th block row in Viis the one containing the IKmatrices. Problem (15) is known to be equivalent to (11) in the sense of having the same optimizer if the matrix Ais totally unimodular and every element of bis an integer [20]. The latter condition is obviously satisfied in the present case. Regarding the former, the following lemma is shown to be true, which is equivalent to total unimodularity of A (Theorem 19.3[20]). Lemma 1 Matrix Asatisfies that ∃ξ∈ {0,±1}s.t. A·ξ∈ {0,±1}. Proof: Let us define ξ=ξ1−ξ2ξ3· · · ±ξN−11×(M+1)·N·K, ξi=11×K−11×K11×K· · · ±11×K,(17) where ξNis positive if Nis odd and negative otherwise. That is, the first Kelements of ξare equal to 1, the following Kones are equal to −1, and this pattern is repeated until the K·M−th element. Note that the last term will be positive if Kis odd and negative otherwise. Then, it is easy to see that R0·ξ∈ {0,1}, and that V I ·ξ∈ {0,±1}. Thus, A·ξ∈ {0,±1}, which completes the proof. Therefore, we can solve the LP (15) rather than the integer program (11). B. Predictive Receding-Horizon Multi-Robot Task Allocation (PMRTA) Algorithm To solve the problem, we need dijk,tijk,tk a, and tE ijk which can be obtained following Algorithm 1. After computing dijk and tijk ∀k, the LP problem expressed in (15) is solved and the assignment corresponding to k= 1 is applied. Once a task is completed, the algorithm is restarted in an event-driven fashion after updating the positions of robots and tasks, and the battery status. In this way, predictions and allocations are constantly updated based on the current information. See Algorithm 2, where the proposed predictive receding-horizon multi-robot task allocation (PMRTA) algorithm is described. IV. RESULTS A case study with 4robots and 16 tasks moving northeast at different speeds is employed using a sample time of 0.1 seconds. The parameters of the robots and the tasks have been generated randomly and can be seen in Table I. An assessment of the effects of the allocation horizon Kin the results and the increase of the computational load with K can be seen in Table II. For comparison purposes, Jhas been computed following (9) for each simulation using the real distance traveled by each robot and the real time in which the tasks were finished. Note that the worst value is obtained with K = 1, which is equivalent to the greedy approach. The best allocation occurs when K=3and stabilizes after K = 4, obtaining the same allocation disregarding the value of Kand the computational burden increases linearly up to 2.02 seconds. We have compared it also with Algorithm 1: dijk,tijk,tk aand tE ijk estimation. Let k= 1; Initialize the estimated position of robots using their current position, p0 ik =pi; Initialize the estimated position of tasks using their current position, q0 jk =qj; while k≤Kdo Compute `ijk using p0 ik,q0 jk,vi, and uj; Compute dijk =||`ijk −p0 ik||2∀i∈ R, j ∈ S; Compute tijk as tijk =dijk vii∈ R, j ∈ R; Use tijk and τjto compute tkusing (3); Compute tkby means of (3); Compute tk+1 aby means of (4); Estimate the position of tasks in k+ 1,q0 jk+1, using q0 jk,ujand the time obtained in tk a; Compute tE ijk ∀i∈ R, j ∈ S by means of (5); Remove from Sthe task with the lowest estimated mean time in k, since we will consider this is the task that has been completed; Compute the position of the robots in k+ 1, p0 ik+1, by means of p0 ik+1 =p0 ik + |S|+1 X j=1 tk a·vi·q0 j−pi ||q0 j−pi||2 ·1 |S| + 1; end Algorithm 2: Predictive Receding-Horizon Multi- Robot Task Allocation (PMRTA) while |S| >0do Update the real position of the robots; Update the real position of the tasks; Update the real state of the batteries; Update the predicted position of the tasks and the robots, dijk,tijk,tk,tk aand tE ijk using Algorithm 1; Solve the allocation using (15); Apply the part of the allocation corresponding to k= 1; Complete the corresponding task and update the number of remaining tasks, |S| =|S| − 1; end the allocation obtained by solving (15) once obtaining that the computational burden is similar to that of K = 1 but the performance decreases significantly, i.e., the periodic recomputing of the allocation is necessary. This phenomenon is to be expected since the predictions employed by the LP are based on several simplifying assumptions. Finally, the allocations obtained using K=3are shown in Fig. 3. There are 16 allocations because there are 16 tasks and a new allocation is computed every time a task is completed. The results are also compared with those achieved by the Genetic Algorithm (GA) method presented in [21], which 0 10 20 0 5 10 15 y coordinate(m) Allocation1 1 2 3 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 10 20 0 5 10 15 Allocation2 1 23 4 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 10 20 0 5 10 15 Allocation3 1 23 4 2 3 5 6 7 8 9 10 11 12 13 14 15 16 0 10 20 0 5 10 15 Allocation4 1 23 4 2 3 6 7 8 9 10 11 12 13 14 15 16 0 10 20 0 5 10 15 Allocation5 1 23 4 2 3 6 7 8 9 10 12 13 14 15 16 0 10 20 0 5 10 15 Allocation6 1 2 3 4 2 6 7 8 9 10 12 13 14 15 16 0 10 20 0 5 10 15 Allocation7 1 2 3 4 2 67 8 9 10 12 14 15 16 0 10 20 0 5 10 15 Allocation8 12 3 4 2 7 8 9 10 12 14 15 16 0 10 20 x coordinate(m) 0 5 10 15 y coordinate(m) Allocation9 1 2 3 4 27 8 910 12 14 16 0 10 20 x coordinate(m) 0 5 10 15 Allocation10 1 2 3 4 27 8 9 12 14 16 0 10 20 x coordinate(m) 0 5 10 15 Allocation11 12 3 4 27 8 91416 0 10 20 x coordinate(m) 0 5 10 15 Allocation12 1 2 3 4 27 8 14 16 0 10 20 x coordinate(m) 0 5 10 15 Allocation13 1 2 3 4 27 816 0 10 20 x coordinate(m) 0 5 10 15 Allocation14 1 2 3 4 7 8 16 0 10 20 x coordinate(m) 0 5 10 15 Allocation15 12 3 48 16 0 10 20 x coordinate(m) 0 5 10 15 Allocation16 12 3 48 Fig. 3: The lines represent the allocation obtained in each iteration. The green line represents the part of the allocation corresponding to k= 1, i.e., the part of the allocation which is applied, while the blue lines represent the part of the allocation for k > 1. In the first allocation, robot 2is sent to task 1, robot 4is sent to task 4, robot 3is sent to task 11, and robot 1is sent to task 5. The second allocation occurs when robot 2completes task 1. In this allocation, robots 1,3, and 4keep on completing the current tasks while robot 2is sent to task 3. Note that in the previous allocation, the second assignment for robot 2was not task 3but task 15. The third allocation is similar to the second one, but robot 4finishes and is sent to a new task (task 13). In the fourth allocation, we can see how task 13 is reallocated to robot 4(since it has not reached the task yet), and, in the fifth allocation, we can see that the proposed algorithm redirects robot 4to task 10 and task 13 is reassigned to robot 3. There are 16 allocations since each time a task is completed a new one is computed. TABLE I: Parameters of the robots in the case study Robots pi(0) ||vi|| λibi(0) wi r1(2,5) 4 1 100 0.2 r2(1,3) 8 2 80 0.5 r3(4,2) 8 1 40 0.4 r4(3,3) 16 2 30 0.1 Tasks qj(0) ˙qjτjφj s1(1,1) (1,1) 1 3 s2(1,6) (3,2) 2 1 s3(2,1) (2,1) 3 5 t4(2,3) (2,2) 2 4 t5(3,5) (2,1) 2 2 t6(3,9) (3,1) 1 3 t7(7,7) (4,2) 4 1 t8(4,5) (2,2) 5 1 t9(5,8) (1,1) 7 6 t10 (6,3) (3,3) 1 1 t11 (7,1) (2,1) 2 4 t12 (7,4) (2,4) 1 3 t13 (8,2) (1,2) 4 5 t14 (8,3) (2,3) 9 6 t15 (9,3) (2,3) 3 2 t16 (9,8) (3,1) 5 1 solves min UJGA = M P j=1 φj·tj(U) + N P i=1 λi·di(U) + γ(U) s.t. ui(n)∈ S ∪ {0} ∀ i, n, (18) where U= [u1(1), u1(2), .., u1(M), u2(1), ..., uN(M)] represents the complete allocation and ui(n)∈ S ∪ {0}, stands for the n−th allocated task of robot ri. Note that ui(n)=0when robot riis idle. Here, φjand λirespectively correspond to the priority given to a certain task sjand the penalty for using robot ri;tj(U)and di(U)correspond to nonlinear functions regarding the time that it takes to complete task sjand the distance traveled by robot riin a given allocation U. Function γ(U)is a soft restriction ensuring the energetic feasibility (no robot has a negative battery level TABLE II: Results of the case-study for different K K 1 2 3 4 ··· 16 16 (no recom.) J609.14 519.38 484.02 504.35 ··· 504.35 945.79 ridi(m) r112.95 26.40 11.20 14.97 ··· 14.97 17.49 r231.27 28.24 26.08 32.72 ··· 32.72 25.32 r322.12 12.65 28.48 22.54 ··· 22.54 24.60 r432.01 28.52 24.74 23.55 ··· 23.55 30.23 sjtj(s) s11.2 1.2 1.2 4.4··· 4.4 15.5 s22.2 2.2 12 13.3··· 13.3 31.5 s312.4 4.3 4.3 3.2··· 3.2 3.6 s44 2 2 2.3··· 2.3 4.3 s52 2.3 2.1 6.4··· 6.4 26.3 s65.4 3.8 8.1 8 ··· 8 33.4 s76.7 16.3 14.1 12.3··· 12.3 38.9 s87.4 7.7 16.7 16.7··· 16.7 45.5 s914.7 10.9 9.9 11 ··· 11 20.4 s10 1.3 10.2 9.4 10.7··· 10.7 39.8 s11 9.1 6.9 2.3 2.4··· 2.4 4.1 s12 2.5 3.4 9.5 9.3··· 9.3 21.2 s13 12.3 8.7 6.4 4.5··· 4.5 5.1 s14 18.1 16.1 11.4 11.4··· 11.4 21.4 s15 9 11.2 8.3 7.8··· 7.8 9.1 s16 7.9 15.6 14.8 16.1··· 16.1 27.9 Computational time (s) 0.74 0.79 0.86 0.93 ··· 2.02 0.76 after the allocation) and that every task is performed once. Finally, GA parameters, which have been tuned by trial and error to achieve a good balance between performance and computational load, can be seen in Table III. Note that given the heuristic nature of GA, the problem has been solved 10 times to average the results. TABLE III: GA tuning parameters Pop. size Max Gen. Max Stall Gen. GCGEGM1 GM2 400 50 10 0.7 0.3 0.5 0.5 The computational load of GA is around 60 seconds and JGA is in the range [600,650], i.e., GA barely reaches the performance achieved by the greedy approach despite its significantly higher computational load. However, it must be taken into account that, unlike the greedy approach and the predictive approach, the implementation of GA here lacks the capability of leaving tasks incomplete. To validate the proposed method, we have generated 1000 random scenarios with N∈[1,10], and M∈[1,20], located in random spots of a 15×15 m square area. These scenarios have been solved using GA and PMRTA ∀K∈[1,M]. The rest of the parameters are contained in the following ranges: vi∈[4,20] m/s; λ∈(0,5);bi∈[0,100];wi∈(0,1); ujconstant with ||uj|| ∈ (0,4] m/s and random direction; τj∈(0,10); and φj∈(0,10) m/s. Our results show that when GA is constrained to achieve an allocation in the same time as the proposed algorithm it achieves a worse allocation in most cases (90.15%). In Fig. 4, it can be seen that PMRTA is superior in almost all cases with small K(K>1), although its performance decreases for larger prediction horizons until it finally becomes worse than the greedy algorithm (K=1). On the other hand, when GA has unlimited time to converge (the stopping criterion was set to 30 generations with no improvement), it outperforms the proposed algorithm in most cases, as expected. However, even in these unfair conditions, the proposed algorithm occasionally beats GA. Also, note that for K = 2 PMRTA outperforms the greedy algorithm and is able to get better results than GA in 18.9% of the cases (the greedy algorithm outperforms the unlimited GA only 7% of the simulations). 1 2 3 4 5 6 7 8 9 1011121314151617181920 K 0 20 40 60 80 100 % of cases won (for the same computation time) PMRTA Time limited GA Fig. 4: Performance comparison between PMRTA and time limited GA. V. CONCLUSIONS A predictive MRTA algorithm that takes advantage of the available information regarding the system evolution has been presented. In particular, the proposed algorithm computes the best allocation based on the predicted system evolution for a given horizon and applies the first element of the calculated sequence in a receding horizon manner. Our results show that the proposed algorithm outperforms well-established heuristical methods such as the greedy algorithm and GA in time-limited optimizations. Also, the proposed algorithm performs remarkably better with small horizons than with larger ones due to the use of a simple internal model for the predictions. To overcome this issue, we plan to iterate the allocation until convergence is obtained and to employ myopic cost functions in future works. Also, in future works, experiments with real robots in more challenging environments will be carried out. REFERENCES [1] F. Nex and F. Remondino, “UAV for 3D Mapping Applications: A Review,” Applied geomatics, vol. 6, no. 1, pp. 1–15, 2014. [2] P. Maini and P. Sujit, “on Cooperation Between a Fuel Constrained UAV and a Refueling UGV for Large Scale Mapping Applications,” in 2015 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 2015, pp. 1370–1377. [3] E. Semsch, M. Jakob, D. Pavlicek, and M. Pechoucek, “Autonomous UAV Surveillance in Complex Urban Environments,” in 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, vol. 2. IEEE, 2009, pp. 82–85. [4] A. Puri, “A Survey of Unmanned Aerial Vehicles (UAV) for Traffic Surveillance,” Department of computer science and engineering, University of South Florida, pp. 1–29, 2005. [5] H. Dan, J. Yamauchi, T. Hatanaka, and M. Fujita, “Control barrier function-based persistent coverage with performance guarantee and application to object search scenario,” in 2020 IEEE Conference on Control Technology and Applications (CCTA). IEEE, 2020, pp. 640– 647. [6] J. Franko, S. Du, S. Kallweit, E. Duelberg, and H. Engemann, “Design of a multi-robot system for wind turbine maintenance,” Energies, vol. 13, no. 10, p. 2552, 2020. [7] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer networks, vol. 38, no. 4, pp. 393–422, 2002. [8] A. Koubˆ aa and A. Khelil, Cooperative Robots and Sensor Networks. Springer, 2014. [9] A. Khamis, A. Hussein, and A. Elmogy, “Multi-robot Task Allocation: A Review of the State-of-the-art,” in Cooperative Robots and Sensor Networks. Springer, 2015, pp. 31–51. [10] W. Dai, H. Lu, J. Xiao, Z. Zeng, and Z. Zheng, “Multi-robot dynamic task allocation for exploration and destruction,” Journal of Intelligent & Robotic Systems, vol. 98, no. 2, pp. 455–479, 2020. [11] B. P. Gerkey and M. J. Matari´ c, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems,” The International journal of robotics research, vol. 23, no. 9, pp. 939–954, 2004. [12] G. A. Korsah, A. Stentz, and M. B. Dias, “A Comprehensive Taxonomy for Multi-Robot Task Allocation,” The International Journal of Robotics Research, vol. 32, no. 12, pp. 1495–1512, 2013. [13] L. Jin, S. Li, H. M. La, X. Zhang, and B. Hu, “Dynamic task allocation in multi-robot coordination for moving target tracking: A distributed approach,” Automatica, vol. 100, pp. 75–81, 2019. [14] L. Jin and S. Li, “Distributed task allocation of multiple robots: A control perspective,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 48, no. 5, pp. 693–701, 2016. [15] C. E. Garcia, D. M. Prett, and M. Morari, “Model predictive control: Theory and practice—a survey,” Automatica, vol. 25, no. 3, pp. 335– 348, 1989. [16] E. F. Camacho and C. B. Alba, Model Predictive Control. Springer science & business media, 2013. [17] J. Kuhn, C. Reinl, and O. Von Stryk, “Predictive control for multi-robot observation of multiple moving targets based on discrete-continuous linear models,” IFAC Proceedings Volumes, vol. 44, no. 1, pp. 257– 262, 2011. [18] B. Augusto de Holanda, S. P. Madruga, A. V. Brito, and T. P. Nascimento, “Dynamic leader allocation in multi-robot systems based on nonlinear model predictive control,” Journal of Intelligent & Robotic Systems, vol. 98, no. 2, pp. 359–376, 2020. [19] M. Gaggero, D. Di Paola, A. Petitti, and L. Caviglione, “When time matters: Predictive mission planning in cyber-physical scenarios,” IEEE Access, vol. 7, pp. 11 246–11 257, 2019. [20] A. Schrijver, Theory of linear and integer programming. John Wiley & Sons, 1998. [21] J. G. Martin, J. R. D. Frejo, R. Garc´ ıa, and E. F. Camacho, “Multi- Robot Task Allocation Problem with Multiple Non-Linear Criteria Using Branch and Bound and Genetic Algorithms,” Intelligent Service Robotics, 2021.