Q-Learning

說明

  • Q-Learning 中最重要的兩個因素為:狀態(State)與動作
  • 狀態表示處於圖中那個節點
  • 動作則為從一節點到另一節點的動作(權重)

情境說明

假設有個房間平面圖,如下:
Room
每個房間都有對外的門可以通到其他房間。透過數學式轉換,可以得到下圖:
path
當走到房間五時就可以出去,為了能夠走出去,所以我們將每個路徑設定權重,目標房間五的權重為100:
weight

獎勵矩陣

接下來我們可以把上面的圖,轉為一個矩陣,矩陣中-1表示不可通過,0表示節點間有路徑、通道,100表示直接到達節點,可得到下圖:
矩陣

學習矩陣

另外,我們要準備一個表格(矩陣)來表示學習到的經驗(從一個節點到另一個節點所獲得的機率),初始化內容為0。
reward matrix

轉換公式

有這兩個矩陣後,Q的值舊可以透過下列公式得出:
formula
在上面的公式中,S表示当前的状态,a表示当前的动作,s表示下一个状态,a表示下一个动作,λ为贪婪因子,0<λ<1,一般设置为0.8。Q表示的是,在状态s下采取动作a能够获得的期望最大收益,R是立即获得的收益,而未来一期的收益则取决于下一阶段的动作。

所以,Q-learning的学习步骤可以歸納為如下:
step

程式碼

import numpy as np
import random

r = np.array([[-1, -1, -1, -1, 0, -1], [-1, -1, -1, 0, -1, 100], [-1, -1, -1, 0, -1, -1], [-1, 0, 0, -1, 0, -1],
              [0, -1, -1, 0, -1, 100], [-1, 0, -1, -1, 0, 100]])

q = np.zeros([6,6],dtype=np.float32)

gamma = 0.8

step = 0
while step < 1000:
    state = random.randint(0,5)
    if state != 5:
        next_state_list=[]
        for i in range(6):
            if r[state,i] != -1:
                next_state_list.append(i)
        next_state = next_state_list[random.randint(0,len(next_state_list)-1)]
        qval = r[state,next_state] + gamma * max(q[next_state])
        q[state,next_state] = qval

print(q)

print(q)
# 验证

for i in range(10):
    print("第{}次验证".format(i + 1))
    state = random.randint(0, 5)
    print('机器人处于{}'.format(state))
    count = 0
    while state != 5:
        if count > 20:
            print('fail')
            break
        # 选择最大的q_max
        q_max = q[state].max()

        q_max_action = []
        for action in range(6):
            if q[state, action] == q_max:
                q_max_action.append(action)

        next_state = q_max_action[random.randint(0, len(q_max_action) - 1)]
        print("the robot goes to " + str(next_state) + '.')
        state = next_state
        count += 1