caa a22 4500 605469431 CHVBK 20210128100322.0 cr unu---uuuuu 210128e20150301xx s 000 0 eng 10.1007/s00500-014-1274-0 doi (NATIONALLICENCE)springer-10.1007/s00500-014-1274-0 Memetic algorithms for optimal task allocation in multi-robot systems for inspection problems with cooperative tasks [Elektronische Daten] [Chun Liu, Andreas Kroll] Multi-robot task allocation means to distribute and schedule a set of tasks to be accomplished by a group of robots to minimize cost while satisfying operational constraints. It can be challenging to solve a large number of tasks and becomes even more challenging when tightly coupled multi-robot tasks are also taken into account. For example, it is more complex to solve problems that include tasks that have to be carried out jointly by two robots due to the resulting temporal and spatial constraints. Additionally, the complexity of task allocation increases exponentially with rising task variety. This paper focuses on multi-robot task allocation in inspection problems with both single- and two-robot tasks. A novel memetic algorithm is proposed combining a genetic algorithm with two local search schemes. Using permutation representation, eight approaches based on four basic coding strategies are designed for multi-robot task allocation of inspection problems with two-robot tasks. The performance of the memetic algorithm is evaluated in case studies on inspecting a large storage tank area of a petroleum refinery. Springer-Verlag Berlin Heidelberg, 2014 Constrained combinatorial optimization nationallicence Multi-robot task allocation nationallicence Cooperation nationallicence Memetic algorithm nationallicence Genetic algorithm nationallicence Inspection nationallicence $$A$$ A : MRTA solution candidate by permutation coding nationallicence $$A_k$$ A k : Task assignment and task schedule of robot $$R_k$$ R k nationallicence $$a_i^k$$ a i k : $$i$$ i -th subtask of $$A_k$$ A k nationallicence $$B$$ B : Set of individuals nationallicence $$B_j$$ B j : Set of best individuals in $$j$$ j -th generation nationallicence $$C$$ C : Set of time costs nationallicence $$C_k (A_k )$$ C k ( A k ) : Time for robot $$R_k $$ R k to complete its tasks $$A_k$$ A k nationallicence $$c_{ijk}^t$$ c i j k t : Traveling time of robot $$R_k $$ R k from inspection position of $$P_i $$ P i to that of $$P_j$$ P j nationallicence $$c_{jk}^s$$ c j k s : Time robot $$R_k $$ R k needs to carry out inspection task of $$P_j $$ P j nationallicence $$c_{jk}^w$$ c j k w : Waiting time of robot $$R_k$$ R k to execute $$P_j$$ P j after arriving at the inspection position of $$P_j$$ P j nationallicence $$E$$ E : Grid map nationallicence $$e_{xy}$$ e x y : Cell of grid map nationallicence $$f^T$$ f T : Function maps the set $$T$$ T to the set $$P$$ P nationallicence $$G_{\mathrm{crt}}$$ G crt : Current generation number nationallicence $$G_{\mathrm{max}}$$ G max : Fixed number of generations nationallicence $$G^{a}$$ G a : Gene-apportion nationallicence $$g_j^{\mathrm{opt}}(i)$$ g j opt ( i ) : $$i$$ i -th element of gene-apportion of temporary optimal individual obtained in $$j$$ j -th generation nationallicence $$H$$ H : Threshold value for grouping subtasks using combination-based coding nationallicence $$J$$ J : Cost function (completion time) nationallicence $$K$$ K : Number of subpopulations nationallicence $$l_k$$ l k : Number of subtasks of $$A_k$$ A k nationallicence $$l_k^z$$ l k z : Number of genes of $$Z_k$$ Z k nationallicence $$M$$ M : Submatrices of $$E$$ E nationallicence $$N^G$$ N G : Number of genes of a chromosome nationallicence $$N^P$$ N P : Number of subtasks nationallicence $$N^Q$$ N Q : Number of subtask groups nationallicence $$N^R$$ N R : Number of robots nationallicence $$N^T$$ N T : Number of tasks nationallicence $$N^b$$ N b : Number of elements in $$B_j$$ B j for all $$j$$ j nationallicence $$N^{s}$$ N s : Maximal size of a subtask group nationallicence $$N^x$$ N x : Size of grid map in $$x$$ x direction nationallicence $$N^y$$ N y : Size of grid map in $$y$$ y direction nationallicence $$N_{\mathrm{pop}}$$ N pop : Population size nationallicence $$N_{\mathrm{run}}$$ N run : Number of runs nationallicence $$P$$ P : Set of subtask nationallicence $$P_i$$ P i : $$i$$ i -th subtasks nationallicence $$P_{ijk}^{\mathrm{path}}$$ P i j k path : Traveling path of robot $$R_k$$ R k from the inspection position of $$P_i $$ P i to that of $$P_j$$ P j nationallicence $$Q$$ Q : Set of subtask groups nationallicence $$Q_i$$ Q i : $$i$$ i -th subtask group nationallicence $$q_j^i$$ q j i : $$j$$ j -th subtask in the sequence of $$Q_i$$ Q i nationallicence $$R$$ R : Set of robots nationallicence $$R_k$$ R k : $$k$$ k -th robot nationallicence $$R_{P}$$ R P : Average relative performance of algorithms nationallicence $$S$$ S : Set of home bases nationallicence $$S_k$$ S k : Home base of robot $$R_k$$ R k nationallicence $$T$$ T : Set of tasks nationallicence $$T_l$$ T l : $$l$$ l -th task nationallicence $$t_l$$ t l : Subtask for a single-robot task nationallicence $$t_{l1}, t_{l2}$$ t l 1 , t l 2 : Two subtasks of a two-robot task nationallicence $$X$$ X : MRTA solution candidate using matrix coding nationallicence $$Z$$ Z : Genotype of an individual - gene sequence for each robot nationallicence $$Z_k$$ Z k : Gene sequence of robot $$R_k$$ R k nationallicence $$z_i^k$$ z i k : $$i$$ i -th gene in the sequence of $$Z_k$$ Z k nationallicence $$\tau _i^a$$ τ i a : Arrival time of robot at inspection position of $$P_i$$ P i nationallicence $$\tau _i^s$$ τ i s : Time of robot starting inspection task $$P_i$$ P i nationallicence $$\theta $$ θ : Number of subtasks of $$Q_i$$ Q i nationallicence $$\mu (i)$$ μ ( i ) : Mean parameter of normal distribution for producing the $$i$$ i -th integer of new gene-apportions nationallicence $$\sigma $$ σ : Standard deviation of normal distribution for producing new gene-apportions nationallicence Liu Chun Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany aut Kroll Andreas Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany aut Soft Computing Springer Berlin Heidelberg 19/3(2015-03-01), 567-584 1432-7643 19:3<567 2015 19 500 https://doi.org/10.1007/s00500-014-1274-0 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00500-014-1274-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Liu Chun Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany aut NATIONALLICENCE 700 1- Kroll Andreas Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany aut NATIONALLICENCE 773 0- Soft Computing Springer Berlin Heidelberg 19/3(2015-03-01), 567-584 1432-7643 19:3<567 2015 19 500