Lecture 01 导论

1. 课程简介

1.1 教学人员

讲师
- Chris Ewin
  2018 年 PhD 毕业于墨尔本大学。主要研究兴趣为自动规划领域：
  - 知识表示（Knowledge representation）
  - 富域规划（Planning in rich domains）
  - 情景演算（Situation Calculus）
  爱好：网球 🎾
  办公室：DMD building, ofﬁce 9.23
  邮箱：cewin@unimelb.edu.au
- Tim Miller
  2005 年 PhD 毕业于昆士兰大学。主要研究兴趣为人工智能领域：
  - 多智能体环境下的决策（Decision making in multi-agent environments）
  - 行动与知识推理（Reasoning about action and knowledge）
  - 自动规划（Automated planning）
  - 人机交互与协作（Human-agent interaction and collaboration）
  爱好：咖啡 ☕️ 以及与之相关的一切办公室：DMD building, ofﬁce 6.09
  邮箱：tmiller@unimelb.edu.au
助教团队
来自一些以前在这门课程中拿到高分的学生，以及一些 PhD 和 Research 的学生：
- 主管助教：Guang Hu
  办公室：DMD building, ofﬁce 6.13
  邮箱：ghu1@student.unimelb.edu.au
- 助教
  Prashan Mathugama, Anam Ahmad Khan, Anubhav Singh, Ruihan Zhang

1.2 研讨会

Workshops 将从第 2 个教学周开始
由于 COVID-19 疫情影响，以下时间段的 workshops 将改为线上模式：
- Mon, 16:15-17:15. Location: PAR-207-221 Bouverie St-B132
- Mon, 17:15-18 :15. Location: PAR-Elec. Engineering-122
- Tue, 18:15-19 :15. Location: PAR-Elec. Engineering-121
- Fri, 12:00-13:00, Location: PAR-Engineering B-313
注意：请仅在受到 COVID-19 疫情影响的情况下注册线上模式。
Zoom 链接将在 LMS 上提供。

1.3 课程大纲

AI 与自动规划导论
经典规划：有很多强假设（strong assumptions），我们基于这些假设求解规划问题。
- 启发式搜索（Heuristic Search）
- 基于宽度搜索（Width-Based Search）
超越经典规划：
- 无因子模型（Factored-Model-Free）
- 非决定论（Non Determinism）
- 不确定性（Uncertainty）
- 软目标（Soft goals）
- 规划识别（Plan Recognition）
- 认知（社会）规划（Epistemic (social) Planning）
- 路径计划（Path-Planning）
- 控制（Control）
强化学习（Reinforcement Learning）：从经验中学习
多智能体规划（Multi agent Planning）
关于人工智能伦理（AI Ethics）的热门 / 最新讨论

作业：2 次个人作业；1 次比赛形式的作业。

1.4 预备知识

算法相关知识，例如：动态规划
基本集合论与命题逻辑
概率论，例如：条件概率
Python

重要的是，你需要及时复习和理解讲义，因为大多数讲座都是建立在以前的知识基础上的。

一个在线演示规划算法的网站：https://qiao.github.io/PathFinding.js/visual/

2. 关于人工智能的定义

我们将就以下话题展开一些简短的讨论：

AI 的概念：当我们谈论 AI 时，我们究竟在谈论什么？
弄清（现代）人工智能的研究领域正在做、不会做和将要尝试做的事情。
AI 的历史：这一切是如何发生的？
一个简短的背景介绍：我们是如何从 “经典 AI” 转变为 “现代 AI” 的。
AI 的现状：技术和应用前景如何？
一段粗略的概述和一些例子。

2.1 什么是人工智能？

关于人工智能的定义，一种工程学的观点是：

“The science of making machines do things that would require intelligence if done by humans.”

—— Marvin Minsky

在70年的人工智能浪潮中，马文 $\cdot$ 明斯基（Marvin Minsky）是一个如雷贯耳的名字，与机器学习、神经网络、虚拟现实、框架理论等热门名词紧紧联系在一起。他是定义和发展 “人工智能” 的先驱者之一，也是人工智能领域的首位图灵奖获得者，被尊称为 “人工智能之父”。

关于人工智能，Minsky 给出的定义是：人工智能这门学科研究的是如何制造出能完成某些事情的机器，而这些事情如果由人类来完成的话，则需要涉及到智能。

