lovesvidon的个人博客分享 http://blog.sciencenet.cn/u/lovesvidon

博文

【Q-learning系列】解决“房间问题”的一个通用方法

已有 6240 次阅读 2018-5-23 21:18 |个人分类:写着玩|系统分类:科研笔记| 强化学习

在阅读本文之前,请先对强化学习,Q-learning以及房间问题有一个初步的了解。可以参考下面这两个链接:

Q-learning Step by Step Tutorial

Q-learning算法分析与代码实现


“房间问题”简单来说就是终点确定的最短路径寻找问题,但是个单目标优化问题,也就是说仅仅只需要考虑路程最短,不需要考虑其它成本。在众多关于Q-learning与“房间问题”的入门介绍的文章中,无一不是参考了上面两篇文章中的方法。这个方法具有很好的可理解性,并可以快速的梳理出实现Q-learning的一般步骤,但存在一个很严重的问题,即需要人工给出Reward Matrix(奖励矩阵),这样很大程度上就限制了其通用性。面对一个仅有6个房间的问题,画出节点图,手工写出奖励矩阵并非难事,但如果是100个房间,10000个房间呢?这就比较难了,不仅手写奖励矩阵很困难,也会极大的增加训练的时间复杂度。为什么这么说,还是用6个房间的这个例子比较好解释。在建立Q-learning中被用来训练更新的Q-Table时,通常以状态(state)为行,动作(action)为列,但实际上在“6个房间问题”里,却用的是当前状态(current state)为行,下一状态(future state)为列。所以需要一个6x6的Q-table:

在Q-learning算法的实现过程中,每次的训练都会有由state去确定action的步骤,即找到可行的action并确定下一个state,相应的Q-Table可以表示成Q(S, A)。也就是依据current state找寻future state,在确定当前状态后,找寻可能的action和需要遍历所有的未来状态,对于“6个房间问题”而言,需要循环6次。假设对于某一特定的状态可行的action和future state有n个,那么在对这n个结果求解其Q(future state, fucture action)中的最大值,至少需要6(n - 1)次循环,如果加上action确定的6次循环,则一次迭代至少需要6n次。想象一下,如果是1920x1080个房间呢?毫无疑问运算量将大大增加。


通用方法

在此之前可先阅读这两篇文章:

强化学习(Q-learning~了解了一波

增强学习系列之(二):实现一个简单的增强学习的例子

以上两篇文章都是关于一维空间寻最短路径的问题,其中的action只有左右两个选项。然而对于一个二维平面的最短路径寻找问题(Path-Finding),处在任何一个状态的动作都只有4个选项,上下左右,所以这个Q-Table也可以写成如下形式(UDLR分别代表上下左右):

这种6x4的矩阵才是通用方法中的Q-Table,即使state多达10000个,矩阵的维度也只有10000x4,远小于第一种方法的10000x10000。使用这个形式Q-Table的关键问题在于如何由action获得下一个的state,也就是action到state的转化问题。还是以“6个房间问题”为例子,通过抽象化的处理,我可以把左边这副实际的房间分布图转换成右边的示意图。


示意图对原图中房间的重新编号与新添的3号房间对最终结果并无任何影响。原先的0号房间编程了5号,1号成了4号,2号变为0号,3号变为1号, 4号成了2号,5号变成了6号。状态0的action矩阵可以写为:


在Action矩阵中,0表示路线被隔断,1表示路线通畅。对于A0来说,只有向右的action是可以通畅的转往状态1的。可以很快的写出A0~A6的Action矩阵,如若仅自动识别可行的action,4x6次循环即可,而如果是遍历和每一个state的关联,则需6x6次循环,效率的提升不言而喻。Action转换为state的基本思想其实也很简单,假设当前处在第r个房间也就是状态r(总共有MxN个房间,M为列数,N为行数),其上下左右的状态分别为,r-M

,r+M,r-1,r+1,处在边界的状态再特殊考虑:

基本的原理就是这样了。

如需原码,请参考链接:

https://github.com/JinyuGuan/Q-learning-Room-Problem.git

https://github.com/JinyuGuan/Q-learning-Room-Problem.git




https://blog.sciencenet.cn/blog-3189881-1115445.html

上一篇:【补充】Chrome内置工具抓包分析
下一篇:【Q-learning系列】从一个简单的寻路问题深入Q-learning
收藏 IP: 36.57.183.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-24 00:21

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部