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 Hopkins University
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Eğitimde Ölçme ve Değerlendirme Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 114
Ö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
- Handshake protocols for energy harvesting communications
Enerji hasadı iletişimi için el sıkışma protokolleri
ONUR TATAR
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MUTLU KOCA
PROF. DR. MUSTAFA HAKAN DELİÇ
- Farklı kuyruk yönetim algoritmaları için tıkanıklık kontrol protokollerinin karşılaştırılması
Comparison of congestion control protocols for different queue management algorithms
ABRAR KHALID SHUKRI ALSHAREEF
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SERKAN ÖZTÜRK
- Girişimsel anjiyografide optimum doz ölçüm yöntemlerinin görüntü kalitesine bağlı olarak geliştirilmesi
Development of optimum dose measurement techniques related to image quality in interventional angiography
TURAN OLĞAR
Doktora
Türkçe
2004
Fizik ve Fizik MühendisliğiAnkara ÜniversitesiFizik Mühendisliği Ana Bilim Dalı
PROF.DR. DOĞAN BOR