Planning Algorithms 学习站 首页 › Part I › 第 1 章 引言

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

虽然本书覆盖的模型和问题很广,但几乎所有主题里都会出现以下几个基本要素:

本书的立场:可行性已经够难了

对本书大多数问题来说,光是可行性就已经很有挑战;最优性对大多数问题要难得多。所以本书很多地方关注找到可行解,而不是最优解。机器人学、控制论等领域的大多数文献关注最优性,但这对很多感兴趣的问题并不一定重要:很多应用中连「该优化什么准则」都很难写出来;就算写出来了,也可能无法得到计算最优计划的实用算法——这时有可行解当然比没有解强。好在很多算法给出的解在实践中离最优并不远。不过对于带概率不确定性的问题,优化出现得更频繁:概率常被用来获得期望代价意义下的最好性能;而可行性通常对应对不确定性做最坏情况分析。

下面这张表把六个要素套到几个不同的问题上——注意同一套语言如何覆盖离散谜题、连续运动和不确定性:

表里「例子」那一列是根据书中各处的描述整理的,用来帮助理解;后面几列里提到的章节就是书中处理这类问题的地方。

1.4 算法、规划器与计划 Algorithms, Planners, and Plans

1.4.1 算法

什么是规划算法?这是个难题,书中不给精确的数学定义,而是解释大意并给出很多例子。更基本的问题是:什么是算法?理论计算机科学的经典回答是 Turing 机:一个有限状态机加一个读写头,可以在一条无限长的纸带上读写(图 1.15)。Church–Turing 论题说:算法就是 Turing 机。输入被编码成符号串(通常是二进制)写在纸带上,Turing 机读取、计算,然后决定接受还是拒绝——这个版本只解决判定问题,但很容易扩展出其他输出,比如一个计划。

Turing 模型对书中很多算法是合理的,但有些并不完全合适,因为计划经常要和物理世界交互:

因此本书对「算法」一词的使用比计算理论更不正式。规划器和计划都被当作算法。

1.4.2 规划器

规划器(planner)就是构造计划的东西,可以是机器,也可以是人。如果是机器,一般就称为规划算法——很多时候它是严格的 Turing 意义下的算法,但不必如此。有时人也会成为规划器:设计出一个在所有情形下都能工作的计划。例如人完全可以设计一个连接到环境的状态机(12.3.1 节)——这时没有额外输入,因为人自己扮演了算法的角色:规划模型作为输入交给人,人「计算」出计划。

1.4.3 计划的三种用法

计划确定之后,有三种用法:

  1. 执行(Execution):在仿真中或在连接物理世界的机械装置(机器人)上执行。
  2. 精化(Refinement):把它改进成一个更好的计划。
  3. 层级包含(Hierarchical Inclusion):把它打包成更高层计划中的一个动作。

1.5 全书结构 Organization of the Book

全书分四个部分。点下面任一章,可以看到书中对它的描述和阅读建议,以及它的前置章节(蓝色)和依赖它的章节(绿色):

读完 Part I 之后怎么走
  • 想学运动规划(Part II,连续状态空间):2.1、2.2 节最重要。
  • 想学不确定性下的规划(Part III):还要读 2.3 节(动态规划、值迭代);Part III 的大部分讨论离散状态空间,读完 Part I 就可以直接开始。
  • 微分约束(Part IV)建立在 Part II 之上,状态空间同时包含位置和速度(即控制论里的状态空间、物理里的相空间)。

本章要点

  1. 机器人学、控制论、AI 说的「规划」侧重点不同(连续运动 / 反馈与稳定 / 离散动作序列),本书把它们统一看作规划算法。
  2. robot、agent、controller、decision maker 是同义词;plan、policy、control law 也是。
  3. 六个要素:状态、时间、动作、初始与目标、准则(可行 vs 最优)、计划(动作序列 / 反馈 / 基于信息状态)。
  4. 状态空间通常太大,只能隐式表示——这个主题贯穿全书。
  5. 可行性本身往往就很难,本书很多时候只求可行解。
  6. 机器与环境的边界是人为画的;Turing 机模型在与物理世界交互时不够用,所以本书对「算法」的用法较宽松,规划器和计划都算算法。
  7. 计划可以被执行、精化或层级包含。