Düşük hesaplama maliyetine sahip miyopik olmayan adaptif örnekleme ve çevresel izleme için Monte Carlo arama ağacı ve dallanma sınırlama yöntemlerinin uygulanması
Application of Monte Carlo tree search and branch-and-bound methods for non-myopic adaptive sampling and environmental monitoring with low computational cost
Yazar: PERİHAN KARAKÖSE
Danışman: DOÇ. DR. CAFER BAL ; DR. ÖĞR. ÜYESİ HARUN YETKİN
Fırat Üniversitesi / Fen Bilimleri Enstitüsü / Mekatronik Mühendisliği Ana Bilim Dalı / Mekanik Sistemler Bilim Dalı
Derece: Doktora, 2024
Konu: Mekatronik Mühendisliği = Mechatronics Engineering

Özet:
Çevresel izleme, doğal kaynakların sürdürülebilir kullanımı ve ekosistem sağlığının korunması açısından son derece önemlidir. Bu tez çalışmasında, su parametrelerinin gerçek zamanlı izlenmesi için Gauss süreçleri (GP) yöntemi kullanılarak gerçekleştirilen çalışmalar incelenmiştir. Tez, dört farklı aşamada ele alınmıştır. Birinci aşamada, eğitim verilerinin konumlarının, GP algoritmasının tahmin performansı üzerinde kritik bir rol oynadığı belirlenmiş ve sınırlı bir bütçeyle tüm alandan örnek toplamak için yeni bir güzergah planlama algoritması geliştirilmiştir. Bu algoritma, 10 farklı veri kümesinde test edilmiş ve literatürde mevcut diğer yaklaşımlarla karşılaştırıldığında üstün performans sergilediği görülmüştür. İkinci aşamada, yaygın olarak kullanılan ödül fonksiyonları (Entropi, UCB ve Seviye Belirleme) kullanılarak İlgi Alanı (ROI) bölgeleri tespit edilmiştir. Bu fonksiyonların keşif ve sömürü dengelerindeki başarıları değerlendirilmiştir. Entropi ödül fonksiyonunun, karmaşık olmayan veri setlerinde belirsizliği en aza indirerek ROI alanlarını daha hızlı keşfettiği belirlenmiştir. Seviye Belirleme ödül fonksiyonunun ise kompleks veri setlerinde daha başarılı sonuçlar verdiği görülmüştür. UCB ödül fonksiyonunun, yüksek belirsizlik içeren haritalarda daha başarılı olduğu ancak düşük belirsizlik durumlarında yerel maksimumlara takılma riskinin bulunduğu tespit edilmiştir. Üçüncü aşamada, gezgin satıcı problemini çözmek amacıyla Monte Carlo arama ağacı (MCTS) ve Dallan ve Sınırla Tekniği (BnB) bir araya getirilmiştir. BnB algoritmasında alt sınır, MCTS algoritması kullanılarak belirlenmiş, bu sayede optimal rota belirleme süresi önemli ölçüde kısaltılmıştır. Algoritma, gerçek bir veri seti üzerinde test edilmiş ve MCTS ile yorucu arama ve adaptif örnekleme algoritmaları (ESAS) karşısında üstün performans sergilemiştir. Bu algoritma, üç farklı hiperparametreye sahip veri setlerinde de başarılı sonuçlar elde etmiştir. Ayrıca, önerilen algoritma literatürdeki farklı alt sınır ve üst sınır belirleme yöntemleriyle karşılaştırılmıştır. Bu karşılaştırmalar sonucunda hesaplama süresinin en kısaya yakın çıkarken, doğruluğun da en düşük RMSE oranına yaklaştığı gözlemlenmiştir. Son aşamada ise MCTS-BnB algoritmasının hesaplama süresini azaltmak amacıyla seyrek temsili girişler kullanılmış ve bu girişler 5 farklı kümeleme yöntemi ile belirlenmiştir. K-Means kümeleme algoritması, en iyi kümeleme performansını göstererek hesaplama süresini önemli ölçüde azaltmıştır. Tez çalışmasının genel bulguları, Gauss süreçleri ve ödül fonksiyonları kullanılarak su parametrelerinin etkili bir şekilde gerçek zamanlı olarak izlenebileceğini göstermektedir. Ayrıca, MCTS ve BnB yöntemlerinin birleştirilmesi, güzergah planlamada önemli iyileştirmelere yol açarak çevresel izlemeye yönelik daha optimal çözümler sunabileceğini ortaya koymaktadır.

Abstract:
Environmental monitoring is of critical importance for the sustainable use of natural resources and the preservation of ecosystem health. This thesis examines studies conducted using Gaussian Processes (GP) methods for real-time monitoring of water parameters. The thesis is structured into four distinct phases. In the first phase, the importance of the locations of training data is emphasized. It has been determined that the locations of training data play a crucial role in the prediction performance of the GP algorithm. To address this, a new path planning algorithm was developed to collect samples from the entire area within a limited budget. This algorithm was tested on 10 different datasets and was found to outperform existing approaches in the literature. In the second phase, commonly used reward functions (Entropy, UCB, and Level Setting) were employed to identify Regions of Interest (ROI). The success of these functions in balancing exploration and exploitation was evaluated. It was found that the Entropy reward function minimized uncertainty more effectively in non-complex datasets, allowing for faster discovery of ROI areas. The Level Setting reward function yielded better results in more complex datasets, while the UCB reward function performed well in high-uncertainty maps but risked getting stuck in local maxima in low-uncertainty situations. The third phase involved combining the Monte Carlo Tree Search (MCTS) and Branch and Bound (BnB) techniques to solve the Traveling Salesman Problem. In the BnB algorithm, the lower bound was determined using the MCTS algorithm, significantly reducing the time required to identify the optimal route. The algorithm was tested on real datasets and demonstrated superior performance compared to MCTS and exhaustive search and adaptive sampling algorithms (ESAS). This algorithm was also successful across datasets with three different hyperparameters. Additionally, the proposed algorithm was compared with different lower and upper bound determination methods in the literature. The comparison revealed that the calculation time was close to the shortest while achieving an accuracy near the lowest RMSE rate. In the final phase, sparse representative inputs were used to reduce the computation time of the MCTS-BnB algorithm, with these inputs determined using five different clustering methods. The K-Means clustering algorithm showed the best clustering performance, significantly reducing the computation time. The overall findings of the thesis demonstrate that water parameters can be effectively monitored in real-time using Gaussian Processes and reward functions. Moreover, combining the MCTS and BnB methods leads to significant improvements in path planning, offering more optimal solutions for environmental monitoring.