Pengembangan Algoritme Niching Particle Swarm Optimization untuk Pencarian Target pada Sistem Multi-Robot
DOI:
https://doi.org/10.25126/jtiik.0813173Abstrak
Robot seringkali digunakan untuk mencari target, dalam hal ini target bisa korban, barang berbahaya dan tidak bisa dijangkau oleh manusia sehingga diganti menggunakan robot.Robot melakukan pencarian untuk menemukan target yang kemudian mengalokasikan diri ke
target dengan asumsi bahwa targetnya dapat memancarkan sinyal. Permasalahan tersebut dipandang sebagai suatu masalah optimasi. Salah satu teknik yang dapat menyelesaikan masalah optimasi merupakan algoritme Particle Swarm Optimization (PSO). Masalah yang sering ditangani PSO sampai saat ini hanya sebatas masalah single-target. Beberapa masalah pada dunia nyata merupakan masalah multi-target, sehingga tidak dapat diselesaikan dengan algoritme PSO. Multi-target merupakan pencarian multi-robot untuk mengoptimasi pencarian target pada satu atau lebih titik optimum di dalam ruang pencarian. Masalah optimasi pada multi-target dapat diselesaikan menggunakan algoritme Niching Particle Swarm Optimization (NichePSO). Penelitian ini bertujuan untuk mengembangkan algoritme NichePSO untuk pencarian target pada sistem multi-robot. Pengembangan algoritme dilakukan dengan menggabungkan algoritme NichePSO dengan parameter robot e-puck yang merupakan kontribusi pertama pada penelitian ini. Kontribusi kedua adalah menerapkan algoritme penghindaran dan menggunakan teknik reflecting untuk robot yang keluar dari batas area pencarian.Pada studi ini membandingkan hasil performa antara algoritme NichePSO tanpa algoritme penghindaran dan dengan algoritme penghindaran, diuji dengan beberapa rintangan dalam lingkungan statis. Hasil penelitian menunjukkan bahwa pengembangan algoritme NichePSO pada tanpa algoritme penghindaran dan dengan algoritme penghindaran jauh berbeda dalam jumlah tabrakan tetapi tidak berbeda secara signifikan dalam waktu pencarian dan nilai fitnes.Abstract
Robots are often used to find targets, in this case targets can be victims, dangerous goods and cannot be reached by humans so they are replaced using robots. The robot does a search to find a target which then allocates itself to the target assuming that the target can emit a signal. This problem is seen as an optimization problem. One technique that can solve optimization problems is the Particle Swarm Optimization (PSO) algorithm. The problem that is often handled by PSO to date is only limited to single-target problems. Some real-world problems are multi-target problems, so they cannot be solved by the PSO algorithm. Multi-target is a multi-robot search to optimize target search at one or more optimum points in the search space. The problem of optimization on multi-targets can be solved using the Niching Particle Swarm Optimization (NichePSO) algorithm. This study aims to develop a NichePSO algorithm for target search on multi-robot systems. The development of the algorithm is done by combining the NichePSO algorithm with the e-puck robot parameters which is the first contribution to this research. The second contribution is to apply avoidance algorithms and use reflecting techniques for robots that come out of the boundary of the search area. In this study comparing the performance results between the NichePSO algorithm without the avoidance algorithm and with the avoidance algorithm, tested with several obstacles in a static environment. The results showed that the development of the NichePSO algorithm without the avoidance algorithm and with the avoidance algorithm differed significantly in the number of collisions but did not differ significantly in search time and fitness values.
Robot seringkali digunakan untuk mencari target, dalam hal ini target bisa korban, barang berbahaya dan tidak bisa dijangkau oleh manusia sehingga diganti menggunakan robot. Robot melakukan pencarian untuk menemukan target yang kemudian mengalokasikan diri ke target dengan asumsi bahwa targetnya dapat memancarkan sinyal. Permasalahan tersebut dipandang sebagai suatu masalah optimasi. Salah satu teknik yang dapat menyelesaikan masalah optimasi merupakan algoritme Particle Swarm Optimization (PSO). Masalah yang sering ditangani PSO sampai saat ini hanya sebatas masalah single-target. Beberapa masalah pada dunia nyata merupakan masalah multi-target, sehingga tidak dapat diselesaikan dengan algoritme PSO. Multi-target merupakan pencarian multi-robot untuk mengoptimasi pencarian target pada satu atau lebih titik optimum di dalam ruang pencarian. Masalah optimasi pada multi-target dapat diselesaikan menggunakan algoritme Niching Particle Swarm Optimization (NichePSO). Penelitian ini bertujuan untuk mengembangkan algoritme NichePSO untuk pencarian target pada sistem multi-robot. Pengembangan algoritme dilakukan dengan menggabungkan algoritme NichePSO dengan parameter robot e-puck yang merupakan kontribusi pertama pada penelitian ini. Kontribusi kedua adalah menerapkan algoritme penghindaran dan menggunakan teknik reflecting untuk robot yang keluar dari batas area pencarian.Pada studi ini membandingkan hasil performa antara algoritme NichePSO tanpa algoritme penghindaran dan dengan algoritme penghindaran, diuji dengan beberapa rintangan dalam lingkungan statis. Hasil penelitian menunjukkan bahwa pengembangan algoritme NichePSO pada tanpa algoritme penghindaran dan dengan algoritme penghindaran jauh berbeda dalam jumlah tabrakan tetapi tidak berbeda secara signifikan dalam waktu pencarian dan nilai fitnes.
Downloads
Referensi
AGASSOUNON, W., MARTINOLI, A., EASTON, K., 2004. Macroscopic modeling of aggregation experiments using embodied agents in teams of constant and time-varying sizes. Autonomous Robots, 17(2–3), p. 163–191.
AKAT, S.B., GAZI, V., 2008. Particle swarm optimization with dynamic neighborhood topology three neighborhood strategies and preliminary results. IEEE Swarm Intelligence Symposium St.
ALFRIANTA, A., HARDHIENATA, M.K.D., PRIANDANA, K., 2019. Pengembangan algoritme penghindaran rintangan pada algoritme particle swarm optimization untuk sistem multi-robot pencari target [skripsi]. Bogor (ID): Institut Pertanian Bogor.
AME, J.M., MILLOR, J., HALLOY, J., SEMPO, G., 2006. Collective decision making based on individual discrimination capability in pre social insects. InProc. 9th International Conference on Simulation of Adaptive Behavior (SAB), p. 713-724.
BEN-ARI, M., MONDADA, F., 2018. Elements of Robotics. Springer.
BENI, G., 2004. From swarm intelligence to swarm robotics. InProc. of the SAB International Workshop on Swarm Robotics, p. 3342:1–9. doi: 10.1007/978-3-540-30552-1_1.
BONABEAU, E., DORIGO, M., THERAULAZ, G., 1999. Swarm intelligence from natural to artificial systems. Oxford University Press. New York.
BRITS, R., ENGELBRECHT, A.P., VAN DEN BERGH, F., 2002. A niching particle swarm optimizer. Department of computer science, University of Pretoria: Pretoria.
CHRISTOPHER, M., CIANCI, RAEMY, X., PUGH, J., MARTINOLI, A., 2006. Communication in a swarm of miniature robots: the e-puck as an educational tool for swarm robotics. International Workshop on Swarm Robotics, 4433, p. 103-115.
CLERC, M., KENNEDY, J., 2002. The particle swarm explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), p. 58–73.
DOCTOR, S, VENAYAGAMOORTHY, G.K., GUDISE, V.G., 2004. Optimal pso for collective robotic search applications. In Congress on Evolutionary Computation, 2, p. 1390–1395.
EBERHART, R.C., KENNEDY, J., 1995. A new optimizer using particle swarm theory. In Sixth International Symposium on Micromachine and Human Science, p. 39–43.
GAGE, D.W., 1995. Many robot MCM search systems. proceedings of autonomous vehicles in mine countermeasures symposium, p. 9–55. Monetery:California.
GHOSH, P., ZAFAR, H., DAS, S., ABRAHAM, A., 2011. Hierarchical dynamic neighborhood based particle swarm optimization for global optimization. IEEE Congress of Evolutionary Computation.
HARDHIENATA, M.K.D., MERRICK, K.E., UGRINOVSKII, V., 2014. Task allocation under communication constraints using motivated particle swarm optimization. IEEE congress on evalutionary computational, p. 3135-3134.
HARDIN, X., CUI, R., RAGADE, J., GRAHAM, ELMAGHRABY, A., 2004. A modified particle swarm algorithm for robotic mapping of hazardous environments. in Proc. of Automation World Congress, 17(1), p. 31–36.
HEREFORD, J., SIEBOLD, M., 2008. Multi robot search using a physically embedded particle swarm optimization. International Journal of Computational Intelligence Research, 4(2), p. 197–209.
KARLA, P., MAHAPATRA, P.B., AGGARWAL, D.K., 2003. On the solution of multimodal robot inverse kinematic functions using real-coded genetic algorithms. Proceedings of IEEE on systems, man and cybernetics, Washington (USA): United States.
KENNEDY, J., EBERHART, R.C., 1995. Particle swarm optimization. Proceedings of the IEEE international conference on neural networks, 4, p. 1942–1948.
KENNEDY, J., EBERHART, R.C., 2001. Swarm Intelligence. San Mateo California:Morgan Kaufmann.
KHAN, K., ASHOK, S., 2012. A comparison of BA, GA, PSO, BP and LM for training feedforward neural networks in e-learning context. Intelligent Systems and Applications, 7, p. 23-29.
KUSWADI, S., SIGIT, R., SULISTIJONO, I.A., TAMARA, M.N., 2017. Disaster swarm robot development: On going project. International Conference on Electrical Engineering and Informatics, p. 45–50. doi: 10.1109/ ICELTICS.2017.8253258.
LI, H., HE, X., XIE, X., LI, L., ZHOU, J., LI, X., 2010. A New Boundary Condition for Particle Swarm Optimization. Journal of Convergence Information Technology, 5(9), p. 215-221. doi: 10.4156/jcit.vol5.issue9.22.
LI, X., 2010. Niching without niching parameters: Particle swarm optimization using a ring topology. IEEE Transactions on Evolutionary Computation, 14(1), p. 150–169.
LOPEZ, B., SUAREZ, DE LA ROSA, J.L., 2003. Task allocation in rescue operations using combinatorial auctions. Artificial Intelligence Research and Development, p. 233–243.
LØVBJERG, M., RASMUSSEN, T.K., KRINK, T., 2001. Hybrid Particle Swarm Optimizer with Breeding and Subpopulations. In Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco:California.
LUO, C., ESPINOSA, A.P., PRANANTHA, D., GLORIA, A.D., 2011. Multi robot search and rescue. IEEE International Symposium on Safety, Security and Rescue Robotics, p. 296–301.
MENG, Y., GAN, J., 2008. Self adaptive distributed multi task allocation in a multi robot system. In IEEE Congress on Evolutionary Computation, p. 398–404.
MOHCENE, B., MOUSSA, S., KAHLA, S., 2014. Maximum power point tracking for photovoltaic systems: A comparison between GA and PSO approaches. International Journal of Hydrogen Energy, 10(6), p. 393-398.
PASSARO, A., STARITA, A., 2008. Particle swarm optimization for multimodal functions a clustering approach. Journal of Artificial Evolution and Applications.
Parsopoulos, K.E., Vrahatis, M.N., 2001. Modification of the Particle Swarm Optimizer for Locating All the Global Minima. Artificial Neural Nets and Genetic Algorithms, p. 324-327. doi: 10.1007/978-3-7091-6230-9_80.
PATEL, P.K., SHARMA, V., GUPTA, K., 2013. Guaranteed convergence particle swarm optimization using personal best. International Journal of Comp uter Applications, 73(7), p. 0975-8887.
PUGH, J, MARTINOLI, A., ZHANG, Y., 2005. Particle swarm optimization for unsupervised robotic learning. Proceedings IEEE Swarm Intelligence Symposium, Pasadena:USA.
PUGH, J., MARTINOLI, A., 2006. Multi-Robot Learning with Particle Swarm Optimization. Proceedings of the fifth international joint conference on Autonomous agents and multiagent system.
PUGH, J., MARTINOLI, A., 2007. Inspiring and modeling multi-robot search with particle swarm optimization. In IEEE Swarm Intelligence Symposium, p. 332–339.
UKIL, A., SHAH, V.H., DECK, B., 2011. Fast computation of arctangent functions for embedded applications: A comparative analysis. IEEE International Symposium on Industrial Electronics.
VAN DEN BERGH, F., ENGELBRECHT, A.P., 2002. A new locally convergent particle swarm optimizer. IEEE International Conference on Systems, Man and Cybernetics, 3.
VAN DEN BERGH F., 2002. An analysis of particle swarm optimizers [Thesis]. South Africa: University of Pretoria.
ZHANG, J., GONG, D., ZHANG, Y., 2014. A niching PSO-based multi-robot cooperation method for locating odor sources. Neurocomputing, p. 123:308-317.
Unduhan
Diterbitkan
Terbitan
Bagian
Lisensi
Artikel ini berlisensi Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
Penulis yang menerbitkan di jurnal ini menyetujui ketentuan berikut:
- Penulis menyimpan hak cipta dan memberikan jurnal hak penerbitan pertama naskah secara simultan dengan lisensi di bawah Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) yang mengizinkan orang lain untuk berbagi pekerjaan dengan sebuah pernyataan kepenulisan pekerjaan dan penerbitan awal di jurnal ini.
- Penulis bisa memasukkan ke dalam penyusunan kontraktual tambahan terpisah untuk distribusi non ekslusif versi kaya terbitan jurnal (contoh: mempostingnya ke repositori institusional atau menerbitkannya dalam sebuah buku), dengan pengakuan penerbitan awalnya di jurnal ini.
- Penulis diizinkan dan didorong untuk mem-posting karya mereka online (contoh: di repositori institusional atau di website mereka) sebelum dan selama proses penyerahan, karena dapat mengarahkan ke pertukaran produktif, seperti halnya sitiran yang lebih awal dan lebih hebat dari karya yang diterbitkan. (Lihat Efek Akses Terbuka).