Application of Metaheuristic Search Algorithms for Path Planning of Smart Vehicles

Abstract

Navigating a smart vehicle in an environment, determined or unknown, requires the localization of such vehicle in that environment using GPS, cameras, vision, laser or ultrasonic sensors, motion planning of the vehicle in free configuration space of the environment, and its ability to deviate from obstacles. In planning a path from a start to a goal configuration, the aim is to obtain the shortest path in less time while avoiding obstacles. Metaheuristic algorithms have been extensively applied to achieve this; while it exploits the environment from an initial solution, it also explores it to find a possible feasible path. Researchers in robotics and automation field have investigated and analysed the performance of population-based algorithms like Genetic Algorithm (GA), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Firefly Algorithm (FA), and Cuckoo Search Algorithm (CSA) to obtain a feasible shortest path. This research work investigates the performance of metaheuristic search algorithms like GA, PSO, FA, and CSA for path planning on four different benchmark problem maps (40 x 40m large, 20 x 20m maze, 20 x 20m rockpile and 20 x 20m pothole) and makes a comparative analysis based on computational time and path length. Furthermore, three sampling methods i.e., Random, Latin hypercube and pseudo-uniform sampling were used. It is observed that all the algorithms were able to achieve the optimal, although CSA performed poorly on path distance using GA and PSO on the maze and pothole map respectively, its performance on other two maps was relatively better both on shortest distance and computational time, however, it is concluded that no single algorithm is universally the best-performing algorithm for all maps. All simulations were performed on MATLAB R2022b. Keywords: Metaheuristic Algorithms, Path Planning, Navigation, Mobile Robot, Smart VehicleAkıllı bir aracın belirli veya bilinmeyen bir ortamda yönlendirilmesi, GPS, kameralar, görüntü, lazer veya ultrasonik sensörler kullanılarak aracın o ortamdaki yerinin belirlenmesini, aracın ortamın serbest konfigürasyon alanında hareket planlamasının yapılmasını ve engellerden sapmak. Başlangıçtan hedef konfigürasyonuna kadar bir yol planlarken amaç, engellerden kaçınarak en kısa yolu daha kısa sürede elde etmektir. Metasezgisel algoritmalar, bunu başarmak için kapsamlı bir şekilde uygulanmıştır; çevreyi bir başlangıç çözümünden yararlanırken, aynı zamanda olası bir uygulanabilir yol bulmak için de araştırır. Robotik ve otomasyon alanındaki araştırmacılar, Genetik Algoritma (GA), Karınca Kolonisi Optimizasyonu (ACO), Parçacık Sürü Optimizasyonu (PSO), Ateşböceği Algoritması (FA) ve Cuckoo Arama Algoritması (CSA) gibi popülasyon tabanlı algoritmaların performansını araştırdı ve analiz etti uygun bir en kısa yol elde etmek için. Bu araştırma çalışması, GA, PSO, FA ve CSA gibi metasezgisel arama algoritmalarının dört farklı kıyaslama problem haritası (40 x 40m büyük, 20 x 20m labirent, 20 x 20m kaya yığını ve 20 x 20m çukur) üzerinde yol planlaması için performansını araştırıyor ve hesaplama süresine ve yol uzunluğuna dayalı olarak karşılaştırmalı bir analiz yapar. Ayrıca, üç örnekleme yöntemi, yani Rastgele, Latin hiperküp ve sözde tekdüze örnekleme kullanılmıştır. Tüm algoritmaların optimumu yakalayabildiği, CSA'nın sırasıyla labirent ve çukur haritasında GA ve PSO kullanarak yol mesafesinde düşük performans göstermesine rağmen, diğer iki haritadaki performansının hem en kısa mesafe hem de hesaplama süresinde nispeten daha iyi olduğu görülmüştür. ancak, tek bir algoritmanın tüm haritalar için evrensel olarak en iyi performans gösteren algoritma olmadığı sonucuna varılmıştır. Tüm simülasyonlar MATLAB R2022b üzerinde gerçekleştirilmiştir. Anahtar Kelimeler: Metasezgisel Algoritmalar, Yol Planlama, Navigasyon, Mobil Robot, Akıllı Araç