在线/离线规划

规划问题是希望在运动期间在线计算目标的轨迹，以允许机器人对移动目标的环境变化和运动过程中遇到的误差作出反应。然而，解决这些问题，是一定困难的。这源于搜索空间的高维度，障碍物的几何性质，优化的成本函数,和机器人的运动学和动力学模型。来在给定的合理的计算资源里，这些问题都会妨碍它足够快的被在线解决。

因此，在运动规划领域出现了两个分支：离线规划offline planning，其中在运动开始之前计算到目标的轨迹，在线规划online planning在运动期间持续地计算目标的轨迹。

在已知的可用模型环境中，规划可以离线完成。可以在执行之前找到并评估解决方案。在动态未知环境中，策略经常需要在线修改。模型和政策必须适应。解决方案通常采用人工智能中常见的反复试验和错误处理。这些包括动态规划，强化学习和组合优化。用于描述计划和调度的语言通常称为action languages动作语言。

给出一个描述世界的可能的初始状态，预期目标，并描述一组可能的行动，规划问题是保证能够制定一个计划（从初始状态）能够产生所想要的目标状态。

规划的困难取决于所采用的简化假设。根据若干问题的性质，可以识别若干类规划问题。

问题描述：

在典型的运动规划问题中，我们希望能解决以下的优化问题：

x是机器人状态空间中的某一点，u是一个执行向量，限制条件如下：

k是障碍物的数目，t_f是最终时间，如果目标方程的值就是时间，如L(x,u)=1,那么t_f就是free的，也就是可移动的。假设（4）中的障碍物不互相重叠，对于目标x_f.

问题（1）是一个两点边界值（TPBV）问题：即满足边界条件的所有轨迹（5），选择一个最小的目标函数（1）满足系统得动态要求（2），控制约束（3) 和障碍约束（4）。

最优得全局策略可以通过Hamilton-Jacobi Bellman (HJB) equation方程来计算，将障碍的集合设为O：

u∗是问题（1）的解决方案，满足在Rn − {x0} − O中，HJB等式：

在（3），（4）的限制下， v(x, t)是C^2的标量函数scalar function，满足：

下标x和t分别表示关于x和t的偏导，<·，·>表示Rn上的内积。

标量函数v(x, t)是值函数，表示最低的成本-cost-to-go从任何给定的状态到目标节点。为一个自动系统和固定边界条件，vt = 0;假设在条件，最小化的成本函数是时间L(x, u) = 1，减少到(7)：

为了满足(10),x˙在vx (x)的vx = f(x,u) 的映射必须等于−1。它遵循最小化的最优控制u∗，它满足方程(10)在负梯度的方向上（−vx(x)）的最优轨迹x˙∗(x,u)。如图所示。方法，除了这里的势能函数是值函数。因为值函数在目标上有一个唯一的最小值，轨迹生成。通过跟随负梯度的价值函数，是全局最优的。

【论文：Off-Line and On-Line Trajectory Planning；URL：Off-Line and On-Line Trajectory Planning - Springer.pdf】

发展历史

20世纪60年代到20世纪80年代，早期的规划工作植根于最优控制理论的领域，它提供了强大的工具来表征和和产生最佳轨迹，这是高速运动所需的必要条件，由Pontryagin’s maximum principle，导致最优控制会有一个two-point boundary value problem，并寻找最优控制算法，产生最佳的轨迹。

经典的规划算法

• 向前链式空间状态搜索，可能通过启发式算法强化
• 向后链式搜索backward chaining search, 使用状态约束进行强化(see STRIPS, graphplan)
• 偏序规划partial-order planning

1971年，斯坦福研究所 SRI International的Richard Fikes和Nils Nilsson开发了一种新的方法来应用定理证明来解决问题。该模型试图在一个世界模型的空间中找到一个操作序列，将初始的世界模型转化为一个目标状态存在的模型。它将世界建模为一组一阶谓词公式，并设计用于与包含大量公式的模型一起工作。这也是所谓的STRIPS。

