基于STRIPS语言的经典规划.pdf

《基于STRIPS语言的经典规划.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于STRIPS语言的经典规划-----大学生研究计划终期报告Name：吕强Number：pb03011106DepartmentofComputerScienceandTechnology，USTCAbstract本文主要就作者在大学生研究计划期间所阅读的资料简要介绍规划的语言以及全序规划算法和偏序规划算法。全序规划主要介绍状态空间搜索算法以及启发式在这种算法上的应用；偏序规划主要介绍POP算法的思想。并在最后比较了全序规划和偏序规划的优缺点。Keywords：STRIPS、状态空间搜索、启发式、偏序规划，POP算法。1．Introduction提出能达到一定目标的

2、行动序列的任务称为规划。规划可分为经典规划和非经典规划。简单的来说，经典规划研究那些完全可观察的、确定性的、有限的、静态的以及离散的环境，非经典规划研究的是部分可观察的或随机的环境[1]。普通的Agent规划有下列几个较难处理的问题：1)一个规划问题中不相关的行动太多时，普通Agent无法处理；2)很难寻找到一个好的启发式函数；3)Agent很多时候并不能够利用问题分解，即不能够把规划问题完全分解为子问题。虽然在理论上，这些困难看起来的确有些难以解决，但是在经典规划理论研究中，往往都是直接忽略或者增加一些假设以避免这些问题，因为在实际应用中，问题往往被限定在一个有限的

3、范围内，我们只需要使用一些特殊技术就能解决这些问题。例如：在以下要介绍的规划算法中，都是假设问题是可以分解的（子目标独立性假设）。2．Planning语言2.1STRIPS在介绍经典规划之前我们先介绍一下规划语言。最初描述规划问题是用情形演算的语言，情形演算是一种特殊的一阶语言，它设置了一些特定的语法对象以描述行动和状态变化。不过情形演算有一个致命的缺憾――框架问题。框架问题分为表示框架问题和推理框架问题，虽然在情形演算中用后继状态公设取代效果公设和框架公设而解决了表示框架问题，但是却无法解决推理框架问题。STRIPS语言是R.File&Nilsson在1971年提出

4、的表示规划问题的一种简洁的形式化语言，它是一种能够描述范围很宽的各种问题的语言。STRIPS语言成功地解决了推理框架问题，在说明它是怎么解决这个问题之前，先介绍STRIPS的相关知识。STRIPS语言定义了以下表示[1]：ò状态：在规划问题中，用一个文字的合取式表示世界中的某一状态。我们采用一阶文字表示这种状态，在一阶状态描述中，这些文字必须是基项(ground)，而且必须是无函数的。另外，还采用了封闭世界假设：在一个状态中没有提到的条件被认为是假的！ò行动（Action）：一个行动是由前提(Precondition)和效果(Effect)来表示和决定的。其中，前提是

5、执行这个行动所必须满足的条件，效果是执行行动之后引起状态的变化，效果一般用删除表(D)和添加表(A)表示。例如：表示一个积木世界中的行动――把积木x从积木y上搬到z上如下图所示。准确地说它表示的是一个行动模式，它包含的意义是指一系列不同的行动，这些行动可以通过把变量x,y，z实例化成不同的常量而得到。Move(x,y,z)PC:on(x,y)∧clear(x)∧clear(z)D:on(x,y)∧clear(z)A:on(x,z)∧clear(y)∧clear(F)ò目标：其实目标表示也应包括在状态表示中，之所以把它单独提出来，是因为目标仅是用正文字的合取式表示的，而

6、且，一个状态S满足目标G(Goal)当且仅当状态S包含G的所有原子。说明：注意这里有一个很重要的假设----无函数假设，之所以使用这个假设，是因为无函数假设保证了任何问题的行动模式都可以被命题化，而不会无限的迭代下去，以至于规划器无法处理。我们知道在情形演算中使用了fluent（变式），fluent是指其值依赖于情形的谓词和函数，如：我们在积木世界中表达B在A上这个状态――On(B,A,S)，注意这里每一个状态表示都与某一“时刻”的状态S联系在一起，正是因此才导致了框架问题(更多细节参见参考书目[1]的第十章)，相对而言，在STRIPS中状态表示为On（B，A），这样

7、，执行某一个行动后原状态未改变的逻辑公式就可以直接“复制”下来，而在情形演算中是必须通过框架公设或后继状态公设来得到的。下面通过一个具体例子来说明STRIPS是如何解决框架问题的。例1：如图1所示的积木世界状态S，S用STRIPS语言表示为：S={on(B,A)∧on(A,C)∧on(C,F)∧clear(B)∧clear(F)}现执行行动Move（B，A，F），此行动的表示如下：Move(B,A,F)PC:on(B,A)∧clear(B)∧clear(F)D:on(B,A)∧clear(F)A:on(B,F)∧clear(A)∧clear(F)行动