人工智能自动规划 04：规划导论
Lecture04规划导论如何描述任意搜索问题？
上节课我们讨论了一些搜索算法，本节课我们将介绍如何将它们作为工具来解决一些通用问题。
你可能已经见过很多AI应用，例如：从1997年IBM国际象棋程序“深蓝”击败当时最顶尖的人类棋手卡斯帕罗夫，到2017年GoogleDeepMind开发的围棋程序AlphaGo击败排名世界第一的柯洁，不过短短二十年。
但是，这些程序有一个通用的缺陷，就是它们只能在特定应用上取得非常好的成绩，而一旦切换到其他领域，表现将非常糟糕。这意味着，你在除了围棋之外的任何方面都要强过AlphaGo。
这能够算是（人工）“智能”吗？
$ o$如何构建一个可以解决新问题的机器
动机：如何开发可以自己做决策的系统或者agents。
1.AI中的自治行为问题的关键在于选择接下来的行动（action），也就是所谓的控制问题（controlproblem）。一般有以下三种方法：
基于编程（Programming-based）：手动指定控制。基于学习（Learning-based）：从经验中学习控制。基于模型（Model-based）：手动指定问题，自动推导控制。$color{blue}{ o}$各方法并不正交，每种都有各自的优劣。$color{blue}{ o}$不同的模型（models）会产生不同类型的控制器（controllers）。
1.1基于编程的方法首先是基于编程的方法，它是能够解决任何任务的最简单的方法，可以想象，为了解决问题，无论angent需要遵循的规则是什么，我们都可以一步步通过编程实现。
$color{blue}{ o}$控制由程序员指定。
例如，假设现在我们需要编写程序玩超级马里奥游戏，我们可以设定并编写如下规则：
如果马里奥发现没有危险，那么奔跑……如果出现了危险，并且马里奥是变大的状态，那么跳跃并击杀…………优点：领域知识（domain-knowledge）可以很容易表达。缺点：并不是真正意义上的通用求解器，无法处理程序员没有预见到的情况。
1.2基于学习的方法目前，研究的核心领域主要集中在基于学习的方法。
$color{blue}{ o}$从经验或者通过模拟来学习得到一个控制器。通常包括以下三种：
无监督（强化学习）：在无监督学习中，angent可以根据行动得到不同的反馈（惩罚或者奖励），通过不断重复这一过程，angent可以学习到在特定情况下采取哪种行动是正确的。例如，在马里奥游戏中，我们可以设定：每次在马里奥“死亡”时，对agent施加惩罚（例如，分数减少1000）。每次敌人“死亡”或者到达目的地时，对agent进行奖励（例如，分数增加1000）。如果我们不断重复这一方法，我们将发现马里奥能够学习到如何在特定情况下做出正确选择。在过去十年中，无监督学习这一领域取得了很多进展，尤其是在我们有了更强大的硬件后，该方法的可行性将大大提高，我们可以通过运行非常多次来提升学习效果。但是，该方法也存在一些问题：在模型训练过程中，会消耗大量的计算时间，尤其是，如果我们不知道应该采用哪些特征进行学习时，该方法将变得更加困难。
有监督（分类）：与无监督学习相对的另一种方法是有监督学习。同样，假如我们希望让马里奥学习如何选择行动，相比简单地对agent施加惩罚/奖励，我们可能知道，对于各种特定情况应该采取什么行动。又或者，假如我们希望构建一个可以实现图像分类（例如，人、动物、植物）的agent，我们可以给每张图标都添加真实的类别标签，然后让agent基于这些信息进行学习，从而构建一个分类模型，这样，当给定一张新的测试图像时，该模型就能够对其进行分类。基于监督者提供的信息，学习对正确和错误的行动进行分类。演化（Evolutionary）：第三种方法是演化算法，这里我们不会对其展开太多讨论。从一系列可能的控制器中：对它们进行试验，选择其中表现最好的，然后通过多次迭代进行变异和重组，保留最优的控制器。优点：不需要太多关于规则的知识。缺点：在实践中，很难知道应该学习哪些特征，并且训练过程很慢。
1.3通用问题求解这里，我们将关注如何用基于模型的方法，来求解通用问题。这个领域已经被研究了数十年，最早的相关研究可以追溯到开始于1959年的GPS研究项目。
目标：写出一个可以解决所有问题的程序。$color{blue}{ o}$写出(Xin{算法})：对于所有的(Yin{问题})，$X$都能够解决$Y$。$color{blue}{ o}$那么，什么叫做一个“问题”？怎样定义“解决”一个问题？显然，这个目标过于宏大，实践上存在诸多困难，因此我们将目标改为专注某一类问题。目标2.0：写出一个可以解决一个大类的问题的程序。随着时间的推移和研究的深入，我们不再满足于仅仅解决某一类问题，我们还希望知道如何更高效地解决这些问题。目标3.0：写出一个可以有效解决一个大类的问题的程序。（一些新问题）$leadsto$（描述问题$ o$使用现成的求解器）$leadsto$（和人类专家程序竞争解决方案）所以，通常采用的方法是：我们得到了一些新问题，我们希望用一些通用目标规划语言来描述这些问题，然后我们用一些现成的通用求解器对其进行求解，我们希望它能够和人类专家利用专业知识得到的解决方案相当，甚至更好。$color{blue}{ o}$用巧妙的解决方法击败人类。参考链接：始于1959年的通用求解器GPS
1.4基于模型的方法$color{blue}{ o}$为问题指定模型：行动(actions)、初始状态(initialsituation)、目标(goals)、传感器(sensors)。
$color{blue}{ o}$让一个求解器自动计算得到控制器。
我们得到了一些领域信息：行动、传感器、目标。我们希望利用这些信息来构建一个求解器，以便我们可以自动计算得到一个控制器，该控制器描述了angent在任何给定状态下应当如何采取行动。
优点：
强大：在某些应用中，泛化性能是非常必要的。快速：可以快速搭建原型。10行PDDL语言描述问题vs.1000行C++代码（语言生成任务）灵活和清晰：修改/保留描述。智能和领域独立性：可以自动决定如何有效对一个复杂问题进行求解。缺点：需要一个模型；计算困难
效率损失：如果没有任何关于国际象棋的特定领域知识，我们不可能击败卡斯帕罗夫。$color{blue}{ o}$二者之间的权衡：“自动且通用”vs.“手动但高效”
基于模型的方法实现的智能行为称为AI中的规划（Planning）。
如何高效实现全自动算法？
1.5例子：经典搜索问题我们来看一个例子：纸牌接龙（Solitaire）
我们可以将其建模为一个经典搜索问题：
状态（States）：描述了域中的所有可能的配置，这里可以理解为纸牌位置。例如：上图中，“黑桃J”位于“红桃Q”上方，而“红桃Q”位于面板上方第二列，“梅花A”则位于“家”中的第一列。我们可以通过描述每张纸牌的位置来描述某种可能的配置（状态），而所有可能的状态构成了这个域的状态空间。行动（Actions）：我们可以通过行动从一个状态映射到另一个状态，即移动纸牌。例如：将“黑桃J”移动到倒数第二列的空位上。初始状态（Initialstate）：初始配置，即游戏开始时关于所有纸牌的位置描述。目标状态（Goalstates）：所有纸牌都“回家”。解（Solution）：如果我们将问题传入规划器，那么将得到一个移动纸牌的序列来完成游戏。2.模型2.1基本状态模型：经典规划目标：写出一个能解决所有经典搜索问题的程序。
状态模型：
有限离散状态空间$S$一个已知的初始状态$s_0inS$一个目标状态的集合$S_GsubseteqS$在每个状态$sinS$中可能采取的行动$A(s)subseteqA$一个确定性转移函数$s’=f(a,s)$，对于所有的$ainA(s)$正的行动代价$c(a,s)$$color{blue}{ o}$一个解是一个可能的行动序列，它将初始状态$s_0$映射到目标状态$S_G$，并且，如果它使得行动代价之和（例如：行动步数）最小化，那么我们称之为最优解。
$color{blue}{ o}$通过放松上面蓝色部分的假设，我们可以得到不同模型和控制器。
2.2不确定性但是无反馈：一致规划除了经典规划，但是还有很多其他类型的规划模型，例如：一致规划（ConformantPlanning）。
一致规划的模型假设大部分都和之前经典规划一样，区别是现在我们的初始状态是一个可能的状态集合。想象一下，假设现在房间内有一个移动机器人和目标点，如果机器人知道自己的初始位置，那么这是一个经典规划问题，但是假如现在房间内的灯是关着的，机器人并不知道自己的具体位置，只知道一些可能的初始位置，这种情况下机器人仍然需要到达目标点，那么我们可以用一致规划模型求解，它将比经典规划更复杂一些。
例如，在上面左边的图中，我们已知初始位置$I$和目标位置$G$，那么可以视为一个经典规划问题。而在右边的图中，已知目标位置$G$，而初始位置$I$有三个可能的位置，但是我们并不知道具体是其中哪个，这是一个更复杂的规划问题，但是我们仍然可以对其求解。例如，我们可以有一个这样的解：机器人总是先向右移动4步，再向下移动2步，如果因为碰到墙壁无法继续移动则停止，显然，这个解对于右图中的一致规划问题也是适用的。
状态模型：
有限离散状态空间$S$一个可能的初始状态集合$S_0inS$一个目标状态的集合$S_GsubseteqS$在每个状态$sinS$中可能采取的行动$A(s)subseteqA$一个非确定性转移函数$F(a,s)subseteqS$，对于所有的$ainA(s)$一致行动代价$c(a,s)$$color{blue}{ o}$一个解还是一个行动序列，但对于任何可能的初始状态和转移，都必须能够到达目标状态。
$color{blue}{ o}$比经典规划更复杂，在最坏的情况下，我们比较难以验证一个规划的一致性；但在特殊情况下，具有部分可观测性的规划是可行的。
2.3基于马尔可夫决策过程（MDPs）的规划AI中的另一类常见问题是马尔可夫决策过程（MarkovDecisionProcesses，MDPs），它是一种完全可观测的概率状态模型：
一个状态空间$S$初始状态$s_0inS$一个目标状态的集合$S_GsubseteqS$在每个状态$sinS$中可能采取的行动$A(s)subseteqA$转移概率$P_a(s’mids)$，其中$sinS,ainA(s)$行动代价$c(a,s)>0$它和经典规划的区别在于：经典规划中我们采用的是一个确定性转移函数，即当我们执行某个行动时，我们能够确切地知道该行动将导致的状态变化；而MDPs采用的是一个概率函数，即当我们采取某个行动时，我们并不知道它将具体导致哪种状态变化，我们只知道这个状态转移的概率是多少。
$color{blue}{ o}$解是将状态映射到行动的函数（策略）。
$color{blue}{ o}$最优解是能够使得到达目标的期望代价最小化的解。
2.4部分可观测马尔可夫决策过程（POMDPs）POMDPs是一种部分可观测的概率状态模型，它假设系统状态由MDP决定，但是智能体无法直接观察状态。相反的，它必须要根据模型的全域与部分区域观察结果来推断状态的分布：
状态$sinS$行动$A(s)subseteqA$转移概率$P_a(s’mids)$，其中$sinS,ainA(s)$初始信念状态$b_0$最终信念状态$b_f$传感器模型由概率$P_a(omids)$给出，其中$oinObs$所以，这种情况下，我们不仅有概率转移函数，而且还有信念状态。也就是说，agent可能并不知道自己的初始状态或者目标状态，只有关于它们的信念，它通过传感器得到有关周围环境的信息，并在此基础上对信念状态作出调整。
无论是MDPs和POMDPs，想要完全求解都面临所谓“维度诅咒”问题：MDPs的状态空间大小随状态变量的数目呈指数级增加；而POMDPs则要更加复杂，由于状态空间随状态变量的数目呈指数增加，因此，POMDPs的复杂度随状态变量数目是呈双指数级增加的。
$color{blue}{ o}$信念状态（Beliefstates）是状态空间$S$上的概率分布。
$color{blue}{ o}$解是将信念状态映射到行动的策略。
$color{blue}{ o}$最优解是能够使得从$b_0$到达$G$的期望代价最小化的解。
2.5例子根据不同的问题类型，我们可能需要不同的求解器。
假设现在有一个路径规划问题：agent$mathbfA$要达到目标$mathbfG$，在一个已知地图中每次移动一格。
如果行动是确定性的，并且初始位置已知，那么这是一个经典规划问题。如果行动是随机性的，并且位置是可观测的，那么这是一个MDP问题。如果行动是随机性的，并且位置是部分可观测的，那么这是一个POMDP问题。不确定性和反馈机制的不同组合：三个问题，三个模型。
3.语言3.1模型、语言和求解器根据不同类型的问题，我们希望得到一个规划器，可以求解该类型下的所有问题（例如MDPs）。
一个规划器是一个某一类模型上的求解器；它接收一个模型描述作为输入，计算得到对应的控制器。
很多模型，很多解的形式：不确定性、反馈、代价……模型通过合适的规划语言（Strips，PDDL，PPDDL等）描述，其中状态表示对该语言的解释。3.2经典规划问题的一种基本语言：Strips最早的规划语言是Strips，尽管这是一种起源于上世纪50年代的古老语言，但是它仍然是如今很多问题研究的基础。大部分的现代规划器，本质上都是基于Strips的扩展变体。
一个问题在STRIPS中表示为一个元组$P=langleF,O,I,G angle$：$F$表示所有原子（布尔变量）的集合变式（Fluents）$F$表示一个问题中的所有原子。例如，在一个规划问题中，一个agent可以处于很多不同位置中的一个，而一个fluent则可以指示该agent可能的位置。例如“Chris站在这个位置”这句话可以是真或假；“Chris站在那个位置”也可以是真或假。域中的每个位置都可以有一个这样的fluent，它是一个布尔变量。$O$表示所有算子（行动）的集合为了从初始状态到达目标状态，需要执行的一系列行动称为算子（operators）。$IsubseteqF$表示初始状态初始状态（Initialsituation）是fluents的一个子集，在初始时其结果为真。例如，当Chris进入房间时，“Chris站在这个位置”可能是一个初始状态。$GsubseteqF$表示目标状态假设Chris试图寻找一条到达房间右上角的路径，“Chris站在房间右上角”就是一个目标状态（goalsituation），同样，它也是fluents的一个结果为真的子集。算子$oinO$表示为：添加列表（Addlist）$Add(o)subseteqF$行动执行后结果为真。删除列表（Deletelist）$Del(o)subseteqF$行动执行后结果为假。前置条件列表（Preconditionlist）$Pre(o)subseteqF$为了行动能够执行，必须为真。所以，回到之前的例子，假如Chris希望移动到房间右上角，采取这些步骤将对域产生影响，我们会添加一个fluent（“Chris站在房间左下角”），而当Chris移动之后，之前的fluent会被删除。而要执行这一行动，前提条件是之前的“Chris站在房间左下角”这一陈述为真。
3.3从语言到模型（STRIPS语义学）一个STRIPS问题$P=langleF,O,I,G angle$决定了状态模型$S(P)$，其中：
状态$sinS$是变式$F$中原子的某种集合。$S=2^F$。初始状态$s_0$为$I$目标状态$s$满足$Gsubseteqs$$A(s)$中的行动$a$是$O$中的$o$，满足$Pre(a)subseteqs$后继状态为$s’=s-Del(a)+Add(a)$行动代价$c(a,s)$均为$1$$color{blue}{ o}$$P$的（最优）解是$S(P)$的（最优）解
$color{blue}{ o}$轻度的语言扩展通常很方便：求反（negation）、条件效应（conditionaleffects）、非布尔变量（non-booleanvariables）；描述更丰富的模型所需的一些信息（代价、概率等）。
3.4例子：砖块世界我们将通过一个具体例子来了解如何描述问题域。砖块世界（TheBlocksworld）是AI规划中最著名的例子之一，在这个游戏中，我们有一个钩爪和一些砖块，钩爪可以用来拾取和放下砖块，我们希望通过钩爪将这些砖块堆叠成某个目标状态。
我们将用Strips来描述这个问题：
命题（Propositions）$on(x,y)$：砖块可以堆叠在另一个砖块上方，例如左图中砖块D在砖块C上方。$onTable(x)$：砖块可以位于桌面上方，例如左图中砖块E、A、B、C都在桌面上方。$clear(x)$：砖块上方没有物体，例如左图中的砖块E、A、B、D。$holding(x)$：表示钩爪正在抓取的砖块。$armEmpty()$：钩爪是否为空闲状态。初始状态例如，左图的初始状态为：({onTable(E),clear(E),dots,onTable(C),on(D,C),clear(D),armEmpty()})目标状态例如，右图的目标状态为：({on(E,C),on(C,A),on(B,D)})动作我们通过执行一系列动作来改变域的状态。在几乎所有的规划任务中，一般都遵循封闭世界假定（closed-worldassumption），即所有没有被指定的事物都可以认为是假命题。例如，在上面的例子中，我们没有指定除了A、B、C、D、E之外的其他砖块的状态，那么我们可以认为不存在其他砖块，即关于其他砖块的命题都是假命题。$stack(x,y)$：实现一个堆叠状态。$unstack(x,y)$：解除一个堆叠状态。$putdown(x)$：拾起砖块。$pickup(x)$：放下砖块。$stack(x,y)$？我们来看一下堆叠（stacking）操作，如果我们要完成一个$stack(x,y)$操作（即将砖块$x$叠放在砖块$y$上方），那么前置条件列表是什么？显然，砖块$x$应该在钩爪上，并且砖块$y$上方没有其他物体。另外，添加列表应该是什么呢？显然，在堆叠$stack(x,y)$完成后，命题$on(x,y)$、$armEmpty()$、$clear(x)$将被加入域中。最后，删除列表应该是什么呢？也就是说，在完成$stack(x,y)$后，之前的哪些命题将不再为真。显然，在完成堆叠后，$holding(x)$和$clear(y)$将不再为真，因此我们将它们加入删除列表。$Pre:{holding(x),clear(y)}$$Add:{on(x,y),armEmpty(),clear(x)}$$Del:{holding(x),clear(y)}$可以看到，在这个例子中，删除列表和前置条件列表相同，虽然这并非总是成立，但在很多实际的域中，这属于很常见的情况。
3.5PDDL前面我们介绍了Strips语言，并且用它描述了砖块世界的问题。PDDL（规划域定义语言）是基于Strips语言的一种扩展，如今在规划领域被广泛采用。
PDDL不是一种命题语言：
通过从一个对象的有限集合中将对象变量实例化，增强了表示能力。（类似于谓词逻辑）行动图式（Actionschemas）通过对象实现参数化。谓词（Predicates）通过对象完成实例化。一个PDDL规划任务可以分为两部分：
域文件（Domainfile）和问题文件（problemfile）。
域文件给出谓词（predicates）和算子（operators）；每个基准域（benchmarkdomain）都有一个域文件。域文件基本上描述了规则，例如在之前的砖块世界中，可以移动、堆叠砖块的前置条件等等。
问题文件给出对象、初始状态和目标状态。问题文件指定了需要处理的情况，例如初始状态、目标状态等等。
PDDL的这种设计非常强大，这意味着对于很多相似的问题，我们可以有一个通用的域文件，然后对于不同问题采用不同的问题文件来编码。
3.6PDDL描述砖块世界域文件：
12345678910(define(domainblocksworld)(:predicates(clear?x)(holding?x)(on?x?y)(on-table?x)(arm-empty))(:actionstack:parameters(?x?y):precondition(and(clear?y)(holding?x)):effect(and(arm-empty)(on?x?y)(not(clear?y))(not(holding?x))))...在上面的域文件中，我们在predicates中定义了5种基本命题：$clear(x)$、$holding(x)$、$on(x,y)$、$onTable(x)$和$armEmpty()$。其中冒号:表示定义，问号?表示参数。然后，我们定义了行动$stack(x,y)$：参数为$x$和$y$；前置条件为({clear(y),holding(x)})，其中and表示后面的所有命题同时满足；在PDDL中，添加列表和删除列表一并用effect表示，其中命题前加not表示删除。我们可以通过这种方式定义域中的所有规则。
问题文件：
123456789(define(problembw-abcde)(:domainblocksworld)(:objectsabcde)(:init(on-tablea)(cleara)(on-tableb)(clearb)(on-tablee)(cleare)(on-tablec)(ondc)(cleard)(arm-empty))(:goal(and(onec)(onca)(onbd))))在问题文件中，我们定义了所有对象变量：砖块$a$、$b$、$c$、$d$、$e$。然后我们还分别定义了初始状态和目标状态。
4.复杂度4.1规划中的算法问题满意规划（SatisficingPlanning）输入：一个规划任务$P$输出：关于$P$的一个规划；或者“不可解”，如果关于$P$的规划不存在。
最优规划（OptimalPlanning）输入：一个规划任务$P$输出：关于$P$的一个最优规划；或者“不可解”，如果关于$P$的规划不存在。
尽管两者看上去非常相似，但是相应的求解技术之间存在很大差异。
$color{blue}{ o}$对于这两种规划问题中的任何一种，其相关的成功技术都几乎是错综复杂的。$color{blue}{ o}$在实践中，满意规划通常更为有效。$color{blue}{ o}$解决这些问题的程序被称为（最优）规划器/规划系统/规划工具。
4.2规划中的决策问题定义（PlanEx）：通过PlanEx，我们可以表示为一个判定问题，给定一个规划任务$P$，判断是否存在一个关于$P$的规划。
$color{blue}{ o}$对应满意规划。
定义（PlanLen）：通过PlanLen，我们可以表示为一个判定问题，给定一个规划任务$P$和一个整数$B$，判断是否存在一个关于$P$的最大长度为$B$的规划。
$color{blue}{ o}$对应最优规划。
4.3NP和PSPACE图灵机：工作在由磁带单元（tapecells）组成的磁带（tape）上，其读/写头（R/Whead）在其中移动。机器具有内部状态（internalstates）。转移规则（transitionrules）指定了，在给定当前单元内容和内部状态的情况下，后继内部状态将是什么，以及读写头是向左还是向右移动，或者保持原位。有一些内部状态是接受状态（“是”；否则为“否”）。
NP：关于存在一个非确定性图灵机的判定问题，该图灵机在按其输入大小的多项式时间内运行。如果在可能的运行中至少有一种能接受，则接受。
PSPACE：关于存在一个确定性图灵机的判定问题，该图灵机在按其输入大小的多项式空间内运行。
关系：可以在确定性多项式空间中模拟非确定性多项式空间。因此PSPACE$oldsymbol{=}$NPSPACE，所以(通常)NP是PSPACE的子集。
$color{blue}{ o}$更多细节请参见教材，个人推荐GareyandJohnson(1979)。
4.4PlanEx和PlanLen的计算复杂度定理：PlanEx和PlanLen是PSPACE-完全问题。
$color{blue}{ o}$至少和其他PSPACE中包含的问题一样困难。
$color{blue}{ o}$更多细节请参阅Bylander(1994)。
4.5特定域的PlanExvs.PlanLen通常，两者具有相同的复杂度。在特定的应用程序中，有界长度规划的存在性问题通常要比规划存在性问题更加困难。这在许多IPC基准域中都会发生：PlanLen是NP-完全问题，而PlanEx是P问题。例如：砖块世界vs.物流问题$color{blue}{ o}$实际上，最优规划（几乎）永远不会很“简单”。
例如，在砖块世界中，我们几乎总是可以得到这样一个解：先将所有砖块移动到桌面上，然后再堆叠成目标状态。但是想找到最优解就明显困难得多。
4.6例子：砖块世界$n$个砖块，$1$个钩爪。一次单独的行动要么是用钩爪拾取一个砖块，要么是将钩爪上的砖块放置在其他砖块/桌面上。$color{blue}{ o}$状态空间可能非常大。特别是，状态空间通常基于指定的输入大小呈指数级增加。
$color{blue}{ o}$换而言之：搜索问题通常都是计算困难的（例如，砖块世界的最优解是一个NP-完全问题）。
5.计算方法5.1计算：如何解决STRIPS规划问题？关键问题：使用PDDL语言的两个主要好处：
说明：简洁的模型描述。在前面的砖块世界的例子中，我们仅用非常短的PDDL文件就可以定义domain，即便是很复杂的问题，我们也可以很容易地将其编码为domain文件来表示，这将带来诸多好处：因为否则的话，我们将不得不编写每一个单独的对象（object）和每一条单独的规则（rule），PDDL语言为我们提供了一种更灵活的选择。计算：揭示有用的启发式信息（结构）另一个问题是计算。语言让我们得以描述问题，使得程序可以理解问题的结构，并且在结构之外加入启发式信息。例如，在吃豆人问题中，我们可以在PDDL规划器之外加入启发式搜索来引导搜索树。为了达到上述目的，通常有两种传统方法：搜索vs.分解
对状态模型$S(P)$直接进行显式搜索，但是通常效率较低，直到最近才有所改善。如今我们采用的最常见的方法是显示搜索：我们有初始状态、目标状态，以及搜索算法（例如：$mathbfA^*$算法）来发现从初始状态到目标状态的路径。另一种方法是分解（decomposition）问题。相比只是找出一条从初始状态到目标状态的路径，我们试图将规划问题分解为一些启发式的子问题，如果我们可以找到这些子问题的解，我们可以将其组合，得到原规划问题的解。通常，这种方法更好一些，因为规划问题的状态空间通常很大，即使采用很好的启发式算法，搜索空间依然很大。5.2经典规划的计算方法通用问题求解器（GeneralProblemSolver,GPS）和Strips（50-70年代）：均值分析、分解、回归……偏序（PartialOrder,POCL）规划（80年代）：处理任何开放的子目标、解决威胁；UCPOP1992图规划（Graphplan）（1995-2000）：建立包含一定长度内的所有可能的并行规划的图；然后通过从目标向后搜索整个图来提取规划。可满足性规划（PlanningasSatisfiability,SATPlan）（1996-）：将规划问题映射为SAT问题；使用最前沿的SAT求解器。启发式搜索规划（HeuristicSearchPlanning）（1996-）：从问题$P$中提取的具有启发函数$h$的搜索状态空间$S(P)$。模型检查规划（ModelCheckingPlanning）（1998-）：使用“符号”宽度优先搜索来搜索状态空间$S(P)$，其中状态集由BDD实现的公式表示。5.3经典规划中的最新技术自图规划以来取得重大进展经验主义方法标准PDDL语言提供规划器和基准；比赛专注于性能和可扩展性解决了大问题（非最优）不同的构想和想法启发式搜索规划SAT规划其他：局部搜索（LPG），蒙特卡洛搜索（Arvand），…这里，我们将主要关注启发式搜索规划，部分关注SAT规划。
6.国际规划竞赛IPC什么是国际规划竞赛（TheInternationalPlanningCompetition，IPC）？
在一系列由IPC组织者设计的基准上运行参赛的规划器。对其中最高效的规划器颁发奖励。
1998,2000,2002,2004,2006,2008,2011,2014PDDL[McDermott等（1998）；FoxandLong（2003）;HoffmannandEdelkamp（2005）]$approx$40domains,$>$1000instances,74plannersin2011最优轨迹vs.满意轨迹其他各种：不确定性、学习……历届冠军
IPC2000:WinnerFF,heuristicsearch(HS)IPC2002:WinnerLPG,HSIPC2004:WinnersatisficingSGPlan,HS;optimalSATPLAN,compilationtoSATIPC2006:WinnersatisficingSGPlan,HS;optimalSATPLAN,compilationtoSATIPC2008:WinnersatisficingLAMA,HS;optimalGamer,symbolicsearchIPC2011:WinnersatisficingLAMA,HS;optimalFast-Downward,HSIPC2014:WinnersatisficingIBACOP,HSPortfolio;optimalSymbA*,symbolicsearchIPC2018:WinnersatisficingFD/BFWS-LAPKT,HSPortfolio/Width-Basedplanning;optimalDelfi,HSportfolio$color{blue}{ o}$在接下来的部分，我们将关注启发式搜索规划。$color{blue}{ o}$上面是一段关于IPC历史的简短摘要，还有许多不同的类别和奖项。
问题：如果规划器$x$和$y$同时竞争IPC’YY，并且$x$获胜了，那么$x$比$y$更好吗？
$color{blue}{ o}$是的，但是这仅仅是对于IPC’YY的标准而言，并且仅适用于这种情况下获胜方的决定标准。在其他domain或根据其他标准下，使用“失败方”有可能会更好。
$color{blue}{ o}$这很复杂，过度简化是非常危险的。（但是，当然，我们一直都在这么做）
7.总结通用问题求解尝试开发在某一大类问题上都能够表现良好的求解器。
如前所述，规划是一种专门针对经典搜索问题的一般问题解决形式。（实际上，我们还解决了无法访问、随机、动态、连续和multi-agent设置。）经典搜索问题需要找到一条从初始状态到目标状态的行动路径。他们假设一个single-agent、完全可观察、确定性的静态环境。尽管存在诸多条件限制，它们在实践中还是无处不在。启发式搜索规划已经主导了国际计划竞赛（IPC），这也是我们目前比较关注的。对于我们的目的而言，STRIPS是最简单的语言，同时它还具有合理的表达能力。它使用布尔变量（事实），并根据前置条件（precondition）、添加列表（addlist）和删除列表（deletelist）来定义行动（actions）。对于STRIPS，规划是否存在（有界或无界）是一个PSPACE-完全问题。事实上，PDDL是用于描述规划问题的标准语言。8.扩展阅读阅读材料：EverythingYouAlwaysWantedtoKnowAboutPlanning(ButWereAfraidtoAsk)[JoergHoffmann,2011]
地址:http://fai.cs.uni-saarland.de/hoffmann/papers/ki11.pdf
内容:Joergpersonalperspectiveonplanning.Verymodernindeed.Excerptfromtheabstract:
Theareahaslonghadanaffinitytowardsplayfulillustrativeexamples,imprintingitonthemindofmanyastudentasanareaconcernedwiththerearrangementofblocks,andwiththeorderinwhichtoputonsocksandshoes(nottomentionthedisposalofbombsintoilets).Workingontheassumptionthatthis“student”isyou–thereadersinearlierstagesoftheircareers–Ihereinaimtoanswerthreequestionsthatyousurelydesiredtoaskbackthenalready:
Whatisitgoodfor?Doesitwork?Isitinterestingtodoresearchin?
补充材料：IntroductiontoSTRIPS,fromsimplegamestoStarCraft:http://www.primaryobjects.com/2015/11/06/artificial-intelligence-planning-with-strips-a-gentle-introduction/
PDDL在线建模编辑器：http://editor.planning.domains
下节内容：生成启发函数
本作品采用知识共享署名-非商业性使用-相同方式共享4.0国际许可协议进行许可。欢迎转载，并请注明来自：YEY的博客同时保持文章内容的完整和以上声明信息！Previous人工智能自动规划03：搜索算法(2)Next自然语言处理05：词性标注人工智能自动规划 02：搜索算法 (1)
Lecture02搜索算法(1)1.基本模型算法1.1基本状态模型：经典规划追求的目标：
写出一个能够解决所有经典搜索问题的程序。状态模型$S(P)$：
有限离散状态空间$S$一个已知的初始状态$s_0inS$一个目标状态的集合$S_GsubseteqS$每个$sinS$中可以采取的行动$A(s)subseteqA$确定性转移函数（deterministictransitionfunction）$s’=f(a,s);; ext{for};;ainA(s)$正的行动代价（actioncosts）$c(a,s)$$color{blue}{ o}$一个解是将$s_0$映射到$S_G$内部的一个可行的行动序列，如果它能够最小化行动代价之和（例$quad$如：移动步数），我们称其为最优解。
$color{blue}{ o}$通过放松蓝色部分的假设，我们可以得到不同的模型和控制器$quad$例如：假设我们的转移函数不是确定性的（deterministic），而是概率性的（probabilistic），所$quad$以基于某个变量，某种情况下可能发生一种转移，而其他情况下可能发生另一种转移。我们并不$quad$知道到底会发生哪种情况，这其中存在着一些概率。
1.2求解状态模型：图里面的寻路用于规划的搜索算法利用了（经典）状态模型$S(P)$与有向图之间的对应关系：
图中的结点代表模型中的状态$s$图中的边$(s,s’)$代表模型中对应的具有相同代价的转移在启发式搜索规划中，问题$P$通过在与模型$S(P)$关联的图上的路径查找算法得以解决。
1.3搜索算法的分类盲目搜索vs.启发式（或者有信息）搜索：
盲目搜索算法：在一般搜索算法中仅使用基本的原始信息。例如：深度优先搜索（DFS）、宽度优先搜索（BFS）、一致代价搜索（UniformCostSearch,UCS，例如：Dijkstra）、迭代深化搜索（IterativeDeepeningSearch,IDS）启发式搜索算法：额外使用启发式函数估计到目标的距离（或剩余代价）。例如：A$^*$搜索、IDA$^*$搜索、爬山算法（HillClimbing）、最佳优先搜索（BestFirst）、WA$^*$搜索、DFSB&B算法、LRTA$^*$搜索……系统搜索vs.局部搜索：
系统搜索算法：同时考虑大量搜索结点。局部搜索算法：一次处理一个（或几个）候选解（搜索结点）。$ o$这不是非黑即白的区别，可以存在混杂的情况。（例如，enforcedhill-climbing）1.4是什么在规划中起作用盲目搜索vs.启发式搜索：对于达到最低满意度要求的规划，启发式搜索在任何情况下都大大优于盲目算法。对于最优规划，启发式搜索也更好。（但差异不太明显）系统搜索vs.局部搜索：对于达到最低满意度要求的规划，两者都有一些成功的案例。对于最优规划，需要系统算法。$ o$在这里，我们介绍了在规划中最成功的搜索算法的子集。仅涵盖了某些盲搜索算法。（为此，请$quad$参阅Russel＆Norvig第3和4章）
1.5搜索算法中的术语术语定义搜索结点$n$包含搜索所到达的状态(states)，以及有关如何到达该状态的信息。路径代价$g(n)$到达$n$的路径代价。最优代价$g^*$一个最优解路径的代价。对于一个状态$s$，$g^*(s)$是到达$s$的最便宜路径的代价。结点扩展生成一个结点的所有后继结点，通过应用适用于该结点状态的所有行动来实现。在此之后，状态$s$本身也被称为扩展过的（expanded）。搜索策略决定下一次扩展哪个结点的方法。OpenList当前所有的候选待扩展结点(nodes)的集合。又称frontier（边缘）。ClosedList所有已经扩展过的状态(states)的集合。仅用于图搜索，而不用于树搜索。又称探索集（exploredset）1.6世界状态vs.搜索状态一个（经典）搜索空间通过下面三种操作定义：
$ extrm{start}(,)$：生成初始（搜索）状态。$ extrm{is-target}(s)$：测试一个给定的搜索状态是否是一个目标状态。$ extrm{succ}(s)$：生成搜索状态$s$的后继状态$(a,s’)$，其中$a$是在生成该后继状态中所采取的行动。搜索状态$ e$世界状态：
前进（Progression）规划是，搜索状态$=$世界状态首先从问题的初始状态出发，考虑行动序列，直到找到一个能够得到目标状态的序列。后退（Regression）规划否，搜索状态$=$世界状态的集合，表示为合取子目标（conjunctivesub-goals）我们从目标状态开始，向后应用行动，直到找到一个能够达到初始状态的行动序列。$ o$在整个课程中，除非另外说明，否则我们只考虑前进（Progression）规划。$quad$我们用“$s$”交替地表示世界状态/搜索状态。
1.7搜索状态vs.搜索结点搜索状态$s$：搜索空间中的状态（顶点）搜索结点$sigma$：搜索状态，加上关于在搜索过程中在何处/何时/如何遇到这些状态的信息。一个搜索结点中包含哪些信息？不同的搜索算法在一个搜索结点$sigma$中存储了不同的信息，但是一般都包含以下几种典型的信息：
$ extrm{state}(sigma)$：关联的搜索状态。$ extrm{parent}(sigma)$：指向该搜索结点$sigma$的来源（即父结点）的指针。$ extrm{action}(sigma)$：一个导致$ extrm{state}( extrm{parent}(sigma))$变为$ extrm{state}(sigma)$行动。$g(sigma)$：$sigma$的代价。（从根结点到$sigma$的路径代价）对于根结点，$ extrm{parent}(sigma)$和$ extrm{action}(sigma)$无定义。
1.8搜索策略的评估指标保证完整性：当一个解存在的时候，我们的策略能够保证找到这个解吗？最优性：返回的解能够保证是最优解吗？复杂度时间复杂度：找到一个解需要花费多长时间？（在生成状态下进行测量）空间复杂度：搜索需要占用多少内存？（在状态下进行测量）典型状态空间特征控制复杂度分支因子$b$：每个状态有多少个继任者？目标深度$d$：到达最浅的目标状态所需行动的数量。2.盲目系统搜索算法2.1在我们开始之前盲目搜索vs.有信息搜索盲目搜索不需要除了问题本身以外的任何输入。优点：可以简单地直接从问题开始，不需要额外信息，不需要考虑启发函数等等。缺点：求解过程比较盲目，会生成大量扩展，实践中计算量很大，效率很低。有信息搜索需要额外输入一个启发函数$h$，该函数将状态映射到它们目标距离的估计优点：在实践中，通常比盲目搜索更加高效缺点：需要找到/实现启发函数$h$注意：在规划中，启发函数$h$是从声明式问题描述中自动生成的。关于盲目搜索，我们将讨论：宽度优先搜索优势：时间复杂度变体：一致代价搜索（Uniformcostsearch）深度优先搜索优势：空间复杂度迭代加深搜索（Iterativedeepeningsearch.）结合了宽度优先搜索和使得优先搜索的优势子过程中使用了深度受限搜索（depth-limitedsearch）关于盲目搜索，我们不会讨论：双向搜索（Bi-directionalsearch）两个单独的搜索空间，一个从初始状态开始向前搜索，另一个从目标开始向后搜索。当两个搜索空间重叠时停止。2.2宽度优先搜索策略：按照生成顺序扩展结点（FIFOfrontier）。
也就是说，先扩展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，以此类推。一般地，在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过。每次总是扩展深度最浅的结点，这可以通过将边缘（frontier）组织成FIFO队列来实现。图例：
图1：一棵简单二叉树上的宽度优先搜索。在每个阶段，用一个记号指出下一个将要扩展的结点。
保证：
完整性可以保证吗？可以最优性可以保证吗？对于一致行动代价（即每条边对应的代价都是一样的）而言，可以保证能够找到最优解。宽度优先搜索总是寻找一个最浅的目标状态。如果每条边的代价不是一致的，则宽度优先搜索找到的解不一定是最优解。例如：假如B、F都是目标状态，A到B的代价是5，而A到C和C到F的代价都是1，宽度优先搜索会得到路径A$ o$B，而不是代价更小的A$ o$C$ o$F。动画演示：
时间复杂度：假设$b$是最大分支因子，$d$是目标深度（最浅目标状态的深度）
生成结点数量的上界是多少？$b+b^2+b^3+cdots+b^d$：在最坏情况下，该算法会生成第一个$d$层中的所有结点。所以，时间复杂度为$O(b^d)$如果算法是在选择要扩展的结点时而不是在结点生成时进行目标检测，那么时间复杂度为多少呢？$O(b^{d+1})$，因为在目标被检测到之前，最坏情况下，之前深度$d$上的其他结点已经被扩展，我们会生成第一个$d+1$层中的所有结点。空间复杂度：和时间复杂度相同，因为所有的生成结点都保留在内存中。
例子
设定：$b=10;;quad10000; ext{nodes/second};;quad1000; ext{bytes/node}$数据：
表1：宽度优先搜索的时间和内存代价
$ o$所以，哪种问题更严重，时间还是内存？
内存。（根据我自身的经验，通常RAM内存在几分钟以内就会耗尽。）从上表可以看出，内存需求是宽度优先搜索算法中相比它的执行时间更令人头疼的问题。要求解一个重要问题，人们可以忍受等待13天搜索到第12层，但是很少有计算机能具备高达P字节的内存支持其存储要求。幸运的是，我们还有其他对内存需求较小的搜索策略。但是，时间需求依然是一个重要的因素。如果你的问题在第16层有一个解，那么（按照我们给的假定）宽度优先搜索（或者事实上任一盲目搜索算法）需要花费350年的时间来求解。一般来讲，指数级别复杂度的搜索问题不能采用盲目搜索算法求解，除非是规模很小的实例。2.3深度优先搜索策略：扩展（LIFOfrontier）中最近的结点。
深度优先搜索总是扩展搜索树的当前边缘结点集中最深的结点。搜索过程如图例所示，搜索很快推进到搜索树的最深层，那里的结点没有后继。当那些结点扩展完之后（如果还没有搜索到解），就从边缘结点集中去掉（减少内存资源的占用），然后搜索算法回溯到下一个还有未扩展后继的深度稍浅的结点。相比宽度优先搜索使用的FIFO队列，深度优先搜索使用LIFO队列，即最新生成的结点最早被选择扩展。该结点一定是最深的未被扩展的结点，因为它比它的父结点深。图例：
图2：二叉树的深度优先搜索。未探索区域用浅灰色虚线表示。已经被探索并且在边缘中没有后代的结点可以从内存中删除。第三层的结点没有后继并且M是唯一的目标结点。
保证：
完整性可以保证吗？不能，因为搜索分支可能无限长度：没有检查沿分支方向上是否存在环（cycles）。$ o$深度优先搜索可以保证完整性的前提是：状态空间是无环的（acyclic），例如：约束满足问题（ConstraintSatisfactionProblems,CSPs）。如果我们增加一个检查是否存在环的流程，那么该算法将能够保证在有限状态空间内的完整性。最优性可以保证吗？不能。最终，算法只是“选择某个方向并希望最优解在该方向上”。（深度优先搜索是一种“希望依赖好运”的方法。）空间复杂度：存储（从当前结点出发）路径上的结点和可应用的行动。所以如果$m$是到达的最大深度，空间复杂度为$O(bm)$。（其中$b$是分支因子）
时间复杂度：如果在状态空间中具有长度为$m$的路径，将生成$O(b^m)$个结点。即使可能存在深度仅为$1$的解。$ o$如果我们碰巧选择了“正确的方向”，那么无论状态空间有多大，我们都可以在$O(bl)$的时间复杂度内找到一个长度为$l$的解。
2.4迭代加深搜索策略：迭代加深的深度优先搜索（iterativedeepeningsearch）是一种常用策略，它经常和深度优先搜索结合使用来确定最佳深度界限。做法是不断地增加深度限制——首先为$0$，接着为$1$，然后为$2$，以此类推——直到找到目标。当深度界限达到$d$，即最浅的目标结点所在深度时，就能找到目标结点。
图例：
图3：二叉树迭代加深搜索算法的四次迭代。
“迭代加深搜索$,=$不断重复同样的工作直到找到一个解”
迭代加深搜索看上去是一个糟糕的算法，因为它似乎做了很多重复的工作。但事实上，这种算法有诸多优势。
保证：
完整性可以保证吗？可以（在假设分支因子$d$有限的情况下）最优性可以保证吗？可以（在假设一致代价的前提下）空间复杂度：$O(bd)$。（其中$b$是分支因子，$d$是最浅目标状态的深度）
时间复杂度：$O(b^d)$，与宽度优先搜索相近，重复生成上层结点需要付出额外代价，但不是很大。
也许迭代加深搜索看起来比较浪费：状态被多次重复生成。但是，事实上这种代价并没有多大，原因是在分支因子相同（或者近似）的搜索树中，绝大多数的结点都在底层，所以上层的结点重复生成多次影响不大。在迭代加深的深度优先搜索中，底层（深度$d$）结点只被生成一次，倒数第二层结点被生成两次，以此类推，一直到根结点的子结点，它被生成$d$次。因此，生成结点的总数为：
[N( ext{IDS})=(d)b+(d-1)b^2+cdots+(1)b^d]对比宽度优先搜索：
例子：$b=10,,d=5$
$ o$迭代加深搜索（IDS）结合了宽度优先和深度优先搜索的优势。当搜索空间较大并且解所在的深度未知时，IDS是首选的盲目搜索方法。另外，如果你确实担忧状态的重复生成，可以先用宽度优先搜索直到有效内存耗尽，然后对边缘集中的所有结点应用迭代加深的深度优先搜索。
下节内容：搜索算法(2)
本作品采用知识共享署名-非商业性使用-相同方式共享4.0国际许可协议进行许可。欢迎转载，并请注明来自：YEY的博客同时保持文章内容的完整和以上声明信息！Previous人工智能自动规划01：导论Next自然语言处理03：N-gram语言模型