【硬核书】规划算法 (Planning Algorithm)，1023页pdf，Steven M. Illinois大学

2022 年 4 月 10 日 专知

规划算法是机器人领域、人工智能领域和控制理论领域中的重要组成部分。这本书提出了许多不同类型的规划算法的统一处理。该学科位于机器人、控制理论、人工智能、算法和计算机图形学的交叉路口。具体课程包括运动规划、离散规划、不确定性下的规划、基于传感器的规划、可见性、决策理论规划、博弈论、信息空间、强化学习、非线性系统、轨迹规划、非完整规划和运动动力学规划。

http://lavalle.pl/planning/

机器人领域（robotics） ：运动规划（motion planning）意味着将一架钢琴从一间屋子搬运到另一间并且确保钢琴不被碰坏。当考虑到复杂的环境，例如不确定性，多物体和动力学后，该领域也随之发展。

人工智能领域（artificial intelligence） :规划意味着通过搜索一系列的逻辑操作(logical operators)或者一些列的动作(actions)使最初的状态变化为最终的状态。当前，规划已经超出了这些范围，包含了很多决策理论思想(decision-theoretic ideas),例如马尔科夫决策过程（Markov decision processes），不完全信息状态（imperfect state information）以及博弈论均衡（game-theoretic equilibria）。

控制理论(control theory) ：传统控制理论往往涉及稳定性、反馈和最优性。人们对设计算法的兴趣越来越大，这些算法为非线性系统找到可行的开环轨迹。

本系列博客侧重于规划相关的算法问题。在机器人领域中，重点是设计一种算法，通过处理复杂的几何模型来生成有效的运动。在人工智能中，重点是设计一种系统，使用决策理论模型来计算适当动作。在控制理论中，重点是计算系统可行轨迹的算法，以及一些额外的反馈和优化。

谁适合这本书？

机器人领域（robotics）: 研究领域包含motion planning, trajectory planning, planning under uncertainty

人工智能领域（artificial intelligence）:是对机器学习的一种补充（machine planning）,强化学习和决策理论都是本书涉及的范围。

控制理论(control theory):反馈、最优性和动力学概念在全书的许多地方都出现了。然而，本书中的技术主要是算法，而不是通常在控制理论中开发的分析技术。

如何使用本书？

若你仅对机器人运动规划感兴趣，只需学习第3-8章：第3、4章介绍了机器人运动规划的基本概念；第5、6章提出了解决系列问题的算法技巧；第7、8章研究了基础问题的一些拓展。若你对非完整规划和其他涉及到不同约束的规划问题感兴趣，可以直接跳到书的第三部分第13-15章。第11、12章关于感知的不确定性，这些问题都在信息空间(information space)内描述。

链接

http://msl.cs.uiuc.edu/msl/

http://planning.cs.uiuc.edu/

第一章: 简介

1.1 规划

机器人领域

运动规划（Motion Planning）可以理解成“搬钢琴问题”（Piano Mover’s Problem），房屋和钢琴的结构图作为规划器的输入，得到一条安全无碰撞的路径。机器人运动规划通常会忽略动力学和其他差分约束，而主要关注移动钢琴所需的平移和旋转。

轨迹规划（Trajectory Planning）通常是指从机器人运动规划算法中获取解，并确定如何在满足机构约束的条件下沿着解移动的问题。

控制领域

在最近的控制理论文献中，运动规划有时是指构建非线性动力系统的输入，将其从初始状态驱动到指定的目标状态。

人工智能领域

与搬钢琴不同的是，人工智能领域的规划多数指的是“解谜问题”，例如解一个魔方或者华容道问题。尽管这些问题可以使用连续空间进行建模，但定义可应用于离散状态集的有限动作集并通过给出适当的动作序列来构建解决方案更自然。

1.2 举例和应用

为什么要学习规划算法？这里至少有两个原因：1）解决人类大脑无法解决的具有挑战的问题；2）规划算法在多个行业和学科中取得了广泛的成功。

