用Q-learning算法實(shí)現(xiàn)自動(dòng)走迷宮機(jī)器人的方法示例

項(xiàng)目描述：

在該項(xiàng)目中，你將使用強(qiáng)化學(xué)習(xí)算法，實(shí)現(xiàn)一個(gè)自動(dòng)走迷宮機(jī)器人。

如上圖所示，智能機(jī)器人顯示在右上角。在我們的迷宮中，有陷阱（紅色×××）及終點(diǎn)（藍(lán)色的目標(biāo)點(diǎn)）兩種情景。機(jī)器人要盡量避開陷阱、盡快到達(dá)目的地。

小車可執(zhí)行的動(dòng)作包括：向上走 u、向右走 r、向下走 d、向左走l。

執(zhí)行不同的動(dòng)作后，根據(jù)不同的情況會(huì)獲得不同的獎(jiǎng)勵(lì)，具體而言，有以下幾種情況。

• 撞到墻壁：-10
• 走到終點(diǎn)：50
• 走到陷阱：-30
• 其余情況：-0.1

我們需要通過修改 robot.py 中的代碼，來實(shí)現(xiàn)一個(gè) Q Learning 機(jī)器人，實(shí)現(xiàn)上述的目標(biāo)。

Section 1 算法理解

1.1 強(qiáng)化學(xué)習(xí)總覽

強(qiáng)化學(xué)習(xí)作為機(jī)器學(xué)習(xí)算法的一種，其模式也是讓智能體在“訓(xùn)練”中學(xué)到“經(jīng)驗(yàn)”，以實(shí)現(xiàn)給定的任務(wù)。但不同于監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)，在強(qiáng)化學(xué)習(xí)的框架中，我們更側(cè)重通過智能體與環(huán)境的交互來學(xué)習(xí)。通常在監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)任務(wù)中，智能體往往需要通過給定的訓(xùn)練集，輔之以既定的訓(xùn)練目標(biāo)（如最小化損失函數(shù)），通過給定的學(xué)習(xí)算法來實(shí)現(xiàn)這一目標(biāo)。然而在強(qiáng)化學(xué)習(xí)中，智能體則是通過其與環(huán)境交互得到的獎(jiǎng)勵(lì)進(jìn)行學(xué)習(xí)。這個(gè)環(huán)境可以是虛擬的（如虛擬的迷宮），也可以是真實(shí)的（自動(dòng)駕駛汽車在真實(shí)道路上收集數(shù)據(jù)）。

在強(qiáng)化學(xué)習(xí)中有五個(gè)核心組成部分，它們分別是：環(huán)境（Environment）、智能體（Agent）、狀態(tài)（State）、動(dòng)作（Action）和獎(jiǎng)勵(lì)（Reward）。在某一時(shí)間節(jié)點(diǎn)t：

智能體在從環(huán)境中感知其所處的狀態(tài)

智能體根據(jù)某些準(zhǔn)則選擇動(dòng)作

環(huán)境根據(jù)智能體選擇的動(dòng)作，向智能體反饋獎(jiǎng)勵(lì)

通過合理的學(xué)習(xí)算法，智能體將在這樣的問題設(shè)置下，成功學(xué)到一個(gè)在狀態(tài) 選擇動(dòng)作 的策略 。

1.2 計(jì)算Q值

在我們的項(xiàng)目中，我們要實(shí)現(xiàn)基于 Q-Learning 的強(qiáng)化學(xué)習(xí)算法。Q-Learning 是一個(gè)值迭代（Value Iteration）算法。與策略迭代（Policy Iteration）算法不同，值迭代算法會(huì)計(jì)算每個(gè)”狀態(tài)“或是”狀態(tài)-動(dòng)作“的值（Value）或是效用（Utility），然后在執(zhí)行動(dòng)作的時(shí)候，會(huì)設(shè)法最大化這個(gè)值。因此，對(duì)每個(gè)狀態(tài)值的準(zhǔn)確估計(jì)，是我們值迭代算法的核心。通常我們會(huì)考慮最大化動(dòng)作的長(zhǎng)期獎(jiǎng)勵(lì)，即不僅考慮當(dāng)前動(dòng)作帶來的獎(jiǎng)勵(lì)，還會(huì)考慮動(dòng)作長(zhǎng)遠(yuǎn)的獎(jiǎng)勵(lì)。

