2
$\begingroup$

I'm working on a q-learning project that involves a "robot" solving a maze, and there is a problem with how I update the Q values (every time the robot ends up switching between two squares instead of actually learning) but I'm not sure where: I am at my wits end. Any pointers are welcome, here is the minimal viable example (I really can't condense it much more).. Thanks!

from enum import Enum
import numpy as np
from random import randrange
import string
import random

class Direction(Enum):
    up=0
    down=1
    left=2
    right=3

stepsTaken=0
nbMaxSteps=500
Q = {}
gamma=0.95
strat=1
epsilon=0.99
maze=[]
penalty=0
#values of each movement
step=-1
stepTrap=-20
stepExit=500
stepWall=-100
#current position of the robot
position=[0, 0]

#funciton that checks if a certain place in the Q matrix is empty, returns 1 if it is
def currentQEmpty():
    global Q
    global position
    moves=[]
    if (position[0]!=0):
        moves.append(Direction.left)
    if (position[0]!=cols-1):
        moves.append(Direction.right)
    if (position[1]!=0):
        moves.append(Direction.down)
    if (position[1]!=rows-1):
        moves.append(Direction.up)
    for d in moves:
        if (Q.get((position[0],position[1],d),'A')=='A'):
            return 1
    return 0

#intialise the Q matrix
cols=10
rows=10
values=np.zeros((rows,cols))
for x in range(rows):
        for y in range(cols):
            for dir in Direction:
                Q[(x, y, dir)] = 0

#fills the Q matrix (replaces empty values only)
def QFill(moves):
    global maze
    global position
    global Q
    global step
    global stepTrap
    global stepWall
    global stepExit
    global gamma
    for d in moves:
        reward=0
        newpos=position
        if d==Direction.up:
            newpos=[position[0], position[1]+1]
        if d==Direction.down:
            newpos=[position[0], position[1]-1]
        if d==Direction.left:
            newpos=[position[0]-1, position[1]]
        if d==Direction.right:
            newpos=[position[0]+1, position[1]]
        reward=reward+values[newpos[0],newpos[1]]
        if(Q.get((position[0],position[1],d),0)==0):
            Q[position[0],position[1],d]=reward

#Qmove: decides which move to make depending on current Q values
#this is where the issue is!
def Qmove(moves):
    global position
    global Q
    global step
    global stepTrap
    global stepWall
    global stepExit
    global gamma
    bestd=0
    newd=moves[random.randint(0,len(moves)-1)]
    for d in moves:
        newpos=position
        if d==Direction.up:
            newpos=[position[0], position[1]+1]
        if d==Direction.down:
            newpos=[position[0], position[1]-1]
        if d==Direction.left:
            newpos=[position[0]-1, position[1]]
        if d==Direction.right:
            newpos=[position[0]+1, position[1]]
        #update value to best value of new position
        if Q.get((newpos[0],newpos[1],d),0)>=Q.get((newpos[0],newpos[1],bestd),0):
            bestd=d
        Q[position[0],position[1],d]=Q.get((position[0],position[1],d),0)+ (values[newpos[0]][newpos[1]] + gamma * Q.get((newpos[0],newpos[1],bestd),1) - Q.get((position[0],position[1],d),0))      
        #update arrow
        if Q.get((position[0],position[1],d),0)>Q.get((position[0],position[1],newd),0):
            newd=d
    return newd

#create maze
ch=['0', '1', '3']
for i in range(cols):
    maze.append([0]*(cols))
    for j in range(cols):
        random_index = randrange(0,len(ch))
        maze[i][j]=ch[random_index]
        if i==cols-1 and j==cols-1:
            maze[i][j]='5'
        if i==0 and j==0:
            maze[i][j]='0'
        if(maze[i][j]=="1"):
            values[i][j]=step
        elif(maze[i][j]=="0"):
            values[i][j]=stepWall
        elif(maze[i][j]=="3"):
            values[i][j]=stepTrap
        else:
            values[i][j]=stepExit
#move
while(stepsTaken<nbMaxSteps):
    moves=[]
    #if he finishes he starts over
    if(position[0]==rows-1 and position[1]==cols-1):
        position[0]=0
        position[1]=0
        penalty=0
    #identify the moves he can legally make
    if (position[0]!=0):
        moves.append(Direction.left)
    if (position[0]!=cols-1):
        moves.append(Direction.right)
    d=moves[0]
    if (position[1]!=0):
        moves.append(Direction.down)
    if (position[1]!=rows-1):
        moves.append(Direction.up)
    dest=[]
    #choose epsilon value
    rand=random.uniform(0, 1)
    if(rand<epsilon**stepsTaken):
        strat=1
        #explore
    else:
        strat=2
        #exploit
    #print(epsilon**stepsTaken)
    if(currentQEmpty() or strat==1):
        QFill(moves)
        d=moves[random.randint(0,len(moves)-1)]#how and why he moves
        print('dumb')
    else:
        d=Qmove(moves)
        print('smart')
    if(d==Direction.left):
        dest.append(position[0]-1) #x decreases by 1 place
        dest.append(position[1]) #y does not change
    if(d==Direction.right):
        dest.append(position[0]+1) #x increases by 1 place
        dest.append(position[1]) #y does not change
    if(d==Direction.up):
        dest.append(position[0]) #x does not change&&
        dest.append(position[1]+1) #y increases by 1
    if(d==Direction.down):
        dest.append(position[0]) #x does not change
        dest.append(position[1]-1) #y decreases by 1
    #penalty is calculated
    penalty=penalty+values[dest[0]][dest[1]]
    if(maze[dest[0]][dest[1]]!='0'): #not a wall
        position=dest
    stepsTaken=stepsTaken+1
    #show Q matrix
    x=position[0]
    y=position[1]
    print("x:",x," y:",y)
    print(" UP:%s" % Q.get((x,y, Direction.up)))
    print(" DOWN:%s" % Q.get((x,y, Direction.down)))
    print(" LEFT:%s" % Q.get((x,y, Direction.left)))
    print(" RIGHT:%s\n" % Q.get((x,y, Direction.right)))
$\endgroup$
  • $\begingroup$ You might want to make your epsilon 0.01 instead of .99. Might help. $\endgroup$ – Jaden Travnik Mar 16 '18 at 3:18
  • $\begingroup$ @JadenTravnik that actually made it worse... Exponentially worse I might add $\endgroup$ – Jessica Chambers Mar 16 '18 at 19:00
  • 1
    $\begingroup$ My bad, I miss read your epsilon calculation. Usually it’s convention to have the equation the other way around. $\endgroup$ – Jaden Travnik Mar 16 '18 at 19:02
-2
$\begingroup$

The posted sourcecode contains of 190 lines of code written in Python and it runs in my IDE without any problems. The status information are printed out to the screen thanks to the while loop and i would give some hints how to improve the program. The first thing to do is to describe the Q-learning problem from an abstract perspective. As far as i can see from the code and the textual description the idea is to build a maze simulation game which contains of normal fields, walls and an exit field. The first thing to do is to create the game itself in a standalone fashion.

Python is a great programming language in doing so. It make sense to realize the maze-game in pygame with some classes and some methods in the classes. Such mini-game would take around 300 lines of code and will result into a shiny looking screenshot of the game. It can be played with a human player and if he is reaching the exit field, he has won the game.

If the code for such a game was created we can discuss about the q-learning part. The advantage is, that the code on top of the game remains short. Because the question is not anymore how the game mechanics will look like but the problem can be simplified to q-learning itself. This helps to reduce the attention only to a small part of the overall project. The q-learning part consists of two subproblems as well. The first one is to control the robot agent with the q-table and the second part is to fill the q-table with the right values. The second step is called q-learning, or simply learning. Because the aim is to generate an array of values.

After this introduction, it's possible to describe what the answer to the posted problem is. The first step is to ask what kind of subproblem is exactly unsolved. Is the robot able to use a manual created q-table and goes to the exit? Is the robot able to generate the q-table from scratch? As far as i can see from the sourcecode both times the answer is no. The recommended workflow is to create first the sourcecode which allows the robot to take an existing q-matrix and acts by it's own in the automode. And then the second question can be discusses how to fill the q-table automatically.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.