Reinforcement Learning ile Optimal Yol Tespiti

Herkese Selam,

Bu yazıda Reinformcement Learning yöntemlerinden biri olan Q-Learning ile örnek bir harita üzerinden en optimum yolu bulan bir agent tasarımı yapacağım. Umarım farkındalık anlamında faydalı bir yazı olur.


Reinforcement Learning (RL),  bir ödülün en üst düzeye çıkarılması için, belirli bir durumda yapılması gereken optimum eylemleri bulma problemleri ile ilgilenen bir makine öğrenmesi tekniğidir.

Esinlendiği nokta davranış piskolojisi olan bu öğrenme tekniği genellikle şu şekilde anlatılır. Herhangi bir ortamda (environment) bulunan bir agent bu ortam içerisinde belirli hareketler yapar ve bu hareketler sonucunda ödüller kazanır (rewards).  Ana amaç toplamda kazanılacak ödülü maksimize etmek ve uzun erimde en fazla ödülü kazandıracak hareket serisini (optimal policy) öğrenmektir.

Reinforcement Learning’in en sık kullanıldığı uygulamaların başında oyunlar gelmektedir. Örneğin 90’lı yıllarda Tavla oyununda bir insanı yenen makine RL ile öğrenimini gerçekleştirmişti. Yine yakın zamanda Dünyanın en iyi GO oyuncusunu yenen makinede öğrenimini RL ile gerçekleştirmişti (Google DeepMind’s Alpha GO).  Bu uygulamalara ek olarak Robotik de, Kontrol’de,  Otonom Araçlarda ve buna benzer bir çok endüstriyel alanlarda da RL tekniğine sık bir şekilde başvurulmaktadır.

Reinforcement Learning derinliği olan detaylı bir konu olduğundan dolayı bu yazı içerisinde daha fazla bu tekniğin detayını anlatmayacağım ancak merak edenler aşağıdaki video’dan veya internet üzerinden aramalar yaparak örnek uygulamaları ve bu tekniğin teorisini öğrenmeye başlayabilirler.

Şimdi bu yazıya konu olacak örnek bir uygulama geliştirme işine geçebiliriz.

Q-Learning For Optimal Hiking

Elimizde şekildeki gibi bir harita var ve bu haritada başlangıç noktasından başlayarak bitiş noktasına en fazla toplam ödülü elde ederek nasıl ulaşabileceğim sorusunun cevabını arıyorum. Ancak bu haritada bir hücreden diğer hücreye geçerken kazanılan ödüller farklı durumlara göre değişkenlik gösteriyor. Haritadan da görüleceğe üzere düzlük ve tepe şeklinde hücreler mevcut bu hücreler arasındaki geçişlerin ödülleri ise aşağıdaki şekilde bize verilmekte.

Düzlük bir hücreden, düzlük bir hücreye geçişte(P-P): -1

Düzlük bir hücreden, tepe bir hücreye geçişte(P-H):-3

Tepe bir hücreden, düz bir hücreye geçişte(H-P): -1

Tepe bir hücreden, Tepe bir hücreye geçişte(H-H): -2

Herhangi bir hücreden, hedef hücreye geçişte: 10

Görüldüğü üzere, elimizde haritanın nasıl olduğu (environment) ve durumlar arasında geçiş yaparken ne kadarlık bir ödül kazandığımız bilgisi bulunuyor. Biz bu verilenleri kullanarak en optimum yolculuğu Q-Learning yöntemi ile öğrenmeye çalışacağız. Q-Learning’in temel mantığı, agent’ın ortam üzerinde yaşadığı deneyimleri kullanarak maksimum fayda ile yolculuğu nasıl bitirebileceğini bulmaktır. Bunun için agent’ın defalarca ortam üzerinde farklı hareketler yaparak ortamı en iyi şekilde öğrenmesi amaçlanmaktadır.

Şimdi yukarıdaki gibi verilen bir haritada kazanacağı ödülü maksimize ederek sonuca gidecek ve optimal yolu bulacak bir Reinforcement Learning kodu yazalım ve sonuçları gözlemleyelim.

Kodu MATLAB ile implemente edeceğiz.

İlk etapta çözmek istediğimiz haritayı ve gerekli tanımlamaları yapıyoruz.

%****************************************************
%Defining Maze Setup
goalmark = 4;
startmark = 2;
rewards = [-1 -2 -3 -1]; 


        %****************************************************
        %You can change maze whatever you want
        %We need 1 start and 1 stop state.
        maze =[  1 0 0 1 1
                 0 2 0 1 0
                 0 0 0 0 0
                 0 0 1 1 0
                 1 0 1 1 0
                 1 1 1 1 4]; 
        %****************************************************

actUp=3;
actDown=4;
actLeft=1;
actRight=2;
ACTIONS = [actLeft, actRight, actUp, actDown];

mazeSize = size(maze);
mazeRow = mazeSize(1);
mazeColumn = mazeSize(2);
%****************************************************

