1.2 State Spaces and Search Problems (状态空间与搜索问题)
为了创建一个理性的规划智能体，我们需要一种方法来数学地表达智能体将存在的给定环境。为此，我们必须正式表达一个 search problem（搜索问题）——给定我们智能体的当前 state（状态）（其在环境中的配置），我们如何到达一个以最佳方式满足其目标的新状态？一个搜索问题由以下要素组成：
- State space（状态空间） - 给定世界中所有可能状态的集合
- 每个状态下可用的 actions（动作）集合
- Transition（转换）模型 - 在当前状态下采取特定动作时输出下一个状态
- 动作 cost（成本） - 在应用动作后从一个状态移动到另一个状态时产生
- Start state（开始状态） - 智能体最初存在的状态
- Goal test（目标测试） - 一个将状态作为输入并确定它是否为目标状态的函数
从根本上说，解决搜索问题的方法是首先考虑开始状态，然后使用动作、转换和成本方法探索状态空间，迭代计算各种状态的子状态，直到我们到达目标状态，此时我们将确定从开始状态到目标状态的路径（通常称为 plan（计划））。考虑状态的顺序是使用预定的 strategy（策略）确定的。我们将很快介绍策略的类型及其有用性。
在继续讨论如何解决搜索问题之前，重要的是要注意 world state（世界状态）和 search state（搜索状态）之间的区别。世界状态包含有关给定状态的所有信息，而搜索状态仅包含规划所需的有关世界的信息（主要是出于空间效率的原因）。为了说明这些概念，我们将介绍本课程的标志性激励示例——Pacman（吃豆人）。Pacman 游戏很简单：Pacman 必须在迷宫中导航并吃掉迷宫中所有的（小）食物颗粒，而不被恶意的巡逻幽灵吃掉。如果 Pacman 吃掉其中一个（大）能量颗粒，他在一段时间内对幽灵免疫，并获得吃掉幽灵得分的能力。
让我们考虑游戏的一个变体，其中迷宫只包含 Pacman 和食物颗粒。在这种情况下，我们可以提出两个截然不同的搜索问题：寻路和吃掉所有豆子。寻路试图解决在迷宫中以最佳方式从位置 \((x_1, y_1)\) 到达位置 \((x_2, y_2)\) 的问题，而吃掉所有豆子试图解决在尽可能短的时间内吃掉迷宫中所有食物颗粒的问题。下面列出了这两个问题的状态、动作、转换模型和目标测试：
Pathing (寻路)
- States (状态): \((x,y)\) 位置
- Actions (动作): North, South, East, West (北、南、东、西)
- Transition model (转换模型) (获取下一个状态): 仅更新位置
- Goal test (目标测试): 是否 \((x,y)=END\)?
Eat-all-dots (吃掉所有豆子)
- States (状态): {\((x,y)\) 位置, 豆子布尔值}
- Actions (动作): North, South, East, West (北、南、东、西)
- Transition model (转换模型) (获取下一个状态): 更新位置和布尔值
- Goal test (目标测试): 是否所有豆子布尔值都为假?
请注意，对于寻路，状态包含的信息少于吃掉所有豆子的状态，因为对于吃掉所有豆子，我们必须维护一个对应于每个食物颗粒的布尔数组，以及它在给定状态下是否已被吃掉。世界状态可能包含更多信息，除了当前的 \((x,y)\) 位置和豆子布尔值之外，还可能编码有关 Pacman 行进的总距离或 Pacman 访问过的所有位置等信息。
1.2.1 State Space Size (状态空间大小)
在估计解决搜索问题的计算运行时，经常出现的一个重要问题是状态空间的大小。这几乎完全是用 fundamental counting principle（基本计数原理）完成的，该原理指出，如果在给定的世界中有 n 个可变对象，它们分别可以取 \(x_1\), \(x_2\), …, \(x_n\) 个不同的值，那么状态的总数是 \(x_1\) · \(x_2\) · … · \(x_n\)。让我们用 Pacman 通过示例来展示这个概念：
假设可变对象及其相应的可能性数量如下：
- Pacman positions（Pacman 位置） - Pacman 可以在 120 个不同的 (\(x\),\(y\)) 位置，并且只有一个 Pacman
- Pacman Direction（Pacman 方向） - 这可以是北、南、东或西，总共 4 种可能性
- Ghost positions（幽灵位置） - 有两个幽灵，每个幽灵可以在 12 个不同的 (\(x\),\(y\)) 位置
- Food pellet configurations（食物颗粒配置） - 有 30 个食物颗粒，每个都可以被吃掉或未被吃掉
使用基本计数原理，我们有 120 个 Pacman 位置，4 个 Pacman 可以面向的方向，\(12 \cdot 12\) 个幽灵配置（每个幽灵 12 个），以及 \(2 \cdot 2 \cdot \ldots \cdot 2 = 2^{30}\) 个食物颗粒配置（30 个食物颗粒中的每一个都有两个可能的值——被吃掉或未被吃掉）。这给了我们总的状态空间大小为 \(120 \cdot 4 \cdot 12^{2} · 2^{30}\)。
1.2.2 State Space Graphs and Search Trees (状态空间图和搜索树)
既然我们已经建立了状态空间的概念以及完全定义一个状态空间所需的四个组件，我们几乎准备好开始解决搜索问题了。拼图的最后一块是状态空间图和搜索树。
回想一下，图是由一组节点和一组连接各种节点对的边定义的。这些边也可能有与之关联的权重。State space graph（状态空间图）是用代表状态的节点构建的，有向边从一个状态存在于其子状态。这些边代表动作，任何关联的权重代表执行相应动作的成本。通常，状态空间图太大而无法存储在内存中（即使是我们上面的简单 Pacman 示例也有 \(\approx 10^{13}\) 个可能的状态，哎呀！），但在解决问题时在概念上牢记它们是很好的。同样重要的是要注意，在状态空间图中，每个状态只表示一次——根本不需要多次表示一个状态，知道这一点在试图推理搜索问题时很有帮助。
与状态空间图不同，我们要关注的下一个结构 search trees（搜索树）对状态可以出现的次数没有这样的限制。这是因为虽然搜索树也是一类以状态为节点、状态之间的动作为边的图，但每个状态/节点不仅编码状态本身，还编码从开始状态到状态空间图中给定状态的整个路径（或 plan（计划））。观察下面的状态空间图和相应的搜索树：
给定状态空间图中的突出显示路径 (S → d → e → r → f → G) 在相应的搜索树中通过跟随树中从开始状态 S 到突出显示的目标状态 G 的路径来表示。同样，从开始节点到任何其他节点的每一条路径都在搜索树中由从根 S 到对应于其他节点的根的某个后代的路径表示。由于通常存在多种从一个状态到达另一个状态的方法，因此状态往往会在搜索树中多次出现。结果，搜索树在大小上大于或等于其对应的状态空间图。
我们已经确定，即使对于简单的问题，状态空间图本身的大小也可能很大，因此问题出现了——如果这些结构太大而无法在内存中表示，我们如何对它们进行有用的计算？答案在于我们如何计算当前状态的子状态——我们只存储我们立即使用的状态，并使用相应的 getNextState、getAction 和 getActionCost 方法按需计算新的状态。通常，搜索问题是使用搜索树解决的，我们在其中非常小心地存储选定的几个节点以便一次观察，迭代地用它们的子节点替换节点，直到我们到达目标状态。存在各种方法来决定进行这种搜索树节点迭代替换的顺序，我们现在将介绍这些方法。