Part I · 第 1 章
引言 Introduction
第 1 章没有公式和算法,但它定下了全书的「世界观」:什么问题叫规划?不同学科说的规划有什么共同点?一个规划问题由哪些要素组成?计划被算出来之后又怎么用?读懂这一章,后面每一部分你都能放进同一个框架里理解。
1.1 规划「规划」 Planning to Plan
「规划」在不同群体里意思不太一样。书里对比了三个社区:
| 社区 | 他们说的「规划」 | 典型例子 |
|---|---|---|
| 机器人学 | 把人给出的高层任务描述转换成低层的运动描述。常用术语是运动规划(motion planning)和轨迹规划(trajectory planning)。经典的运动规划通常忽略动力学等微分约束,只关心让物体平移和旋转;轨迹规划则是拿到运动规划的解之后,决定如何沿着它运动,使之满足机器人的机械限制。近年的工作也开始考虑不确定性、微分约束、建模误差和最优性。 | 钢琴搬运工问题(Piano Mover's Problem):给定房子和钢琴的精确 CAD 模型,算出怎样把钢琴从一个房间搬到另一个房间而不碰到任何东西。 |
| 控制论 | 历史上关注为微分方程描述的物理系统设计输入(机械、电子,甚至化学、经济、社会系统)。经典控制论发展了反馈策略(feedback policy,执行中能自适应地响应),重视稳定性(不让动力学失控),也很强调优化资源消耗(能量、时间)。近年控制文献里,运动规划有时指为非线性动力系统构造输入,使其从初始状态到达目标状态。 | 遥控一艘在冰面上滑行的气垫船,让它从静止出发、最后静止在另一个地点。即使在忽略模型误差的理想模拟器里,算出所需输入也已经很难。 |
| 人工智能 | 「规划」和「AI 规划」更偏离散:不是在连续空间里搬钢琴,而是解谜题、或完成离散建模的任务。很自然地定义有限动作集,作用在离散状态集上,解是一个合适的动作序列。AI 里还花了大量精力研究表示语言(本书不是重点),近年也把决策论引入规划来建模不确定性、对抗和优化(Part III)。 | 魔方、滑块拼图(图 1.1)、搭积木。 |
那「规划」到底有没有特定含义?不然什么都能算规划了。书的态度是:先把规划看成算法的一个分支——所以书名叫 Planning Algorithms。重点是各学科里规划问题的算法与计算问题;但它不局限于组合数学和渐近复杂度分析(纯算法领域的主要关注点),还包括很多本身不一定是算法、但有助于建模、求解和分析规划问题的概念。
执行计划的一方:robot(机器人)、decision maker(决策者)、agent(智能体)、controller(控制器)、博弈中的 player(参与者)。
计划本身:plan(计划)、policy(策略)、control law(控制律)。
书里关心的是:为一个或多个决策者找到策略的规划算法。
自然要问的问题:什么是计划?计划如何表示?如何计算?要达成什么?如何评价它的好坏?谁(什么)来用它?本章给出这些问题的一般回答。至于「谁用计划」,取决于应用:大多数情况下由算法执行,但用户也可以是人——比如规划算法给你一个投资策略。
1.2 动机示例与应用 Motivational Examples and Applications
为什么学规划算法?书里给了两个理由:一是有趣——让机器解决连人都觉得很难的问题,涉及建模、设计高效算法和实现鲁棒系统;二是有用——规划算法已经在机器人、制造、药物设计、航天等行业广泛成功,而且还在快速增长。下面按「这本书在哪一部分讲它」整理了 1.2 节的例子:
- 离散 vs 连续:魔方和滑块拼图因为运动部件的规则性和对称性,很容易离散化;Alpha 1.0 拼图(图 1.2)没有这些性质,只能在连续空间里规划——它是专门设计来同时为难人类和运动规划算法的基准。
- 从「玩」到「产业」:看起来纯属游戏的拼图问题,在汽车装配中真实存在(图 1.3),用软件直接操作 CAD 模型可以省掉昂贵、耗时的实体样机。
- 感知多就好吗?移动机器人可以装很多传感器来精确估计环境和自身位姿(图 1.7 的建图),也可以做成低成本、几乎不感知却能可靠完成特定任务的机器人——这种取舍在第 11、12 章仔细讨论。
- 约束越来越多:泊车引入微分约束(车只能沿后轮方向运动,nonholonomic);高速驾驶还要考虑动量;越野高速驾驶同时涉及动力学、不确定性和避障,仍有大量未解的研究问题。
1.3 规划的基本要素 Basic Ingredients of Planning
虽然本书覆盖的模型和问题很广,但几乎所有主题里都会出现以下几个基本要素:
- 状态:规划问题都有一个状态空间,刻画所有可能出现的情形——机器人的位置和朝向、拼图中方块的位置、直升机的位置和速度……离散(有限或可数无限)和连续(不可数无限)的状态空间都允许。一个反复出现的主题:状态空间通常被规划算法隐式表示——大多数应用里它的大小(状态个数或组合复杂度)太大,根本无法显式表示。但状态空间的定义仍然是形式化规划问题、设计和分析算法的重要组成部分。
- 时间:所有规划问题都是一串随时间做出的决策。时间可以显式建模(比如尽快开车穿过障碍赛道),也可以是隐式的——只体现「动作必须一个接一个」,比如还原魔方:具体时刻不重要,顺序才重要。钢琴搬运的解可以做成动画,但计划不规定速度,这也是隐式时间。时间也可以离散或连续;连续时可以想象计划在做一个连续统的决策。
- 动作:计划产生动作来操纵状态。AI 里常叫 actions、operators;控制论和机器人学里叫 inputs、controls。形式化里必须说明施加动作后状态如何变化:离散时间用状态值函数,连续时间用常微分方程。大多数运动规划问题避免显式提时间,直接给出连续状态空间中的一条路径(它可以由微分方程积分得到,但没必要)。有些问题中动作也可以由自然选择——它干扰结果、不受决策者控制,这样就引入了不可预测性(第 10 章)。
- 初始状态与目标状态:通常从某个初始状态出发,试图到达某个指定的目标状态,或目标集合中的任意一个状态。
- 准则:用状态和执行的动作来刻画想要的结果。按准则分两类关注点:
- 可行性(feasibility):找到一个能到达目标状态的计划,不管效率。
- 最优性(optimality):在可行的基础上,按某种仔细定义的方式优化性能。
- 计划:一般来说,计划给决策者施加一个特定的策略或行为。它可以只是一个动作序列,也可以更复杂:如果无法预测未来状态,计划可以把动作规定为状态的函数——不管未来到达哪个状态,都能确定合适的动作,这就是反馈(feedback)或反应式(reactive)计划。甚至状态都可能测不到,这时只能根据到当前为止能获得的信息来决定动作——这叫信息状态(information state),计划以它为条件。
对本书大多数问题来说,光是可行性就已经很有挑战;最优性对大多数问题要难得多。所以本书很多地方关注找到可行解,而不是最优解。机器人学、控制论等领域的大多数文献关注最优性,但这对很多感兴趣的问题并不一定重要:很多应用中连「该优化什么准则」都很难写出来;就算写出来了,也可能无法得到计算最优计划的实用算法——这时有可行解当然比没有解强。好在很多算法给出的解在实践中离最优并不远。不过对于带概率不确定性的问题,优化出现得更频繁:概率常被用来获得期望代价意义下的最好性能;而可行性通常对应对不确定性做最坏情况分析。
下面这张表把六个要素套到几个不同的问题上——注意同一套语言如何覆盖离散谜题、连续运动和不确定性:
表里「例子」那一列是根据书中各处的描述整理的,用来帮助理解;后面几列里提到的章节就是书中处理这类问题的地方。
1.4 算法、规划器与计划 Algorithms, Planners, and Plans
1.4.1 算法
什么是规划算法?这是个难题,书中不给精确的数学定义,而是解释大意并给出很多例子。更基本的问题是:什么是算法?理论计算机科学的经典回答是 Turing 机:一个有限状态机加一个读写头,可以在一条无限长的纸带上读写(图 1.15)。Church–Turing 论题说:算法就是 Turing 机。输入被编码成符号串(通常是二进制)写在纸带上,Turing 机读取、计算,然后决定接受还是拒绝——这个版本只解决判定问题,但很容易扩展出其他输出,比如一个计划。
Turing 模型对书中很多算法是合理的,但有些并不完全合适,因为计划经常要和物理世界交互:
- 机器与环境之间的边界是一条任意画的线,因问题而异(图 1.16a)。一旦画定,传感器向机器提供环境信息(执行时的输入),机器执行动作对环境施加作用(输出),作用可能改变环境,之后又被传感器测到——机器和环境在执行中紧密耦合。这是机器人学和其他用到规划的领域的根本特征。
- 以 Turing 机为基础,通常意味着必须先把物理世界仔细建模、写到纸带上,算法才能做决策。如果执行过程中世界变了(比如有人在机器人周围走动;或者机器人把东西扔到桌上却无法精确预测它停在哪里),就不清楚该怎么办。可以用传感器测量结果,但该把多少信息显式建模写上纸带又成了难题。
- 在线算法(on-line algorithm)模型更适合这类问题,但它仍不足以涵盖本书所有主题。
- 物理世界中的过程比「状态机 + 一条符号纸带」复杂得多。甚至可以用一个机器人和一排无限长的开关来模拟纸带(图 1.17)——机器人携带的计算机模拟有限状态机。机器人与环境之间允许的复杂交互,可能产生许多别的计算模型。
因此本书对「算法」一词的使用比计算理论更不正式。规划器和计划都被当作算法。
1.4.2 规划器
规划器(planner)就是构造计划的东西,可以是机器,也可以是人。如果是机器,一般就称为规划算法——很多时候它是严格的 Turing 意义下的算法,但不必如此。有时人也会成为规划器:设计出一个在所有情形下都能工作的计划。例如人完全可以设计一个连接到环境的状态机(12.3.1 节)——这时没有额外输入,因为人自己扮演了算法的角色:规划模型作为输入交给人,人「计算」出计划。
1.4.3 计划的三种用法
计划确定之后,有三种用法:
- 执行(Execution):在仿真中或在连接物理世界的机械装置(机器人)上执行。
- 精化(Refinement):把它改进成一个更好的计划。
- 层级包含(Hierarchical Inclusion):把它打包成更高层计划中的一个动作。
- 执行有两种类型。(a) 规划器产生计划,以某种方式编码后输入给机器——机器是可编程的。一般假设计划交出去后机器就自主运行、不再和规划器交互(实践中当然可以更新计划,但本书不提倡:计划本身就应该考虑执行时出现的新信息)。(b) 规划器产生的计划编码了整台机器——计划就是一台为原始任务专门设计的机器。这时可以做一个「极简主义者」,设计足以完成任务的最简单的机器;如果它是有限状态机,有时也可以看作 Turing 意义下的算法。
- 精化:规划器接受一个计划作为输入,输出一个(希望是)更好的计划——考虑更多问题因素,或者只是更高效。可以反复精化,最后执行最终版本。机器人学里沿用了几十年的流程(图 1.19):先算无碰撞路径 → 改成满足车轮微分约束的路径 → 决定以什么速度沿路径走(考虑动量)→ 加入反馈使机器人在不可预测的扰动下尽量贴着路径走。这种做法的取舍在 14.6.1 节进一步讨论。
- 层级包含:原计划成为更大计划中的一个动作,就像子程序。为此原计划必须保证终止,这样大计划才能继续执行后面的动作。层级包含可以做任意多次,得到一棵计划树:每个顶点是一个计划,根是主计划,一个顶点的孩子是被当作动作纳入它的那些计划;树的深度和每个顶点的孩子数都不受限制。在层级规划中,机器与环境的分界线被画在多个地方:机器 \(M_1\) 的环境 \(E_1\) 可能包含另一台机器 \(M_2\),\(M_2\) 又与它自己的环境 \(E_2\) 交互(图 1.20)。层级规划的例子见 7.3.2 和 12.5.1 节。
1.5 全书结构 Organization of the Book
全书分四个部分。点下面任一章,可以看到书中对它的描述和阅读建议,以及它的前置章节(蓝色)和依赖它的章节(绿色):
- 想学运动规划(Part II,连续状态空间):2.1、2.2 节最重要。
- 想学不确定性下的规划(Part III):还要读 2.3 节(动态规划、值迭代);Part III 的大部分讨论离散状态空间,读完 Part I 就可以直接开始。
- 微分约束(Part IV)建立在 Part II 之上,状态空间同时包含位置和速度(即控制论里的状态空间、物理里的相空间)。
本章要点
- 机器人学、控制论、AI 说的「规划」侧重点不同(连续运动 / 反馈与稳定 / 离散动作序列),本书把它们统一看作规划算法。
- robot、agent、controller、decision maker 是同义词;plan、policy、control law 也是。
- 六个要素:状态、时间、动作、初始与目标、准则(可行 vs 最优)、计划(动作序列 / 反馈 / 基于信息状态)。
- 状态空间通常太大,只能隐式表示——这个主题贯穿全书。
- 可行性本身往往就很难,本书很多时候只求可行解。
- 机器与环境的边界是人为画的;Turing 机模型在与物理世界交互时不够用,所以本书对「算法」的用法较宽松,规划器和计划都算算法。
- 计划可以被执行、精化或层级包含。