但是，这种定义是否具有可操作性可能需要打个问号：

我们如何能够知道哪些人类活动涉及到智能？
另外，如何定义人类的智能？

2.2 图灵测试

图灵测试（The Turing test）由艾伦·麦席森·图灵发明，指测试者与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。进行多次测试后，如果有超过30%的测试者不能确定出被测试者是人还是机器，那么这台机器就通过了测试，并被认为具有人类智能。图灵测试一词来源于计算机科学和密码学的先驱阿兰·麦席森·图灵写于 1950 年的一篇论文《计算机器与智能》，其中 30% 是图灵对 2000 年时的机器思考能力的一个预测，目前我们已远远落后于这个预测。

但是，它目前还只能从理论上证明，无法被复现出来。

2.3 另一种关于人工智能的定义

这里是另一种关于人工智能的视角：

“The exciting new effort to make computers think. Machines with minds, in the full and literal sense.”

—— John Haugeland

和 Minsky 给出的定义存在同样的问题：

什么是 thinking（思考）？
什么是 mind（心灵）？

2.4 一种理性的视角

关于人工智能，这里给出了一种理性的视角：

“The branch of computer science that is concerned with the automation of intelligent behavior.”

—— Luger and Stubbleﬁeld

智能行为（Intelligent behavior）：做出 “好的”（理性的）选择
人类真的是 “理性（rational）” 的 Agents 吗？
我们经常犯错；我们并不全是国际象棋大师，即便我们可能已经知道关于国际象棋的所有规则。更多关于人类系统性的错误可以参考 Daniel Kahneman 的著作 Thinking, fast and slow。

2.5 理性 Agent

