3.1　问题求解智能体

想象一下，一个智能体正在罗马尼亚度假。它想参观景点，想学习罗马尼亚语，想享受罗马尼亚的夜生活但又不想宿醉，等等。这一决策问题是复杂的。现在，假设智能体目前位于Arad，并且买了一张第二天从Bucharest起飞且不能退款的机票。智能体观察路牌后发现，从Arad出发有3条路：一条通往Sibiu，一条通往Timisoara，还有一条通往Zerind。但这都不是它的目的地，所以除非智能体熟悉罗马尼亚的地理环境，不然它不知道该走哪条路。

如果智能体没有额外信息，也就是说，如果环境是 未知的 （unknown），那么智能体只能随机执行一个动作。这种情况将在第4章讨论。在本章中，我们假设智能体总是能够访问与世界相关的信息，例如图3-1中的地图。有了这些信息，智能体可以执行以下4个阶段的问题求解过程。

● 目标形式化 （goal formulation）：智能体的目标为到达Bucharest。目标通过限制智能体的目的和需要考虑的动作来组织其行为。

● 问题形式化 （problem formulation）：智能体刻画实现目标所必需的状态和动作——进而得到这个世界中与实现目标相关的部分所构成的抽象模型。对智能体来说，一个好的模型应该考虑从一个城市到其相邻城市的动作，这时，状态中只有“当前所在城市”会由于动作而改变。

● 搜索 （search）：在真实世界中采取任何动作之前，智能体会在其模型中模拟一系列动作，并进行搜索，直到找到一个能到达目标的动作序列。这样的序列称为 解 （solution）。智能体可能不得不模拟多个无法到达目标的序列，但最终它要么找到一个解（例如从Arad到Sibiu到Fagaras再到Bucharest），要么发现问题是无解的。

● 执行 （execution）：现在智能体可以执行解中的动作，一次执行一个动作。

一个重要的性质是，在一个完全可观测的、确定性的、已知的环境中， 任何问题的解都是一个固定的 动作 序列 ：开车到Sibiu，然后到Fagaras，最后到达Bucharest。如果模型是正确的，那么一旦智能体找到了一个解，它就可以在执行动作时忽略它的感知（“闭上眼睛”），因为解一定会到达目标。控制理论家称之为 开环 （open-loop）系统，因为忽略感知打破了智能体和环境之间的环路。如果模型有可能是不正确的，或者环境是非确定性的，那么监控感知的 闭环 （closed-loop）方法会更安全（见4.4节）。

在部分可观测或非确定性环境中，问题的解将是一个根据感知推荐不同的未来动作的分支策略。例如，智能体可能规划从Arad开车到Sibiu，但还需要一个应变规划，以防它不小心到了Zerind或者发现了“Drum Închis”（道路封闭）的标志。

3.1.1　搜索问题和解

搜索 问题 （problem）的形式化定义如下。

● 可能的环境 状态 （state）的集合，我们称之为 状态空间 （state space）。

● 智能体启动时的 初始状态 （initial state），例如 Ar ad 。

● 一个或多个 目标状态 （goal state）的集合。有时问题只有一个目标状态（如 Bucharest ），有时存在若干个可供选择的目标状态，也有时目标是由一个适用于许多状态（可能是无限多个状态）的属性所定义的。例如，在一个真空吸尘器世界里，目标可能是让任何位置都没有灰尘，而无论该状态的其他情况如何。我们通过给问题指定一个I s -G oal 方法来将这3种可能性都考虑在内。在本章中，为了简单起见，我们有时会直接用“目标”一词，它表示“任一可能的目标状态”。

● 智能体可以采取的 行动 （action）。给定一个状态 s ，A ctions ( s )将返回在 s 中可以执行的有限 动作集合。我们称集合中的任一动作在 s 中都是 适用的 （applicable）。例如：

● 转移模型 （transition model）用于描述每个动作所起到的作用。R esult ( s , a )将返回在状态 s 中执行动作 a 所产生的状态。例如：

