连续空间中的局部搜索

建机场的优化问题

使用已有的局部搜索算法

首选爬山法和模拟退火能够处理连续状态和动作空间。连续空间的分支因子是无限的，最陡爬山、随机爬山、局部束搜索要产生无限个后继，不可行。
遗传算法对状态编码，假设n个01位，最多表示2n个状态，无法表示连续空间的无限多个状态。

将连续问题离散化

处理连续状态空间的一种方法是离散化（discretize）。例如，我们可以将(xi, yi)的位置限制在矩形网格上间距为的固定点，而不是允许它的位置可以为连续二维空间中的任意点。

首选爬山法和模拟退火法不用离散即可使用，随机生成长度为的向量

使用梯度：求解

梯度上升/梯度下降

牛顿-拉弗森法

约束优化（constrained optimization）

如果一个优化问题的解必须满足对变量值的一些硬性约束，那么这个问题就是受约束的。约束优化问题的难度取决于约束和目标函数的性质。

有等式约束、不等式约束、混合约束等

复杂环境的搜索

不确定性的环境（假设环境是完全可观察的）

吸尘器问题引入动作的不确定性

扩展转移模型

Result函数返回的不再是单个状态，而是一组可能的状态

扩展解

与或树

循环解

考虑移动动作的不确定性：移动可能失败（呆在原地）

存在一个循环解（cyclic solution），即反复尝试Right动作，直到它生效。我们可以用一个新的while结构来表示上述过程：

完全不可观察的环境（Agent没有任何传感器）

无传感器的吸尘器

我们称，智能体可以强迫（coerce）世界到达状态7。

无传感器问题的解是一个动作序列，而不是条件规划（因为它没有感知）

搜索信念状态空间

我们将底层物理问题转化为信念状态问题，即对信念状态而非物理状态进行搜索。信念状态空间包含物理状态的每一个可能子集。如果原问题P有N个状态，那么信念状态问题有2^N个信念状态，尽管有很多状态都无法从初始状态到达。

信念状态空间搜索的形式化