Path planning for ships in the presence of obstacles


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2015

Tezin Dili: İngilizce

Öğrenci: DİNDAR ÖZ

Danışman: ALİ FUAT ALKAYA

Özet:

ENGELLİ ORTAMLARDA GEMİLER İÇİN YOL PLANLAMASI Deniz ticaret ve seyahat rotalarının artması ve global ticaretin konteyner gemiciliğine olan talebinin büyümesi deniz ulasımı ve demiratma sahası isletmeciliginin önemini kaydadeger oranda arttırdı. Çevresel kosullar altında yol bulma, dönüs kısıtlamaları altında yol bulma ve demir atma sahası planlaması gibi deniz ulasımında önemli rol oynayan bir çok sürecin verimli ve güvenli olarak gerçeklenmesinde bilgisayar biliminin sundugu çözümler etkili bir sekilde kullanılabilmektedir. Bu tez çalısmasında gemi ulasımında sıkça karsılasılan yol bulma ve planlama problemlerinden üçü için grafik teorisi ve optimizasyon yöntemleri kullanılarak birer modelleme ve çözüm gelistirildi. Bu problemler; etkisizlestirme problemi, dönüs kısıtları altında en kısa yol problemi ve demiratma sahası optimizasyonu problemidir. Etkisizlestirme problemi için optimum çözümü çogu zaman makul zamanda bulan, Kesin Ceza Arastırma Algoritması önerildi. Ikinci problem için, esnek açılarda harekete izin veren yeni bir ayrıklastırma modeli sunuldu. Klasik ızgara modelinin bir genellestirmesi olan bu modele Yogun Komsuluklu Izgara (LAG) adını verdik. Bu modeli kullanarak dönüs kısıtlamalı en kısa yol problemi için bir çözüm algoritması tasarladık ve algoritmamızı buzlu sularda gemi navigasyonu senaryosu ile gösterdik. Son olarak demiratma sahası planlaması problemini ele aldık. Demiratma sahası planlamasının güvenligini ölçmek için yeni metrikler önerdik. Ayrıca, kullanım ve güvenligi dikkate alan yeni bir demiratma sahası planlayıcısı önerdik. Bu planlayıcı ile güncel planlayıcılardan iki tanesine göre %98’e varan güvenlik performansı iyilesmesi gözlemledik. Demiratma sahalarının farklı derinlikli bölgelerini modelledik ve mevcut demiratma sahası planlayıcılarından birini olusturdugumuz modele uyarlayarak kullanım performansında kayda deger bir iyilesme gözlemledik. ABSTRACT PATH PLANNING FOR SHIPS IN THE PRESENCE OF OBSTACLES With the increasing number of trade and travel routes over sea and the growing demandof global commerce for containerships, maritime transportation and the operation of anchorage areas gained significant importance. In the safe and efficient management ofmany processes in seaborne shipping, such as path finding under various environmental conditions, path finding with turn constraints and anchorage planning, the means of computer science are being utilized substantially. In this thesis study, three well-known path finding and planning problems in ship navigation is modelled and solved using graph theory and optimization methods. The problems are namely; obstacle neutralization problem, shortest path problem with turn constraints and finally anchorage optimization problem. For the obstacle neutralization problem we proposed Exact Penalty Search Algorithm, that can find the optimum solution in reasonable time for most cases. As for the second problem, a new discretization model for flexible turn angles is presented. It is called Large Adjacency Grids (LAG), which is a generalization of classical lattice. Over LAG we designed an algorithm in order to solve turn constrained shortest path problem after which we demonstrated our algorithm on a ship navigation example in ice-covered waters. Finally we focused on anchorage planning problem. We presented novel metrics to capture safety performance of anchorage planning. Moreover we proposed a new anchorage planning strategy that takes both utilization and safety into account. Our planning strategy achieved upto 98% improvement in terms of safety over two of the recent algorithms. We also modeled nonuniform depth segments of anchorage areas and adapted one of the existing anchorage planning algorithms to our model by which we observed significant improvement in terms of area utilization.