Stochastic Path Planning in the Presence of Disambiguation and Neutralization Capabilities

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği (İngilizce) Anabilim Dalı, Türkiye

Tezin Onay Tarihi: 2019

Tezin Dili: İngilizce

Öğrenci: SERKAN YILDIRIM

Asıl Danışman (Eş Danışmanlı Tezler İçin): Ali Fuat Alkaya

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

Özet:

The Canadian Traveler Problem (CTP) and the Obstacle Neutralization Problem (ONP) are two well-studied graph-theoretic path-planning problems in the literature and both problems have been shown to be computationally intractable. The most important stage in this research is proposing a new probabilistic graph theoretic path-planning problem in the simultaneous presence of disambiguation and neutralization capabilities. This appears to be the first of its kind in the literature despite the close and inherent relationship between CTP and ONP. This new problem is named as the Canadian Traveler Problem with Neutralizations (CTPN). An optimal algorithm, CAON*, is proposed to solve the CTPN exactly. Computational experiments are provided on Delaunay graphs to assess the relative performance of this algorithm in comparison to the well-known value iteration and AO* algorithms. The relative utility and importance of the disambiguation and neutralization capabilities are investigated. In another stage, heuristics are proposed to solve CTPN. The exact algorithm proposed to solve CTPN cannot give results for the large instances of the problem. Therefore, heuristics are designed to run in faster execution times with admissible results. These heuristics and the exact algorithm are compared in terms of performance and quality in the experiments part of this stage. In the last stage, Disambiguation Points Sampling (DPS) heuristic is developed to solve discrete Stochastic Obstacle Scene Problem (D-SOSP). CAO* is a fast exact algorithm due to its opponents which solves D-SOSP optimally. However, for the large problem instances, it does not give results because of the huge state space. DPS heuristic is developed to solve the D-SOSP with CAO* algorithm in reasonable execution times with promising results.