Pengembangan Algoritme Niching Particle Swarm Optimization untuk Pencarian Target pada Sistem Multi-Robot

Penulis

Siti Raehan, Agus Buono, Medria Kusuma Dewi Hardhienata

Abstrak

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.

Teks Lengkap:

PDF

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.




DOI: http://dx.doi.org/10.25126/jtiik.0813173