Kısmi Olarak Gözlemlenebilir Markov Karar Süreci (POMDP)

Kısmi olarak gözlemlenebilir Markov karar süreci bir belirsizlik ortamıdır. Robotlar üzerlerinde bulunan sensörler ile etrafı algılarlar. Robot sensörler ile aldığı verileri yorumlayarak kendisine verilen görevi yerine getirmeye çalışır. Görevi yerine getirirken yaptığı her hareketten sonra yeniden algılama yaparak hedefin yerini yeniden belirlemiş olur. Yani bir futbol oyununda top rakip oyuncudayken diğer oyuncunun topa doğru hamle yaparken attığı her adım sonrası yeniden algılama yapmalıdır çünkü oyuncunun hedefi gidip o topa hamle etmesi ama hedef hareketli olduğu için her an yeri değişebiliyor ve bunun içinde oyuncu topa hamle yaparken attığı her adım sonrası yeniden algılama yapmalıdır ve hedefin yerini yeniden belirleyerek hedefe ulaşmaya çalışır.

Kismi olarak gözlemlenebilir Markov karar süreci MDP`nin özel bir şeklidir. Bu POMDP modelinin MDP`den farkı karar vericinin içinde bulunduğu mevcut durumu tam olarak gözlemliyemiyor olmasıdır. Yani karar verici MDP`de geçtiği yeni durumun ne olduğunu önceden belirlemiş ve geçtiği yeni durumun ne olduğunu bilmektedir ama POMDP bir belirsizlik modelidir. POMDP`de ise geçtiği yeni durum ne olduğunu tam olarak bilemez. Sadece geçebileceği tüm muhtemel durumların olasılıklarını bilir. Bir eylem seçip diğer bir düşünülen duruma geçtiğinde, her geçtiği durum için bir gözlem elde ediyor olasıdır. Böylelikle her eylem sonunda hedef odaklı değil de geçtiği her durumda hedefe yönelik yeni gözlemler yaparak daha kesin sonuçlarla hedefe ulaşma yöntemidir. Örneğin, 3 durumlu bir modelde, karar verici, S1 durumunda iken seçtiği a1 eyleminden sonra hangi durumda olduğunu kesin olarak bilemez, sadece şu anda bulunduğu durumun S1,S2 ve S3 olma olasılıklarını bilir. İşte bu olasılıkların hepsi karar vericinin içinde “düşünülen durumlar (belief states)” kavramını oluşturur. Kısaca POMDP`de “düşünülen durumlar” kavramı kullanılacaktır. POMDP her zaman bir eylem seçip diğer bir düşünülen duruma geçtiğinde bir yeni gözlem elde ediyor olmasıdır. Her durumda elde ettiği yeni gözlemler bir sonraki adımda, karar vericinin düşünülen durumlarındaki olasılıkları etkileyecektir. Yapılan bu gözlemler, karar vericinin bir sonraki adımda geçeceği durumla ilgili bilgileri verir.

Değer Yenileme

POMDP değer yenilenmesinde en önemli nokta, hesaplanan değer fonksiyonlarının her zaman parçalı, doğrusal ve konveks olmasıdır. Smallwood ve Sondik (1973), Bellman operatörü kullanarak, sonlu ufuklu problemler için, her adımda değer fonksiyonunun, parçalı, doğrusal ve konveks olma özelliğini koruduğunu ispatlamışlardır. Sonsuz ufuklu problemler için ise, konveks olup parçalı ve doğrusal olmayabileceğini göstermişlerdir. Yine de bu, parçalı, doğrusal konveks bir fonksiyona yaklaştırılabilir. şekil 2.8(a)‟da iki durumlu bir POMDP için, bir doğrusal değer fonksiyonu, şekil 2.8(b)‟de ise, bir problem için tüm planlar göz önüne alınarak oluşturulmuş, parçalı, doğrusal konveks değer fonksiyonu gösterilmiştir.

şekil 2.8(b)‟ deki kırmızı ile çizilmiş olan, &3 planının değerini gösteren vektör, parçalı, doğrusal, konveks fonksiyonun bir parçası değildir. Çünkü diğer tüm vektörler tarafından bastırılmıştır. Bu tip baskın olmayan vektörlerin göz önüne alınmasına gerek yoktur. Bu tip vektörlerin elenmesinde “budama (pruning)” yöntemi kullanılır.

Sezgisel Aramalı Değer Yenileme

Yaklaşık POMDP planlama problemlerinde genellikle amaç, ele alınan planın değeri, yani beklenen ortalama uzun dönem ödülü ile optimal planın değeri arasındaki farkın enküçüklenmesidir.
HSVI (heuristic search value iteration) sezgisel aramayı parçalı, doğrusal, konveks değer fonksiyonu gösterimi ile birleştiren bir yaklaşık POMDP çözüm algoritmasıdır. Sezgisellikten kasıt, modelin çözümü kolaylaştırılırken optimal değerinden fedakarlık yapılmış olmasıdır. Yani sezgisel algoritmalar, optimal çözümler vermek yerine, optimale yakınsayan çözümler sunmaktadır. Sezgisel aramalı değer yenileme, geleneksel değer yenilenme algoritmalarındaki gibi değer üzerinde değil, değerin alt ve üst sınırlarında güncellemeler yapar.
HSVI`in iki algoritması vardır. Bir tanesi kısaca şu şekilde özetlenebilir;
Algoritma 1: ƃ = HSVI(ε)
HSVI, regret(ƃ, ) ≤ ε olacak şekilde planlar ele alır.
1. ilk sınırlar, yani oluşturulur.
2. width( ( )) ≤ ε olduğu sürece explore( ,ε,0) algoritması çağırılır.
3. İstenilen kesinlik değerine ulaşıldığında, alt sınır değeri ile ifade edilen mevcut plan ƃ optimale yakınsayan plandır.