Using Swarm Robots in Motion Planning

Abstract

Swarm robots have been used successfully in many studies to solve complex tasks. The common task of swarm robots depends on the communication between them. In this study, differently, swarm robots were used in the motion planning study. With the help of swarm robots, a path was found that would allow the main mission robot to travel the shortest distance from the starting point to the end point without hitting the obstacles. This study was named Traffic Police Algorithm (TPA). According to the algorithm, robotic individuals belonging to the swarm are provided to spread in a certain order within the boundaries of the environment almost everywhere in the configuration space. The swarm robot members with this random propagation pattern are positioned as close to each other as far as communication distance. If there is no member closest to the target point, the members move randomly at a predetermined distance. When a robot sees the target point, it transmits the distance and orientation angle by notifying other neighboring robots nearby. All robots transmit distance and orientation information to neighboring robots that they can see, and this information is finally transmitted to the main task robot at the starting point. The main task robot at the starting point found the shortest distance using the Dijkstra algorithm, one of the search methods, to find the shortest path among the nodes transmitted to it. The developed algorithm was initially tested in a virtual environment and its implementation will be done in future studies. 

Keywords

• Swarm robots
• Motion planning
• Mobil robots

Sürü Robotların Hareket Planlamada Kullanılması

Öz

Sürü robotlar, karmaşık görevleri icra edebilen, tekil robotlara göre daha basit yapıda ve birlikte hareket kabiliyetine sahip robotlardır. Birden fazla robotun aynı görevin bir parçasını icra edebilmesi ilkesine dayanan bir yaklaşımdır. Günümüzde artan bir şekilde, birçok farklı alanda sürü robot uygulamaları üzerine çalışılmaktadır. Sürü robotlar özellikle doğadaki canlıların hayatlarını devam ettirmek için gösterdiği dayanışmayı örnek alır. Sürünün ortak bir görevi yerine getirmesi aralarındaki iletişime bağlıdır. Bununla birlikte karşılaştıkları sorunları, kendi başlarına çözmeleri gerekmektedir. Robotikte nihai hedeflerden birisi otonom robotlar yapmaktır. Böyle robotlar üst düzey görevleri kabul edecekler ve görevlerini insan müdahalesi olmadan yerine getireceklerdir. Günlük hayatta, yapılması gereken görevlerde insan faktörünün dezavantajlarını azaltmak, işlem süresini kısaltmak, zor, karmaşık işlemlerin üstesinden gelmek veya iş güvenliğini sağlamak için insan müdahalesi olmadan hareket eden akıllı robot çalışmaları kaçınılmaz olmuştur. Hareket planlama çalışması, robotun engellere çarpmadan hareket edebileceği ve başlangıç pozisyonundan bitiş noktasına doğru en kısa mesafede seyahatini sağlayacak bir yolu arama gayretidir. Özellikle karanlık ve girilmesi zor alanlarda(deprem yıkıntıları, mağaralar, yer altı yapıları… gibi) sürü robotların, arama kurtarma veya operatör görevini icra eden ana robota, gideceği yolu bulmada yardımcı olması yapılacak görevi hızlandıracaktır. Bu amaçla detayı bilinmeyen bir ortama bırakılan sürü robot üyelerinin gidilecek hedef noktayı bulmaları üzerine bir çalışma yapılmıştır. Bu çalışmaya Trafik Polisi Algoritması(TPA) ismi verilmiştir. Sürüye ait robot üyelerin yapılandırma alanının hemen her yerinde ortamın sınırları içerisine yayılmaları sağlanmıştır. Bu rasgele yayılım düzenine sahip sürü robot üyeleri birbiriyle haberleşme mesafesi kadar yakına konumlanmaktadır. Hedef noktaya en yakın üye yoksa üyeler önceden belirlenen kadar mesafe, rastgele hareket edecektir. Hedef noktayı gören robot yakınındaki diğer robotlara bildirimde bulunarak komşu robotlara mesafe ve yönelim açısı parametrelerini iletecektir. Tüm robotlar komşu robotlara mesafe ve yönelim bilgisini aktararak bu bilgiler sonunda başlangıç noktasındaki ana görev robotuna yakın sürü robot üyeleri tarafından ana görev robotuna iletecek ve bu robot kendisine iletilen düğümler arasında arama yöntemlerinden Dijkstra algoritması yardımıyla en kısa mesafeyi bulması sağlanarak hedef noktaya yönlendirilmiştir.

