角括号<> 表述名字
圆括号（）元素名字
方括号[]围绕着option
An asterisk（*）means “zero or more of”
a plus（+）means“one or more of”
规划系统是问题求解算法，它在关于状态和行动的显示命题表示或关系表示上运转。这些表示方法使获得高效启发式和强有力且灵活的问题求解算法成为可能。
状态空间搜索能够在前向方向（前进）和后向方法（后退）上操作。有效的启发式可由子目标独立性假设和状态规划问题的各种松弛而获得。
一个规划图可从初始状态开始增量式地构造出来。每一层包含一个所有在那个时间步出现的文字和行动的超集，并且对文字之间或行动之间互斥（或简称mutex）关系进行编码。规划图为状态空间和偏序规划器产生有有的启发式，并能直接用于GRAPHPLAN算法中。
其他方法包括情景演算公理上的一阶逻辑推理；将规划问题编制为布尔满足性问题或约束满足问题；在偏序规划空间进行显示地搜索。
进行规划的每一种主流方法都有其拥护者，而哪种方法最好还没有达成一致。方法之间的竞争和杂交导致了规划系统的效率上的重要收货。
规划系统的五大类：
基于图规划的规划系统：
其代表有美国卡乃基一梅隆大学( Carnegie Mellon University) 的图规划系统GraphPlan (Blum和Furst) 、德国的IPP、英国的STAN 、美国盛顿大学(University ofWashington)的SGP(Daniel S。Weld 等)89]。
先来介绍几个概念:
1.有效(valid) 规划解:规划问题的一个有效规划解是一一个动作的集合和对每- - 一个动作发生时间的指定。
2.规划图(planning graph) :是一个具有两类节点和三类边的有向、分层图。规划图各层是命题层(propositionlevels)和动作层(actionlevels)交替出现的，命题层包含命题节点(标识为一些命题)，动作层包含动作节点(标识为动作)。规划图的第- - 层是命题层，包括规划问题初始条件下的所有命题。
图规划在两个阶段(phases)交替进行:图扩展( graph expansion)阶段和解提取(solutionextraction)阶段。图扩展阶段正向扩展规划图直到目标状态的所有命题都出现为止。解提取阶段反向搜索规划图以求出规划解。
基于启发式搜索的规划方法
目前规划系统为了提高效率，几乎都采用了启发信息。启发式搜索的基本思想是:人为给定一个评估函数，对每个搜索状态进行计算，得到每个状态的值，从而决定哪个状态较好。但是，这个启发函数用在与领域无关的规划系统上比较困难。
在当前智能规划研究中，领域无关的启发信息的抽取技术是基于实现目标的动作数量，对要解决的问题P放宽到一个比较简单的问题P’，抽取技术就是基于P’来评估。Bonet提出的向前搜索的一个放宽方法7就是将操作的删除边忽略，对于每个状态s，得到在放宽了的问题P’的启发函数h’(s)就可以作为原有问题P的启发函数h*(s)的下限，这样h’(s)就可以作为合适的启发函数作用在原有问题P.上。.
实质上，初始状态和操作可以理解为-一个定义了的节点有向图，对于每个操作op都有一条由其前提条件节点指向正效果节点的边，这样从初始状态到达节点p的开销就可以计算。从状态s到节点p的开销g(s)递归定义为:
O(p)表示添加效果为p的操作集，就是p∈Add(op)。g,(Prec(op)) 是从状态从状态s到操作op前提条件节点的计算。
Bonet对上面的g ,(p)提出更为简单的向前计算过程，首先初始化图上各个节点:当p∈s，令g,(p)为0;否则令g,(p)=∞。这样，每一次操作op作用在状态s上，每个添加效果节点p∈Add(op)添加到s，g,(p) 更新为:
g,(p)= min[g,(p),1 + g,(Prec(op))]
这个计算g,(p)的过程一直到g,(p) 不再改变为止，显然，这个过程在节点数目一-定的情况下，时间复杂度是多项式的。
这样，节点集C的估算g , (C)可以由在这节点集C里面每个节点估算来得到。同理h(s)定义为:
def h(s)= g,(G)g, (C)可以定义为三种估算:节点集C中所有节点估算值的和、节点集C中节点最小估算、节点集C中节点最大估算。在HSp[28]中，Bonet 主要采用两种估算:
A) g,(C)为节点集中所有节点估算值的和，称作添加启发函数haa:
1.HSP
规划系统HSP ( Heuristic Search Planner)[3在AIPS-00的规划大赛上取得了成功，它的与领域无关的启发信息的抽取是基于实现目标的动作数量，对要求解的问题P放宽到一个比较简单的问题P’，抽取技术就是基于P’来评估。Bonet提出的向前搜索的-一个放宽方法就是将操作的删除边忽略。对于每个状态s得到在放宽了的问题P’的启发函数h’(s)就可以作为原有问题P的启发函数h*(s)的下限，这样h’(s)就可以作为合适的启发函数作用在原有问题P .上。
2.FF
两个版本的FF (FAST-FORWARD)规划系统23参与了这次比赛。第-一个版本是FF-v2.2，它大致跟在2000年比赛使用的FF-v2.2版本- 致， 只是改掉了在预处理阶段存在的小错误:另一个版本是Metric-FF，它能处理用数字表示的约束和对用数字表示的状态数值变量的影响。两个版本的FF (FAST-FORWARD)规划系统23参与了这次比赛。第-一个版本是FF-v2.2，它大致跟在2000年比赛使用的FF-v2.2版本- *致， 只是改掉了在预处理阶段存在的小错误:另一个版本是Metric-FF，它能处理用数字表示的约束和对用数字表示的状态数值变量的影响。
Metric-FF可以根据用户两个要求来分别对规划系统进行两种设置。这两个要求是: 1.在最短时间内生成合法规划; 2、 生成最优的规划。前- -种设置搜索技术采用跟FF-v2.2类似的加强爬山法。这种方法是:采用放宽规划长度作为从初始状态到目标状态距离的估计和利用动作互斥来剪枝向前搜索;后一种设置搜索技术采用类似标准的A算法，利用采用放宽规划长度作为从初始状态到目标状态距离的估计也就是启发函数。在两种设置中放宽规划很自然的从STRIPS/ADL中扩展得到。只需要在预处理阶段把数值型约束和影响转化，使得它们都是严格单调的。
在这些严格单调的限定下通过忽略所有删除边和数值影响变元来放宽一一个规划。 如果这个放宽规划得到解决，那么Metric-FF 综合考虑它的逻辑和数值因素跟FF-v2.2计算启发函数，假如在没有一个放宽规划能到达这个状态，那就证明这个状态是不可达的。
3.LGP
规划系统LPGl76 (Local Search in Planning Graphs)是一个基于局部搜索和规划图的规划系统，并且能处理在PDDL2.1领域上用数值来表示的度量和持续时间，和能解决生成规划和优化规划方面问题。
LGP基本的搜索策略基于Walksat- 一个 高效的SAT问题求解程序。LGP的搜索空间是一个“动作图”(“actiongraphs”),部分规划子图就表示了部分规划搜索步骤就是一一个图的修改，使得一个“动作图”转换成为另一个“动作图”。LGP使用了一种紧凑的规划图表示形式来定义搜索邻近点，使用参数启发函数来评价它的值。这些参数表示在这个部分规划中不同种类冲突的权值在搜索过程中动态计算。评价函数采用了–些通常的启发技术，例如对一个前提条件计算启发搜索开销和启发执行开销。持续的动作和数字化的量值都表示在“动作图”，且通过评价函数模型化。LGP在测试例子中能产生高质量的规划，因为每一次生成一个规划的序列，下一次质量会在这基础上得到提高。LGP采用了跟FF.相似的“最好优先”(best-first)算法，系统能在进行了若干步搜索后会自动转换到“最好优先”搜索。
基于逐步细化的分层规划方法
以SHOP2[36为代表的层次规划方法思想是:首先勾画出- -个完整但又比较粗略的规划解，然后逐步细化、逐步明确，直到足以具体完成整个规划的每一步 操作，层次规划方法实际上把不同性质的问题放在不同层次上加以考虑。
SHOP2
SHOP2[36]是-一个分层任务网络规划系统。跟在一般的规划需要一组目标不一 一样， 取而代之是SHOP2需要一个半序的任务序列去执行。为了解决一些领域上的规划问题，SHOP2需要- -些基于领域知识的方法来将一一个任务分解为- 组半序的子任务。 为了得到合法的规划，SHOP2将问题变形:它递归地将任务分解为子任务，直到它到达能被规划操作直接执行的原始的任务。
跟大多数分层任务网络规划系统不一样，SHOP2是从初始状态向前规划:给出几个任务需要分解SHOP2按它们同一执行顺序来得到规划。在规划过程中的每个点上，SHOP2已经知道在这个点之前所执行的操作，故SHOP2了解当前状态。这种技术使得SHOP2的预处理估计机制相当强大: SHOP2预处理方法和操作可以包含逻辑推理、复杂数值计算和外接程序。
SHOP2比SHOP成功的地方在于它的预处理过程。SHOP 需要他的任务是全序结构,然而SHOP2只需要它的任务是半序结构。因为SHOP2可以插入不同的子任务，- - 些领域知识在SHOP2比SHOP更容易表示。
基于约束可满足的规划方法
起初SATPLAN是Henry Kautz和Bart Selman深入地分析了传统的基于定理证明的规划以后提出来的完全不同于以往演绎技术的一种特殊的规划系统，它克服了传统规划系统的异常(每一个模型不一定对应一一个有效的规划解)情况，使得每-一个 正确模型都有一个有效的规划解与其相对应。
SAT规划系统的体系结构如图11.10 所示，编译器(Compiler) 的输入是规划问题(包括初始状态、目标状态和动作集合)，它首先猜测规划解的长度，产生一个逻辑命题公式，如果逻辑命题公式是可满足的，它蕴涵着规划解是存在的:符号表( Symbol Table)记录了命题变量和规划实例之间的对应;简化器(Simplifier)运用较快(通常为线性时间)的技术(如单元子句法，纯文字消去法等)来降低CNF公式的规模;求解器(Solver)运用系统或统计的方法来找到-一个满足的赋值:解码器(Decoder) 用符号表把赋值转换成一个规划解。如果求解器发现公式是不可满足的，那么编译器就会产生新的编码(代表更长的规划解)。
由基于SAT的规划的体系结构可以看到，这种规划方法关键在于两个环节，- -个是编码方式，另一个是求解方式。有关第一个问题的研究取得了一系列的进展，如[38]中综合叙述了几种普遍的编码方式，由于基于SAT的规划算法是基于SAT算法来实现的，所以第二个问题其实就是选择好的SAT算法，而可满足性(SAT)问题是人工智能研究领域中的一个基本理论问题，最近几年来，每年都有新的SAT算法问世，人们设计各种各样的技术来提高解决SAT问题的效率39-441，这几年来主要有GSAT算法和WALKSAT算法，但是这两个算法都不是完备的，一一个比较经典的完备SAT 算法是DP算法，以下就先来介绍GSAT算法和DP算法。
总结GraphPlan和SATPlan的相同点和异同点之处，共同点: SATPlan 和GraphPlan都分两阶段进行，建立一个命题结构( Propositional Structure) ，在图规划中是规划图，在SAT规划中是CNF wff， 在第一-步所建立的结构中搜索规划解。异同点:图规划(GrphPlan)用的实例化命题结构算法较好，SAT规划( SatPlan)的搜索算法更加强大。
结合以上两种算法的优点，Kautz 和Selman于1998 年在AIPS.上提出了BLACKBOX规划算法，此系统分三个步骤进行工作:
1.把一个规划问题(以标准的STRIPS形式描述的)转化为一个规划图。
2.把第一步中生成的规划图转化成一个CNF wff。
3.运用最快的SAT引擎解决wff。
基于模型检测的规划方法
模型检测(Model Checking)是当前计算机研究领域上的一个热点，它将一个系统模型跟逻辑需要进行比较，从而发现不一致性。传统上，这个思想用来硬件电路上的验证和网络协议的验证。近期，这个思想用在智能规划中，取得了令人瞩目的成就，产生了一系列功能较强的规划系统:MBP、MIPS 、TALPL ANNER、TLPI AN和UMOp。
命题公式可以转化为不同的范式，一 般情况下转化得到的范式有合取范式(CNF,Conjunctive Normal Form)和析取范式(DNF，Disjunctive Normal Form)。对于每个命题公式都有一个相应的逻辑范式来跟其相等价，但是这样的范式复杂度是以指数级增长的。为何要使用范式?其主要理由有两个:
1、当采用某种范式来描述命题公式的时候，相当一部分算法更加容易来设计。例
如:很多定理机器证明的算法基础–消解规则，它就采用合取范式来描述命题公式，假如不采用合取范式来描述，那么设计消解规则将是比较困难的。
2、当采用某种范式来描述命题公式的时候，相当一部分可计算问题解决起来的效率
更加高。例如:测试命题公式的有效性是一个co-NP 难题，但这个命题公式采用合取范式来描述时，那么这复杂度就是-一个多项式时间，只需要对每一个合取项进行检查是否对一个命题变量p都包含了p和→p。
但是对于一-些可计算问题来说，转化为一个普通的范式通常不是一个最好的解决方案。就如采用合取范式来测试命题公式的有效性，它的时间复杂度是多项式时间，但是这是由空间复杂度来换取的，它的空间复杂度为指数级。
近期在智能规划系统上，各位研究者也根据相应的设计采取了不同的范式，其中之一是两元判定图表BDD’511 (Binary Decision Diagrams)，采用BDD的主要原因是:采用BDD表达的两个谓词公式时，两个BDD范式逻辑相等，当且仅当这两个BDD范式是语法相等，即两个BDD范式逻辑相等，当且仅当这两个BDD范式是同一个BDD范式。然而,BDD范式空间复杂度也是没加限制的命题公式的指数级倍数，但是在BDD.上的操作通常可以是在多项式时间完成。
BDD表达式是基于三重布尔操作ifthen-else ite ( p,φ,,φ2 )定义为
(p^φ)v(-p^φ2)，p是一个命题。任何- -个布尔表达式都能采用这个布尔操作和其命题变量和常量(1: true，0: false)。它为布尔函数提供了一个有效地的、规范的表达方法，被广泛用于模型检测领域，特别是使用在协议验证方面。
智能规划的应用
目前智能规划应用在自动系统中使得自动化系统灵活性、健壮性和适应性得到提高。主要应用研究领域有:机器人、智能企业和商业软件。
在IJCAI-01的智能规划讨论会上，会议主题是“资源约束规划”，目标是为实际应用上的规划研究学者提供一一个交流的平台。 会议.上的规划系统都是在计算机实际应用系统中得到广泛使用的规划系统，例如:美国宇航局的ASPEN规划系统、马里兰大学的CIRCA、.美国宇航局的EUROPA、华盛顿大学的LPSAT规划系统和爱丁堡大学的O-Plan规划系统等等。这次会议主要讨论内容有:混合规划系统、整合规划系统、资源约束上的推理技术、时序规划、智能规划和调度、优化目标规划和有关规划的模型、问题领域和实验结果。
航空航天中的应用
智能规划的一个重要应用领域是航天航空，有兴趣的读者可以参照《宇航学报》上的一篇综述《航天器自主运行技术的进展》[68], 这是宇航专业的文章，可是它大部分讲的是智能规划的一个重要应用领域是航天航空，有兴趣的读者可以参照《宇航学报》上的一篇综述《航天器自主运行技术的进展》[68], 这是宇航专业的文章，可是它大部分讲的是
ASPEN
在航天航空应用中取得最好效果的是美国宇航局的ASPEN (Automated Scheduling andPlanning Environment)00规划系统。ASPEN获得了1999年美国宇航局的软件比赛优秀奖并旷泛用在进行外太空任务的宇航器上，包括Citizen Explorer、MARS-01 和DS-T 等宇航器目前对外也有其商业版本出售。
在宇航器中智能规划的应用主要是将较高层次的科学研究和工程操作指令转化为较低层次的宇航器执行指令。ASPEN结合了宇航器操作约束、飞行规范、 宇航器硬件模型、科学实验目标和操作过程来自动生成较低层次的宇航器操作序列。通过自动生成宇航器操作序列和结合了相关的领域知识APSEN使得宇航任务可以由一个小分队来控制，这样降低了开销。
ASPEN是一个基于面向对象的系统，提供了- -组可重用的软件部件，这些部件可以比较简单地应用在目前复杂的规划系统上，包括:
1、约束模型语言，可以令用户方便的定义应用领域。
2、约束管理系统，用来表示和维护宇航器的可操作性、资源约束和操作需要的条件。3、一组搜索策略，用来规划生成和修改，并满足“硬约束”。
4、一种语言来表示规划选择和优化这些选择。
5、 “软”的、实时的修正规划能力。
6、时序推理系统，用来表示和维护时序约束。
7、图形化规划和调度的界面。
这方面应用的-一个具体例子是哈勃空间望远镜(HST, Hubble Space Telescope)的修复,在修复过程中,地面人员不断得到关于HST能作什么、不能作什么的最新信息，然后对修复工作作出规划,从而使HST恢复了正常观测能力!
机器人中的应用
规划在机器人中的应用主要有:环境的模型化描述、机器人能力的模型化描述、目标的模型化描述和实时的输入响应。机器人规划研究跟其它规划研究领域不一样，主要在于机器人处于有噪音的各类部分的环境模型中，它通过感应器和交流信道得到的信息都存在噪音，这样机器人就需要将感应和执行的整合来进行直接规划。
目前主要研究领域包括: 1、路径规划:指在机器人从一个开始的位置如何走到目标位置的控制机制并且要满足动态的约束。2、感知规划:主要是有关如何采集外部和内部信息的规划，例如:辨别物体确定机器人位置对环境的观察。3、任务规划:跟传统的规划问题相似，不过更加注重时间和资源的分配在动态的环境、不确定的或部分已知的状态知识的条件下进行规划。4、规划交流:多个机器人之间和人与机器人之间如何进行信息交换，包括询问信息和反馈信息两大部分。
智能规划在机器人学中具体的应用方向有:环境模型的描述，控制知识的表示，路径规划，任务规划，非结构环境下的规划，含有不确定性时的规划，协调操作(运动)规划，装配规划，基于传感信息的规划，任务协商与调度和制造(加工)系统中机器人的调度。
在智能工厂中的应用
智能规划是人工智能研究中应用性很强的–个研究领域.例如,在工厂作业调度规划问题中(Job shop scheduling)，就是要考虑在有限的加工资源(车床,刨床,钻床)的情况下，根据已知的工件的加工顺序要求对整个车间的生产作出安排,使得加工完所有工件所需的时间尽可能的少,每台机床的等待时间尽可能的短.这就使工厂在同样设备条件下，由于作业调度规划合理而增加了生产能力,从而给工厂带来了可观的经济效益.
智能规划在智能化工厂“中的应用”是指从生产设计到生成产品监测生产的一系列过程它不只包括单个企业，还可以处理多个企业之间的关系，例如:供应链和虚拟企业。主要采用资源约束的方法进行求解[72]。目前主要研究领域包括:
1、生产流程规划:在一个功能化的工厂中将-一个生产要求转变为一组详细的操作指令。许多基于知识工程的软件在这方面取得了较好的效果，先将现实生产流程转化为知识库中信息，然后再根据相应的生产要求来转化。
2、生产安排规划和调度:将生产安排用来迎合客户的需求按时交货，即我们通常说的ERP作业调度。
商业中的应用
1.网路信息集成
网络信息集成74的过程是根据领域本体的内容，从互联网上采集信息并将信息集成到领域本体中，网络信息集成的实质意义是为网络信息提供–种重新组织和理解的机制。目前研究主要集中在查询规划中。查询规划可以定义为:把对信息对象框架的查询转化成只对信息源作访问的操作序列。在规划的执行过程中有时需要将信息源返回的结果合并起来分析以作出下一步的规划。所以信息的合并是查询规划中的一个重要环节。我们把信息的合并定义为:合并两个残缺信息对象的框架，即将两个属性值对集结合成一一个 属性值对集。合并的依据是信息源之间的相关链接。目前查询规划已经扩展到生物信息查询上，较好的有在IBM公司的DiscoveryLink系统上的应用75]。
2.运输规划
网络信息集成74的过程是根据领域本体的内容，从互联网上采集信息并将信息集成到领域本体中，网络信息集成的实质意义是为网络信息提供–种重新组织和理解的机制。目前研究主要集中在查询规划中。查询规划可以定义为:把对信息对象框架的查询转化成只对信息源作访问的操作序列。在规划的执行过程中有时需要将信息源返回的结果合并起来分析以作出下一步的规划。所以信息的合并是查询规划中的一个重要环节。我们把信息的合并定义为:合并两个残缺信息对象的框架，即将两个属性值对集结合成一一个 属性值对集。合并的依据是信息源之间的相关链接。目前查询规划已经扩展到生物信息查询上，较好的有在IBM公司的DiscoveryLink系统上的应用75]。
在目前物流应用问题中根据动态的不断改变的运输要求而对一-队交通工具进行实时规划(行程调整和计划安排) [701。 这些交通工具可以是:在一个房子里边的移动机器人、在一个城市道路上的的士甚至是经典的电梯问题。然而在这个问题中存在着很多的制约条件来使得运输规划变得复杂，例如时间限制(Time window)、最终期限、运输能力、行程时间、资源优化，更多的是象交通状况、天气状况、车辆中途损坏等不可预测的事件。另外运输规划在突发事件的大规模运输调度中也有所应用73]，例如:短时间内的军事调度和部署。
另一个典型的工厂作业调度规划问题是考虑在有限辆的货运汽车的前提下，在不同的地点之间运送货物.规划的输出是一张车辆运转计划表,使得汽车尽可能地满载运输,空车运行情况尽可能地少,车辆闲置的情况尽可能地少,这当然也会给运输公司带来可观的效益.美国联帮太平洋铁路(Union Pacific Railroad, UPRR)有 31000 多英里的铁路，覆盖美国西部的24个州。手工编制部分调度计划需要几天时间，而且由于规划的资源利用率低造成很大浪费. Murphy等人1996 年1月为美国联帮太平洋铁路建立的铁路自动调度系统(Rail TrainScheduler, RTS), RTS能够产生好的,低费用的调度计划691.美国联帮太平洋铁路由于使用了这个调度系统，每年可节约资金50万美元。.
protege
可以自定义本体也可以使用URI进行获取本体。
http://www.pizza.com/ontologies/pizza.owl
关于形式语义学(参考书籍：形式语义学引论 第二版)：
形式语义学(Formal Semantics)，是研究程序设计语言的语义的学问，以数学为工具，运用符号和公式，严格的解释程序设计语言的语义，使语义形式化。
形式语义学：
操作语义学(Operational Semantics),着重模拟数据加工过程中计算机系统的操作;
指称语义学(Denotational Semantics),主要刻画数据加工的结果，而不是加工过程的细节;
代数语义学(Algebraic Semantics),可看作是指称语义学的一个分支，以使用代数学为特征;
公理语义学(Axiomatic Semantics)，用公理化的方法描述程序对数据的加工
