Distributed area partitioning for multi-robot coverage

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, BİLGİSAYAR MÜHENDİSLİĞİ ANABİLİM DALI, Türkiye

Tezin Onay Tarihi: 2022

Tezin Dili: İngilizce

Öğrenci: BURAK HOCAOĞLU

Danışman: EROL ŞAHİN

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu tez çalışması bilinen iki boyutlu bir ortamda sürü robotlarında dağıtık alan paylaşımı problemine odaklanmaktadır. Tarama alanı paylaşımı problemi, ilgili bir bölgenin belirli bir sayıda parçalara ayrılmasını ve bu parçaların bir görev tanımına ya da bedel fonksiyonuna göre işlemenin minimum eforla gerçekleşmesini ele alır. Bu doğrultuda, problem, ajan pozisyonlarına bağlı olan bir dağıtık optimizasyon problemi formatında tanımlanacaktır. Ana hedef genel iş yükünü eşit miktarda paylaşmaktır. Genel iş yükü, her bir ajanın bölgedeki diğer noktalara olan uzaklığıyla doğru orantılıdır. Aynı zamanda da, bu ajanları paylaşımın optimum olduğu pozisyonlara doğru bir rotada yönlendiren yerel bir kontrol mekanizmasının yardımıyla paylaşılır. Ajan pozisyonları, bu konfigürasyona ulaştığı zaman ilgili bölgeyi işlemek için harcanacak toplam eforun minimum olduğu bir şekilde parçalar. Spesifik olarak Lloyd Algoritması kullanılarak temel yaklaşımın Merkezi Voronoi Teselasyonu (CVT) olduğu durum incelenecektir. Lloyd Algoritması ajanların dağıtıldığı konveks dış sınırları olan bölgelerde basit bir fikir sağlamaktadır, fakat genel bir konkav problem karşısında güvenilirlik sağlayamaz. Bu aşamada CVT kullanırken hesaba katılmayan dinamikleri yakalamak ve konkav problemlerde stabil yakınsama sağlamak için Lloyd Algoritmasına buluşsal yöntemler eklenecektir ve yakınsama davraınşı Jeodezik Voronoi Teselasyonuna (GVT) benzeyecektir. Görev fonkiyonu ve kontrol mekanizması da iş yükünün eşit paylaşımı için güncellenecektir. Daha sonra, ajanların, buluşsal yöntemlerin gidişatı ayarladığı, varmaları gereken ara hedefleri veren farklı merkezilik metrikleri ile analizler yapılacaktır. Bu merkezlik metrikleri ajanların lokal iş yükünün hesabında ve bunların optimizasyonunda yeni dinamikler ekleyecektir. Bu çalışma sunulan yaklaşımların kalitatif ve kantitatif sonuçlarını sağlamaktadır. Deneyler, Lloyd Algoritmasının temel halinde başarısız olduğu konkav iki boyutlu alanlarda yapılmıştır.