0.引言
上回书说到Q-Learning介绍、算法原理,并引出了路径寻优的故事,这回我们仔细说一下如何利用Q-Learning算法解决这个问题。
上次故事的传送门:
1.问题的抽象
回顾一下问题的设定:从任意地点出发,如何让机器寻到最优路径达到地址5。
抽象一下,无论是走房间还是路径寻优,本质上都可以抽象成以下的“节点-路径”关系。
因此,我们可以为路线进行奖励设定,所有可到达节点5的行动连接设定为100,其他均为0。如下图所示。
2.R矩阵设定
根据上图,设定action和state两个RL参数的含义:
1.state,定义为所处的地点/节点。
2.action,定义为移动行为,即从一个地点到另一个地点的行为。
这样我们就可以得到一个奖励函数的矩阵:R(s,a)。我们将列向量定义为state、行向量定义为action,其中的值为连接的值,主要有三类初始值:
0,即通过action没有到达节点5的行动
100,通过action到达节点5的行动
-1,没有连接关系的节点,也意味着系统不鼓励这种行为,如地点1无法到达地点2
得到R矩阵如下:
3.Q矩阵设定及Q值函数定义
Q矩阵形式上与R矩阵类似,Q矩阵是智能体的核心矩阵,主要作用是基于当前状态指导下一步可能的最佳行动策略。我们不知道任何一个步骤是否可以到达地点5,因此初始化时Q矩阵全部为0,然后通过做出行动、获得反馈、更新Q矩阵来迭代生成Q矩阵。
Q值更新的策略是一个比较简单的公式:
Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]
上式表明,Q值更新取决于本次状态、执行后的R值,加上基于下一个状态所有可能行动策略的Q的最大值乘以一个gamma系数,即折扣系数。折扣系统通常在0~1之间,代表了未来行动对当前影响的大小,是人为设定的超参数。
这也反应了其所遵从的马尔科夫决策过程的理念,在序列决策过程中,当前行动的决策不受历史行为的影响,而是受到后续行动的影响是最大的,其中越接近当前的行动影响越大。
4.Q-learning算法
我们的智能体将会通过经验学习,而不是监督学习,通常将其称之为无监督学习。智能体可以通过状态更新寻到最优策略,并到达目的地。每轮迭代包括了智能体从出发地到目的地整个过程的行动、状态和Q值计算等。当智能体到达目的地后,再开始下一轮更新,具体算法如下所示:
Q-learning算法如下所示:
1. Set the gamma parameter, and environment rewards in matrix R.
2. Initialize matrix Q to zero.
3. For each episode:
Select a random initial state.
Do While the goal state hasn't been reached.
End Do
5.Q值迭代获得Q矩阵并进行路径优化
通过Q值迭代得到Q矩阵后,智能体就可以按照Q矩阵的来进行路径选择了。即按照当前状态寻找奖励最大化的行动。具体策略如下:
Algorithm to utilize the Q matrix:
1. Set current state = initial state.
2. From current state, find the action with the highest Q value.
3. Set current state = next state.
4. Repeat Steps 2 and 3 until current state = goal state.
6.计算过程举栗?
关于Q值迭代和Q矩阵路径寻优,我们将计算过程举个栗子,便于理解。
1)Q矩阵初始化为0矩阵。
2)R矩阵初始化为连接关系矩阵,具体参见R矩阵设定环节。
3)做一次Q值迭代,求解Q(1,5)
Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]
Q(1, 5) = R(1, 5) + 0.8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100 + 0.8 * 0 = 100
其中R(1,5)通过查找R矩阵获得,Q(5,1)、Q(5,4),Q(5,5)为三个可能在状态5选择的行为,Q值通过查找Q矩阵获得,而此时的Q矩阵中的值均为0,结果如上式所示。更新后Q矩阵如下所,Q(1,5)变为100。
4)重复步骤1-3多次,最终会收敛得到一个固定的Q矩阵如下所示。
5)归一化,所有值除以5,得到Q矩阵如下。
6)在任何状态下,按照Q矩阵寻优,即如下图所示,在状态3算则3->1或3->4,因为两个的Q值均为最大值80,然后1->5或4->5。
结语
到这里,我们说到了Q-Learning路径寻优问题的抽象、R矩阵设定、Q矩阵设定及Q值函数定义、Q-learning算法、Q值迭代获得Q矩阵并进行路径优化,以及计算过程举例。
下一次将呈现出完整的代码,并对代码进行讲解,有兴趣的小伙伴可以尝试自己实现先,并分享你们的经验心得。
参考资料
http://mnemstudio.org/path-finding-q-learning-tutorial.htm