Ant Colony Optimization Modelling for Task Allocation in Multi-Agent System for Multi-Target

  • Iis Rodiah IPB University
  • Medria Kusuma Dewi Hardhienata IPB University
  • Agus Buono IPB University
  • Karlisa Priandana IPB University
DOI: https://doi.org/10.29207/resti.v6i6.4201
Keywords: task allocation, sistem multi-agen, multi-target, ACO.

Abstract

Task allocation in multi-agent system can be defined as a problem of allocating a number of agents to the task. One of the problems in task allocation is to optimize the allocation of heterogeneous agents when there are multiple tasks which require several capabilities. To solve that problem, this research aims to modify the Ant Colony Optimization (ACO) algorithm so that the algorithm can be employed for solving task allocation problems with multiple tasks. In this research, we optimize the performance of the algorithm by minimizing the task completion cost as well as the number of overlapping agents. We also maximize the overall system capabilities in order to increase efficiency. Simulation results show that the modified ACO algorithm has significantly decreased overall task completion cost as well as the overlapping agents factor compared to the benchmark algorithm.

 

Downloads

Download data is not yet available.

References

J. Parker, “Task allocation for multi-agent systems in dynamic environments,” 12th Int. Conf. Auton. Agents Multiagent Syst. 2013, AAMAS 2013, vol. 2, pp. 1445–1446, 2013.

A. Khamis, A. Hussein, and A. Elmogy, “Multi-robot Task Allocation: A Review of the State-of-the-Art,” Stud. Comput. Intell., vol. 604, pp. 31–51, 2015, doi: 10.1007/978-3-319-18299-5_2.

M. Irfan and A. Farooq, “Auction-based task allocation scheme for dynamic coalition formations in limited robotic swarms with heterogeneous capabilities,” 2016 Int. Conf. Intell. Syst. Eng. ICISE 2016, pp. 210–215, 2016, doi: 10.1109/INTELSE.2016.7475122.

Y. Miao, L. Zhong, Y. Yin, C. Zou, and Z. Luo, “Research on dynamic task allocation for multiple unmanned aerial vehicles,” Trans. Inst. Meas. Control, vol. 39, no. 4, pp. 466–474, 2017, doi: 10.1177/0142331217693077.

F. Tang and L. E. Parker, “A complete methodology for generating multi-robot task solutions using ASyMTRe-D and market-based task allocation,” Proc. - IEEE Int. Conf. Robot. Autom., no. April, pp. 3351–3358, 2007, doi: 10.1109/ROBOT.2007.363990.

M. K. D. Hardhienata, K. E. Merrick, and V. Ugrinovskii, “Task allocation in multi-agent systems using models of motivation and leadership,” 2012 IEEE Congr. Evol. Comput. CEC 2012, 2012, doi: 10.1109/CEC.2012.6256114.

J. P. Wang, Y. Gu, and X. M. Li, “Multi-robot task allocation based on ant colony algorithm,” J. Comput., vol. 7, no. 9, pp. 2160–2167, 2012, doi: 10.4304/jcp.7.9.2160-2167.

G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” Int. J. Rob. Res., vol. 32, no. 12, pp. 1495–1512, 2013, doi: 10.1177/0278364913496484.

H. Liu, P. Zhang, B. Hu, and P. Moore, “A novel approach to task assignment in a cooperative multi-agent design system,” Appl. Intell., vol. 43, no. 1, pp. 162–175, 2015, doi: 10.1007/s10489-014-0640-z.

M. Khani, A. Ahmadi, and H. Hajary, “Distributed task allocation in multi-agent environments using cellular learning automata,” Soft Comput., vol. 23, no. 4, pp. 1199–1218, 2019, doi: 10.1007/s00500-017-2839-5.

S. S. Chiddarwar and N. R. Babu, “Multi-agent system for off-line coordinated motion planning of multiple industrial robots,” Int. J. Adv. Robot. Syst., vol. 8, no. 1, pp. 102–112, 2011, doi: 10.5772/10533.

Yan Jin, A. A. Minai, and M. M. Polycarpou, “Cooperative real-time search and task allocation in UAV teams,” in 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), 2003, vol. 1, no. December, pp. 7–12. doi: 10.1109/CDC.2003.1272527.

Q. Cheng, D. Yin, J. Yang, and L. Shen, “An Auction-Based Multiple Constraints Task Allocation Algorithm for Multi-UAV System,” Proc. - 2016 Int. Conf. Cybern. Robot. Control. CRC 2016, pp. 1–5, 2017, doi: 10.1109/CRC.2016.7.

H. A. Kurdi et al., “Autonomous task allocation for multi-UAV systems based on the locust elastic behavior,” Appl. Soft Comput. J., vol. 71, pp. 110–126, 2018, doi: 10.1016/j.asoc.2018.06.006.

N. Noguchi and O. C. Barawid, Robot farming system using multiple robot tractors in Japan agriculture, vol. 44, no. 1 PART 1. IFAC, 2011. doi: 10.3182/20110828-6-IT-1002.03838.