Şimdi ise durumlar arası kazanılacak ödül matrisini oluşturuyoruz.

%****************************************************
%Construct Reward Matrix
rewardMat =  zeros(mazeRow*mazeColumn,length(ACTIONS));
transitMat = zeros(mazeRow*mazeColumn,length(ACTIONS));
stateIterator=0;
rew = 0;
rewforGoal =10;
for i=1:mazeRow
    for j=1:mazeColumn
        stateIterator = (i-1)*mazeColumn+j;     % Defining Current State
        
        %****************************************************
        %Up
        if(i-1>=1)
            if(maze(i-1,j)==0 && maze(i,j)==0)  % plain plain
                rew = -1;
            end
            if(maze(i-1,j)==0 && maze(i,j)==1)  % hill plain
                rew = -1;
            end
            if(maze(i-1,j)==1 && maze(i,j)==0)  % plain hill
                rew = -3;
            end
            if(maze(i-1,j)==1 && maze(i,j)==1)  % hill-hill
                rew = -2;
            end
                        
            if maze(i-1,j)==goalmark
                rewardMat(stateIterator,actUp)= rewforGoal; 
            else
                rewardMat(stateIterator,actUp)= rew;
            end
            
            transitMat(stateIterator,actUp) = stateIterator-(abs(mazeColumn-j)+abs(1-j)+1);
        end
        
        %****************************************************
        %Down
        if(i+1<=mazeRow) if(maze(i+1,j)==0 && maze(i,j)==0) % plain plain rew = -1; end if(maze(i+1,j)==0 && maze(i,j)==1) % hill plain rew = -1; end if(maze(i+1,j)==1 && maze(i,j)==0) % plain hill rew = -3; end if(maze(i+1,j)==1 && maze(i,j)==1) % hill-hill rew = -2; end if maze(i+1,j)==goalmark rewardMat(stateIterator,actDown)= rewforGoal; %10 else rewardMat(stateIterator,actDown)= rew; end transitMat(stateIterator,actDown) = stateIterator+(abs(mazeColumn-j)+abs(1-j)+1); end %**************************************************** %Left if(j-1>0)
            if(maze(i,j-1)==0 && maze(i,j)==0) % plain plain
                rew = -1;
            end
            if(maze(i,j-1)==0 && maze(i,j)==1) % hill plain
                rew = -1;
            end
            if(maze(i,j-1)==1 && maze(i,j)==0) % plain hill
                rew = -3;
            end
            if(maze(i,j-1)==1 && maze(i,j)==1) % hill-hill
                rew = -2;
            end
            
            if maze(i,j-1)==goalmark
                rewardMat(stateIterator,actLeft)= rewforGoal;  %10
            else
                rewardMat(stateIterator,actLeft)= rew;
            end
                        
            transitMat(stateIterator,actLeft) = stateIterator-1;
        end
        
        %****************************************************
        %Right
        if(j+1<=mazeColumn)
            if(maze(i,j+1)==0 && maze(i,j)==0) % plain plain
                rew = -1;
            end
            if(maze(i,j+1)==0 && maze(i,j)==1) % hill plain
                rew = -1;
            end
            if(maze(i,j+1)==1 && maze(i,j)==0) % plain hill
                rew = -3;
            end
            if(maze(i,j+1)==1 && maze(i,j)==1) % hill-hill
                rew = -2;
            end
            
            
            if maze(i,j+1)==goalmark
                rewardMat(stateIterator,actRight)= rewforGoal;  %10
            else
                rewardMat(stateIterator,actRight)= rew;
            end
            
            transitMat(stateIterator,actRight) = stateIterator+1;
        end
        %****************************************************
    end
end

Sıra kod içerisinde kullanacağımız diğer parametreleri tanımlama kısmına geldi. Bu tanımları yapıyoruz.

%**************************************
%Finding Goal and Start states positions
[sx,sy] = find(maze==startmark);
startState = (sx-1)*mazeColumn+sy;

[gx,gy] = find(maze==goalmark);
goalState = (gx-1)*mazeColumn+gy;

%**************************************
%Initializing Parameteters
Q = transitMat*0; 
Q(goalState,1)= 10; 
gamma = 1;
alpha = 0.5;
randomProb = 0.25;
tx = sx;
ty = sy;
V = zeros(mazeColumn*mazeRow,1);
episode=30000;
stepSize=20;
rewforGoal =10;
%**************************************

Sırada öğrenmeyi gerçekleştirecek kısmı kodlamaya geldi (Q-Learning).

