Path planning of autonomous mobile robots based on Voronoi diagram and ant colony optimization

Abstract

Path planning aims to enable autonomous robots to navigate safely and efficiently from a starting point to a target point in challenging and dynamic environments. Path planning in robotics is highly significant and still an ongoing subject of research. The increasing use of robots in various applications such as industrial automation, service robotics, and autonomous vehicles has brought forth the need for reliable and efficient path planning algorithms. The inherent capability of Voronoi diagrams to partition space based on proximity makes them an effective framework for research in path planning. Ant colony optimization, a bio-inspired optimization technique, is based on the foraging behavior of ants and is commonly employed to address the traveling salesman problem and various other combinatorial optimization problems. A hybrid method was adopted in this study by combining a Voronoi diagram and an ant colony algorithm. To create paths for the robot where it can stay as far away from obstacles as possible, a Voronoi diagram was utilized. Additionally, to find the shortest path from the starting point to the destination among these paths, ant colony optimization was employed. The main contribution of the study lies in the combination of the Voronoi diagram for obstacle avoidance and ant colony optimization for finding the optimal path. The combination of these techniques makes an effective contribution to robotic path planning by focusing on ensuring safety by avoiding obstacles while optimizing the shortest path. Experimental studies show that the hybrid method produces successful results for the desired purpose.

Keywords

• Path Planning
• Voronoi diagram
• Ant colony optimization
• Autonomous mobile robot

Otonom mobil robotların Voronoi diyagramı ve karınca kolonisi optimizasyonuna dayalı yol planlaması

Abstract

Yol planlama, zorlu ve dinamik ortamlarda otonom robotların başlangıç noktasından hedef noktasına güvenli ve verimli bir şekilde gitmesini sağlamayı amaçlamaktadır. Robotikte yol planlama oldukça önemlidir ve halen devam eden bir araştırma konusudur. Robotların endüstriyel otomasyon, servis robotiği ve otonom araçlar gibi çeşitli uygulamalarda kullanımının artması, güvenilir ve verimli yol planlama algoritmalarına olan ihtiyacı ortaya çıkarmıştır. Voronoi diyagramlarının uzayı yakınlığa dayalı olarak bölümlendirme konusundaki doğal yeteneği, onları yol planlama araştırmaları için etkili bir çerçeve haline getirmiştir. Biyo-ilhamlı bir optimizasyon tekniği olan karınca kolonisi optimizasyonu, karıncaların yiyecek arama davranışına dayanmakta ve genellikle gezici satıcı problemini ve diğer çeşitli kombinatoryal optimizasyon problemlerini çözmek için kullanılmaktadır. Bu çalışmada Voronoi diyagramı ile karınca kolonisi algoritmasının birleştirilmesiyle hibrit bir yöntem denenmiştir. Robotun engellerden mümkün olduğu kadar uzak durabileceği yollar oluşturmak için Voronoi diyagramı kullanılmıştır. Ayrıca bu yollar arasında başlangıç noktasından hedef noktasına en kısa yolu bulmak için karınca kolonisi optimizasyonundan yararlanılmıştır. Deneysel çalışmalar, Voronoi diyagramının engellerden uzakta oluşturduğu yollar arasında karınca kolonisi optimizasyonu kullanılarak en kısa yolun bulunabileceğini göstermektedir.

Keywords

• Yol planlama
• Voronoi diyagramı
• Karınca kolonisi optimizasyonu
• Otonom mobil robot

References

1. Dijkstra E W (1959) A note on two problems in connexion with graphs. Numerische Mathematik, 1(1): 269-271.
2. Tuncer A (2015) Performance Comparison of Genetic Algorithm and A* in Path Planning for Mobile Robots. International Journal of Advanced Computational Engineering and Networking, 3: 15-18.
3. Kavraki L E, Kolountzakis M N, & Latombe J C (1998) Analysis of probabilistic roadmaps for path planning. IEEE Transactions on Robotics and automation, 14(1): 166-171.
4. Kothari M & Postlethwaite I (2013) A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees. Journal of Intelligent & Robotic Systems: 71, 231-253.
5. Tuncer A., Yildirim M (2016) Design and implementation of a genetic algorithm IP core on an FPGA for path planning of mobile robots. Turkish Journal of Electrical Engineering and Computer Sciences 24(6): 5055-5067.
6. Miao C, Chen G, Yan C, & Wu Y (2021) Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering, 156: 107230.
7. 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.
8. Çavuş V, Tuncer A (2017) İnsansız Hava Araçları İçin Yapay Arı Kolonisi Algoritması Kullanarak Rota Planlama. Karaelmas Fen ve Mühendislik Dergisi 7(1): 259-265.

9. Candeloro M, Lekkas A M, Sørensen A J, & Fossen T I (2013) Continuous curvature path planning using voronoi diagrams and fermat's spirals. IFAC Proceedings Volumes, 46(33): 132-137.
10. Wei H X, Mao Q, Guan Y, & Li Y D (2017) A centroidal Voronoi tessellation based intelligent control algorithm for the self-assembly path planning of swarm robots. Expert Systems with Applications, 85: 261-269.
11. Liu Z, Gao L, Liu F, Liu D, & Han W (2022, July) Fusion of weighted Voronoi diagram and A* algorithm for mobile robot path planning. In 2022 2nd International Conference on Electrical Engineering and Mechatronics Technology (ICEEMT), IEEE, 403-406.
12. Ho S L, Lin J K, Chou K Y, & Chen Y P (2022, July) Voronoi Diagram based Collision-free A* Algorithm for Mobile Vehicle in Complex Dynamic Environment. In 2022 IEEE International Conference on Consumer Electronics-Taiwan, IEEE, 429-430.
13. Jiang L, Wang S, Meng J, Zhang X, Li G, & Xie Y (2019, July) A Fast Path Planning Method for Mobile Robot Based on Voronoi Diagram and Improved D Algorithm. In 2019 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), IEEE, 784-789.
14. Chi W, Ding Z, Wang J, Chen G, & Sun L (2021) A generalized Voronoi diagram-based efficient heuristic path planning method for RRTs in mobile robots. IEEE Transactions on Industrial Electronics, 69(5): 4926-4937.
15. Luo Q, Wang H, Zheng Y, & He J (2020) Research on path planning of mobile robot based on improved ant colony algorithm. Neural Computing and Applications, 32: 1555-1566.
16. Liu C, Wu L, Xiao W, Li G, Xu D, Guo J, & Li W (2023) An improved heuristic mechanism ant colony optimization algorithm for solving path planning. Knowledge-Based Systems, 271: 110540.
17. Wu L, Huang X, Cui J, Liu C, & Xiao W (2023) Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot. Expert Systems with Applications, 215: 119410.
18. Zong C, Yao X, & Fu X (2022) Path Planning of Mobile Robot based on Improved Ant Colony Algorithm, 2022 IEEE 10th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), Chongqing, China, 1106-1110.
19. Aurenhammer F (1991) Voronoi diagrams–a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3): 345-405.
20. Dorigo M, Birattari M, & Stutzle T (2006) Ant colony optimization. IEEE computational intelligence magazine, 1(4): 28-39.