1.3 基本规划要素

状态（state）：包含所有可能情况的状态空间

时间（time）：可以是具体的时间序列也可以是逻辑序列

动作（action）：规划是通过产生动作来操纵状态。AI领域通常称为动作（action）和操作（operator）。控制理论和机器人领域通常称为输入（input）和控制（control）。制定规划的时候，需要指明在动作下状态如何变化。这可以表示为离散时间的状态值函数（state-valued function）或连续时间的常微分方程（ordinary differential equation）。

起点和终点（initial and goal state）

一种标准（A criterion）：这根据执行的状态和动作对规划的预期结果进行编码。根据标准的类型，通常有两种不同的规划问题：可行性（feasibility）和最优性（optimality）。对于很多问题，可行性已经难以解决，最优性则更难，故重点多在可行性。

一种规划（A plan）:一般而言，规划将特定的策略或行为强加给决策者。它可能简单地指定要采取的一系列动作，但往往更加复杂。若无法预测未来的状态，那么规划器可以将动作视为状态的函数。此时，动作就取决于未来的状态，可以理解为反馈（feedback）或反应计划(reactive plans)。若状态无法测量，那么合适的动作需要从有限的获取信息中做出决定，这就是所谓的信息空间（information state）,规划的动作基于该信息状态。

1.4 算法、规划器和书籍

1.4.1 算法

广义的算法定义可以参考图灵机，但图灵机的使用往往要与物理世界交互，如图所示。使用图灵机的基础是物理世界必须首先仔细地建模，如果在算法执行期间，环境模型发生改变，那规划器将不能做出准确的判断。比如在人员嘈杂的环境内规划路径，此时在线算法（on-line algorithm）较为合适。

1.4.2 规划器

规划器负责构造规划，可以是机器或者是人。如果规划器是个机器，那可以被视为是个规划算法

1.4.3 规划

一旦一个规划被制定，有三种使用方式：

执行（Execution）:可以在仿真或者真实物理世界中执行。有两种执行方式，第一是规划器产生规划算法，并给机器人，此时机器人可以视为是可编程的并且可以在执行前接受规划器给出的可能的规划。此时可以认为机器人是“一键启动且自动执行”的，如图1.18（a）。第二种如1.18(b)所示，在这种情况下，规划器生成的规划对整个机器进行编码。规划是一种专用机器，旨在解决最初交给计划者的特定任务。在这种解释下，规划器可能是一个极简主义者，设计出尽可能简单的机器来充分解决所需的任务。如果规划被编码为有限状态机，那么它有时可以被视为图灵意义上的算法（取决于将机器连接到磁带是否保留其操作）。

2. 改进（Refinement）:算法被用来迭代。如图1.19，如果规划用于精细化，则规划器将其作为输入接受并确定有望改进的新规划。新规划可能会考虑更多问题方面，或者可能只是更有效。可以重复应用细化，以产生一系列改进的计划，直到执行最后一个。

3. 封装（Hierarchical Inclusion）：将其封装为上层的规划一个动作，每个动作都可以拆解。该规划被合并为更高级的规划中的一项行动。原规划可以想象成更大规划中的一个子程序。

1.5 本书的组织结构

第一部分：简介

介绍了本书的基本背景。

第一章：简介

本章提供了一些一般性观点，并包括一些示例和规划算法的应用。

第二章：离散规划

本章涵盖了最简单的规划形式，可被视为进入本书其余部分的跳板。

第二部分：运动规划

具体介绍了机器人运动规划，也称为在连续状态空间内的规划（Planning in Continuous State Spaces）

第三章：几何表示和变换

本章给出了表达运动规划问题的重要背景。3.1 节描述了如何构建几何模型，其余部分说明如何转换它们。第 3.1 和 3.2 节对后面的章节很重要。

第四章：C空间（Configuration Space）

