基于命题可满足性的经典最优规划方法

摘要：

基于Graphplan的编码方式是2006年国际规划竞赛中著名的最优规划系统SATPLAN2006采用的编码方式.首先给出与编码相关的概念与性质,在基于Graphplan的编码方式的基础上,设计一种新的编码方式:基于FA的编码方式,并从理论上证明该编码方式的有效性.设计并实现对应的规划系统FA-SP,利用国际规划竞赛选用的Benchmark问题予以测试.实验结果表明,与SATPLAN2006相比,FA-SP对于所测两类规划域编码规模均有所压缩,除个别问题外求解效率都有一定程度的提高;对于顺序规划域Blocks World,编码规模平均压缩了40%,求解效率平均提高了2倍;对于并发规划域Logistics,带有小于5%的框架公理的FA编码规模平均压缩了75%,求解效率也有不同程度的提高.

关键词：基于可满足性的规划、基于Graphplan的编码、编码、框架公理、规划系统

所属期刊栏目：37

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金60603031,60773097,60873044;教育部高等学校博士学科点专项科研基金20060183044,20070183057

在线出版日期：2010-06-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：192-196