一种优化的一致性规划状态变量选择算法-计算机应用研究.PDFVIP

第３３卷第６期 计 算 机 应 用 研 究 Ｖｏｌ３３Ｎｏ６ ２０１６年６月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｊｕｎ．２０１６ 一种优化的一致性规划状态变量选择算法 李伟生，李颜秀 （重庆邮电大学计算机科学与技术学院，重庆４０００６５） 摘　要：研究了一致性规划任务信念状态空间的表示方法。针对一致性有限域表示（ＣＰＴＦＤＲ）算法在任务生 成阶段选择状态变量的不足，提出了一种基于初始状态中文字相容互斥的状态变量选择算法———ＭＥＣＶ算法。 ＣＰＴＦＤＲ未考虑初始信念状态中文字的互斥性，产生冗余的编码信息，降低了编码的效率。ＭＥＣＶ算法利用有 用正负文字构造新的未覆盖事实集，提取初始信念状态中处于不同世界状态的文字组成互斥组，再编码状态变 量。实验结果表明该算法能有效地压缩信念状态空间。 关键词：一致性规划；ＣＰＴＦＤＲ；信念状态空间；变量选择；互斥组 中图分类号：ＴＰ１８１　　　文献标志码：Ａ　　　　　文章编号：１００１３６９５（２０１６）０６１７１７０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１６．０６．０２６ Ｏｐｔｉｍｉｚｅｄｓｔａｔｅｖａｒｉａｂｌｅｓｓｅｌｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｉｎｃｏｎｆｏｒｍａｎｔｐｌａｎｎｉｎｇｔａｓｋ ＬｉＷｅｉｓｈｅｎｇ，ＬｉＹａｎｘｉｕ （ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓ＆Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ４０００６５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓｓｔｕｄｙｆｏｃｕｓｅｄｏｎｔｈｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅｂｅｌｉｅｆｓｔａｔｅｓｉｎｃｏｎｆｏｒｍａｎｔｐｌａｎｎｉｎｇｔａｓｋｓ．Ｔｈｅｓｔａｔｅｖａｒｉａｂｌｅｓｓｅｌｅｃ ｔｉｏｎａｌｇｏｒｉｔｈｍｉｎｔｈｅｐｒｏｃｅｓｓｏｆＣＰＴＦＤＲｇｅｎｅｒａｔｉｏｎｉｓｎｏｔｅｎｏｕｇｈｔｏｄｅａｌｗｉｔｈｔｈｅｍｕｔｅｘｃｏｎｄｉｔｉｏｎｓ．Ｔｈｉｓｐａｐｅｒｐｕｔｆｏｒｗａｒｄａ ｎｅｗｍｅｔｈｏｄｎａｍｅｄＭＥＣＶ（ｍｕｔｕａｌｌｙｅｘｃｌｕｓｉｖｅｃｈｏｏｓｅｖａｒｉａｂｌｅｓ）．ＣＰＴＦＤＲｄｉｄｎｏｔｔｈｉｎｋｏｖｅｒｔｈｅｍｕｔｕａｌｌｙｅｘｃｌｕｓｉｖｅｂｅ ｔｗｅｅｎｉｎｉｔｉａｌｂｅｌｉｅｆｓｔａｔｅｓ．Ｉｔｇｅｎｅｒａｔｅｄｒｅｄｕｎｄａｎｔｉｎｆｏｒｍａｔｉｏｎｗｈｉｃｈｒｅｄｕｃｅｄｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｅｎｃｏｄｉｎｇ．Ｆｉｒｓｔ，ＭＥＣＶｕｓｅｄｔｈｅ ｕｓｅｆｕｌｐｏｓｉｔｉｖｅａｎｄｎｅｇａｔｉｖｅｌｉｔｅｒａｌｔｏｍａｋｅａｎｅｗｕｎｃｏｖｅｒｅｄｆａｃｔｓｅｔ．Ａｎｄｔｈｅｎｉｔｔｏｏｋｏｕｔｔｈｅｍｕｔｕａｌｌｙｅｘｃｌｕｓｉｖｅｌｉｔｅｒａｌｆｒｏｍ ｄｉｆｆｅｒｅｎｔｒｅａｌｓｔａｔｅｗｈｉｃｈｉｎｔｈｅｉｎｉｔｉａｌｂｅｌｉｅｆｓｔａｔｅｓｔｏｍａｋｅａｍｕｔｕａｌｌｙｅｘｃｌｕｓｉｖｅｇｒｏｕｐ．Ｆｉｎａｌｌｙ，ｉｔｕｓｅｄｔｈｅｎｅｗｕｎｃｏｖｅｒｅｄｆａｃｔ ｓｅｔａｎｄｍｕｔｕａｌｌｙｅｘｃｌｕｓｉｖｅｇｒｏｕｐｅｎｃｏｄｉｎｇｓｔａｔｅｖａｒｉａｂｌｅｓ．Ｔｈｅｏｕｔｃｏｍｅｓｏｆｃｏｍｐａｒａｔｉｖｅｅｘｐｅｒｉｍｅｎｔｓｖａｌｉｄａｔｅｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆｔｈｅｎｅｗａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｃｏｎｆｏｒｍａｎｔｐｌａｎｎｉｎｇ；ＣＰＴＦＤＲ；ｂｅｌｉｅｆｓｔａｔｅ；ｃｈｏｏｓｅｖａｒｉａｂｌｅｓ；ｍｕｔｅｘｇｒｏｕｐｓ 法（ＭＣＰＴ）表示的是信念状态空间，该方法是多值表示方法在 ０　引言