Notes on AIMA4 Chapter 4 Searching in Complex Environment

有些问题只关心最佳状态，并不关心到达最佳状态的路径。这些问题甚至没有预设初始状态。典型的，八皇后问题，数值优化问题等等。八皇后问题有一个IsGoal的判定方法，可以区分一个状态是否是目标所求，但无法准确度量一个状态有多好，但根据状态和目标的差距可以设计启发式的度量方法。很多数值问题无法判定一个状态是否最优，但是可以准确度量一个状态的好坏程度，但由于没有目标定义，即便有最佳状态自己也不知道。所以两者都有状态质量的度量方法。由于不关心路径，所以动作执行和状态切换只是头脑里的风暴，没有物理世界对应的操作成本。
这类不关心路径的问题，都可以用Local Search类的方法求解。从一个随机生成的初始状态出发，不断从邻居状态里寻找最佳的跳过去。对于八皇后，邻居状态可以是一个随机选择一个皇后，挪动到该列随机的一个位置。对于数值优化问题，可以通过附近撒点，计算经验梯度，跳转到最佳的点上去。对于八皇后问题，可以通过IsGoal Test终止，对于数值优化问题，可以通过检测收敛终止。这就是爬山法。
Local Search受局部最优点的影响，跳出局部最优的方法是加入随机性。一种办法是加入一定的随机游走，这就是随机爬山法。模拟退火是一种随机爬山法，大概思路是，随机找个后继状态，如果该状态优于当前，则切换到该状态，否则以一定概率切换到该状态。此概率由两个因素决定。一是该后继状态与当前状态的价值差，一是随着时间逐渐降低的温度T。温度降到0时，返回其结果。
另一种办法是随机重启爬山法。大概思路是如果此局无望，则推倒重来。停止当前搜索，随机穿越，在一个新的初始态开始搜索。此方法对求解八皇后问题尤其有效。随机重启法非常容易并行。
还有一种办法是局部群束搜索。不是维护一个当前状态，而是k个，相当于k路搜索。每次列举出k个状态的所有后继，从中选出k个最好的再继续。有个不好处是k个前沿状态很容易同质化，可以在选优的方式里加入随机性，如以等比于其适应性的概率从后继列表中选优。称之为随机群束搜索。
进化算法也可以归类为随机群束搜索法。只是后继的生成方式是用crossover和mutation。进化算法适用于存在局部模式的情况，每个组块代表一种有意义的局部模式，组块之间重新组合才有价值。进化理论的两个有意思的结论：1、学习能力可以显著放松适应度地形（基因型到适应度的映射），脑力可以弥补一些生理缺陷以获得繁衍的机会。2、难以学习的能力都在基因组里，不难学习的无需放到基因组里。
连续状态空间可以通过离散化解决，也可以通过梯度法解决。如果适应度地形有良好的数学形式，可以通过沿着梯度寻求适应度最大的状态。梯度法需要确定步长。line search，即在最大梯度方向上以翻倍的速率搜索步长，直至f下降。如果适应度地形二阶可导，则可用二阶泰勒展开式做局部拟合，以此二次函数的极值点作为下一个状态x = x - f''(x)^{-1} * f'(x)，即步长=f"(x)^{-1}。就是牛顿法。多元时二次导是海森矩阵，O(n^2)，故而太多维度时此法不可行，可用近似方案-拟牛顿法，根据最近经历的点序列和其梯度序列近似拟合一个二次函数出来求解。在维度极高到百万后，像深度学习模型，估计二次近似都不可行（待研究）。
如果状态有硬约束，则是约束优化问题。其中凸优化问题，在满足KKT条件下，有多项式解，可处理上千变量的问题。线性规划问题是凸优化中研究得最多和应用得最广泛的一种。值得再花些心思研究透彻。
Chapter 3和前述所讲内容，都假设了状态的完全可观测性和状态上动作结果的确定性。完全可观测性，叫直接可观测性更恰当，相当于智能体直接看到了物理状态s，而不是像我们日常是通过光线/声音等物体的表象去推断物理状态（康德的物自体）。动作结果的确定性是说，一个物理状态s上执行动作a，所得结果是唯一且确定的某另一物理状态s'。而我们日常的行为总会存在不确定性，用锤子砸核桃，用力太大桃肉就成了粉末，用力太小桃皮还纹丝未动。所以通常我们需要在动作后增加观测，以确定新的状态。
动作不确定性问题中，一个状态下执行某动作，可能的后果不止一种。因此计划时要考虑执行时会碰到的各种情况，产出的不是一个动作序列，而是一种应变计划，如：先做动作A1，然后如果发现到达状态S1就做动作A2，如果到达状态S2就做动作A3。方案搜索过程可通过构造与或树来进行。OR节点智能体选择动作，AND节点环境给出响应。由于环境响应存在不确定性，所以每种情况都得处理，所以AND。由于自己的动作自己有选择权，所以为OR。无环的情况，只需要if结构，简单的递归算法可求解。有环的情况（即从S出发执行动作序列后再次到达S），需要while结构，要保证每个叶子结点都是GOAL，每个非叶子节点的状态，都有途径到达叶子节点。AND-OR搜索也可以通过best-search方式进行，也可以有启发式函数，也有admissible的概念保证成本最优性，但是启发式函数对成本的估算需要基于应变计划而非动作序列。
无观测问题sensorless/conformant problem中，智能体全无观测，所以无法知道初始状态是什么，但是知道Actions(s)、Result(s,a)或Results(s,a)，即假设状态为s，执行动作a会有什么结果。智能体要在这种信息闭塞的状态下完成任务。不少问题都可以简化为完全无观测问题的思路，如假设有个机器清洁桌面污渍，其设计可能是把桌面全抹一遍，而不管污渍在哪里。医生也经常在不知你感染何种病菌的情况下，不做检测，直接开广谱抗生素。此类问题，是要求一个动作序列，不管物理初始状态为何，动作序列执行完，都能达到目标状态。无观测是对外无观测，智能体总是知道自己内部的信念状态的，信念状态即外界可能处于的状态的集合。无观测问题可以形式化为信念状态空间的搜索问题。Actions(b) - 信念状态b中s可用动作的并集，Result(b,a) - 在信念状态b中的s上应用动作a的结果的并集。Is-Goal(b) - b中每个s是否都是目标状态。
无观测问题在原子表示法下，信念状态的空间复杂度太高，对应的计算复杂度也太高。一种解决方案是用因子分解简化表示。一种是增量的信念状态搜索法：因为无观测问题的解，是任何初始物理状态的解。我们可以只关注一个物理状态的求解，再拿其他物理状态验证，如果一个解失败就回溯换一个解。也就成了普通的搜索问题，只是Is-Goal(s)测试的不是当前状态s，而是s所代表的路径是否对其他物理状态同样适用。
部分可观测性，是指物理状态无法直接观测到，智能体只能通过感知去推断。由于不同的物理状态可能有相同的感知表象，智能体的信念状态b可能包含多个物理状态s。在此情况下，执行一个动作a之后，可能会到达的物理状态也是一个集合b'，通过新的感知o，b'中的部分物理状态可以排除，剩下的就是新的信念状态b''。基于对物理状态的了解，如Actions(s)，Result(s,a)/Results(s,a), Percept(s)/Percepts(s)，可以构造信念状态空间下的知识：Actions(b) - b中s上可用动作的并集，Predict(b,a) - b上应用动作a未观测时对b'的预测，Results(b,a) - b上应用动作a并有了新的观测o后所有可能的b''的集合。如此部分可观测性问题的形式和前述动作不确定性问题一致，只是从物理状态切换成了信念状态。也可用AND-OR求解。应对信念状态表示和计算的复杂性，也可以采用增量信念状态搜索法。
前述问题都假设了智能体对世界是有充分的知识的，如Actions(s)，Result(s,a)/Results(s,a), Percept(s)/Percepts(s)。现实是只能提经常发现自己处在未知的新环境里，几乎一无所知，只能靠自己去探索。我们假设智能体只知道Actions(s)和Is-Goal(s)。Result(s,a)/Results(s,a)需要智能体从经验中学习。另外或许智能体一个启发式度量函数h(s)，比如智能体有一个残缺的地图和一个GPS定位器。地图上除了标注了初始位置和目标位置，其他所有信息都被抹掉了。在这种情况下智能体只能选择Online seach方法，在根本不知道每个动作会导致什么结果的情况下，智能先随机尝试一个动作，然后观察世界的变化，更新知识（地图等），再根据已有知识计算下一个动作。动作--> 观察 --> 计算 --> 动作的同步循环或异步交织。
在线计算的方法讲了两种，都是在动作结果确定性和完全可以观测性的前提下讲的。一是DFS，一是LRTA*。两种算法都是边求解边绘制地图，DFS重探索，LRTA*重求解效率。Leaning Real Time A* 算法在探索的过程中除了产出地图，还在admissible启发式度量的基础上计算了更为精准的价值度量函数，更新规则：H(s) = min_a {H(s') + Cost(s,a,s')}，其中s'=Result(s,a) ，并依据此度量函数指导搜索过程。在有限状态问题中，估计H随着时间会越来越精准，逼近真实价值，搜索效率也高。在无限状态空间中不适用。LRTA*是爬山法的一种，只是问题中有动作成本，所以在启发式度量之上做了成本估计的细化。LRTA*的探索+估计值函数的方法，使其可以归类为RL的一种。两种算法都只能在安全可逆的环境中应用。
Online search并非只在未知世界有用，在不确定性和部分可观测问题中也需要。在这类问题中的求解中，随着搜索深度的加深，一些分支情况发生的概率可能非常低，且如果其并不会导致严重的风险，进一步求解徒费工夫收益甚微。可以给智能体加上一个RePlan的动作，计划里写明这些情况等碰到了再说。如此，智能体只需要遍历大概率和高风险的路径，节约能量还可以快速响应。
另，行为和行为之间有互相抵消等关系，在当前的问题描述里都被隐藏在了Result(s,a)函数中。如果状态有因子分解的表示，如经纬度，对GoNorth和GoSouth这种动作，我们就可以直接描述其对状态因子的影响，或者智能体可以通过探索学习得到这个影响，就可以避免很多愚蠢的探索行为。