Value_Iteration/value_Iteration.py at master · Machoper/Value_Iteration · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
gamma = 1
epsilon = 0.001
MAX_ITERS = 1000
wind = 3

u = [[0 for x in range(7)] for x in range(7)]

# Actions
stay = u"\u2022"
W = u"\u2190"
N = u"\u2191"
E = u"\u2192"
S = u"\u2193"
NW = u"\u2196"
NE = u"\u2197"
SE = u"\u2198"
SW = u"\u2199"
Actions = [stay, W, N, E, S, NW, NE, SE, SW]
direction = [[stay for x in range(7)] for x in range(7)]


# Reward function
def r(state):
    if state[0] == 3 and state[1] == 6:
        return 0
    else:
        return -1


# Wind function
def w(state):
    if wind == 1:
        return state
    if wind == 2:
        if 2 < state[1] < 6:
            state = (state[0] - 1, state[1])
        if state[0] < 0:
            state = (0, state[1])
        if state[0] > 6:
            state = (6, state[1])
        return state
    if wind == 3:
        if 2 < state[1] < 6:
            state = (state[0] - 2, state[1])
        if state[0] < 0:
            state = (0, state[1])
        if state[0] > 6:
            state = (6, state[1])
        return state


# Transition function
def t(s, a):
    s = w(s)
    if a == W:
        if s[1] > 0:
            s = (s[0], s[1]-1)
    elif a == N:
        if s[0] > 0:
            s = (s[0]-1, s[1])
    elif a == E:
        if s[1] < 6:
            s = (s[0], s[1]+1)
    elif a == S:
        if s[0] < 6:
            s = (s[0]+1, s[1])
    elif a == NE:
        if s[0] == 0 and s[1] == 6:
            return s
        elif s[0] == 0:
            s = (s[0], s[1]+1)
        elif s[1] == 6:
            s = (s[0]-1, s[1])
        else:
            s = (s[0]-1, s[1]+1)
    elif a == NW:
        if s[0] == 0 and s[1] == 0:
            return s
        elif s[0] == 0:
            s = (s[0], s[1]-1)
        elif s[1] == 0:
            s = (s[0]-1, s[1])
        else:
            s = (s[0]-1, s[1]-1)
    elif a == SE:
        if s[0] == 6 and s[1] == 6:
            return s
        elif s[0] == 6:
            s = (s[0], s[1]+1)
        elif s[1] == 6:
            s = (s[0]+1, s[1])
        else:
            s = (s[0]+1, s[1]+1)
    elif a == SW:
        if s[0] == 6 and s[1] == 0:
            return s
        elif s[0] == 6:
            s = (s[0], s[1]-1)
        elif s[1] == 0:
            s = (s[0]+1, s[1])
        else:
            s = (s[0]+1, s[1]-1)
    return s


# Value Iteration
u_prime = [[0 for x in range(7)] for x in range(7)]
iterations = 0
while iterations <= MAX_ITERS:
    iterations += 1
    delta = 0
    u = u_prime
    for i in range(7):
        for j in range(7):
            s = (i, j)
            MAX_V = -9999
            MAX_A = stay
            for a in Actions:
                s_prime = t(s, a)
                value = u[s_prime[0]][s_prime[1]]
                if value > MAX_V:
                    MAX_V = value
                    MAX_A = a
            u[i][j] = r(s) + gamma * MAX_V
            direction[i][j] = MAX_A
            if abs(u[i][j] - u[i][j]) > delta:
                delta = abs(u[i][j] - u[i][j])
    if delta >= epsilon:
        break


# Output value function and policy map
for i in range(7):
    print(u[i])
print('\n')
output = ''
for j in range(7):
    for k in range(7):
        output += direction[j][k] + ' '
        if len(output) == 14:
            print(output)
            output = ''