AO* and Penalty Based Algorithms for the Canadian Traveler Problem
Kanadalı Gezgin Problemi İçin AO* ve Ceza Tabanlı Algoritmalar
- Tez No: 413243
- Danışmanlar: DOÇ. DR. VURAL AKSAKALLI
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: İstanbul Şehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri ve Sistemler Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 65
Özet
Kanadalı Gezgin Problemi (KGP), stokastik graflarda, bazı kenarların belli bir olasılığa göre kapalı veya açık olabildiği ve bu kenarların ancak komşu noktalarının ziyaret edilmesi suretiyle geçilebilirliklerinin tespit edilebildiği, zorlu bir güzergah planlama problemidir. Bu problemde hedef, belirli bir başlangıç ve bitiş noktası arasındaki en kısa beklenen gezinme uzunluğunu veren gezinme planını bulmaktır. Bu tezin organizasyonu şu şekildedir: Birinci bölümde, CTP ve SOSP'nin formülasyonları ve bu problemleri konu alan geniş bir literatür taraması sunulacaktır. İkinci bölümde, mevcut AO* arama algoritmasına, KGP'nin problem yapısından faydalan- maya olanak tanıyacak iyileştirmeler yapılarak elde ettiğimiz, MDP tabanlı bir optimal algoritma tanıtılacaktır. Bu yeni algoritma, CAO*, önbelleklemeli AO* (AO* with caching) olarak adlandırılmıştır. CAO*, daha önce ziyaret edilmiş durumların her seferinde yeniden genişletilmesinin önüne geçen önbellekleme mekanizması ve durum-uzayını dinamik olarak budamaya olanak tanıyan kabul edilebilir alt sınırlar kullanması olmak üzere iki önemli özelliğe sahiptir. CAO* polinom zamanlı degildir, ancak bu özellikleri sayesinde orta ölçekli problemler için optimal sonuçlar bulmada çözüm süresini ciddi ölçüde kısaltmaktadır. Son olarak, bu bölümde gerçek, mayınlı deniz alanı verileri kullanılarak hazırlanmış bilgisayar simülasyonları sunulacaktır. Üçüncü bölümde, KGP için, çevrimiçi uygulanabilir, basit, fakat hızlı ve etkili bir ceza-tabanlı sezgisel tanıtılacaktır. Ardından bu sezgiselin optimale çok yakın çözümler verdiğini gösteren bilgisayar simülasyonları sunulacaktır. KGP'nin suboptimal çözümünde bir diğer etkili yöntem olan, örnekleme tabanlı algoritmaların, KGP için yüksek kaliteli çözümler ürettiğini gösteren bir çalışma literatürde mevcuttur. Son bölümde, bu iki algoritmik çatının Delaunay ve grid graflar üzerinde, bir adet ceza-tabanlı ve dört adet örnekleme tabanlı algoritma kullanılarak bilgisayar simülasyonları üzerinde karşılaştırması yapılacaktır. Karşılaştırmalarımızda ceza ta- banlı algoritmamızın, hem çözüm hızı hem de çözüm kalitesi açısından rollout tabanlı algoritmalara üstünlük sağlamış olması, ceza tabanlı algoritmaların, KGP'nin suboptimal çözümünde hızlı ve efektif bir aday olabileceğini göstermektedir.
Özet (Çeviri)
The Canadian Traveler Problem (CTP) is a challenging path planning problem on stochastic graphs where some edges are blocked with certain probabilities and status of edges can be disambiguated only upon reaching an end vertex. The goal is to devise a traversal policy that results in the shortest expected traversal length between a given starting vertex and a termination vertex. The organization of this thesis is as follows: In the first chapter we define CTP and its variant SOSP and present an extensive literature review related to these problems. In the second chapter, we introduce an optimal algorithm for the problem, based on an MDP formulation which is a new improvement on AO* search that takes advantage of the special problem structure in CTP. The new algorithm is called CAO*, which stands for AO* with Caching. CAO* uses a caching mechanism and makes use of admissible upper bounds for dynamic state-space pruning. CAO* is not polynomial-time, but it can dramatically shorten the execution time needed to find an exact solution for moderately sized instances. We present computational experiments on a realistic variant of the problem involving an actual maritime minefield data set. In the third chapter, we introduce a simple, yet fast and effective penalty-based heuristic for CTP that can be used in an online fashion. We present computational experiments involving real-world and synthetic data that suggest our algorithm finds near-optimal policies in very short execution times. Another efficient method for sub-optimally solving CTP, rollout-based algorithms, have also been shown to provide high quality policies for CTP. In the final chapter, we com- pare the two algorithmic frameworks via computational experiments involving Delaunay and grid graphs using one specific penalty-based algorithm and four rollout-based algorithms. Our results indicate that the penalty-based algorithm executes several orders of magnitude faster than rollout-based ones while also providing better policies, suggesting that penalty-based algorithms stand as a prominent candidate for fast and efficient sub-optimal solution of CTP.
Benzer Tezler
- Yerel olmayan plastisitede varlık ve teklik teoremleri
Existence and uniqueness theorems in nonlocal plasticity
REHA ARTAN
- OTA/AO 23C3 distal radius kırığı olan hastalarda kırık hatları ve parçalanma bölgelerinin haritalanması
Fracture lines and comminution zones in OTA/AO type 23C3 distal radius fractures: The Distal Radius Map
ABDULHAMİT MİSİR
Tıpta Uzmanlık
Türkçe
2016
Ortopedi ve TravmatolojiSağlık BakanlığıOrtopedi ve Travmatoloji Ana Bilim Dalı
DOÇ. DR. KAHRAMAN ÖZTÜRK
- Soliter böbrekli ratlarda parsiyel nefrektomi sırasında renal arter ven klemplemenin ve sadece renal arter klemplemenin etkilerinin biyokimyasal ve histopatolojik düzeyde karşılaştırılması
Biochemical and histopathological comparison of the effects of renal artery vein clamping and renal artery clamping only during partial nephrectomy in rats with solitary kidney
TUNAHAN ATEŞ
- Siklotrifosfazen halkası içeren bazı polimerik yapıların sentezi ve uygulamaları
Synthesis and applications of some polymeric structures including cyclotriphosphazene ring
ALPER ÖNDER
- Alev geciktirici katkı maddelerinin kauçuk malzemede mekanik ve yanma özelliklerine etkisinin incelenmesi
An investigation of flame retardants in rubber materilas on their mechanical and flammibility properties
MESUT DEMİRTAŞ
Yüksek Lisans
Türkçe
2012
Polimer Bilim ve TeknolojisiKarabük ÜniversitesiMetal Eğitimi Ana Bilim Dalı
DOÇ. DR. MUSTAFA ACARER
PROF. DR. ŞENNUR CANDAN