Problem-solving agent

• Deterministic, fully observable ⇒ single-state problem
Agent knows exactly which state it will be in; solution is a sequence
• Non-observable ⇒ conformant problem
Agent may have no idea where it is; solution (if any) is a sequence
• Nondeterministic and/or partially observable ⇒ contingency problem
percepts provide new information about current state
solution is a contingent plan or a policy
often interleave search, execution
• Unknown state space ⇒ exploration problem (“online”)

确定性，完全可观察的 => 单一状态问题：

• 在一个确定性和完全可观察的环境中，智能体总是能精确地知道自己处于哪个状态，因为环境的行为是可预测的，所有相关信息都对智能体是可见的。

不可观察的 => 一致性问题：

• 在一个不可观察的环境中，智能体可能不知道它当前的状态。这意味着智能体必须规划出一组无论实际状态如何都能确保达到目标的行为。应急问题的解决方案是一个应急计划或策略。应急计划规定了根据智能体的感知（提供了关于当前状态的新信息）来采取的行动。策略是一种通用策略，告诉智能体在不同情况下应该做什么。智能体通常将搜索（规划下一步）与执行（执行计划并观察结果）相结合。

非确定性和/或部分可观察的 => 应急问题：

• 在一个非确定性的环境中，行动的结果是不确定的，而在一个部分可观察的环境中，智能体没有关于当前状态的所有信息。

未知状态空间 => 探索问题（“在线”）：

• 当状态空间未知时，智能体必须探索环境以了解它，同时尝试解决问题。

  Problem Formulation

1. 初始状态(initial state)：问题的起点，例如“在阿拉德（Arad）”。

   • 这是指智能体开始解决问题时的具体状态。

2. 动作(actions)：智能体可以执行的操作，例如“驾车从阿拉德到泽林德（Arad → Zerind）”。

   • 这些动作定义了智能体如何从一个状态转移到另一个状态。

3. 后继函数 S(x)(successor function)：给定状态 x，返回一组动作-状态对，例如 S(Arad) = {〈Arad → Zerind, Zerind〉, …}。

   • 这个函数描述了从当前状态可以采取的所有可能动作以及这些动作将导致的新状态。

4. 目标测试(goal test)：判断一个状态是否是目标状态，可以是显式的或隐式的。

   • 显式：例如，状态 x = “在布加勒斯特（atBucharest）”。
   • 隐式：例如，NoDirt(x)，表示某个条件满足时即为目标状态。

5. 路径成本（累加的）(path cost  additive)：从初始状态到目标状态的行动总成本，例如行驶距离的总和、执行的动作数量等。

   • c(x, a, y) 是单步成本，假设它大于或等于 0。
   • 路径成本用于评估不同解决方案的效率。

解决方案(solution)：从初始状态到目标状态的一系列动作。 

Selecting a state space

Example: The 8-puzzle

 

1. 状态（States）

• 定义：在8拼图问题中，状态是指拼图板上各个数字瓷砖的整数位置。
• 分析：每个瓷砖只能占据一个特定的位置，因此整个拼图板的状态可以用一个9个整数的数组来表示，其中每个整数代表一个瓷砖，0代表空白格。例如，一个3x3的拼图板可能的状态是 [1, 2, 3, 4, 5, 6, 7, 8, 0]，其中数字按照从左到右、从上到下的顺序排列。
• 注意：在考虑状态时，我们忽略了瓷砖移动过程中的中间位置，只关心瓷砖在格子中的最终位置。

2. 动作（Actions）

• 定义：动作是指可以将空白格（0）移动到相邻位置的操作。
• 具体动作：
  • 向左移动空白格
  • 向右移动空白格
  • 向上移动空白格
  • 向下移动空白格
• 分析：每个动作都假设空白格旁边有一个可移动的瓷砖，且移动是合法的（即空白格不能在边界外移动）。我们忽略了如“解卡”等复杂动作，只考虑基本的移动。

3. 目标测试（Goal Test）

• 定义：目标测试是用来判断当前状态是否是目标状态。
• 分析：在8拼图问题中，目标状态是预先给定的，通常是 [1, 2, 3, 4, 5, 6, 7, 8, 0]。智能体需要比较当前状态与目标状态，如果两者相同，则目标测试通过。

4. 路径成本（Path Cost）

• 定义：路径成本是指从初始状态到达目标状态所执行动作的总成本。
• 分析：
  • 在8拼图问题中，每个动作的成本被定义为1。
  • 因此，路径成本就是从初始状态到目标状态所执行的动作数量。

 State Spaces

• For finite state spaces, we can enumerate 
• For infinite state spaces, we need to define a function that generates the next state

 对于有限状态空间，可以枚举

对于无限状态空间，需要定义一个函数，该函数能够根据当前状态和执行的动作生成下一个状态。

Solving Problems 

• n.S T AT E: the corresponding state in the state-space
• n.P ARE N T : the node that generated n
• n.AC T I ON : the action applied to n.P ARE N T which resulted in n
• n.P AT H-C OS T : the cost of the path from the initial state to n, as indicated by the P ARE N T pointers

• n.STATE: 这是节点n在状态空间中对应的状态。在搜索算法中，每个节点代表状态空间中的一个特定状态。

• n.PARENT: 这是生成节点n的节点。在搜索树中，每个节点（除了初始节点）都有一个父节点，表示它是通过在父节点上应用某个动作而生成的。

• n.ACTION: 这是应用于n.PARENT并导致生成节点n的动作。换句话说，这是从父节点移动到当前节点所采取的动作。

• n.PATH-COST: 这是从初始状态到节点n的路径成本。这个成本是通过沿着从初始节点到当前节点的父指针链累加计算得出的。路径成本通常用来评估不同路径的优劣。

Tree search

• Expansion takes place by applying successor functions to the selected node,
providing new states.
• Nodes that have been generated, but not expanded are referred to as the frontier or
fringe.
• Different search strategies behave very differently.
• The search tree is not the same as the state space. In the route finding example,
there are 20 nodes in the state space, but the search tree has an infinite number of
nodes.

在搜索算法中，扩展（Expansion）是一个关键步骤，它涉及到对已选定的节点应用后继函数（successor function），从而生成新的状态。这些新状态可能会是目标状态，也可能需要进一步扩展。扩展是搜索算法发现新状态并探索状态空间的关键步骤。

在搜索过程中，有些节点虽然已经被生成，但还没有被扩展。这些节点被称为前沿（frontier）或边缘（fringe），它们是搜索树中等待进一步扩展的节点集合。前沿是搜索算法关注的焦点，因为只有扩展前沿中的节点，才能发现新的状态并继续搜索。

不同的搜索策略在处理前沿和扩展时会有非常不同的行为。例如，宽度优先搜索（BFS）会优先扩展前沿中的节点，而深度优先搜索（DFS）会优先扩展当前路径上的节点。这些策略的选择会影响算法的效率、可扩展性和找到解决方案的可能性。

需要注意的是，搜索树并不是状态空间本身。在路径查找等问题的例子中，状态空间可能包含20个节点，但搜索树可以包含无限多个节点，因为它可能会无限地扩展，直到找到目标状态或达到某个终止条件。

每次都将节点的周围节点展开