● 动作代价函数 （action cost function），在编程中记作A ction -C ost ( s , a , s' )，在数学运算中记作 c ( s , a , s' )。它给出了在状态 s 中执行动作 a 从而转移到状态 s' 的数值代价。问题求解智能体应该使用反映其自身性能指标的代价函数；例如，对于寻径智能体，动作代价可能是以英里为单位的长度（如图3-1所示），也可能是完成动作所花费的时间。

一个动作序列形成一条 路径 （path），而 解 （solution）是一条从初始状态到某个目标状态的路径。我们假设动作代价是可累加的；也就是说，一条路径的总代价是各个动作代价的总和。 最优解 （optimal solution）是所有解中路径代价最小的解。在本章中，我们假设所有的动作代价都为正，以减少复杂性。 ^[1]

状态空间可以用 图 （graph）来表示，图中的顶点表示状态，顶点之间的有向边表示动作。图3-1所示的罗马尼亚地图就是这样一个图，每条道路表示两种动作，即两个方向各表示一种。

3.1.2　问题形式化

我们将前文中去往Bucharest的问题形式化为一个 模型 （model）——一种抽象的数学描述，而不是真实存在的实物。与简单的原子状态描述 Arad 相比，实际的旅行的世界状态包括很多内容：旅行伙伴、当时的广播节目、窗外的风景、附近是否有执法人员、到下一个休息站的距离、道路状况、天气、交通等。所有这些因素都被排除在我们的模型之外，因为它们与寻找前往Bucharest的路线问题无关。

从表示中剔除细节的过程称为 抽象 （abstraction）。一个良好的问题形式化应该具有适度的细节层次。如果智能体的动作细化到“右脚向前移动1厘米”或“方向盘向左转动1度”的层次上，那它可能永远都找不到走出停车场的路，更不用说去Bucharest了。

我们能更精确地定义合适的 抽象层级 （level of abstraction）吗？我们所选择的抽象状态和动作对应于大量具体的世界状态和动作序列。现在考虑抽象问题的解，例如，从Arad到Sibiu，到Rimnicu Vilcea，到Pitesti，再到Bucharest的路径。这个抽象解对应于大量更详细的路径。例如，从Sibiu开往Rimnicu Vilcea的途中，我们可以打开收音机，而在其他的旅程中关掉收音机。

如果我们能够将任何抽象解细化为更详细的世界中的解，那么这种抽象就是合理的；一个充分条件是，对于“in Arad”的每个详细状态，都有一条到达“in Sibiu”状态的详细路径，以此类推。 如果执行解中的每个动作都比原始问题更容易，那么抽象是有用的；在我们的示例中，“从Arad开车到Sibiu”的动作，任何一个一般水平的司机都可以在不进一步搜索或规划的情况下完成。因此，选择一个好的抽象需要删除尽可能多的细节，同时保留合理性，并确保抽象动作易于执行。如果没有构造有用的抽象的能力，智能体将被真实世界完全淹没。

[1] 在任何存在负代价环的问题中，代价最优解为在这个环中循环无限次。不存在负代价环时，Bellman-Ford算法和Floyd-Warshall算法（本章暂未涉及）可以处理负代价动作。只要连续的零代价动作的数量是有限的，处理零代价动作就很容易。例如，假设有一个机器人，其移动的代价为正，但旋转90°的代价为0；只要连续旋转90°动作的数量不超过3个，本章的算法就可以处理这个问题。存在无限多个任意小的动作代价的问题也很复杂。考虑Zeno悖论的情况，存在一个动作，它每次向目标移动剩余距离的二分之一，代价为上一次移动代价的二分之一。这个问题不存在动作数量有限的解，但为了防止搜索在没有完全到达目标的情况下采取无限数量的动作，我们可以要求所有动作的代价至少为， ， 为某个较小的正值。 zOvqi9TBXrzXuEtSyemzGHFjQKWFmiH1FcO/+DgxWU6NsjEwhyvzXFQCYWLYH9p1