Memetic algorithms for optimal task allocation in multi-robot systems for inspection problems with cooperative tasks
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605469431 | ||
| 003 | CHVBK | ||
| 005 | 20210128100322.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150301xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s00500-014-1274-0 |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s00500-014-1274-0 | ||
| 245 | 0 | 0 | |a Memetic algorithms for optimal task allocation in multi-robot systems for inspection problems with cooperative tasks |h [Elektronische Daten] |c [Chun Liu, Andreas Kroll] |
| 520 | 3 | |a 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. | |
| 540 | |a Springer-Verlag Berlin Heidelberg, 2014 | ||
| 690 | 7 | |a Constrained combinatorial optimization |2 nationallicence | |
| 690 | 7 | |a Multi-robot task allocation |2 nationallicence | |
| 690 | 7 | |a Cooperation |2 nationallicence | |
| 690 | 7 | |a Memetic algorithm |2 nationallicence | |
| 690 | 7 | |a Genetic algorithm |2 nationallicence | |
| 690 | 7 | |a Inspection |2 nationallicence | |
| 690 | 7 | |a $$A$$ A : MRTA solution candidate by permutation coding |2 nationallicence | |
| 690 | 7 | |a $$A_k$$ A k : Task assignment and task schedule of robot $$R_k$$ R k |2 nationallicence | |
| 690 | 7 | |a $$a_i^k$$ a i k : $$i$$ i -th subtask of $$A_k$$ A k |2 nationallicence | |
| 690 | 7 | |a $$B$$ B : Set of individuals |2 nationallicence | |
| 690 | 7 | |a $$B_j$$ B j : Set of best individuals in $$j$$ j -th generation |2 nationallicence | |
| 690 | 7 | |a $$C$$ C : Set of time costs |2 nationallicence | |
| 690 | 7 | |a $$C_k (A_k )$$ C k ( A k ) : Time for robot $$R_k $$ R k to complete its tasks $$A_k$$ A k |2 nationallicence | |
| 690 | 7 | |a $$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 |2 nationallicence | |
| 690 | 7 | |a $$c_{jk}^s$$ c j k s : Time robot $$R_k $$ R k needs to carry out inspection task of $$P_j $$ P j |2 nationallicence | |
| 690 | 7 | |a $$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 |2 nationallicence | |
| 690 | 7 | |a $$E$$ E : Grid map |2 nationallicence | |
| 690 | 7 | |a $$e_{xy}$$ e x y : Cell of grid map |2 nationallicence | |
| 690 | 7 | |a $$f^T$$ f T : Function maps the set $$T$$ T to the set $$P$$ P |2 nationallicence | |
| 690 | 7 | |a $$G_{\mathrm{crt}}$$ G crt : Current generation number |2 nationallicence | |
| 690 | 7 | |a $$G_{\mathrm{max}}$$ G max : Fixed number of generations |2 nationallicence | |
| 690 | 7 | |a $$G^{a}$$ G a : Gene-apportion |2 nationallicence | |
| 690 | 7 | |a $$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 |2 nationallicence | |
| 690 | 7 | |a $$H$$ H : Threshold value for grouping subtasks using combination-based coding |2 nationallicence | |
| 690 | 7 | |a $$J$$ J : Cost function (completion time) |2 nationallicence | |
| 690 | 7 | |a $$K$$ K : Number of subpopulations |2 nationallicence | |
| 690 | 7 | |a $$l_k$$ l k : Number of subtasks of $$A_k$$ A k |2 nationallicence | |
| 690 | 7 | |a $$l_k^z$$ l k z : Number of genes of $$Z_k$$ Z k |2 nationallicence | |
| 690 | 7 | |a $$M$$ M : Submatrices of $$E$$ E |2 nationallicence | |
| 690 | 7 | |a $$N^G$$ N G : Number of genes of a chromosome |2 nationallicence | |
| 690 | 7 | |a $$N^P$$ N P : Number of subtasks |2 nationallicence | |
| 690 | 7 | |a $$N^Q$$ N Q : Number of subtask groups |2 nationallicence | |
| 690 | 7 | |a $$N^R$$ N R : Number of robots |2 nationallicence | |
| 690 | 7 | |a $$N^T$$ N T : Number of tasks |2 nationallicence | |
| 690 | 7 | |a $$N^b$$ N b : Number of elements in $$B_j$$ B j for all $$j$$ j |2 nationallicence | |
| 690 | 7 | |a $$N^{s}$$ N s : Maximal size of a subtask group |2 nationallicence | |
| 690 | 7 | |a $$N^x$$ N x : Size of grid map in $$x$$ x direction |2 nationallicence | |
| 690 | 7 | |a $$N^y$$ N y : Size of grid map in $$y$$ y direction |2 nationallicence | |
| 690 | 7 | |a $$N_{\mathrm{pop}}$$ N pop : Population size |2 nationallicence | |
| 690 | 7 | |a $$N_{\mathrm{run}}$$ N run : Number of runs |2 nationallicence | |
| 690 | 7 | |a $$P$$ P : Set of subtask |2 nationallicence | |
| 690 | 7 | |a $$P_i$$ P i : $$i$$ i -th subtasks |2 nationallicence | |
| 690 | 7 | |a $$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 |2 nationallicence | |
| 690 | 7 | |a $$Q$$ Q : Set of subtask groups |2 nationallicence | |
| 690 | 7 | |a $$Q_i$$ Q i : $$i$$ i -th subtask group |2 nationallicence | |
| 690 | 7 | |a $$q_j^i$$ q j i : $$j$$ j -th subtask in the sequence of $$Q_i$$ Q i |2 nationallicence | |
| 690 | 7 | |a $$R$$ R : Set of robots |2 nationallicence | |
| 690 | 7 | |a $$R_k$$ R k : $$k$$ k -th robot |2 nationallicence | |
| 690 | 7 | |a $$R_{P}$$ R P : Average relative performance of algorithms |2 nationallicence | |
| 690 | 7 | |a $$S$$ S : Set of home bases |2 nationallicence | |
| 690 | 7 | |a $$S_k$$ S k : Home base of robot $$R_k$$ R k |2 nationallicence | |
| 690 | 7 | |a $$T$$ T : Set of tasks |2 nationallicence | |
| 690 | 7 | |a $$T_l$$ T l : $$l$$ l -th task |2 nationallicence | |
| 690 | 7 | |a $$t_l$$ t l : Subtask for a single-robot task |2 nationallicence | |
| 690 | 7 | |a $$t_{l1}, t_{l2}$$ t l 1 , t l 2 : Two subtasks of a two-robot task |2 nationallicence | |
| 690 | 7 | |a $$X$$ X : MRTA solution candidate using matrix coding |2 nationallicence | |
| 690 | 7 | |a $$Z$$ Z : Genotype of an individual - gene sequence for each robot |2 nationallicence | |
| 690 | 7 | |a $$Z_k$$ Z k : Gene sequence of robot $$R_k$$ R k |2 nationallicence | |
| 690 | 7 | |a $$z_i^k$$ z i k : $$i$$ i -th gene in the sequence of $$Z_k$$ Z k |2 nationallicence | |
| 690 | 7 | |a $$\tau _i^a$$ τ i a : Arrival time of robot at inspection position of $$P_i$$ P i |2 nationallicence | |
| 690 | 7 | |a $$\tau _i^s$$ τ i s : Time of robot starting inspection task $$P_i$$ P i |2 nationallicence | |
| 690 | 7 | |a $$\theta $$ θ : Number of subtasks of $$Q_i$$ Q i |2 nationallicence | |
| 690 | 7 | |a $$\mu (i)$$ μ ( i ) : Mean parameter of normal distribution for producing the $$i$$ i -th integer of new gene-apportions |2 nationallicence | |
| 690 | 7 | |a $$\sigma $$ σ : Standard deviation of normal distribution for producing new gene-apportions |2 nationallicence | |
| 700 | 1 | |a Liu |D Chun |u Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany |4 aut | |
| 700 | 1 | |a Kroll |D Andreas |u Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany |4 aut | |
| 773 | 0 | |t Soft Computing |d Springer Berlin Heidelberg |g 19/3(2015-03-01), 567-584 |x 1432-7643 |q 19:3<567 |1 2015 |2 19 |o 500 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00500-014-1274-0 |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s00500-014-1274-0 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Liu |D Chun |u Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Kroll |D Andreas |u Department of Measurement and Control, Mechanical Engineering, University of Kassel, Mönchebergstraße 7, 34125, Kassel, Germany |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Soft Computing |d Springer Berlin Heidelberg |g 19/3(2015-03-01), 567-584 |x 1432-7643 |q 19:3<567 |1 2015 |2 19 |o 500 | ||