No Access

Immigrants Based Adaptive Genetic Algorithms for Task Allocation in Multi-Robot Systems

Pranab K Muhuri

Department of Computer Science, South Asian University, New Delhi 110021, India

E-mail Address: pranabmuhuri@cs.sau.ac.in

Corresponding author.

Search for more papers by this author

and

Amit Rauniyar

Department of Computer Science, South Asian University, New Delhi 110021, India

E-mail Address: amitrauniyar90@gmail.com

Search for more papers by this author

https://doi.org/10.1142/S1469026817500250Cited by:24 (Source: Crossref)

Abstract

Optimal task allocation among the suitably formed robot groups is one of the key issues to be investigated for the smooth operations of multi-robot systems. Considering the complete execution of available tasks, the problem of assigning available resources (robot features) to the tasks is computationally complex, which may further increase if the number of tasks increases. Popularly this problem is known as multi-robot coalition formation (MRCF) problem. Genetic algorithms (GAs) have been found to be quite efficient in solving such complex computational problems. There are several GA-based approaches to solve MRCF problems but none of them have considered the dynamic GA variants. This paper considers immigrants-based GAs viz. random immigrants genetic algorithm (RIGA) and elitism based immigrants genetic algorithm (EIGA) for optimal task allocation in MRCF problem. Further, it reports a novel use of these algorithms making them adaptive with certain modifications in their traditional attributes by adaptively choosing the parameters of genetic operators and terms them as adaptive RIGA (aRIGA) and adaptive EIGA (aEIGA). Extensive simulation experiments are conducted for a comparative performance evaluation with respect to standard genetic algorithm (SGA) using three popular performance metrics. A statistical analysis with the analysis of variance has also been performed. It is demonstrated that RIGA and EIGA produce better solutions than SGA for both fixed and adaptive genetic operators. Among them, EIGA and aEIGA outperform RIGA and aRIGA, respectively.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