在 Q-Learning 算法中，我們把這個(gè)長(zhǎng)期獎(jiǎng)勵(lì)記為 Q 值，我們會(huì)考慮每個(gè) ”狀態(tài)-動(dòng)作“ 的 Q 值，具體而言，它的計(jì)算公式為：

也就是對(duì)于當(dāng)前的“狀態(tài)-動(dòng)作” ，我們考慮執(zhí)行動(dòng)作 后環(huán)境給我們的獎(jiǎng)勵(lì)，以及執(zhí)行動(dòng)作 到達(dá) 后，執(zhí)行任意動(dòng)作能夠獲得的最大的Q值，為折扣因子。

不過一般地，我們使用更為保守地更新 Q 表的方法，即引入松弛變量 alpha，按如下的公式進(jìn)行更新，使得 Q 表的迭代變化更為平緩。

根據(jù)已知條件求。

已知：如上圖，機(jī)器人位于 s1，行動(dòng)為 u，行動(dòng)獲得的獎(jiǎng)勵(lì)與題目的默認(rèn)設(shè)置相同。在 s2 中執(zhí)行各動(dòng)作的 Q 值為：u: -24，r: -13，d: -0.29、l: +40，γ取0.9。

1.3 如何選擇動(dòng)作

在強(qiáng)化學(xué)習(xí)中，「探索-利用」問題是非常重要的問題。具體來說，根據(jù)上面的定義，我們會(huì)盡可能地讓機(jī)器人在每次選擇最優(yōu)的決策，來最大化長(zhǎng)期獎(jiǎng)勵(lì)。但是這樣做有如下的弊端：

• 在初步的學(xué)習(xí)中，我們的 Q 值會(huì)不準(zhǔn)確，如果在這個(gè)時(shí)候都按照 Q 值來選擇，那么會(huì)造成錯(cuò)誤。
• 學(xué)習(xí)一段時(shí)間后，機(jī)器人的路線會(huì)相對(duì)固定，則機(jī)器人無法對(duì)環(huán)境進(jìn)行有效的探索。

因此我們需要一種辦法，來解決如上的問題，增加機(jī)器人的探索。由此我們考慮使用 epsilon-greedy 算法，即在小車選擇動(dòng)作的時(shí)候，以一部分的概率隨機(jī)選擇動(dòng)作，以一部分的概率按照最優(yōu)的 Q 值選擇動(dòng)作。同時(shí)，這個(gè)選擇隨機(jī)動(dòng)作的概率應(yīng)當(dāng)隨著訓(xùn)練的過程逐步減小。

在如下的代碼塊中，實(shí)現(xiàn) epsilon-greedy 算法的邏輯，并運(yùn)行測(cè)試代碼。

import random 
import operator 

actions = ['u','r','d','l'] 
qline = {'u':1.2, 'r':-2.1, 'd':-24.5, 'l':27} 
epsilon = 0.3 # 以0.3的概率進(jìn)行隨機(jī)選擇 

def choose_action(epsilon):     
  action = None 
   if random.uniform(0,1.0) <= epsilon: # 以某一概率 
    action = random.choice(actions)# 實(shí)現(xiàn)對(duì)動(dòng)作的隨機(jī)選擇 
   else:  
     action = max(qline.items(), key=operator.itemgetter(1))[0] # 否則選擇具有最大 Q 值的動(dòng)作 
   return action 

range(100): 

  res += choose_action(epsilon) 

print(res) 

res = '' 

for i in range(100): 

   res += choose_action(epsilon) 

