Distributed area partitioning for multi-robot coverage
Çoklu-robot taramada dağıtık alan paylaşımı
- Tez No: 732764
- Danışmanlar: DOÇ. DR. EROL ŞAHİN, DR. ÖĞR. ÜYESİ HAKAN YILDIZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 68
Ö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.
Özet (Çeviri)
This thesis focuses on the distributed coverage area partitioning problem in a robotic swarm deployed over a known, two-dimensional environment. The goal is to split a region of interest into a number of subregions such that the amount of effort required to cover each subregion is approximately equal with respect to an objective function. Towards this end, the problem is defined as a distributed optimization problem, where the decision varibles are the locations of robots. Then, the proposed solution approach is described as a control mechanism driving each robot to better positions. At the end, robot positions will converge to a configuration where the total effort to process their subregion is minimal. Specifically, first, Lloyds Algorithm is deployed on the base approach to workload partitioning by converging to a Centroidal Voronoi Tesselation (CVT). Lloyds Algorithm provides a basic idea for convex problems where the deployment region has convex boundaries, but fails to provide reliability when used in a non-convex region. At this point, heuristics are added to reinforce the capabilities of Lloyds Algorithm to capture the dynamics missed when using CVT and to enable stable convergence in non-convex problems, converting the behaviour to converging to a Geodesic Voronoi Tesselation (GVT). Also, the model as the objective function and the control mechanism is revised for equitable workload partititoning. After that, various analyses are conducted with different centrality metrics whose results give the actual target locations that agents need to arrive, while heuristics refine how each agent arrives. These centrality metrics add new dynamics to how local workloads of each agent is defined, as well as optimizing them. This work provides qualitative and quantitative results of the proposed approaches. The experiments are done in non-convex two-dimensional environments where Lloyds Algorithm fails in its base form.
Benzer Tezler
- Novel data partitioning and scheduling schemes for dynamic federated vehicular cloud
Dinamik federe araç bulutu için yeni bir görev yükü paylaşımı ve iş planlaması şemaları
WISEBORN MANFE DANQUAH
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. DENİZ TURGAY ALTILAR
- Uydu verileri ile İstanbul Boğazı ve Haliç'de su kirliliğinin makro düzeyde belirlenmesi
Intrepretation at macro level as pollution of water resources of remotely sensed data of Bosphorus and golden horn estuary by an unsupervised and supervised classification method
H.GONCA COŞKUN
- Dağıtılmış nesneye dayalı sistemler için dağıtılmış bileşik nesne modeli
Distributed composite object model for distributed object based system
GÜRAY YILMAZ
Doktora
Türkçe
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. TAKUHİ NADİA ERDOĞAN
- Service discovery oriented clustering for mobile and adhoc networks
Anlık kablosuz ağlarda servis keşfi temelli kümeleme
GÜLŞAH BULUT
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Bölümü
DR. CEVAT ŞENER