基于压缩编码的经典最优规划方法  

Classical optimal planning method based on compacted encodings

作　　者：吕帅[1] 刘磊[1] 江鸿[1] 魏唯[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（工学版）》2010年第6期1644-1649,共6页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(60603031;60773097;60873044;60873148;60973089);高等学校博士学科点专项科研基金项目(20060183044)

摘　　要：在基于Graphplan的编码方式的基础上,设计了基于PMA的编码方式,并从理论上证明了该编码方式的有效性;提出了编码求解过程中的一种目标状态预处理策略;设计并实现了相应的规划系统PMA-SP,并利用国际规划竞赛选用的Benchmark问题予以测试。结果表明:与SATPLAN2006相比,对于顺序规划域Blocks World,编码规模压缩了40%,求解效率提高了2倍;对于并发规划域Logistics,编码规模压缩了80%以上,求解效率各有好坏,PMA-SP对于所测两类规划域编码规模有所压缩,求解效率也有一定程度的提高。Based on Graphplan-encoding,a new encoding called PMA-based encoding by reducing the mutex axioms of actions,is proposed.The soundness and completeness of the new encoding are justified.The preprocessing method for goal states during encoding solving process is also proposed. The corresponding planner called PMA-SP based on the above encoding is designed and implemented,and test with benchmarks adopted by International Planning Competition.Comparing with the planner SATPLAN2006,the experimental results demonstrate that,for both tested domains,the scales of encodings of PMA-SP are compacted and the solver efficiencies are improved.For sequential planning problem Blocks World,the scales of encodings of PMS-SP are compacted nearly 40%and solver efficiencies are increased nearly two times.For parallel planning problem Logistics,the scales of encodings of PMA-SP are compacted more than 80%.

关 键 词：人工智能 基于可满足性的规划 基于Graphplan的编码 互斥公理 规划系统 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]