print(res) 
 ldllrrllllrlldlldllllllllllddulldlllllldllllludlldllllluudllllllulllllllllllullullllllllldlulllllrlr

Section 2 代碼實(shí)現(xiàn)

2.1 Maze 類理解

我們首先引入了迷宮類 Maze，這是一個(gè)非常強(qiáng)大的函數(shù)，它能夠根據(jù)你的要求隨機(jī)創(chuàng)建一個(gè)迷宮，或者根據(jù)指定的文件，讀入一個(gè)迷宮地圖信息。

• 使用 Maze("file_name") 根據(jù)指定文件創(chuàng)建迷宮，或者使用 Maze(maze_size=(height, width))來隨機(jī)生成一個(gè)迷宮。
• 使用 trap number 參數(shù)，在創(chuàng)建迷宮的時(shí)候，設(shè)定迷宮中陷阱的數(shù)量。
• 直接鍵入迷宮變量的名字按回車，展示迷宮圖像（如 g=Maze("xx.txt")，那么直接輸入 g 即可。
• 建議生成的迷宮尺寸，長(zhǎng)在 6~12 之間，寬在 10～12 之間。

在如下的代碼塊中，創(chuàng)建你的迷宮并展示。

from Maze import Maze 
%matplotlib inline 
%confer InlineBackend.figure_format = 'retina' 
  ## to-do: 創(chuàng)建迷宮并展示 
g=Maze(maze_size=(6,8), trap_number=1) 
g 
Maze of size (12, 12
)

你可能已經(jīng)注意到，在迷宮中我們已經(jīng)默認(rèn)放置了一個(gè)機(jī)器人。實(shí)際上，我們?yōu)槊詫m配置了相應(yīng)的 API，來幫助機(jī)器人的移動(dòng)與感知。其中你隨后會(huì)使用的兩個(gè) API 為 maze.sense_robot() 及 maze.move_robot() 。

• maze.sense_robot() 為一個(gè)無參數(shù)的函數(shù)，輸出機(jī)器人在迷宮中目前的位置。
• maze.move_robot(direction) 對(duì)輸入的移動(dòng)方向，移動(dòng)機(jī)器人，并返回對(duì)應(yīng)動(dòng)作的獎(jiǎng)勵(lì)值。

隨機(jī)移動(dòng)機(jī)器人，并記錄下獲得的獎(jiǎng)勵(lì)，展示出機(jī)器人最后的位置。

rewards = []   
 ## 循環(huán)、隨機(jī)移動(dòng)機(jī)器人10次，記錄下獎(jiǎng)勵(lì) 
for i in range(10): 
  res = g.move_robot(random. Choice(actions)) 
   rewards.append(res)   
 ## 輸出機(jī)器人最后的位置 
print(g.sense_robot())   
## 打印迷宮，觀察機(jī)器人位置 
g 

(0,9)

2.2 Robot 類實(shí)現(xiàn)

Robot 類是我們需要重點(diǎn)實(shí)現(xiàn)的部分。在這個(gè)類中，我們需要實(shí)現(xiàn)諸多功能，以使得我們成功實(shí)現(xiàn)一個(gè)強(qiáng)化學(xué)習(xí)智能體。總體來說，之前我們是人為地在環(huán)境中移動(dòng)了機(jī)器人，但是現(xiàn)在通過實(shí)現(xiàn) Robot 這個(gè)類，機(jī)器人將會(huì)自己移動(dòng)。通過實(shí)現(xiàn)學(xué)習(xí)函數(shù)，Robot 類將會(huì)學(xué)習(xí)到如何選擇最優(yōu)的動(dòng)作，并且更新強(qiáng)化學(xué)習(xí)中對(duì)應(yīng)的參數(shù)。