%**************************************
%Start Q Learning
for it=1:episode
    tx = sx;
    ty = sy;
    next=0;
    for step=1:stepSize
        next = 0;
        
        %*************************************
        %Defining Current Position and fing possible actions
        curr =  (tx-1)*mazeColumn+ty;
        actionOptions = Q(curr,:);
        %*************************************
        
        %*************************************
        % Finding Next Action with using random probability
        while next==0
            %choosing random action
            if rand < randomProb
                randAction = randperm(length(actionOptions));
                index = randAction(1);
            else
                [value, index] = max(actionOptions);
            end
            next = transitMat(curr, index);
        end
        %*************************************
        
        %*************************************
        % Get reward for current position
        rew = rewardMat(curr,index);
        %*************************************
        
        
        %*************************************
        % Q Learning Equation
        if(curr~=goalState)
            Q(curr,index) = Q(curr,index) + alpha*( (rew+gamma*max(Q(next,:))) - (Q(curr,index)));
        end
        %*************************************
        
        %*************************************
        % Finding Next Step Position
        sect = fix((next/mazeColumn));
        
        if sect == 0
            sect =1;
        end
        
        rest = mod(next,mazeColumn);
        
        if next==mazeColumn*mazeRow
            tx = sect;
            ty = mazeColumn;
        else
            if ty == 0
                tx = sect;
                ty = mazeColumn;
            else
                tx = sect+1;
                ty = rest;
            end                        
        end
        %*************************************
        
    end
end
%*****************************************

Şimdi ise yazdığımız algoritmayı görselleştirelim.

%****************PLOT*********************


%***********************************************
 % get the figure and axes handles
 hFig = gcf;
 hAx  = gca;
 % set the figure to full screen
 set(hFig,'units','normalized','outerposition',[0 0 1 1]);
%***********************************************
 
 
%***********************************************
%Plot V Values using Q Matrix
subplot(1,3,1);
V = max(Q,[],2);
V = reshape(V,mazeRow,mazeColumn);
%V(goalState) = 10;
imagesc(V); 
title('V Values');
hold on;
for i=1:mazeRow
    for j=1:mazeColumn
        cell = (i-1)*mazeColumn+j;
        content = sprintf('%2.2f',V(cell));
        labels = text(j-0.20,i, content); 
        set(labels);
    end
end
%***********************************************


%***********************************************
%Plot Q Values
subplot(1,3,2);
imagesc(maze);
title('Q Values');
hold on;
for i=1:mazeRow
    for j=1:mazeColumn
        cell = (i-1)*mazeColumn+j;
        
        label1 = text(j-0.15,i-0.21, sprintf('%2.2f',Q(cell,actUp))); 
        set(label1,'FontSize',8);

        label2 = text(j-0.15,i+0.22, sprintf('%2.2f',Q(cell,actDown))); 
        set(label2,'FontSize',8);
        
        label3 = text(j-0.40,i, sprintf('%2.2f',Q(cell,actLeft))); 
        set(label3,'FontSize',8);
        
        label4 = text(j+0.16,i, sprintf('%2.2f',Q(cell,actRight))); 
        set(label4,'FontSize',8);        
    end
end
%***********************************************


%***********************************************
%Plot Optimal Path
subplot(1,3,3);
imagesc(maze);
title('Optimal Path');
hold on;
curr = startState;
tx = sx;
ty = sy;
QPr = Q;
QPr(QPr==0)=-1000;
while curr~=goalState
    curr =  (tx-1)*mazeColumn+ty;
    
    if curr==startState
        labelN = text(ty-0.40,tx-0.4, sprintf('START'));
        set(labelN,'FontSize',15);
    elseif curr==goalState
        labelN = text(ty-0.35,tx, sprintf('GOAL'));
        set(labelN,'FontSize',15);
        continue;
    end
        
    actionOptions = QPr(curr,:);    
    [value, index] = max(actionOptions);        
    
    if index == actLeft
        labelN = text(ty-0.2,tx, sprintf('L'));
        set(labelN,'FontSize',25);
        ty = ty-1;
    end
    
    if index == actRight
        labelN = text(ty-0.2,tx, sprintf('R'));
        set(labelN,'FontSize',25);
        ty = ty+1;
    end
    
    if index == actUp
        labelN = text(ty-0.2,tx, sprintf('U'));
        set(labelN,'FontSize',25);
        tx = tx -1;
    end
    
    if index == actDown
        labelN = text(ty-0.2,tx, sprintf('D'));
        set(labelN,'FontSize',25);
        tx = tx +1;
    end
end
%***********************************************

Şimdi yazdığımız kodu deneyip test edelim.

İlk olarak aşağıdaki gibi bir harita veriyorum.
maze =[ 1 0 2 1 1
0 0 0 1 0
0 0 0 0 0
0 0 1 1 0
1 4 1 1 0
1 1 1 1 1];

0: Düzlük
1: Tepe
2: Başlangıç Noktası
4: Bitiş Noktası

Parametreler: Gamma:0.7- Alpha: 0.5 – Episode: 30000

Sonuç:

Çıktı olarak 3 farklı matrisimiz var. Bunlardan birincisi bulunan V değerlerini  İkincisi bulunan Q değerleri, üçüncüsü ise optimal path’in ne olduğunu gösteriyor.

 

Advertisements

About ... from Emrah METE

Bilgisayar Mühendisi
This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.