问题求解智能体

智能体可以执行以下 4 个阶段的问题求解过程。

• 目标形式化(goal formulation):智能体的目标为到达 Bucharest。目标通过限制智能体的 目的和需要考虑的动作来组织其行为。
• 问题形式化(problem formulation):智能体刻画实现目标所必需的状态和动作——进而得 到这个世界中与实现目标相关的部分所构成的抽象模型。对智能体来说，一个好的模型 应该考虑从一个城市到其相邻城市的动作，这时，状态中只有“当前所在城市”会由于 动作而改变。
• 搜索(search):在真实世界中采取任何动作之前，智能体会在其模型中模拟一系列动作， 并进行搜索，直到找到一个能到达目标的动作序列。这样的序列称为解(solution)。智能 体可能不得不模拟多个无法到达目标的序列，但最终它要么找到一个解(例如从 Arad 到 Sibiu 到 Fagaras 再到 Bucharest)，要么发现问题是无解的。
• 执行(execution):现在智能体可以执行解中的动作，一次执行一个动作。

一些关键概念：

• 可能的环境状态(state)的集合，状态空间(state space)。
• 智能体启动时的初始状态(initial state)。
• 一个或多个目标状态(goal state)的集合。
• 智能体可以采取的行动(action)。
• 转移模型(transition model)用于描述每个动作所起到的作用。
• 动作代价函数(action cost function)，在编程中记作 Action-Cost(s, a, s’ )，在数学运算中记 作 c(s, a, s’ )。

搜索问题(problem)的形式化定义如下：

• 可能的环境状态(state)的集合，我们称之为状态空间(state space)。
• 智能体启动时的初始状态(initial state)。
• 一个或多个目标状态(goal state)的集合。
• 智能体可以采取的行动(action)。Actions(s) 将返回在 s 中可以执行的有限 a 动作集合。我们称集合中的任一动作在 s 中都是适用的(applicable)。
• 转移模型(transition model)用于描述每个动作所起到的作用。
• 动作代价函数(action cost function)，在编程中记作 Action-Cost(s, a, s’ )，在数学运算中记 作 c(s, a, s’ )。

问题示例

一些问题名字：

• 网格世界(grid world)问题是一个由正方形单元格组成的二维矩形阵列，在这个阵列中， 智能体可以从一个单元格移动到另一个单元格。
• 推箱子问题(sokoban puzzle)；
• 滑块问题(sliding-tile puzzle)中，若干滑块(有时称为块或片)排列在一个有若干空 白区域的网格中，其中滑块可以滑进空白区域，或华容道问题；
• 旅行问题(touring problem)描述的是一组必须访问的地点，而非单一目的地。旅行商问 题(traveling salesperson problem，TSP)，就是一个旅行问题，即地图上每个城市都必须被访问。
• 超大规模集成电路布图(VLSI layout)问题需要在一个芯片上定位数百万个元件和连接 点，以最小化芯片面积、电路延迟和杂散电容，并最大化成品率。
• 机器人导航(robot navigation)是寻径问题的一个推广。

搜索算法

搜索算法(search algorithm)将搜索问题作为输入并返回问题的解或报告 failure(当解不存在 时)。完备的搜索算法探索无限状态空间的方式必须是系统的(systematic)，以确保它最终能够 到达与初始状态相关的任何状态。

问题求解性能评估：

• 完备性(completeness):当存在解时，算法是否能保证找到解，当不存在解时，是否能保 证报告失败?
• 代价最优性(cost optimality):它是否找到了所有解中路径代价最小的解? a
• 时间复杂性(time complexity):找到解需要多长时间?可以用秒数来衡量，或者更抽象地用状态和动作的数量来衡量。
• 空间复杂性(space complexity):执行搜索需要多少内存?