Protocols for stochastic shortest path problems with dynamic learning
Başlık çevirisi mevcut değil.
- Tez No: 400340
- Danışmanlar: PROF. DONNİELL E. FİSHKİND, PROF. CAREY E. PRİEBE
- Tez Türü: Doktora
- Konular: Eğitim ve Öğretim, Education and Training
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2007
- Dil: İngilizce
- Üniversite: Johns Hopkıns Unıversıty
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Eğitimde Ölçme ve Değerlendirme Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Özet yok.
Özet (Çeviri)
The research problem considered in this dissertation, in its most broad setting, isa stochastic shortest path problem in the presence of a dynamic learning capability(SDL). Specifically, a spatial arrangement of possible-obstacles needs to be traversedas swiftly as possible, and the status of the obstacles may be disambiguated (at acost) en route. The central question is to find a protocol that decides what and whereto disambiguate so as to minimize the expected length of the traversal. No efficientlycomputable optimal protocol is known and many similar problems have been provenintractable.Chapter 1 defines SDL in continuous and discrete settings, and introduces the RandomDisambiguation Paths Problem (RDP), a continuous variant of SDL whereinthe possible-obstacles are disc-shaped regions in the plane. For any RDP instance,the continuous plane can be approximated by a graph (a lattice), giving rise to theDiscrete RDP Problem (DRDP).Chapter 2 casts SDL as a Markov Decision Process and develops the correspondingBellman equation. Introduced in this chapter is a new improvement on the well-knownAO Algorithm, called the BAO Algorithm, which employs stronger pruning techniquesand substantially shortens the running time needed to find an exact solutionto relatively small DRDP instances. The chapter also presents a Partially ObservableMarkov Decision Process (POMDP) formulation of RDP.Chapter 3 discusses visibility graphs and introduces the tangent arc graph data structure(TAG). TAG is a new data structure comprised of the topological superimpositionof all of the visibility graphs generated by a collection of all subsets of disc-shapedobstacles. Although there are exponentially many such subsets, TAG is polynomiallysized.The chapter then points out that the well-known A Algorithm with a slightlystronger admissibility requirement on the heuristic function is equivalent to Dijkstra?sAlgorithm under a change of variable.Chapter 4 introduces the simulated risk disambiguation protocol (SR)?a suboptimalbut, effective and efficiently computable algorithm for RDP and DRDP. This protocolinitially assumes that all discs are riskily traversable. Then, a chosen ?undesirabilityfunction? is used (for each such possible traversal) to combine length and risk into asingle measure of traversal undesirability. A shortest traversal in this undesirabilitysense is what the DM traverses until the first ambiguous disc is encountered, at whichpoint a disambiguation is performed and the problem data is updated accordingly.This procedure is iteratively repeated until arrival at the destination.In Chapter 5, another suboptimal, but very efficiently computable protocol is proposedfor RDP and DRDP, called the continually reactivated (CR) disambiguationprotocol. The CR protocol is defined as the optimal protocol in an altered RDP settingwherein the discs are continually reactivated, and this CR protocol is efficientlycomputed in the RDP setting through the use of TAG. The CR protocol is thenproved to be optimal for parallel graphs in the discrete SDL setting, and this theoremis extended to yield optimal protocols for a broader class of SDL problems where theDM?s choice is just between parallel avenues under fixed policies within the avenues.Chapter 6 presents summary, conclusions, and directions for future research.
Benzer Tezler
- Path planning with hybrid use of artificial intelligence algorithms in autonomous mobile vehicles
Otonom mobil araçlarda yapay zeka algoritmalarının hibrit kullanımı ile rota planlaması
AHMET AKTAŞ
Yüksek Lisans
İngilizce
2022
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. İLKER MURAT KOÇ
- Wavelength routing algorithms far optical networks
Optik ağlarda yönlendirme algoritmaları
DEMETER GÖKIŞIK
Yüksek Lisans
İngilizce
1998
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SEMİH BİLGEN
- Konut bölgelerinde parsel düzeni uygulamasının kent topraklarının rasyonel kullanımı çerçevesinde mimari açıdan değerlendirilmesi
An Architeet's Criticism of the Currently Practised method of plot formation in residential areas from the point of View of rational utilization of urban deatories
SUZAN ESİRGEN
Yüksek Lisans
Türkçe
1986
Şehircilik ve Bölge PlanlamaGazi ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
DOÇ. DR. UMUR ERKMAN
- Implementation of IBM binary synchronous communication protocol on burroughs large systems
IBM ikili eşzamanlı veri iletişim protokolünün burroughs büyük boy sistemlerinde gerçekleştirimi
SONER ÖNDER