Agents：
- 通过传感器（sensors）感知环境（$\to$ 认知（percepts））
- 通过执行器（actuators）对环境采取行动（$\to$ 行动（actions））
$\color{blue}{\to}$ 例如：人类、动物、机器人、软件智能体（软件机器人）等等。
理性 Agent（Rational Agents） 会选择做 “正确的事（the right thing）”。
$\color{blue}{\to}$ 什么是 “做正确的事”？
$\quad$理性 Agent 选择它们的行动（actions）以最大化性能度量（performance measure）
$\color{blue}{\to}$ 问题：一台自动吸尘器的性能度量是什么？
$\quad$每小时清洁面积 $\mathrm{m^2/h}$ 、清洁程度、能耗等等。
$\color{blue}{\to}$ 如果这台自动吸尘器的传感器不够好会发生什么？
尝试做 “正确的事”！
$\to$ 假设的最佳情况（“正确的事”）通常无法达到。
$\color{blue}{\to}$ Agent 可能无法感知所有的相关信息。（例如：床底下是否有污垢？）
理性（Rationality） vs. 全知（Omniscience）：
- 一个全知 Agent（omniscient agent）知道关于环境的一切信息，并且知道它的行动将带来的实际效应。
- 一个理性 Agent（rational agent）只是充分利用了它所拥有的资源，在其感知 (percepts）和知识（knowledge）的基础上最大化了预期的性能。
$\color{blue}{\to}$ 例如：过马路之前，我检查过交通状况。在穿越时，我被一颗陨石击中了。我缺乏理性吗？

将输入映射到可能的最佳输出：

性能度量 $\times$ 感知 $\times$ 知识 $\to$ 行动

$\color{blue}{\to}$ 人工智能作为一种思想大致可以从 思维 vs. 行动 和 人性 vs. 理性 的维度进行分类：

	人性	理性
思维	像人类一样思考的系统（认知科学）	理性思考的系统（逻辑：知识与演绎）
行动	具有类似人类行为的系统（图灵测试）	理性行动的系统（如何做出好的行动选择）

$\to$ 智能的一个核心方面（以及一种可能的定义方式）就是在世界上成功行动的能力。

3. 人工智能简史

AI 的起源：Darmouth 1956

1956 年 8 月，在美国汉诺斯小镇宁静的达特茅斯学院中，约翰$\cdot$麦卡锡（John McCarthy，人工智能之父、LISP 语言发明者）、马文$\cdot$明斯基（Marvin Minsky，人工智能与认知学专家）、克劳德$\cdot$香农（Claude Shannon，信息论的创始人）、艾伦$\cdot$纽厄尔（Allen Newell，计算机科学家）、赫伯特$\cdot$西蒙（Herbert Simon，诺贝尔经济学奖得主）等科学家正聚在一起，讨论着一个完全不食人间烟火的主题：用机器来模仿人类学习以及其他方面的智能。会议的提案是基于这样一种设想：原则上，智能的每一个方面都可以被精确地描述，以至于可以制造一台机器来模拟它。 会议足足开了两个月的时间，虽然大家没有达成普遍的共识，但是却为会议讨论的内容起了一个名字：人工智能。因此，1956 年也就成为了人工智能元年。
Computers and Thought 1963

1963 年出版的 Computers and Thought 杂志收录了一些早期的有关 AI 下国际象棋和跳棋的论文和程序，证明了一些关于逻辑、几何和规划的定理。
AI：60 年代、70 年代和 80 年代 在 60 年代、70 年代和 80 年代早期，人工智能的许多重要贡献都与程序设计和程序中的知识表示有关：
- Lisp（函数式编程）
- Prolog（逻辑编程）
- 基于规则的程序设计
- “专家系统” 的 Shells 和架构
AI 方法论：理论即程序
在 60 年代、70 年代和 80 年代，一篇 AI 相关的学位论文通常是：
- 选择一项任务和一个域 X
- 分析 / 反思 / 找到如何解决任务
- 在程序中刻画这种推理
然后，这篇论文就是：
- 一个关于 X （科学发现、电路分析、计算幽默、故事理解等）的理论，以及
- 一个实现该理论的程序，并通过一些示例进行了测试。
这种工作模式产生了许多很好的想法……但有一个问题……
方法论存在的问题
$\to$ 用程序来表达的理论无法被证伪：当程序失败时，总是可以归咎于 “知识缺失”。

解决问题的三种方法：
- 缩小域（专家系统）
  - 问题：缺少泛化性
- 接受程序只是一种说明或者一种演示
  - 问题：科学价值有限
- 填补缺失的知识（直觉、常识）
  - 问题：到目前为止还没有成功
AI 寒冬：80 年代
$\color{blue}{\to}$ 基于知识的方法在 80 年代陷入僵局，这也是一个充满争议和争论的时代：
- 好的老式 AI 只是一种 “规则应用”，但智能不是（Haugeland）
对主流 AI 的许多批评对于当时有一部分是适用的；对于现在则不太适用。
AI：从 90 年代到 2018
AI 技术的形式化和更多数学知识的应用。一些顶级期刊如 AIJ、JAIR、AAAI 和 IJCAI 上的最新论文的研究领域有：
1. SAT和约束
2. 搜索和规划
3. 概率推理
4. 概率规划
5. 一阶逻辑推理
6. 机器学习
7. 自然语言
8. 视觉和机器人
9. 多智能体系统
$\color{blue}{\to}$ 领域 1 到 4 通常被认为是关于技术的，但更准确的看法是将它们视为模型和求解器。

4. 目前的方向

这些领域背后的共同点是：相比于解决某些特定域下的某些特定问题，我们真正试图尝试的是构建一些智能系统，以解决一些更加通用的问题。

4.1 求解器

\[\mathrm{Problem} \; \Longrightarrow \; \fbox{$\mathrm{Solver_{\,}}$} \; \Longrightarrow \; \mathrm{Solution}\]

例子：

问题：John 的年龄是 Peter 的 3 倍。在 10 年以内，它将变为只有 2 倍。请问 John 和 Peter 现在的年龄是多少？
表示为：$\mathrm{J}=3\mathrm{P}\; ;\;\mathrm{J}+10=2(\mathrm{P}+10)$
求解器：Gauss-Jordan（变量消除）
解为：$\mathrm{P}=10\; ;\;\mathrm{J}=30$

这就是我们如今尝试在做的事情：构建一个可以解决一些通用的问题的求解器。

求解器的 通用性 体现在其能够处理任何可以表示为一个模型实例的问题。
然而，线性方程模型是 易处理的（tractable），我们可以在一个合理的时间内对其进行计算求解；但对于 AI 模型，情况并非如此。

4.2 AI 求解器

\[\mathrm{Problem} \; \Longrightarrow \; \fbox{$\mathrm{Solver_{\,}}$} \; \Longrightarrow \; \mathrm{Solution}\]

基本模型与任务包括：
- 约束满足 / SAT：寻找满足约束的状态
- 规划问题：寻找能够产生所需状态的行动序列
- 带反馈规划：寻找能够产生所需状态的策略
这些模型的求解器是 通用的；并非专门针对某些特定实例。
所有这些模型都是 难处理的（intractable），而且有些模型非常强大。例如：POMDPs（部分可观马尔可夫决策过程）
挑战主要是计算方面的：如何进行大规模扩展。
为此，求解器必须能够 识别和利用（recognize and exploit） 问题的 结构（structure）。
我们采用的方法论是 经验主义的（empirical）：我们不去比较哪种模型更复杂，我们会采用一些现实世界的基准，让不同的模型进行竞争。

4.3 SAT 和 CSPs

SAT（布尔可满足性问题）：确定一组子句（clauses）的组合是否存在可能满足的情况。（即结果为 TRUE）例如：

\[x\lor \lnot y \lor z\lor \lnot w \lor \dots\]

对于上面的例子求解非常简单，可以发现，只要 $x$ 为 TRUE，那么这整个陈述（statement）为 TRUE。如果只有一个子句，这会很简单；但是，很多情况下，我们会遇到包含成千上万的子句的情况，这会导致问题变得非常困难。

事实上，这已经被证明是一个 NP 完全问题。，在实践中这意味着 SAT 算法在最坏情况下，时间复杂度与变量数量之间呈 指数的（exponential） 关系。（例如：$100$ 个变量的时间复杂度为 $2^{100}=10^{30}$）
然而，目前的 SAT 求解器设法解决了 成千上万个变量 和子句的问题，并得到了广泛的应用。（例如：电路的设计、验证、规划等）
约束满足问题（CSPs） 是对 SAT 问题的的泛化，它可以容纳非布尔变量，以及非子句约束。
关键是在搜索树的每个结点中进行 高效（多项式时间）推理：单位解析（unit resolution）、基于冲突的学习（conﬂict-based learning） 等等。
还有很多其他想法从 逻辑上可行，但是 无法实现（无法大规模扩展）：纯搜索、纯推理等。

4.4 经典规划模型

规划（Planning）是实现自主行为（autonomous behavior）的一种 基于模型的方法。
一个系统可以处于很多种 状态（states） 之一。
状态会对一个变量的集合进行赋值。
行动（Actions） 会改变某些特定变量的值。
基本任务：寻找能够驱动初始状态转变为目标状态的 行动序列(action sequence)。

\[\mathrm{Model} \; \Longrightarrow \; \fbox{$\mathrm{Planner_{\,}}$} \; \Longrightarrow \; \textrm{Action Sequence}\]

复杂度：NP 困难；即 最坏情况下，与变量的数量呈指数关系。
规划器（Planner）：是通用的；无论变量是什么，它都应该能在任何域上工作。

5. AI 对于我们的意义

5.1 为什么我们需要这种 AI

国家象棋：2 名玩家的零和游戏（zero-sum game）
音乐 / 语音识别
推荐系统
医疗诊断：决策支持系统
自动驾驶汽车
玩 Atari 游戏：深度学习
……

5.2 为什么我们需要这种 AI 规划

需要更强自主性（autonomy）设定的一些场景：

太空探索：（RAX）第一个人工智能控制系统，无需人为监督即可控制航天器。（1998）
业务流程管理
第一人称视角射击和游戏：经典规划器玩 Atari 游戏
互动故事（Interactive Storytelling）
网络安全
物流 / 运输 / 制造业：多模式运输、森林灭火、PARC 打印机
……

6. 总结：AI 和自动问题求解

过去 20 年出现的 研究议程：一系列 难处理模型（intractable models） 的 求解器。
与其他程序不同，求解器 具有 通用性，因为它们不针对单个问题，而是针对一个问题系列（模型）。
挑战在于计算：如何大规模扩展。
问题的绝对规模 不应妨碍有意义的解决方案。
对于给定问题的结构，必须能够识别和 利用（exploit）。
有很多想法的余地，但方法论是 经验性的。
持续进步
- 有效的推论方法：h 推导、冲突学习……
- 可处理岛（islands of tractability）：树宽度方法（treewidth methods）、松弛（relaxations）
- 转换：收集不完整的信息、扩展目标……

下节内容：搜索算法

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。欢迎转载，并请注明来自：YEY 的博客同时保持文章内容的完整和以上声明信息！

人工智能自动规划 01：导论

墨尔本大学 COMP90054 课程笔记