Anahtar Kelimeler

• Sürü robotlar
• Hareket planlama
• Mobil robotlar

References

1. Bertram Raphael. (2012). IEEE Global History Network. Institute of Electrical and Electronics Engineers.
2. Brambilla, M., Ferrante, E., Birattari, M., & Dorigo, M. (2013). Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1), 1–41. https://doi.org/10.1007/s11721-012-0075-2.
3. Dijkstra's algorithm. 30 Haziran 2020 tarihinde https://en.wikipedia.org/wiki/Dijkstra's_algorithm adresinden alındı.
4. F. Aurenhammer. (1991). ‘‘Voronoi diagrams—A survey of a fundamental geometric data structure’’. ACM Comput. Surv., vol. 23, no. 3, pp. 345–405. https://doi.org/10.1145/116873.116880.
5. Philip L. Frana & Thomas J. Misa. (August 2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM. 53 (8): 41–47. https://doi.org/10.1145/1787234.1787249.
6. J. Kennedy, R. Eberhart. (1995). "Particle swarm optimization," Proceedings of ICNN'95 - International Conference on Neural Networks, Perth, WA, Australia, 1995, pp. 1942-1948 vol.4. https://doi.org/10.1109/ICNN.1995.488968.
7. Jaradat M. A., Garibeh M. H., Feilat E. A. (2012). “Autonomous mobile robot dynamic motion planning using hybrid fuzzy potential field” Springer-Verlag Soft Comput 16:153–164. https://doi.org/10.1007/s00500-011-0742-z.
8. J.C. Latombe. (1991). Robot Motion Planning. Kluwer Academic Publishers. https://doi.org/10.1007/978-1-4615-4022-9.

9. J.C. Latombe. (1999). Motion Planning: A Journey of Robots Molecules Digital Actors and Other Artifacts, The International Journal of Robotics Research 30: 846-894. https://doi.org/10.1177/02783649922067753.
10. Kavraki, L. E., P. Svestka, J-C. Latombe, ve M. Overmars. (1996). "Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces", IEEE Transactions on Robotics and Automation, vol. 12, issue 4, no. 4, pp. 566-580. https://doi.org/10.1109/70.508439.
11. Khatib, O. (1986). Real-Time Obstacle Avoidance for Manipulators and Mobile Robots. The International Journal of Robotics Research, 5(1), 90–98. https://doi.org/10.1177/027836498600500106.
12. LaValle, S. M., & Kuffner, J. J. (2001). Randomized Kinodynamic Planning. The International Journal of Robotics Research, 20(5), 378–400. https://doi.org/10.1177/02783640122067453.
13. Lozano Perez T. ve Wesley M.A. (1979). An Algorithm for Planning Collision Free Paths Among Polyhedral Obstacles, Comm. ACM 22(10):560-570. https://doi.org/10.1145/359156.359164.
14. Motion Planning. 30 Haziran 2020 tarihinde https://en.wikipedia.org/wiki/Motion_planning adresinden alındı.
15. Shlyakhov, N. E., Vatamaniuk, I. V, & Ronzhin, A. L. (2017). Survey of Methods and Algorithms of Robot Swarm Aggregation. Journal of Physics: Conference Series, 803. https://doi.org/10.1088/1742-6596/803/1/012146.
16. Soysal, O., & Sahin, E. (2005). Probabilistic aggregation strategies in swarm robotic systems. Içinde Proceedings 2005 IEEE Swarm Intelligence Symposium, 2005. SIS 2005. (ss. 325–332). IEEE. https://doi.org/10.1109/SIS.2005.1501639.
17. Steven M. LaValle. (2006). Planning Algorithms. Cambridge University Press. https://doi.org/10.1017/CBO9780511546877.
18. Yıldırım Ş, Yaşar E. (2015). "An algorithm of avoiding obstacles with intelligent objects". Recent Innovations in Mechatronics (RIiM) Vol. 2. No. 1-2. https://doi.org/10.17667/riim.2015.1-2/14.
19. Yıldırım Ş, Yaşar E. (2015) Development of an obstacle-avoidance algorithm for snake-like robots, Measurement Journal, 68-73. https://doi.org/10.1016/j.measurement.2015.04.021.
20. What Is an Object? 30 Haziran 2020 tarihinde https://docs.oracle.com/javase/tutorial/java/concepts/object.html adresinden alındı.