Tez No	İndirme	Tez Künye	Durumu
312062		Evolutionary algorithms for solving DEC-POMDP problems / MO-KGMKS problemlerinin çözümünde evrimsel algoritmalar Yazar:BARIŞ EKER Danışman: PROF. DR. HÜSEYİN LEVENT AKIN Yer Bilgisi: Boğaziçi Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2012 131 s.
Merkezi Olmayan Kısmen Gözlemlenebilir Markov Karar Süreci (MO-KGMKS)modeli, kısmen gözlemlenebilir ortamlarda çoklu etmen planlama problemini adreslemektedir.Modelin NEXP-complete kompleksliğe sahip olmasından dolayı, sadece küçük boyutluproblemler optimal bir şekilde çözülebilir. Bu sebepten dolayı, birçok araştırmacıdaha büyük boyutlu problemler için en iyiye yakın çözüm üretebilecek yaklaşık çözümyordamları üzerine yoğunlaşmıştır. Bununla birlikte, şimdiye kadar geliştirilen yaklaşıkçözüm yordamları bile büyük boyutlu problemleri ancak az sayıda adım için çözebilmektedir.Bunun bir nedeni etmen stratejilerini temsil ederken ve strateji uzayını tararkenkiüssel hafıza gereksinimidir. Bu tezde sonlu adımlı MO-KGMKS problemlerini yaklaşıkolarak çözmek için dört yeni yaklaşım sunuyoruz. ?Ilk yaklaşım, MAP, MO-KGMKS problemleriniKGMKS problemi olarak modelleme ve daha sonrasında verimli bir KGMKSçözümcüsü ile çözme temellidir. Diğer yaklaşımların hepsi, yani ES-BV, ES-OH ve GAFSC,evrimsel yordamların uygulanması temeline dayanmaktadır. ES-BV, MAP yöntemindeolduğu gibi inanç vektörlerini kullanır ve strateji vektörlerini evrimsel stratejileri (ES)kullanarak bulmaya çalışır. ES-OH yaklaşımı gözlem tarihçesini kullanmayı, karar vermekiçin bunu bir sinir ağına girdi yapmayı ve sinir ağlarını eğitmek için ES kullanmayıönerir. GA-FSC yordamı ise stratejileri temsil etmek için sonlu durum kontrolcülerinikullanır ve genetik yordamları kullanarak en iyi stratejiyi arar. Bütün yordamlar en bilinenMO-KGMKS problemlerinde test edilmiştir. Sonuçlarımızı bu konudaki en ileritekniklerle ve birbirleriyle karşılaştırdık. MAP haricinde bu çalışmadan geliştirilen yordamlarınvarolan en iyi yordamlarla karşılaştırılabilir bir performansa sahip olduğunu veGA-FSC kullanılması durumunda problemler için çözüm adım sayısının artırıldığını gösterdik.
The Decentralized Partially Observable Markov Decision Process (DEC-POMDP)model addresses the multiagent planning problem in partially observable environments.Due to its NEXP-complete complexity, only small size problems can be solved exactly.For this reason, many researchers concentrate on approximate solution algorithms that canhandle more complex cases and produce near optimal solutions. However, even the approximatesolution techniques developed so far can handle large size problems only for smallhorizons. One reason for this is the exponential memory requirements while representingthe agent policies and searching the policy space. In this thesis, we propose four newapproaches to solve finite horizon DEC-POMDP problems approximately. The first approach,called MAP, is based on modeling DEC-POMDP problems as a POMDP problemand then solving using an efficient POMDP solver. The other approaches, namely ES-BV,ES-OH and GA-FSC, are all based on the application of evolutionary algorithms. The ESBVmakes use of belief vectors as in the case of MAP and tries to find policy vectors usingevolution strategies (ES). The ES-OH proposes to use the observation history and input itinto a neural network to make a decision and it uses ES to train the neural networks. TheGA-FSC algorithm makes use of finite state controllers for representing the policies andsearch for the optimal policy using genetic algorithms (GA). All algorithms were tested onthe major well-known DEC-POMDP problems. We compared our results with the currentstate of the art methods and we also compared our algorithms with each other. We showedthat all the algorithms developed in this study, except MAP, have comparable performanceto that of the existing top algorithms and in the case of the GA-FSC, the solution horizonfor the problems are extended at least an order of magnitude.