AO* and Penalty Based Algorithms for the Canadian Traveler Problem

Abstract

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.

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.