【人工智能】问题形式化

【人工智能】问题形式化

引例

• 我们需要从阿拉德（Arad），到达首都布加勒斯特（Bucharest）期间只能开车从相邻的城市穿过，不能一次性坐飞机到达。要完成这个任务，如何和人工智能的搜索扯上关系，如图：

• 智能体的目标是开车去布加勒斯特。我们将目标考虑成是世界的一个状态集合，目标被满足的那些状态的集合。比如其中的一个状态集合{Arad、Sibiu、Fagaras、Bucharest}智能体沿着这条路（这个状态集合）就能够到达目的地。如下图红色箭头所示：

• 智能体的任务是找出现在和未来如何行动，以使它达到一个目标状态。为达到目标，寻找这样的行动序列的过程被称为搜索（智能体在搜索上面红色箭头的路径的过程被称为搜索）。
• 搜索算法的输入是问题，输出是问题的解，以行动序列的形式返回问题的解。解一旦被找到，它所建议的行动将会付诸实施，这被称为执行阶段。
• 那么，我们通过形式化，搜索和执行就完成了对智能体的简单设计。
• 问题的形式化是在给定目标下确定需要考虑哪些行动和状态的过程。现在我们假设智能体将在开车从一个主要城镇到另一个城镇的层次上考虑行动。因此**每个状态表示智能体在一个特定的城镇中，比如说智能体在Pitesti城市，那么可以说智能体的状态就可以表达为< Pitesti >**。
• 那么我们将上面例子的相关知识总结概括一下就是：- 目标形式化： - 到达布加勒斯特- 问题形式化： - 状态：不同的城市- 动作：城市间行驶- 问题的解： - 城市序列：比如Arad、Sibiu、Fagaras、Bucharest
• 我们最终的解就是城市序列，智能按照这个序列执行动作（这里指的是开车到达下一个状态）一步一步执行，就能到达最后的目标状态。
• 通过这个栗子，引出通用的问题形式化!

问题形式化

• 一个问题可以由四个组成部分来形式化：1. 初始状态（智能体一开始的初始状态）2. 动作或后续函数（智能体能够执行的动作，以及执行该动作后获得的代价）3. 目标测试（智能体对所在状态进行一个判断该状态是否为终止状态的操作）4. 路径代价（到达目标状态到时候，评价一下从初始状态经过的动作序列获取的总代价）
• 其中一个解是从初始状态到目标状态的动作系列，简单来说，智能体的问题都可以描述为：- 定义智能体的初始状态，找出智能体可以走的动作序列，然后进行执行，执行后得到的新状态，智能体对目前状态进行目标状态的测试。 - 如果不是目标状态，则将从初始状态达到该新状态的代价保存起来，继续重复寻找该新状态可以执行的动作。- 如果是目标状态，则over，返回从初始状态到达该目标状态的总代价即可。

举个栗子

1. 假如我们现在有一个吸尘器，对两个房子进行吸收尘灰，目标是两个房子都干净，那么这个问题如何形式化为智能体的搜索问题。也就是如何找到这个问题的四个部分：初始状态、动作或后续函数、目标测试、路径代价- 很容易得到四个部分分别如下：- 1. 状态：机器人的位置及灰尘位置2. 动作：向左、向右、吸尘3. 目标测试：所有位置均无尘4. 路径代价：一个动作的代价为1

• 由此将一个问题建模成了智能体的搜索问题

1. 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 - 这个问题的目标是将初始状态转移到目标状态的最小步数。比如初始状态是下面这个：- 目标状态是这个：- 我们的目标就是将初始状态变为目标状态所需要的最小步数，应该怎么做？那么这个问题，我们应该如何形式化呢？- 还是找到那四个关键基本组成部分：初始状态、动作或后续函数、目标测试、路径代价1. 状态：8个数字的放置情况2. 动作：空格向上、向下、向左、向右移动3. 目标测试：目标状态(给定的)4. 路径代价：每移动一步的代价为1

[1] ​《人工智能-问题形式化》 忆臻 PhD Candidate（MLNLP社区）