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

基于命题可满足性的经典最优规划方法 吕帅刘磊江鸿魏唯 (吉林大学计算机科学与技术学院 长春130012) 式。首先给出与编码相关的概念与性质，在基于Graphptan的编码方式的基础上，设计一种新的编码方式：基于FA 的编码方式，并从理论上证明该编码方式的有效性。设计并实现对应的规划系统FA-SP，利用国际规划竞赛选用的 缩，除个别问题外求解效率都有一定程度的提高；对于顺序规划域BlocksWorld，编码规模平均压缩了40％，求解效率 不同程度的提高。 关键词基于可满足性的规划，基于Graphplan的编码，编码，框架公理，规划系统 中图法分类号TPl81文献标识码A Classical MethodBasedon OptimalPlanning PropositionalSatisfiability Shuai Lei WEIWei LU LIU JIANG Hong of Scienceand 130012，China) Computer Technology，JilinUniversity，Changchun (College Abstract isanovel SATPLAN2006，whichisthestate-of-the-art Graphplan-basedencoding encodingadoptedby opti— ITlal ofInternational in2006．It definedthe andcharactersabout planner PlanningCompetitionfirstly concepts encoding． anew FA-based themutexado- Basedon reducing Graphplan-basedencoding，itproposedencoding，calledencoding，by msofactionsand frameaxioms．It thesoundnessand ofthe appending justifies completenesscorrespondingproposed and the calledFA—SP，andtesteditwithbenchmarks designedimplementedcorrespondingplanner adopted encoding．We resultsvalidatethatforboth International withSATPLAN2006，the by PlanningCompetition，respectively．Comparing scalesof ofFA—SPare andsolverefficienciesofthemare alltWOdomains