Optimal Robot Path Planning using Particle Swarm Optimization Algorithm

Abstract

The problem of robot path planning is one of the major problems in the field of robotics and automation. Since the high working speed of the robots requires extreme performance from the control systems, accuracy of the robot movement and path planning is important. In the robot path planning process, from a starting point to the end point, the robot is intended to reach the destination by drawing a geometric path as soon as possible without getting stuck on the existing obstacles. The robot path planning problem is classified as difficult due to the fact that there are many path options in the searched space space and the shortest distance between these paths is decided. Classical robot path planning methods have difficulty finding solutions as the problem becomes more complex. Therefore, in recent years, the importance of heuristic methods for optimum solution of the path planning problem in the field of robotics has been increasing. In the literature, many heuristic algorithms have been used for different applications of the problem for robot path planning problem. In this study, the path planning process is simulated by using Particle Swarm Optimization (PSO) algorithm in order to reach the end point in order to use the shortest path without hitting the obstacles encountered by a robot at the starting point until it reaches the destination. The shortest robot path was calculated by using PSO algorithm according to three different endpoints B (4,6), C (6,8) and D (8,10), whose starting point is fixed A (0,0). Simulations were also performed for each different destination by changing the position of the obstacles in the study. In this way, robot path planning was tried to be solved in three different positions. Since the obstacles used in the study are circular, the mathematical formula of the distance between a point and a line was used to find the distance between the starting and ending points and thus, the circular obstacles were tried to be avoided. The robot path planning problem solving with PSO algorithm is shown with tables and graphs for each case. According to the results of the study with PSO, the shortest calculations of the robot path were found in three different cases. In this way, it is shown that PSO algorithm solutions are applicable for robot path planning.

Keywords

• Particle Swarm Optimization
• Optimal Robot Path Planning
• Robot Path Simulation

Parçacık Sürü Optimizasyon Algoritması Kullanılarak Optimum Robot Yolu Planlama

Öz

Robot yolu planlama problemi robotik ve otomasyon alanı için önemli problemlerden bir tanesidir. Robotların yüksek çalışma hızı, kontrol sistemlerinden aşırı performans gerektirdiği için robot hareketinin doğruluğu ve yol planlaması önem arz etmektedir. Robot yol planlama işleminde, bir başlangıç noktasından son noktaya kadar robotun var olan engellere takılmadan en kısa bir şekilde geometrik bir yol çizerek varış noktasına ulaşması amaçlanır. Robot yol planlama problemi arama yapılan alan uzayında birçok yol seçeneğinin bulunması ve bu yollar arasında en kısa mesafenin karar verilmeye çalışılması nedeniyle zor problemler sınıfına girmektedir. Klasik robot yolu planlama yöntemleri problem karmaşıklaştıkça çözüm bulmakta zorlanmaktadır. Bundan dolayı son yıllarda robotik alanında yol planlama probleminin optimum çözümü için sezgisel yöntemlerin önemi artmaktadır. Robot yolu planlama problemi için literatürde birçok sezgisel algoritma probleminin farklı uygulamaları için kullanılmıştır. Bu çalışmada başlangıç noktasında yer alan bir robotun varış noktasına gidene kadar karşılaşacağı engellere çarpmadan en kısa yolu kullanacak şekilde bitiş noktasına ulaşması için Parçacık Sürü Optimizasyon (PSO) algoritması kullanılarak yol planlama işleminin simülasyonu yapılmıştır. Başlangıç noktası sabit A(0,0) olan ve üç farklı bitiş noktalarına B(4,6), C(6,8) ve D(8,10) göre PSO algoritması ile en kısa robot yolu hesaplanmıştır. Aynı zamanda her bir farklı varış noktası için çalışmada engellerin konumları da değiştirilerek simülasyon işlemi yapılmıştır. Bu şekilde üç farklı konumda robot yolu planlaması çözülmeye çalışılmıştır. Çalışmada kullanılan engeller daire şeklinde olduğundan başlangıç ve bitiş noktaları arasındaki mesafeyi bulmak için bir nokta ve bir doğruya uzaklığının matematiksel formülü kullanılmış ve bu şekilde dairesel engellerden kaçınılmaya çalışılmıştır. PSO algoritması ile yapılan robot yolu planlama problem çözümü her bir durum için tablolar ve grafikler ile gösterilmiştir. PSO ile yapılan çalışma sonuçlarına göre üç farklı durumda robot yolunun en kısa hesaplamaları bulunmuştur. Bu şekilde PSO algoritması çözümlerinin robot yolu planlaması için uygulanabilir olduğu gösterilmiştir.

