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

Classical optimal planning method based on compacted encodings

在基于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%.