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: Endüstri ve Endüstri Mühendisliği, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Industrial and Industrial Engineering, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: En kısa yol problemi, Markov karar süreçleri, Shortest path problem, Markov decision processes
- Yıl: 2015
- Dil: İngilizce
- Üniversite: İstanbul Şehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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
- Contact modeling as applied to the dynamic simulation of legged robots
Bacaklı robotların dinamik simülasyonları için temas modeli
ORHAN AYİT
Yüksek Lisans
İngilizce
2015
Mekatronik MühendisliğiSabancı ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. KEMALETTİN ERBATUR
- Elektrik motoru seçim kriterleri ve kontrol organına bir limiter konulmuş motorun optimal parametrelerinin simpleks metodu ile tayini
Başlık çevirisi yok
VOLKAN ÇAKMAKÇI
- Toplu taşıma hatlarının optimizasyonu için bir model önerisi: Sivas örneği
A model proposal for the optimization of public transportation lines: The case of Sivas
İSMAİL ÖZÇELİK
Yüksek Lisans
Türkçe
2026
Ulaşımİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. HÜSEYİN ONUR TEZCAN
- IEEE 1149.1 standardı kullanarak test edilebilir lojik devre tasarımı
Testable lojik circit design by using IEEE 1149.1 standard
A.BETÜL TUNCER
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. AHMET DERVİŞOĞLU
- Ayrık zamanlı sistemlerde belli zaman özelliklerini sağlayan optimum PID kontrolör tasarımı
PID design for discrete time control system to satisfy certain time domain specification
UFUKTAN YAVUZ
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiPROF.DR. M. KEMAL SARIOĞLU