Multi-agent coverage control with adaptation to performance variations and imprecise localization

Abstract

In this thesis, an adaptive collaboration approach for a multi-agent system consisting of nonholonomic wheeled mobile robots is proposed. The positions of the agents are not known precisely but their locations are known to be within uncertainty circles. For the collaboration among the robots, the workspace partitioning algorithm is chosen as Guaranteed Power Voronoi Diagram (GPVD or GPD) which not only takes the localization uncertainty into account but also is capable of changing the regions of the generator points with respect to corresponding weight parameters. Also, the assumption is that the actuation capabilities of the robots are different from each other. The agents do not know those parameters related to their actuation performances beforehand. The contribution of the thesis is that the performance parameters of the agents are learned online by the proposed adaptive estimator algorithm and Hopfield Neural Network (HNN) estimator under localization uncertainty. The proposed algorithm is based on the coverage control which performs collaboration among the robots by assigning the regions from the workspace according to their actuation performances automatically. The definition of the actuation performances is different capabilities of the agents. The examples of strong actuation performances may include powerful motors and favorable terrain while wheel slip and weak motors can be counted as examples for the weak actuator performances. The proposed multi-agent collaborative coverage algorithm learns the performance parameters of the robots by using two approaches proposed in the thesis. The first approach is based on an adaptive estimator with a non-holonomic estimation model. The second method uses an HNN estimator. The theoretical proof, analysis and verification of the aforementioned methods are given in the related sections. After estimating the performance parameters, the weights are calculated using a neighbor based weight estimation algorithm. The weight variables are utilized in the GPD algorithm so that the workspace is partitioned according to the performance parameters of the agents in a guaranteed sense. At the end, the agents take regions from the workspace according to their actuation performances and achieve the optimal collaborative coverage so that the agents with strong actuators take larger regions from the environment than the agents with poor actuators. Thus, the collaborative coverage algorithm enables the robots to deploy themselves to an optimal configuration which minimizes the total coverage cost by taking imprecise localization into account. Moreover, a multi-agent coverage collaboration method with an energy-efficient optimal coverage control law and Hopfield networks is proposed in the related section. By using the algorithm a trade-off between coverage time and energy consumption among agents can be done. Meanwhile, the collaboration is achieved according to the actuation performances of the agents. The theoretical results are verified with MATLAB and ROS/Gazebo simulations and experiments that show the efficiency of the algorithm. The ROS implementation of the algorithm is explained. The experimental results are given in the related section.