首先 Robot 有多個(gè)輸入，其中 alpha=0.5, gamma=0.9, epsilon0=0.5 表征強(qiáng)化學(xué)習(xí)相關(guān)的各個(gè)參數(shù)的默認(rèn)值，這些在之前你已經(jīng)了解到，Maze 應(yīng)為機(jī)器人所在迷宮對(duì)象。

隨后觀察 Robot.update 函數(shù)，它指明了在每次執(zhí)行動(dòng)作時(shí)，Robot 需要執(zhí)行的程序。按照這些程序，各個(gè)函數(shù)的功能也就明了了。

運(yùn)行如下代碼檢查效果（記得將 maze 變量修改為你創(chuàng)建迷宮的變量名）。

import random 
import operator    

 class Robot(object):  

  def __init__(self, maze, alpha=0.5, gamma=0.9, epsilon0=0.5):  

     self. Maze = maze 
     self.valid_actions = self.maze.valid_actions 

     self.state = None 
     self.action = None   

     # Set Parameters of the Learning Robot 
     self.alpha = alpha 
     self.gamma = gamma  

     self.epsilon0 = epsilon0 
     self. Epsilon = epsilon0 
     self.t = 0  

     self.Qtable = {} 
     self. Reset()  

  def. reset(self): 
     """ 
         Reset the robot 
     """ 
     self.state = self.sense_state() 
     self.create_Qtable_line(self.state)  

  def. set status(self, learning=False, testing=False): 
     """ 
     Determine whether the robot is learning its q table, or 
     executing the testing procedure. 
     """ 
     self. Learning = learning 
     self.testing = testing   

   def. update_parameter(self): 
     """ 
     Some of the paramters of the q learning robot can be altered, 
     update these parameters when necessary. 
     """ 
     if self.testing: 
       # TODO 1. No random choice when testing 
      self. Epsilon = 0 
     else: 
       # TODO 2. Update parameters when learning 
       self. Epsilon *= 0.95   

    return self. Epsilon   

   def. sense_state(self): 
     """ 
     Get the current state of the robot. In this 
     """ 

      # TODO 3. Return robot's current state 
          return self.maze.sense_robot()  

   def. create_Qtable_line(self, state): 
    """ 
     Create the qtable with the current state 
    """ 
     # TODO 4. Create qtable with current state 
     # Our qtable should be a two level dict, 
     # Qtable[state] ={'u':xx, 'd':xx, ...} 
     # If Qtable[state] already exits, then do 
     # not change it. 
     self.Qtable.setdefault(state, {a: 0.0 for a in self.valid_actions})       
   def. choose_action(self): 
     """ 
    Return an action according to given rules 
     """   
     def. is_random_exploration():  

       # TODO 5. Return whether do random choice 
       # hint: generate a random number, and compare 
       # it with epsilon 
      return random.uniform(0, 1.0) <= self. Epsilon 

     if self. Learning: 
       if is_random_exploration(): 
        # TODO 6. Return random choose aciton 
         return random. Choice(self.valid_actions) 
       else: 
         # TODO 7. Return action with highest q value 
         return max(self.Qtable[self.state].items(), key=operator.itemgetter(1))[0] 
     elif self.testing: 
       # TODO 7. choose action with highest q value 
       return max(self.Qtable[self.state].items(), key=operator.itemgetter(1))[0] 
     else: 
       # TODO 6. Return random choose aciton 
      return random. Choice(self.valid_actions)   

  def. update_Qtable(self, r, action, next_state): 
     """ 
     Update the qtable according to the given rule. 
     """ 
     if self. Learning: 
       # TODO 8. When learning, update the q table according 
       # to the given rules 
      self.Qtable[self.state][action] = (1 - self.alpha) * self.Qtable[self.state][action] + self.alpha * ( 
             r + self.gamma * max(self.Qtable[next_state].values())) 

  def. update(self): 
       """ 
     Describle the procedure what to do when update the robot. 
    Called every time in every epoch in training or testing. 
     Return current action and reward. 
     """ 
     self.state = self.sense_state() # Get the current state 
     self.create_Qtable_line(self.state) # For the state, create q table line 

    action = self.choose_action() # choose action for this state 
     reward = self.maze.move_robot(action) # move robot for given action 

    next_state = self.sense_state() # get next state 
     self.create_Qtable_line(next_state) # create q table line for next state 

     if self. Learning and not self.testing: 
       self.update_Qtable(reward, action, next_state) # update q table 
      self.update_parameter() # update parameters   

    return action, reward 
 # from Robot import Robot 
 # g=Maze(maze_size=(6,12), trap_number=2) 
 g=Maze("test_world\maze_01.txt") 
 robot = Robot(g) # 記得將 maze 變量修改為你創(chuàng)建迷宮的變量名 
 robot.set_status(learning=True,testing=False) 
 print(robot.update())  

 g 