A. T. J. R. Cobbenhagen, D. J. Antunes, M. J. G. van de Molengraft, and W. P. M. H. Heemels, “Heterogeneous multi-agent resource allocation through multi-bidding with applications to precision agriculture⁎,” IFAC-PapersOnLine, vol. 51, no. 23, pp. 194–199, 2018, doi: 10.1016/j.ifacol.2018.12.034.

M. Davoodi, J. M. Velni, and C. Li, “Coverage control with multiple ground robots for precision agriculture,” Mech. Eng., vol. 140, no. 6, pp. 4–8, 2018, doi: 10.1115/1.2018-jun-4.

R. Cao et al., “Task assignment of multiple agricultural machinery cooperation based on improved ant colony algorithm,” Comput. Electron. Agric., vol. 182, p. 105993, Mar. 2021, doi: 10.1016/J.COMPAG.2021.105993.

A. Hussein and A. Khamis, “Market-based approach to Multi-robot Task Allocation,” in 2013 International Conference on Individual and Collective Behaviors in Robotics (ICBR), Dec. 2013, pp. 69–74. doi: 10.1109/ICBR.2013.6729278.

J. Yang and Z. Luo, “Coalition formation mechanism in multi-agent systems based on genetic algorithms,” Appl. Soft Comput., vol. 7, no. 2, pp. 561–568, Mar. 2007, doi: 10.1016/j.asoc.2006.04.004.

L. Wang, Z. Wang, S. Hu, and L. Liu, “Ant Colony Optimization for task allocation in Multi-Agent Systems,” China Commun., vol. 10, no. 3, pp. 125–132, Mar. 2013, doi: 10.1109/CC.2013.6488841.

P. C. Pendharkar, “An ant colony optimization heuristic for constrained task allocation problem,” J. Comput. Sci., vol. 7, pp. 37–47, 2015, doi: 10.1016/j.jocs.2015.01.001.

M. Sriatun, “Modifikasi ant colony optimization untuk menyelesaikan masalah task allocation dalam skenario bencana tanah longsor mamik sriatun,” 2019.

H. Cui, X. Liu, T. Yu, H. Zhang, Y. Fang, and Z. Xia, “Cloud Service Scheduling Algorithm Research and Optimization,” Secur. Commun. Networks, vol. 2017, no. Dc, pp. 1–7, 2017, doi: 10.1155/2017/2503153.

M. Dorigo, V. Maniezzo, and A. Colorni, “Ant System : An Autocatalytic Optimizing Process Technical Report 91-016,” Leonardo, pp. 1–21, 1991.

J. Li and W. Zhang, “Solution to Multi-objective Optimization of Flow Shop Problem Based on ACO Algorithm,” in 2006 International Conference on Computational Intelligence and Security, Nov. 2006, pp. 417–420. doi: 10.1109/ICCIAS.2006.294166.

I. Alaya, C. Solnon, and K. Ghédira, “Ant colony optimization for multi-objective optimization problems,” Proc. - Int. Conf. Tools with Artif. Intell. ICTAI, vol. 1, pp. 450–457, 2007, doi: 10.1109/ICTAI.2007.108.

S. K. Chaharsooghi and A. H. Meimand Kermani, “An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP),” Appl. Math. Comput., vol. 200, no. 1, pp. 167–177, 2008, doi: 10.1016/j.amc.2007.09.070.

B. Yagmahan and M. M. Yenisey, “Ant colony optimization for multi-objective flow shop scheduling problem,” Comput. Ind. Eng., vol. 54, no. 3, pp. 411–420, 2008, doi: 10.1016/j.cie.2007.08.003.

D. Angus and C. Woodward, “Multiple objective ant colony optimisation,” Swarm Intell., vol. 3, no. 1, pp. 69–85, 2009, doi: 10.1007/s11721-008-0022-4.

Y. Li, H. Soleimani, and M. Zohal, “An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives,” J. Clean. Prod., vol. 227, pp. 1161–1172, 2019, doi: 10.1016/j.jclepro.2019.03.185.

K. Khurshid, S. Irteza, and A. A. Khan, “Application of ant colony optimization based algorithm in MIMO detection,” 2010 IEEE World Congr. Comput. Intell. WCCI 2010 - 2010 IEEE Congr. Evol. Comput. CEC 2010, 2010, doi: 10.1109/CEC.2010.5586173.

Published
2022-12-27
How to Cite
Rodiah, I., Medria Kusuma Dewi Hardhienata, Agus Buono, & Karlisa Priandana. (2022). Ant Colony Optimization Modelling for Task Allocation in Multi-Agent System for Multi-Target. Jurnal RESTI (Rekayasa Sistem Dan Teknologi Informasi), 6(6), 911 - 922. https://doi.org/10.29207/resti.v6i6.4201
Issue
Vol 6 No 6 (2022): Desember 2022
Section
Information Systems Engineering Articles

Copyright (c) 2022 Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi)

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright in each article belongs to the author

  1. The author acknowledges that the RESTI Journal (System Engineering and Information Technology) is the first publisher to publish with a license Creative Commons Attribution 4.0 International License.
  2. Authors can enter writing separately, arrange the non-exclusive distribution of manuscripts that have been published in this journal into other versions (eg sent to the author's institutional repository, publication in a book, etc.), by acknowledging that the manuscript has been published for the first time in the RESTI (Rekayasa Sistem dan Teknologi Informasi) journal ;