自动规划

规划(Planning)问题
规划是指设计一个动作规划以达到目标。规划选择要素化表示(factored representation)，用一组变量表示世界的一个状态。

经典规划
PDDL语言：
状态是流(fluent)的合取，这些流是基元的(无变量的)、无函数的原子。
动作：由一些动作模式(action schema)组成的集合.
每个动作模式包含变量列表、前提(precondition)和效果(effect). 前提和效果是由可以包含状态的文字(literal)的合取。

在状态s执行一个动作a的结果是一个状态s':
首先\(Del(a)\)，删去a的效果中的负文字；然后\(Add(a)\)， 加入a的效果中的正文字。可以写为\(Result(s,a) = (s-Del(a))\cup Add(a)\).

一组动作模式可以定义为规划域(domain). 域中的一个特定问题用一个初始状态和一个目标来定义：
初始状态是基元原子的合取，这里使用封闭世界假设（即没有提到的原子都是假的）。目标是可以含有变量的文字的合取。

经典规划问题可以视为搜索问题，通过前向/后向搜索求解，也可以定义启发式搜索。

分层规划(Hierarchical Planning)
层次任务网络(Hierarchical task network(HTN)):
包含基元动作(primitive actions)（具有标准的前提-效果模式）和高层动作(high-level action, HLA)，包含至少一个细化(refinement)的动作序列，序列中每个动作可以是一个HLA或一个基元动作。一个只包含基元动作的HLA细化称为HLA的实现（implementation）。

一般用单个称为Act的顶层动作来表示HTN规划，目的是找到达到目标的Act的实现。经典规划问题可以定义为对每个基元动作\(a_i\)，Act有一个细化\([a_i,Act]\), 这意味着递归定义了Act使得可以任意地向里面添加动作。另一方面，通过为Act提供另一个细化，使得步骤列表为空，前提为达到问题目标，来最终消去Act。可以通过搜索算法（如BFS，DFS）搜索找到基元实现。

情景演算(situation calculus)
将一阶逻辑加入到规划问题中。
初始状态\(S_0\)称为一个情景. 如果s是情景，a是动作，则\(Result(s,a)\)（或\(do(s,a)\)）也是情景。情景对应动作的一个序列或历史。

能够从一个情景变化到下一个情景的一个函数或关系称为流(fluent). 一般地，情景s作为流的最后一个参数。如关系(谓词)流\(Hold(r,x,s)\)表明机器人r在情景s下握住x。类似有函数流。

每个动作的前提条件(preconditions), 如\[Poss(pickup(r,x),s)\Leftrightarrow \forall z.\lnot Holding(r,z,s)\land NextTo(r,x,s)\]
每个动作也有效果(effect)：根据动作的结果得到的流。称为效果公理。如\[Fragile(x)\Rightarrow Broken(x, do(drop(r,x),s))\]
效果公理的规范形式：
(1) \(P_F(x,a,s) \Rightarrow F(x, do(a,s))\)
(2) \(N_F(x,a,s) \Rightarrow\lnot F(x, do(a,s))\)
如上面的效果可以改写为\[\exists r.\{a = drop(r,x)\}\Rightarrow Broken(x, do(a,s))\]
解释闭包公理(Explanation closure axiom)
(3) \(\lnot F(x,s)\land F(x, do(a,s))\Rightarrow P_F(x,a,s)\), 如果流F原本是False，但经过动作a之后变成True，则\(P_F\)必须变成True。
(4) \(F(x,s)\land \lnot F(x,do(a,s))\Rightarrow N_F(x,a,s)\), 如果流F原本是True但经过动作a之后变成False，则\(N_F\)必须变成True。

后继状态公理(successor state axioms)
F在后继状态中为True 当且仅当以下至少之一成立：
(a) 某动作使F成立
(b) F原本是True，且没有动作使F变成False
例：\[Holding(r, g, do(a,s))\Leftrightarrow\\ a=Grab(g)\lor[ Holding(r, g, s)\land a\ne Release(g)]\]

    所属分类：人工智能     发表于2022-05-24