（'d', -0.1）
Maze of size (12, 12)

2.3 用 Runner 類訓(xùn)練 Robot

在完成了上述內(nèi)容之后，我們就可以開始對(duì)我們 Robot 進(jìn)行訓(xùn)練并調(diào)參了。我們準(zhǔn)備了又一個(gè)非常棒的類 Runner ，來實(shí)現(xiàn)整個(gè)訓(xùn)練過程及可視化。使用如下的代碼，你可以成功對(duì)機(jī)器人進(jìn)行訓(xùn)練。并且你會(huì)在當(dāng)前文件夾中生成一個(gè)名為 filename 的視頻，記錄了整個(gè)訓(xùn)練的過程。通過觀察該視頻，你能夠發(fā)現(xiàn)訓(xùn)練過程中的問題，并且優(yōu)化你的代碼及參數(shù)。

嘗試?yán)孟铝写a訓(xùn)練機(jī)器人，并進(jìn)行調(diào)參。可選的參數(shù)包括：

• 訓(xùn)練參數(shù)
  • 訓(xùn)練次數(shù) epoch
• 機(jī)器人參數(shù)：
  • epsilon0 (epsilon 初值)
  • epsilon 衰減（可以是線性、指數(shù)衰減，可以調(diào)整衰減的速度），你需要在 Robot.py 中調(diào)整
  • alpha
  • gamma
• 迷宮參數(shù):
  • 迷宮大小
  • 迷宮中陷阱的數(shù)量
• 可選的參數(shù)：
• epoch = 20
• epsilon0 = 0.5
• alpha = 0.5
• gamma = 0.9
• maze_size = (6,8)
• trap_number = 2

from Runner import Runner 

g = Maze(maze_size=maze_size,trap_number=trap_number) 
r = Robot(g,alpha=alpha, epsilon0=epsilon0, gamma=gamma) 
r.set_status(learning=True) 

 runner = Runner(r, g) 
runner.run_training(epoch, display_direction=True) 
 #runner.generate_movie(filename = "final1.mp4") # 你可以注釋該行代碼，加快運(yùn)行速度，不過你就無法觀察到視頻了。 
 g

使用 runner.plot_results() 函數(shù)，能夠打印機(jī)器人在訓(xùn)練過程中的一些參數(shù)信息。

• Success Times 代表機(jī)器人在訓(xùn)練過程中成功的累計(jì)次數(shù)，這應(yīng)當(dāng)是一個(gè)累積遞增的圖像。
• Accumulated Rewards 代表機(jī)器人在每次訓(xùn)練 epoch 中，獲得的累積獎(jiǎng)勵(lì)的值，這應(yīng)當(dāng)是一個(gè)逐步遞增的圖像。
• Running Times per Epoch 代表在每次訓(xùn)練 epoch 中，小車訓(xùn)練的次數(shù)（到達(dá)終點(diǎn)就會(huì)停止該 epoch 轉(zhuǎn)入下次訓(xùn)練），這應(yīng)當(dāng)是一個(gè)逐步遞減的圖像。

使用 runner.plot_results() 輸出訓(xùn)練結(jié)果

 runner.plot_results() 

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。