Optimal ship navigation and algorithms for stochastic obstacle scenes

Abstract

Bu tez araştırması iki farklı fakat alakalı bölümden oluşmaktadır. Birinci bölümde, optimal gemi navigasyon problemini göz önüne aldık. Bu problemde amaç, engellerin bulunduğu bir alanda emniyet mesafesi ve dönüş-yarıçapı kısıtı altında verilen iki koordinat arasında en kısa yolu bulmaktır. Bahsi geçen engeller enkaz, kaya formasyonları, küçük adalar, buz blokları, diğer gemiler ve hatta tüm kıyı şeridi olabilir. Gemi navigasyon problemi için 8-komşulu tamsayı örgü ayrıklaştırması üzerinde graf-teori tabanlı bir çözüm sunduk ve A* algoritmasından faydalandık. Sunduğumuz çözümde, dönüş-yarıçapı kısıtı için şu üç koşulu açıkça hesaba katılmıştır: (1) gemilerin iskele (sol) ve sancak (sağ) dönüş yarıçapları farklı olması, (2) dönüşlerde geminin hızının düşmesi, (3) dönüş yapmadan önce belirli bir mesafe aynı doğrultuda gitmesidir. üçüncü kısıt navigasyon alanının istenilen çözünürlükte ayrıklaştırmasına imkan tanır. Optimal (ayrık) yol belirlendikten sonra keskin dönüşleri, gerçek gemi dönüşlerine benzetmek için yumuşatma işlemi yaptık. Bu metodolojimizi 100.000 DWT ticari bir geminin buzlu denizlerdeki navigasyonu örneği üzerinde test ettik ve İstanbul Teknik üniversitesi'nde bulunan Tam Donanımlı Köprü-üstü (TDK) Simülatöründe konsept-ispatını sunduk.İkinci bölümde, stokastik engelli ortamlar problemini göz önüne aldık. Bu problemde bir ajan, olası-engellerin olduğu bir bölgede hedef bir konuma ulaşmak için yol almalıdır ve yolculuk esnasında olası-engellerin belirsizliği bir ücret karşılığında giderilebilir. Buradaki amaç, gidilen yolu en kısa yapacak şekilde hangi engelin neresinden belirsizlik gidermenin yapılacağını belirleyen bir algoritma bulmaktır. Bu problemin belirli politikalar altındaki paralel caddelerle kısıtlanmış durumu bağlamındaki graf-teori tabanlı versiyonu için polinom-zamanlı bir yöntem sunduk. Bunun yanında, problemin sürekli ortamlardaki versiyonu için sunulan algoritmaların nasıl ayrık ortamlara uyarlanacağını gösterdik. Bu kısımda, navigasyon kılavuzu olarak penaltı fonksiyonlarını kullanan algoritmaları kapsayacak şekilde genel bir çatı önerdik. Bu çatı içerisinde, çok kısa koşma süresinde optimala yakın değerler veren yeni bir algoritmayı tanıttık. Bu algoritmamızı, sentetik veri üzerinde olduğu gibi gerçek deniz mayın tarlası verisi üzerinde de hesaplamasal deneylerle test ettik.

This thesis is comprised of two different but related sections. In the first section, we consider the optimal ship navigation problem wherein the goal is to find the shortest path between two given coordinates in the presence of obstacles subject to safety distance and turn-radius constraints. These obstacles can be debris, rock formations, small islands, ice blocks, other ships, or even an entire coastline. We present a graph-theoretic solution on an appropriately-weighted directed graph representation of the navigation area obtained via 8-adjacency integer lattice discretization and utilization of the $A^{*}$ algorithm. We explicitly account for the following three conditions as part of the turn-radius constraints: (1) the ship's left and right turn radii are different, (2) ship's speed reduces while turning, and (3) the ship needs to navigate a certain minimum number of lattice edges along a straight line before making any turns. The last constraint ensures that the navigation area can be discretized at any desired resolution. We illustrate our methodology on an ice navigation example involving a 100,000 DWT merchant ship and present a proof-of-concept by simulating the ship's path in a full-mission ship handling simulator at Istanbul Technical University.In the second section, we consider the stochastic obstacle scene problem wherein an agentneeds to traverse a spatial arrangement of possible-obstacles, and the status of the obstacles may be disambiguated en route at a cost. The goal is to find an algorithm that decides what and where to disambiguate en route so that the expected length of the traversal is minimized. We present a polynomial-time method for a graph-theoretical version of the problem when the associated graph is restricted to parallel avenues with fixed policies within the avenues. We show how previously proposed algorithms for the continuous space version can be adapted to a discrete setting. We propose a generalized framework encompassing these algorithms that uses penalty functions to guide the navigation in realtime. Within this framework, we introduce a new algorithm that provides near-optimal results within very short execution times. Our algorithms are illustrated via computational experiments involving synthetic data as well as an actual naval minefield data set.