AN EFFECTIVE PATH PLANNING ALGORITHM FOR SWARM OF ROBOTS IN AN UN-KNOWN ENVIRONMENT
Date
2022-01-25
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In many circumstances, several mobile robots —independent agents— team up to
achieve goals that are hard or impossible for an individual robot. These mobile
robots cooperate to perform any particular task, complexity of this cooperation is
correlated with the swarm size. Each individual robot is to interact with the local
environment using sensors. The primary concern for the swarm is to define and
follow a safe route from initial to target location. To achieve this task, many
algorithms exist in the literature, namely, Neural Network, Genetic Algorithms,
Bacterial Foraging Optimization, Ant Colony Optimization, Artificial Potential Field
etc. Among these, Bacterial Foraging Optimization (BFO) algorithm has attracted the
attention of many scientists due to its effectiveness of finding the destination with the
consideration of all known obstacles in the work space ensuring safety. Furthermore,
it discovers and always follows the determined path correctly. BFO is a
straightforward but strong bioinspired method of optimization using the analogy of
swarming principles and social behavior in nature.
The BFO successfully searches for an optimal path from start to goal point in the
presence of obstacles over a flat surface map. However, the algorithm suffers from
getting stuck in local minima whenever non-convex obstacles are encountered. In
case of any of these robots from the swarm getting stuck is considered as the failure
of the whole task.
This research proposes an improved version of BFO algorithm that can effectively
avoid obstacles, both of convex and non-convex nature. The proposed algorithm
helps the robot to recover from local minima by covering a certain distance in an
opposite direction to the obstacle. The algorithm will start generating virtual
obstacles to generate a safe path when facing acute angle. This information is then
passed onto other robots, so that they can also avoid local minima.
To test the effectiveness of the proposed algorithm, a comparison is made against the
existing BFO algorithm. The performance of both algorithms is tested in an unknown
dynamic and static environments. Through results, it is witnessed that the proposed
approach successfully recovers from the local minima, whereas, BFO gets stuck.
Description
BİLİNMEYEN ORTAMLARDA ROBOT SÜRÜLERİ İÇİN ALGORİTMA PLANLAMADA ETKİN BİR YOL
ÖZ: Birçok durumda birkaç mobil robot —bağımsız ajan— tek bir robot için gerçekleştirilmesi zor veya imkânsız hedefleri elde etmek amacıyla ekip halinde bir araya gelebilirler. Bu mobil robotlar belli bir görevi yerine getirmek için iş birliği yapabilirler, bu, sürünün büyüklüğüyle tam bir karşılıklı ilişki halindedir. Tek tek her robot sensörlerini kullanarak yerel ortamla karşılıklı olarak etkileşir. Sürü açısından birincil endişe başlangıçtan hedef yere kadar güvenli bir yolun tanımlanması ve izlenmesidir. Literatürde bu hedefin gerçekleştirilmesiyle ilgili Neural Network (Sinir Ağları), Genetic Algorithms (Genetik Algoritmalar), Bacterial Foraging Optimization (Bakteriyel Besin Arama Optimizasyonu), Ant Colony Optimization (Karınca Kolonisi Optimizasyonu), Artificial Potential Field (Yapay Potansiyel Alan), v.b. gibi pek çok algoritma mevcuttur. Bunlar arasında Bacterial Foraging Optimization (BFO) algoritması çalışma ortamında bilinen tüm engelleri göz önüne alarak güvenliği ve hedefin bulunmasını sağlamaktaki etkinliği nedeniyle pek çok bilimcinin dikkatini çekmektedir. Ayrıca, belirlenen yolu keşfeder ve doğru olarak izler. BFO kümeleşme prensiplerini ve doğadaki sosyal davranışlar analojisini kullanan, ilhamını biyolojiden alan doğrudan yaklaşımlı ama güçlü bir optimizasyon yöntemidir. BFO yassı bir yüzey haritası üzerinde engellerin varlığında başlangıçtan hedef noktaya kadar optimal yolu başarıyla araştırır. Ancak bu algoritma, konveks olmayan engellerin işe karışması durumunda yerel asgari şartlara sıkışmak gibi bir zayıflığa sahiptir. Sürünün robotlarından herhangi birinin sıkışıp kalması durumu görevinin tamamının başarısızlığı olarak görülmektedir. Bu araştırma BFO algoritmasının hem konveks olan hem de olmayan niteliklerdeki engellerden başarıyla kaçınılmasını sağlayan iyileştirilmiş bir versiyonunu önermektedir. Önerilen algoritma engele zıt yöndeki belli bir mesafeyi kapsayarak robotun yerel asgari değerlerden kurtulmasına yardım eder. Sert bir açıyla karşılaşıldığında algoritma güvenli bir yol oluşturmak için görsel engeller oluşturmaya başlar. Daha sonra bu bilgi diğer robotlara aktarılarak onların da yerel minimumlardan kaçınmaları sağlanır. Önerilen algoritmanın etkinliğinin test edilmesi için mevcut BFO algoritmasıyla bir karşılaştırma yapılmıştır. Her iki algoritmanın performansı bilinmeyen dinamik ve statik ortamlarda test edilmiştir. Sonuçlara göre, önerilen algoritmanın yerel minimumlardan başarıyla kurtulduğu ve BFO‘nun sıkışıp kaldığı gözlenmiştir.
ÖZ: Birçok durumda birkaç mobil robot —bağımsız ajan— tek bir robot için gerçekleştirilmesi zor veya imkânsız hedefleri elde etmek amacıyla ekip halinde bir araya gelebilirler. Bu mobil robotlar belli bir görevi yerine getirmek için iş birliği yapabilirler, bu, sürünün büyüklüğüyle tam bir karşılıklı ilişki halindedir. Tek tek her robot sensörlerini kullanarak yerel ortamla karşılıklı olarak etkileşir. Sürü açısından birincil endişe başlangıçtan hedef yere kadar güvenli bir yolun tanımlanması ve izlenmesidir. Literatürde bu hedefin gerçekleştirilmesiyle ilgili Neural Network (Sinir Ağları), Genetic Algorithms (Genetik Algoritmalar), Bacterial Foraging Optimization (Bakteriyel Besin Arama Optimizasyonu), Ant Colony Optimization (Karınca Kolonisi Optimizasyonu), Artificial Potential Field (Yapay Potansiyel Alan), v.b. gibi pek çok algoritma mevcuttur. Bunlar arasında Bacterial Foraging Optimization (BFO) algoritması çalışma ortamında bilinen tüm engelleri göz önüne alarak güvenliği ve hedefin bulunmasını sağlamaktaki etkinliği nedeniyle pek çok bilimcinin dikkatini çekmektedir. Ayrıca, belirlenen yolu keşfeder ve doğru olarak izler. BFO kümeleşme prensiplerini ve doğadaki sosyal davranışlar analojisini kullanan, ilhamını biyolojiden alan doğrudan yaklaşımlı ama güçlü bir optimizasyon yöntemidir. BFO yassı bir yüzey haritası üzerinde engellerin varlığında başlangıçtan hedef noktaya kadar optimal yolu başarıyla araştırır. Ancak bu algoritma, konveks olmayan engellerin işe karışması durumunda yerel asgari şartlara sıkışmak gibi bir zayıflığa sahiptir. Sürünün robotlarından herhangi birinin sıkışıp kalması durumu görevinin tamamının başarısızlığı olarak görülmektedir. Bu araştırma BFO algoritmasının hem konveks olan hem de olmayan niteliklerdeki engellerden başarıyla kaçınılmasını sağlayan iyileştirilmiş bir versiyonunu önermektedir. Önerilen algoritma engele zıt yöndeki belli bir mesafeyi kapsayarak robotun yerel asgari değerlerden kurtulmasına yardım eder. Sert bir açıyla karşılaşıldığında algoritma güvenli bir yol oluşturmak için görsel engeller oluşturmaya başlar. Daha sonra bu bilgi diğer robotlara aktarılarak onların da yerel minimumlardan kaçınmaları sağlanır. Önerilen algoritmanın etkinliğinin test edilmesi için mevcut BFO algoritmasıyla bir karşılaştırma yapılmıştır. Her iki algoritmanın performansı bilinmeyen dinamik ve statik ortamlarda test edilmiştir. Sonuçlara göre, önerilen algoritmanın yerel minimumlardan başarıyla kurtulduğu ve BFO‘nun sıkışıp kaldığı gözlenmiştir.