在STRIPS，problem solver的任务是找到一个算子序列，将给定的初始问题转化为满足目标条件的初始问题。操作符是构建解决方案的基本元素。每个操作符对应一个动作例程，其执行导致代理执行某些操作。定理证明和搜索的过程通过一个世界模型的空间被分开。

Graphplan是Avrim Blum和Merrick Furst在1995年开发的自动规划算法。Graphplan将一个规划问题作为输入，在STRIPS 表示，如果可能的话，就会产生一个达到目标状态的操作序列。

graphplan的名称是一个新的planninggraph，从而减少了从对状态空间图的直接探索中找到解决方案所需的搜索量。

降低到别的问题 Reduction to other problems

• 降低到命题可满足性问题(satplan)，1992年，H. A. Kautz and B. Selman提出的Satplan(更被称为“可满足性计划”)是一种自动规划的方法。它将规划问题实例转化为布尔可满足性问题的实例，然后用一种建立可满足性的方法(如DPLL算法或WalkSAT)来解决。
• 降低到模型检查Model checking,两者本质上都是遍历状态空间的问题，而经典的规划问题可以堪为模型检查问题的子问题。为检验硬件和软件设计的模型，开发了一种重要的模型检查方法，该模型由时序逻辑公式给出。

时间规划 Temporal planning

时间规划可以用经典规划相似的方法来解决。主要的区别是，由于可能有几个临时重叠的行动，同时持续地进行，因此，状态的定义必须包括关于当前绝对时间的信息，以及每一个行动的执行情况。此外，在合理或实时的规划中，状态空间可能是无限的，不像古典规划或整数时间的规划。时间规划与调度问题密切相关。时间规划也可以是timed automata。

时序逻辑规范的开创性工作是由Amir Pnueli完成的，获得了1996图灵奖，“将时序逻辑引入计算机科学的开创性工作”。模型检查Problem checking是由刚开始创业的E. M. Clarke， E. A. Emerson，J. P. Queille和J. Sifakis所构思的。也因为这些功劳，Clarke, Emerson, and Sifakis 共同获得了2007图灵奖，应为在模型检验的开创性工作。

概率规划

在状态空间足够小的情况下，概率规划可以用迭代方法(如值迭代和策略迭代)来解决。在部分可观察性的情况下，概率规划同样用迭代方法解决，但使用的是信任空间而不是状态定义的值函数的表示。MDPs（Markov decision process）至少早在20世纪50年代就已经为人所知(cf. Bellman 1957)。关于马尔可夫决策过程的一个核心研究是 Ronald A. Howard在1960年出版的书，Dynamic Programming and Markov Processes动态规划和马尔可夫过程。它们被广泛应用于学科领域，包括机器人、自动控制、经济学和制造业。（e.g. Markov decision process和Partially observable Markov decision process）

基于优先级/偏好的规划

在基于优先级的规划中，目标不仅是生成规划，而且还满足用户指定的首选项。不同于更常见的基于奖励的规划，例如与MDPs对应的，首选项不一定具有精确的数值。基于偏好的规划软件的例子包括PPLAN和HTNPlan-P(基于优先级的HTN规划)。

规划系统的应用

Hubble Space Telescope（哈勃太空望远镜）短期的系统SPSS，长期的规划系统Spike。哈勃太空望远镜(HST)是NASA/ESA资助的项目，于1990年发射进入轨道。太空望远镜科学研究所(STScI)负责管理科学项目的征集/选择、计划和日程安排，以及对HST的数据存档。

【出处：wiki， URL：https://en.wikipedia.org/wiki/Automated_planning_and_scheduling#Classical_planning】

主要事件

发展分析

瓶颈

离线规划可以在行动之前就获取策略信息，但是不能动态的更新自己的结果。而在线规划则需要具备更高的前提条件，如果在很多特殊情况下，如地震等灾害后的场景下，很多设备和机器人是很难执行在线规划的。此外其自身的运算能力需要很大的提高。

未来发展方向

INTEGRATED ONLINE/OFFLINE PLANNING： 将离线与在线规划有效的结合应用，无论是对环境的依赖上还是执行能力上都可以获取到满意的结果。

Contributor：Ruiying Cai