求取最小二范数解的具体过程

2018年03月14日

推导一遍案例中求取最小二范数解的具体过程

#机器学习

Q-learning人工智能玩推箱子小游戏

2018年03月10日

基本已知条件

1, 舞台情景: 16x16的方格, 游戏中用一个16x16的矩阵表示, 如下:

// 第一关的数据
levels[0]=[
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,2,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,0,1,1,1,1,0,0,0,0],
[0,0,0,0,1,1,1,3,0,3,2,1,0,0,0,0],
[0,0,0,0,1,2,0,3,4,1,1,1,0,0,0,0],
[0,0,0,0,1,1,1,1,3,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,2,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]];

//...

下图是第一关真实场景.

看这个数据, 对照实际图, 可以知道各个单元格数字代表的意义:

0 代表空格
1 代表树, 是推不动的
2 代表目标位置
3 代表箱子
4 代表悟空

游戏的规则就是控制悟空, 推动箱子, 最终把所有箱子放置到目标位置.

设计思路

不知道Qlearning的请自行搜索相关理论, 我这里假设你已经知道了Qlearning.

Qlearning中最重要的两个概念: State和Action. State表示游戏状态, Action表示可能采取的动作.

Qlearning种的两个最重要的矩阵: R矩阵和Q矩阵.

先来说Q矩阵:

在推箱子游戏中, State有多少种? 计算过程如下:

- 游戏场地的方格数: 16x16
- 每个方格可能的情况: 5
- 假设每个方格的情况是相互独立的(不考虑一个游戏只可能有一个悟空等情况)
- count(state) = 5^(16x16)

这是个很大的数字, 显然这种方法不合适构建Q矩阵. 但是我们知道, 这种算法是不严谨的, 不可能有这么多情况, 还有很多已知条件没有考虑. 但是我并不想考虑那么多, 怎么办?

我们建立一个State和Action的映射字典Q = {state->actions}. 遇到一种state的时候, 先去Q中查找有没有这种情况出现过, 如果没有, 我们假设actions={上:0, 下:0, 左:0, 右:0}, 也就是假设所有的行为都等价. 并把state->actions作为一个键值对存入字典. 下次再遇到这种情况, 就可以更新里面的值了. 所以初始的Q字典只是一个空字典而已.

那么R矩阵怎么得到? 也就是说怎么决定悟空的每一步奖励值.

我们不妨设默认初始值都是-1, 因为我们不管悟空往哪里走, 我们不想让悟空移动太多. 同时每次action总会有产生一些后果, 每种后果都会有不同的奖励值.

- 如果悟空推树, 奖励值是-10, 树怎么能推动呢?
- 如果什么都没有推, 只是移动了一下, 奖励值是默认值-1
- 如果推箱子奖励值是-2, 因为移动箱子是很危险的, 要谨慎
- 如果把箱子推到了目标位置, 奖励10
- 如果任务成功, 所有箱子都达到了目标位置, 奖励是1000
- 如果任务失败(箱子不能推/或被困住), 奖励是-1000

前5条都好办, 但是我们如何识别任务失败呢? 为了思考简单些, 我们定义失败为:
- 有一个箱子不能再推动, 但是所在位置又不是目标位置;
- 所有箱子不能再被推动(箱子的对面都是空的才能被推动)
- 走了1w步还没有完成任务.

那么怎么定义一个箱子无法被推动呢? 我们简单的认为两个挨着的面都是树, 也就是卡在角落里了. 这种定义不太严谨, 有时候一堆箱子堆在一起不能动也算失败, 但是我们程序写起来就难了, 所以不能这么定义.

所以我们这样来计算任务是否失败:

function failed(matrix){
    // 找到所有箱子及其坐标
    boxes=[]
    for (let i=0;i<matrix.length;i++){
        row = matrix[i];
        up_row = matrix[i-1] or []
        below_row = matrix[i+1] or []
        for(let j=0;j<row.length;j++){
            me = row[j]
            around=[below_row[j], row[j-1], up_row[j], row[j+1], below_row[j]]
            if (me==3){
                // 有一个箱子不能再推动, 但是所在位置又不是目标位置; 
                for(let c=0;c<4;c++){
                    if(around[c]==1 or around[c]==3)
                }                
            }
        }
    }
}