Bu tezde çok etmenli sistemler için uyarlamalı bir işbirliği (kolaborasyon) yöntemi önerilmiştir. Etmenler holonomik olmayan tekerlekli robotlar olarak ele alınmıştır. Robotların konumları tam olarak bilinmemekte, bir belirsizlik yarıçapı içerisinde oldukları varsayılmaktadır. Voronoi tabanlı koordinasyon ve işbirliği yöntemleri literatürde özellikle son zamanlarda yaygın olarak karşılaşılmakta olan problemlerdir. Voronoi tabanlı kapsama kontrolü, haritayı optimal şekilde, bir konumsal optimizasyon fonksiyonuna göre birden çok etmenin olduğu durumda kapsamayı amaçlar. Etmenlerin haritayı bölgelendirmesi için Voronoi diyagramları kullanılır. Bir yoğunluk fonksiyonu haritadaki her nokta için bilgi dağılımını verecek şekilde tanımlanır. Etmenler Voronoi bölgelendirmesi ve yoğunluk fonksiyonunu kullanarak optimizasyonun çözümüne ulaşırlar. Her bir etmen için bulunan optimal noktalar, bir kontrol kuralı kullanılarak etmenleri görevi yerine getirecek şekilde optimal çözüme ulaştırır. Literatürde bir çok çeşidi bulunan Voronoi diyagramlarından en basiti olan klasik Voronoi diyagramı oluşturucu noktaların konumlarında belirsizlik olmadığını ve bölgelerin ağırlıklandırılmadığını varsayar. Sweepline algoritması klasik Voronoi diyagramının çiziminde kullanılan ve iyi sonuç veren bir algoritmadır. Eklemeli ağırlıklandırmalı Voronoi diyagramları (AWVD), çarpma ağırlıklandırmalı Voronoi diyagramları (MWVD) ve güç Voronoi diyagramları (PVD ya da PD) Voronoi diyagramlarının çeşitlerindendir. Bu algoritmaların ortak özelliği ağırlıklandırmalı olmalarıdır, bu da oluşturucu noktaların birer ağırlıkları olduğu anlamına gelir. Bu ağırlıklar kullanılarak bölgelerin büyüklükleri değiştirilebilmektedir. Özellikle, güç Voronoi diyagramları, ayırıcı eğrilerinin (bisector curve) klasik Voronoi diyagramlarında olduğu gibi doğru olması nedeniyle çok etmenli robotik yöntemlerinde çokça kullanılmaktadır. Bir diğer tür olan ve bu tezde çokça kullanılacak olan Guaranteed Voronoi diyagramları (GVD), oluşturucu noktaların konumlarının belli birer nokta değil, konumlarında belirsizlik olan noktalar olduğunu varsayar. Bu şekilde konum belirsizliği bir çember ya da elips ile modellenebilir. Bu da oluşan Guaranteed Voronoi bölgelerinin dışında belirsiz ve hiçbir etmene ait olmayan bölgelerin oluşmasına neden olur. Ayrıca, GVD'lerin ayırıcı eğrileri birer hiperboldür. Eğer, literatürde önerildiği gibi GVD'lerin uzaklık fonksiyonları güç uzaklık fonksiyonu olarak tanımlanırsa, bu diyagramlar Guaranteed güç diyagramları (GPD ya da GPVD) adını alır ve güç diyagramlarında olduğu gibi oluşturucu noktaların ağırlık değerleri değiştirilerek noktaların bölgelerinin büyüklükleri değiştirilebilir ve aynı zamanda konumlama belirsizlikleri göz önüne alınabilir. Bu da çok etmenli robotlu sistemlerde, bir parametreye ya da değişkene göre etmene ilişkin bölgenin büyüklüğünün değiştirilebilmesini olanaklı kılar. Bu tezde de, literatürde de yapıldığı gibi bu ağırlıklar otomatik olarak uyarlamalı bir algoritma ile değiştirilerek etmenlerin çalışma alanlarının eyleyici performansı gibi kestirilen parametrelere göre atanmasını sağlayan yöntemler kullanılmıştır. Bu şekilde robotlar arası işbirliği yapılması sağlanmakta ve eyleyici performansı yüksek robotların daha geniş çalışma alanına sahip olması mümkün hale getirilmektedir. Önerilen algoritmanın önemli parçalarından bir diğeri ise kestirim algoritmasıdır. Hareketli bir sistemin model kullanılarak parametrelerinin kestirilmesi literatürde uygulaması olan bir yöntemdir. Bu iş için uyarlamalı doğrusal olmayan yöntem, temel alınan bir yayında önerilmiştir. Alternatif olarak bu tezde önerilen Hopfield Yapay Sinir Ağları ile her bir etmenin performans parametreleri kestirilebilmektedir. Yapay Sinir Ağlarını temel alan başka yöntemler ile ilgili olarak, örneğin sınıflandırma yapan ağlar, literatürde bahsedildiği üzere doğruluk ile ilgili sıkıntılar yaşanabilmektedir. Holonomik ve holonomik olmayan modeller ile yapılan kestirimler ile ilgili sonuçlar tez içerisinde verilmiştir. Holonomik modelde robotun noktasal dinamiğe sahip olduğu varsayılmakta ve kontrol kuralı özel bir dönüşüm ile holonomik olmayan robotların kontrol işaretlerini üretebilmektedir. Holonomik olmayan model ile yapılan kestirimde ise, hem kontrol kuralı hem de kestiricinin denklemleri holonomik olmayan tek tekerlekli bir aracın kinematik modeli olarak ele alınmaktadır. Algoritmaya ilişkin bir diğer parça olan olan kontrol kuralı, holonomik olmayan araçlar için özel olarak türetilmiş bir kontrol kuralı ve holonomik dinamikler için kullanılan bir kontrol kuralının ürettiği kontrol işaretlerinin holonomik olmayan robotlara özel bir dönüşüm ile dönüştürülmesine dayalı olmak üzere iki farklı yöntem olarak incelenmiştir. Her iki kontrol kuralının Lyapunov tabanlı ıspatı yapılmış ve asimptotik kararlılık incelenmiştir. Elde edilen sonuçlara göre konum ile ilgili hatalar ve kestirim hataları sıfıra ilk koşuldan bağımsız bir şekilde asimptotik olarak gitmektedir. Ayrıca etmenlere ilişkin uyarlama kuralı ile elde edilen ağırlıklar da kararlı kalmaktadır. Hopfield ağının asimptotik kararlılığı da Lyapunov tipi bir ıspat ile literatürde yapıldığı gibi incelenmiştir. Tezin ilk kısmında giriş bilgileri ve literatür taraması verilmiştir. İkinci kısım, çok etmenli sistemlerde Voronoi tabanlı kapsama kontrolü ile ilgili temelleri sunmaktadır. Voronoi diyagramları ve çeşitleri ile birlikte konumsal optimizasyon ile kapsama kontrolüne ilişkin bilgiler ve ıspatlar verilmiştir. Üçüncü kısım olan konum belirsizliği altında uyarlamalı kapsama kontrolü, önerilen bir çok etmenli koordinasyon algoritmasını açıklamaktadır. Bu algoritma, literatürde var olan uyarlamalı çok etmenli koordinasyon algoritmasını temel almakta ve GPD ile çalışma alanı bölgelendirmesini sağlamaktadır. Gradyan tabanlı bir kestirici kullanılarak, yoğunluk fonksiyonu kestirilmekte ve holonomik olmayan kontrol kuralı ile robotlar bulunan optimal noktalara ulaştırılmaktadır. Böylelikle algoritma, dışarıdan aldığı sensör bilgisini bir konsensus protokolü ve kestirici ile hesaplayarak etmenlerin otonom bir şekilde koordinasyon kontrolü yapmasını sağlamaktadır. Yine Lyapunov tipi bir ıspat ile teorik analiz yapılmış ve simülasyonlar ile elde edilen sonuçlar doğrulanmıştır. Dördüncü kısım, konum belirsizliği altında eyleyici performans değişimlerine göre uyarlamalı işbirliği yapan bir algoritmayı önermektedir. Bu algoritma, yoğunluk fonksiyonunun sabit olduğu durumda, otomatik olarak etmenlerin ağırlıklarını parametre kestirim vektörlerinden çıkararak, GPD ile bölgelendirme yapmakta ve performansı yüksek robotlara daha çok çalışma alanı, performansı düşük olanlara ise daha az çalışma alanı vermektedir. Bu şekilde enerji ve zaman açısından fayda sağlanabilmektedir. Lyapunov tipi bir ıspat ile uyarlamalı parametre kestirici, ağırlık kestirici ve holonomik olmayan kontrol kuralının global asimptotik kararlılığı ıspatlanmıştır. Elde edilen sonuçlar, simülasyon ile doğrulanmıştır. Beşinci kısımda ise, parametre kestiricisi olarak HNN kullanılmış ve temel alınan çalışmada olduğu gibi kestirim modeli olarak holonomik bir nokta dinamiği modeli seçilmiştir. Kontrol kuralı da holonomik bir kural olup, holonomik olmayan robotlar için özel bir dönüşüm kullanmaktadır. Bu şekilde holonomik olmayan robotların kontrol işaretleri elde edilmektedir. Lyapunov tipi bir ıspat ile HNN kestiricisi, ağırlık kestiricisi ve kontrol kuralının global asimptotik kararlı olduğu ıspatlanmış ve sonuçlar simülasyonlar ile doğrulanmıştır. Ayrıca, etmenlerden bir ya da birkaçının eyleyicilerinin bozulması ve tamamen hareketsiz kalması durumu için özel bir algoritma önerilmiştir. Bu algoritma, hareketsiz robotları tespit ederek bu robotlar ilişkin ağırlıkları otomatik olarak sıfıra getirmektedir . Altıncı kısımda enerji tüketimi ve kapsama zamanı arasında bir ayarlanabilir denge sağlayan, Hopfield ağlarına dayalı bir kestirici kullanan bir işbirlikçi kapsama kontrolü algoritması önerilmiştir. Lyapunov tipi bir ıspat ile kararlılık incelenmiştir ve global asimptotik kararlılık kanıtlanmıştır. Yedinci kısımda üçüncü, dördüncü, beşinci ve altıncı bölümlere ilişkin simülasyon sonuçları verilmiştir. Üçüncü bölümdeki algoritma için 5, 10 ve 15 robot ile simülasyon yapılmış, dördüncü bölüme ilişkin iki senaryo ile ilgili sonuçlar verilmiştir. Beşinci bölümde HNN ile yapılan 5, 10 ve 15 robotlu simülasyon sonuçları incelenmiş, Hopfield parametrelerinin değişimlerine göre sistemin tepkisi verilmiş ve son olarak hareketsiz etmenlere ilişkin simülasyon sonuçları sunulmuştur. Altıncı bölüme ilişkin simülasyon sonuçları 6 robot için verilmiştir. Sekizinci kısım olan uygulama kısmı, ROS/Gazebo simülasyon ortamında alınan sonuçları ve robotlar ile elde edilen deneysel sonuçları göstermektedir. C++ ile yazılan ROS düğümleri ve haberleşme diyagramları verilmiştir. Elde edilen sayısal sonuçlar ve deney sonuçları sunulmuştur.