可能性规划问题表示与求解研究

作     者：李丹丹 

作者单位：东北师范大学 

学位级别：硕士

导师姓名：谷文祥

授予年度：2008年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：可能性理论 可能性规划 定性效用理论 PDDL 图规划 

摘      要：早期智能规划研究一直集中在经典规划领域,它假设动作是确定的、初始条件是已知的、目标被定义为一些命题的集合。但很多实际问题并不满足这样的条件,因此,一些学者开始尝试不确定规划的研究,其中绝大部分集中于概率规划研究。然而,动作效果的概率在实际中很难获得,尤其是人工智能研究中的不确定性通常是顺序的、定性的。一些研究认为,可能性理论更适用解决那些概率模型无法解决或者概率信息很难获得的问题。 本文利用可能性理论提出了一种基于PDDL(Planning Domain Definition Language)的可能性规划问题表示方法——Poss-PDDL,给出了基于可能性理论框架下的定性决策理论和图规划算法的可能性规划求解方法——可能性图规划,设计并开发了可能性规划问题求解器Poss-Graphplan。PDDL是国际规划器大赛的标准域定义语言,这使得Poss-PDDL更具通用性和标准性。由于用可能性理论表示动作效果和状态的不确定性更具优势,因此Poss-Graphplan更适用于解决那些概率模型无法解决或者很难获得概率信息的不确定规划问题。我们证明了应用可能性图规划方法求解可能性规划问题得到的规划解是最优的。同时,我们用C语言在Windows系统下实现了可能性图规划器,实验结果表明,可能性图规划方法在问题求解能力和速度上的表现都较为突出。