本章介绍拓扑中的概念，并使用它们来制定C空间，即运动规划中出现的状态空间。第 4.1、4.2 和 4.3.1 节对于理解后面章节中的大部分材料很重要。除了前面提到的部分之外，第 4.3 节的所有内容都为第 6 章的组合方法提供了有用的背景知识。

第五章：基于采样的运动规划

本章介绍了近年来在文献中占主导地位并已在机器人领域内外应用的运动规划算法。如果理解了C空间代表连续状态空间的基本思想，那么大部分概念应该就可以理解了。除了运动规划和机器人技术之外，它们也适用于出现连续状态空间的其他问题。第 14 章重新审视在不同的约束下基于采样的规划。

第六章：组合运动规划

本节中介绍的算法有时称为精确算法，因为它们构建离散化的表示方式而不会丢失任何信息。它们是完备的，这意味着如果存在，它们必须找到解决方案；否则，他们报告失败。基于采样的算法在实践中更有用，但它们的完整性概念较弱。

第七章：基本运动规划的扩展

本章介绍了许多问题和算法，它们是第 5 章和第 6 章方法的扩展。大多数问题和算法都可以用这些章节的知识来解决。第 7.4 节涵盖了封闭运动链的规划，这首先需要了解第 4.4 节中的附加材料。

第八章：反馈运动规划

这是一个过渡章节，将反馈引入到运动规划问题中，但仍然没有引入微分约束，这些约束被推迟到第四部分。第二部分的前几章集中在计算开环规划，这意味着在规划执行过程中可能发生的任何错误都被忽略，但计划将按计划执行。使用反馈产生一个闭环计划，在执行期间响应不可预测的事件。

第三部分：决策理论规划

即在不确定性下的决策规划，多数问题为离散状态空间，可以读完第一部分后直接开始学习，有一些章节涉及到连续状态空间，需要第二部分的一些知识。

第九章基本决策理论

本章的主要思想是为面临其他决策者干扰的决策者设计最佳决策。其他人可能是游戏中的对手，也可能是虚拟的不确定性模型。本章侧重于一步决策，并为第 III 部分提供了一个结构框架，因为不确定性下的规划可以被视为多步决策。

第十章序列决策理论

本章采用第 9 章中的概念，并通过将一系列基本决策问题链接在一起来扩展它们。2.3 节中的动态规划概念在这里变得很重要。对于本章中的所有问题，都假设当前状态总是已知的。存在的所有不确定性都与对未来状态的预测有关，而不是测量当前状态。

第十一章传感器和信息空间

本章将第 10 章的表述扩展为在执行期间当前状态未知时的规划框架。关于状态的信息是从传感器观察和先前采取的动作的中获得的。信息空间用于解决感知不确定性问题的目的与C空间用于运动规划的目的类似。(The information space serves a similar purpose for problems with sensing uncertainty as the configuration space has for motion planning).

第十二章传感不确定下的规划

本章节介绍了一些关于传感不确定性的规划问题和算法。这包括定位、地图构建、追-逃问题和操纵等问题。所有这些问题都在信息空间规划的思想下统一起来，这是第 11 章的内容。

第四部分：微分约束下的规划

被视为第二部分的延伸。在这里，运动规划中出现的连续状态空间可能存在全局（障碍）和局部（差分）约束。还考虑了动力系统，它产生包括位置和速度信息的状态空间（这与控制理论中的状态空间或物理和微分方程中的相空间的概念相吻合）。

第十三章微分模型

本章介绍了许多涉及差分约束的模型，以此作为对第四部分的介绍。这包括车轮滚动产生的约束以及机械系统动力学产生的一些约束。

第十四章微分约束下的采样规划

介绍了在第 13 章的模型下解决规划问题的算法。许多算法是第 5 章方法的扩展。所有方法都是基于采样的，因为在差分约束中，组合规划技术几乎无法完成。

第十五章系统理论与分析技术

本章概述了主要在控制理论文献中的概念和工具。它们是对第 14 章算法的补充，并且经常在差分约束下的规划算法的开发中提供重要的见解或组件。