Application of Monte Carlo tree search and branch-and-bound methods for non-myopic adaptive sampling and environmental monitoring with low computational cost

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.