Anahtar Kelimeler

• Parçacık Sürü Optimizasyonu
• Optimum Robot Yolu Planlama
• Robot yolu Simülasyonu

References

1. Abdelbar, A. M., Abdelshahid, S., & Wunsch, D. C. (2005). Fuzzy PSO: a generalization of particle swarm optimization. Paper presented at the Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005.
2. Ayari, A., & Bouamama, S. (2017). A new multiple robot path planning algorithm: dynamic distributed particle swarm optimization. Robotics and biomimetics, 4(1), 8.
3. Boğar, E. (2016). Tek ve Çok Amaçlı Robot Yol Planlama Problemi için Hibrit Bir Optimizasyon Yöntemi. (Yüksek Lisans), Pamukkale Üniversitesi, Fen Bilimleri Enstitüsü, Denizli.
4. Chakraborty, J., Konar, A., Chakraborty, U. K., & Jain, L. C. (2008). Distributed cooperative multi-robot path planning using differential evolution. Paper presented at the 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence).
5. Chander, A., Chatterjee, A., & Siarry, P. (2011). A new social and momentum component adaptive PSO algorithm for image segmentation. Expert Systems with Applications, 38(5), 4998-5004.
6. Darvishzadeh, A., & Bhanu, B. (2014). Distributed multi-robot search in the real-world using modified particle swarm optimization. Paper presented at the Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation.
7. Doctor, S., Venayagamoorthy, G. K., & Gudise, V. G. (2004). Optimal PSO for collective robotic search applications. Paper presented at the Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753).
8. Eokultv. (2019). İki Nokta Arasındaki Uzaklık. Retrieved from https://www.eokultv.com/iki-nokta-arasindaki-uzaklik/3025

9. Grandi, R., Falconi, R., & Melchiorri, C. (2013). Coordination and control of autonomous mobile robot groups using a hybrid technique based on particle swarm optimization and consensus. Paper presented at the 2013 IEEE International Conference on Robotics and Biomimetics (ROBIO).
10. Hereford, J. M. (2006). A distributed particle swarm optimization algorithm for swarm robotic applications. Paper presented at the 2006 IEEE International Conference on Evolutionary Computation.
11. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization (PSO). Paper presented at the Proc. IEEE International Conference on Neural Networks, Perth, Australia.
12. Pugh, J., Segapelli, L., & Martinoli, A. (2006). Applying aspects of multi-robot search to particle swarm optimization. Paper presented at the International Workshop on Ant Colony Optimization and Swarm Intelligence.
13. Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2010). Robotics: modelling, planning and control: Springer Science & Business Media.
14. Suvaydan, F. (2011). Mobil robotlar için yol planlama problemi ve karınca kolonisi ile yol planlama problemlerinin optimal çözümü. (Yüksek Lisans), Düzce Üniversitesi, Fen Bilimleri Enstitüsü, Düzce.
15. Tefek, M. F., & Uğuz, H. (2016). Investigation of Fuel Cost and Emission Effects of Wind Energy Into Power Systems by Using Gsa, Tlbo and Pso Algorithms. Paper presented at the 8 th International Ege Energy Syposium, Afyonkarahisar, Turkey.
16. Zhang, Y., Gong, D.-W., & Zhang, J.-H. (2013). Robot path planning in uncertain environment using multi-objective particle swarm optimization. Neurocomputing, 103, 172-185.