1. B. P. Gerkey and M. J. Mataric , A framework for studying multi-robot task allocation, in Multi-Robot Systems: From Swarms to Intelligent Automata, eds. A. Schulte et al. (Kluwer Academic Publishers, Dordrecht, The Netherlands, 2003), pp. 15–26. Google Scholar
2. Y. Cao, W. Yu, W. Ren and G. Chen , An overview of recent progress in the study of distributed multi-agent coordination, IEEE Trans. Ind. Informatics 9 (1) (2013) 427–438. Crossref, Google Scholar
3. L. Vig and J. A. Adams , Coalition formation: From software agents to robots, J. Intell. Robotic Syst. 50 (1) (2007) 85–118. Crossref, Google Scholar
4. T. Sandholm, K. Larson, M. Andersson and O. Shehory , Coalition structure generation with worst case guarantees, Artif. Intell. 111 (1) (1999) 209–238. Crossref, Google Scholar
5. O. Shehory and S. Kraus , Task allocation via coalition formation among autonomous agents, IJCAI, Vol. 1 (1995), pp. 655–661. Google Scholar
6. D. E. Goldberg , Genetic Algorithms (Pearson Education India, 2006). Google Scholar
7. S. N. Sivanandam and S. N. Deepa , Introduction to Genetic Algorithms (Springer Science & Business Media, 2007). Google Scholar
8. A. Haidar and B. Verma , A genetic algorithm based feature selection approach for rainfall forecasting in sugarcane areas, 2016 IEEE Symp. Series Computational Intelligence (SSCI) (IEEE, 2016), pp. 1–8. Google Scholar
9. H. Y. Liu and J. F. Chen , Multi-robot cooperation coalition formation based on genetic algorithm, Machine Learning and Cybernetics, 2006 Int. Conf. IEEE (2006), pp. 85–88. Google Scholar
10. Z. Li, B. Xu, L. Yang, J. Chen and K. Li , Quantum evolutionary algorithm for multi-robot coalition formation, in Proc. First ACM/SIGEVO Summit on Genetic and Evolutionary Computation (ACM, 2009), pp. 295–302. Google Scholar
11. J. Yang and Z. Luo , Coalition formation mechanism in multi-agent systems based on genetic algorithms, Appl. Soft Computing 7 (2) (2007) 561–568. Crossref, Google Scholar
12. J. J. Grefenstette , Genetic algorithms for changing environments, PPSN, Vol. 2 (1992), pp. 137–144. Google Scholar
13. H. G. Cobb and J. J. Grefenstette , Genetic algorithms for tracking changing environments, in Proc. of the Fifth Int. Conf. on Genetic Algorithms (1993), pp. 523–530. Google Scholar
14. H. Cheng, S. Yang and J. Cao , Dynamic genetic algorithms for the dynamic load balanced clustering problem in mobile ad hoc networks, Exp. Syst. Appl. 40 (4) (2013) 1381–1392. Crossref, Google Scholar
15. M. Srinivas and L. M. Patnaik , Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE Trans. Syst. Man Cybern. 24 (4) (1994) 656–667. Crossref, Google Scholar
16. F. A. Omara and M. M. Arafa , Genetic algorithms for task scheduling problem, J. Parallel Distributed Comput. 70 (1) (2010) 13–22. Crossref, Google Scholar
17. L. Vig and J. Adams , Multi-robot coalition formation, IEEE Trans. Robotics 22 (4) (2006) 637–649. Crossref, Google Scholar
18. M. Agarwal, N. Kumar and L. Vig , Non-additive multi-objective robot coalition formation, Exp. Syst. Appl. 41 (8) (2014) 3736–3747. Crossref, Google Scholar
19. T. Balch and R. C. Arkin , Behavior-based formation control for multi-robot teams, IEEE Trans. Robotics Automation 14 (6) (1998) 926–939. Crossref, Google Scholar
20. M. B. Dias, R. Zlot, N. Kalra and A. Stentz , Market-based multirobot coordination: A survey and analysis, in Proc. IEEE 94 (7) (2006) 1257–1270. Crossref, Google Scholar
21. R. Zlot and A. Stentz , Market-based multi-robot coordination for complex tasks, Int. J. Robotics Res. 25 (1) (2006) 73–101. Crossref, Google Scholar
22. M. B. Dias, Traderbots: A new paradigm for robust and efficient multi-robot coordination in dynamic environments. Dissertation, Carnegie Mellon University Pittsburgh (2004). Google Scholar
23. L. E. Parker , ALLIANCE: An architecture for fault tolerant multi-robot cooperation, IEEE Trans. Automation 14 (2) (1998) 220–240. Crossref, Google Scholar
24. B. P. Gerkey and Maja J. Matari , Sold!: Auction methods for multi-robot coordination, IEEE Trans. Robotics Automation 18 (5) (2002) 758–768. Crossref, Google Scholar
25. J. A. Adams , Coalition formation for task allocation: Theory and algorithms, Autonomous Agents Multi-Agent Syst. 22 (2) (2011) 225–248. Crossref, Google Scholar
26. B. P. Gerkey and M. J. Mataric , Multi-robot task allocation: Analyzing the complexity and optimality of key architectures, in Proc.ICRA’03. IEEE International Conference on. Robotics and Automation, 2003. Vol. 3 (IEEE, 2003), pp. 3862–3868. Google Scholar
27. L. E. Parker , Multiple Mobile Robot Systems (Springer Handbook of Robotics. Springer Berlin Heidelberg, 2008), pp. 921–941. Crossref, Google Scholar
28. B. P. Gerkey and M. J. Matarić , A formal analysis and taxonomy of task allocation in multi-robot systems, Int. J. Robotics Res. 23 (9) (2004) 939–954. Crossref, Google Scholar
29. L. E. Parker and F. Tang , Building multirobot coalitions through automated task solution synthesis, Proc. IEEE 94 (7) (2006) 1289–1305. Crossref, Google Scholar
30. O. Shehory and S. Kraus , Methods for task allocation via agent coalition formation, Artif. Intell. 101 (1) (1998) 165–200. Crossref, Google Scholar
31. L. Vig and J. A. Adams , Issues in multi-robot coalition formation, Multi-Robot Systems. From Swarms to Intelligent Automata Volume III (Springer, Netherlands, 2005) pp. 15–26. Crossref, Google Scholar
32. F. Tang and L. E. Parker , A complete methodology for generating multi-robot task solutions using asymtre-d and market-based task allocation, 2007 IEEE International Conf. Robotics and Automation, (IEEE, 2007), pp. 3351–3358. Google Scholar
33. Y. Zhang and L. E. Parker , IQ-ASyMTRe: Forming executable coalitions for tightly coupled multirobot tasks, IEEE Trans. Robotics 29 (2) (2013) 400–416. Crossref, Google Scholar
34. J. Guerrero and G. Oliver , Multi-robot coalition formation in real-time scenarios, Robotics Autonomous Syst. 60 (10) (2012) 1295–1307. Crossref, Google Scholar
35. M. Nanjanath and M. Gini , Repeated auctions for robust task execution by a robot team, Robotics Autonomous Syst. 58 (7) (2010) 900–909. Crossref, Google Scholar
36. P. M. Shiroma and M. F. M. Campos , CoMutaR: A framework for multi-robot coordination and task allocation, in Intelligent Robots and Systems, 2009. International Conf. IROS 2009. IEEE/RSJ IEEE (2009), pp. 4817–4824. Google Scholar
37. G. A. Korsah, A. Stentz, and M. B. Dias , A comprehensive taxonomy for multi-robot task allocation, Int. J. Robotics Res. 32 (12) (2013) 1495–1512. Crossref, Google Scholar
38. S. S. Talay, T. R. Balch, and N. Erdogan , A generic framework for distributed multi-robot cooperation, J. Intell. Robotic Syst. 63 (2) (2011) 323–358. Crossref, Google Scholar
39. Y. Zhang and L. E. Parker , Considering inter-task resource constraints in task allocation, Autonomous Agents Multi-agent Syst. 26 (3) (2013) 389–419. Crossref, Google Scholar
40. J. G. Manathara, P. B. Sujit and R. W. Beard , Multiple UAV coalitions for a search and prosecute mission, J. Intell.Robotic Syst. 62 (1) (2011) 125–158. Crossref, Google Scholar
41. S. H. Liu, Y. Zhang, H. Y. Wu and J. Liu , Multi-robot task allocation based on swarm intelligence, J. Jilin Univ. 40 (1) (2010) 123–129. Google Scholar
42. Z. Yu et al., A quantum-inspired ant colony optimization for robot coalition formation, Control and Decision Conference, 2009. CCDC’09. Chinese (IEEE, 2009). Google Scholar
43. R. Abbasian and M. Mouhoub , A new parallel GA-based method for constraint satisfaction problems, Int. J. Comput. Intell. Appl. 15 (3) (2016) 1650017. Link, Google Scholar
44. H. M. Harmanani and H. A. Salamy , A simulated annealing algorithm for system-on-chip test scheduling with, power and precedence constraints, Int. J. Comput. Intell. Appl. 6 (04) (2006) 511–530. Link, Google Scholar
45. A. Hmer and M. Mouhoub , A multi-phase hybrid metaheuristics approach for the exam timetabling, Int. J. Comput. Intell. Appl. 15 (04) (2016) 1650023. Link, Google Scholar
46. Y. Cai and S. X. Yang , A PSO-based approach with fuzzy obstacle avoidance for cooperative multi-robots in unknown environments, Int. J. Comput. Intell. Appl. 15 (1) (2016). Link, Google Scholar
47. T. Blickle and L. Thiele, A mathematical analysis of tournament selection, ICGA (1995). Google Scholar
48. S. Lee, S. Soak, K. Kim, H. Park and M. Jeon , Statistical properties analysis of real world tournament selection in genetic algorithms, Appl. Intell. 28 (2) (2008) 195–205. Crossref, Google Scholar
49. S. Yang , Genetic algorithms with memory-and elitism-based immigrants in dynamic environments, Evol. Comput. 16 (3) (2008) 385–416. Crossref, Google Scholar
50. F. Vavak and T. C. Fogarty , Comparison of steady state and generational genetic algorithms for use in non-stationary environments, in Proc. IEEE International Conf. Evolutionary Computation, 1996 (IEEE, 1996). Google Scholar
51. X. Yu, K. Tang, T. Chen and X. Yao , Empirical analysis of evolutionary algorithms with immigrants schemes for dynamic optimization, Memetic Comput. 1 (1) (2009) 3–24. Crossref, Google Scholar
52. S. Yang , Genetic algorithms with elitism-based immigrants for changing optimization problems, Workshops on Applications of Evolutionary Computation. (Springer, Berlin Heidelberg, 2007), pp. 627–636. Google Scholar
53. T. T. Nguyen, S. Yang and J. Branke , Evolutionary dynamic optimization: A survey of the state of the art, Swarm Evol. Comput. 6 (2012) 1–24. Crossref, Google Scholar
54. E. Alba and B. Sarasola , ABC, a new performance tool for algorithms solving dynamic optimization problems, Evolutionary Computation (CEC), 2010 IEEE Congress on. IEEE, 2010. Google Scholar
55. A. Rauniyar and P. K. Muhuri , Multi-robot coalition formation problem: Task allocation with adaptive immigrants based genetic algorithms, 2016 IEEE Int. Conf. Systems, Man, and Cybernetics (SMC) (IEEE, 2016), pp. 000137–000142. Google Scholar