术，它从规划问题初始状态出发，构造个能够到达问题目标状态动作或操作序列。智能规划研究起源于问题求解，是人工智能研究中较早出现研究领域之。它研究可以追溯到年代和通过问题求解系统以及系统哺。年，和提出Ⅺ口系统在智能规划领域中具有划时代意义。智能规划虽然是人工智能中较早研究领域之，通常我们可以这样定义，如果个实体在初始状态下经过个动作序列，最后到达目标状态，我们就称这个动作序列为个规划。给定初始状态和目标状态，求解实体从初始状态执行怎样规划才能到达目标状态过程叫做求规划解，求得规划叫做规划解。直观说，个规划解实质上就是个动作序列，此动作序列能实现种目标。智能规划就是设计这个动作序列过程，即主要解决怎么做，而不解决为什么这样做。般地，我们在做规划之前，大多做以下假设环境状态改变完全是由智能体玛句订矾旬南肌幽乏旬独创性声明本人郑重声明所提交学位论文是本人在导师指导下独立进行研究工作所取得成果。据我所知，除了特别热以标注和致谢地方外，论文中不包含其他入已经发表或撰写过研究成果。对本人研究做出重要贡献个人和集体，均已在文中作了确说明。本声明法律结果由本人承担。学位论文作者签名查日期五琏螋学位论文使用授权书本学位论文作者完全了解东北师范大学有关保留使用学位论文规定，即东北师范大学有权保留并向国家有关部门或机构送交学位论文复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以采用影印缩印或其它复制手段保存汇编本学位论文。同意将本学位论文收录到巾匿优秀博硕士学位论文全文数据库中国学术期刊光艋版电子杂志社中豳学位论文全文数据库中国科学技术信息研究所等数据库中，并以电子出版物形式出版发行和提供信息服务。保密学位论文在解密后适用本授权书学位论文作者签名簿圜期趁呈吐乏方学位论文作者毕业后去向工作单位通讯地址指导教师签名日期电话邮编东北师范大学硕士学位论文课题研究背景第章引言智能规划是当前人工智能领域中极为活跃个研究热点，近十年来，有关智能规划研究在润题攒述和阍题求解两方面得到了新突破。相对于早期智能规划系统，现代规巅系统无论在规划求解效率上还是在规划求解规模上都有很大提高。然而，经典智能规划要求知识完整性，即假设对于规划世界知识是完全，规划过程中动作效果是确定，但在现实世界中，我们得到信息往往是不完全不确定，这就使规划理论应焉范萋受到极大限制。因此不确定规划就缛到研究者重视并得到迅速发展，尤其是用概率方法来定量描述问题不确定性概率规划问题。年，由国际人工智能规划与调度会议委员会主办第网届国际规划竞赛特别增加了概率规划部分比赛，可见概率规划已经弓起了人们足够重视。解决概率规划方法很多，也涌现出很多高效概率规划器。教授与教授于年开发出经飙规划器，提出新颖规划图结构给规划领域带来了突破性进展。算法高效性，使得基于该算法概率规划器脱颖丽出强，成为薪磺究热点，其中觚曲疆算法就是图规划框架下款较好概率规划器。算法在图规划框架下利用动态规划算法找到个随机规划解。但该规划解是在“每个时闻步只允许执行个非空动作限制下求褥，由于这个限制存在，使得规划器无法并行执行动作。丽且，算法只考虑概率信息，没有涉及命题及目标效用值信息，导致找到规划解相对冗长，浪费求解时问。算法后续发展算法也都存在这些不足，使得概率规划算法无法高效处理现实世界中不确定规划闯题。针对概率规划中存在这些问题，本文提出了种新概率规划算法。首先，我们在规划图中添加了结果结点，对其进行了扩展。其次，定义了并行有效轨迹及各种结点间互斥关系，使得嬲算法打破了传统概率规划方法中“每个时间步只允许执行个非空动作限制，弥补了算法不足。最后，在规划中引用了效用理论，使得。印算法可以找到成功概率最大且具有最大期望效用值最优规划解。新算法更适合于解决实际问题，进步拓宽了概率靓划应用领域。东北师范大学硕士学位论文本文主要工作及意义本文针对以往概率规划算法中“每个时间步只允许执行个非空动作”和“没有考虑状态效用值信息”两点不足之处，提出了新概率规划算法孤。本文主要工作表现在以下几个方面添加了结果结点，对经典规划图进行了扩展，并定义了并行有效轨迹概念，给出并行有效轨迹生成原则。重新定义了命题互斥动作结点互斥及结果结点互斥概念，从而在概率规划算法中可以使用互斥信息，提高了规划器求解速度。在概率规划问题中引入了效用理论，使规划算法可以找到成功概率较大且具有最大期望效用值规划解。利用语言开发了概率规划器，达到了理论预期效果，实现了概率规划中动作并行执行，并且所有目标都能以最大期望效用值去实现，从而提高了规划器求解质量。新算法更适合于解决实际问题，具有较高理论研究价值。同时，印肌规划器开发，促进了概率规划在实际应用方面发展。东北师范大学硕士学位论文第二章智能规划智能规划是人工智能中个重要研究领域，其主要思想是对周围环境进行认识与分析，根据自己要实现目标，对若干可供选择操作及所提供资源限制施行推理，综合制定出实现目标规划西。智能规划是个交叉研究领域，它涉及知识表达知识推理非单调逻辑情景演算人机交互和知识挖掘等多个方面。本章我们将介绍智能规划些相关概念。智能规划概念智能规划是种问题求解技术，它从规划问题初始状态出发，构造个能够到达问题目标状态动作或操作序列。智能规划研究起源于问题求解，是人工智能研究中较早出现研究领域之。它研究可以追溯到年代和通过问题求解系统以及系统哺。年，和提出Ⅺ口系统在智能规划领域中具有划时代意义。智能规划虽然是人工智能中较早研究领域之，通常我们可以这样定义，如果个实体在初始状态下经过个动作序列，最后到达目标状态，我们就称这个动作序列为个规划。给定初始状态和目标状态，求解实体从初始状态执行怎样规划才能到达目标状态过程叫做求规划解，求得规划叫做规划解。直观说，个规划解实质上就是个动作序列，此动作序列能实现种目标。智能规划就是设计这个动作序列过程，即主要解决怎么做，而不解决为什么这样做。般地，我们在做规划之前，大多做以下假设环境状态改变完全是由智能体。由于不确定规划问题能更加贴切描述现实中发生问题，因此不确定规划受到了研究者格外重视。研是上世纪年代最著名最经典规划器之，是利用算法中规划图结构进行概率规划问题求解方法。本文主要工作包括两个方面添加了结果结点，对经典规划图进行了扩展，并定义了并行有效轨迹概念，给出并行轨迹生成原则，使在概率规划算法中处理并行动作成为可能。重新定义了命题及动作结点间互斥概念，从而在概率规划算法中可以使用互斥信息，提高了规划器求解速度。在概率规划问题中引入了效用理论，使规划算法可以找到成功概率较大且具有最大期望效用值规划解。利用语言开发了概率规划器，达到了理论预期效果，实现了概率规划中动作并行执行，并且所有目标都能以最大期望效用值去实现，从而提高了规划器求解质量。通过以上工作，使得新算法更适合于解决实际问题，具有较高理论研究价值。同时，规划器开发，也会有较好发展前景。本文后续工作进步完善规划器各项性能指标，实现多目标并行概率规划算法，并加入时序要求，使其能处理持续动作，扩大使用范围。东北师范大学硕士学位论文参考文献谷文祥，刘日仙，张友红，等人工智能规划研究中图规划框架下非确定规划第六届中国青年运筹与管理学者大会，徐丽，赵成丽，姜贵栋，等图规划框架下概率规划第三届不确定系统年会丁德路，姜云飞智能规划及其应用研究计算机科学第期，年月，高济，朱淼良，何钦铭人工智能基础高等教育出版社年月，硼刘日仙，谷文祥，欧华杰人工智能规划领域定义语言计算机科学增刊，期刊源，Ⅲ，玛句订矾旬南肌幽乏旬独创性声明本人郑重声明所提交学位论文是本人在导师指导下独立进行研究工作所取得成果。据我所知，除了特别热以标注和致谢地方外，论文中不包含其他入已经发表或撰写过研究成果。对本人研究做出重要贡献个人和集体，均已在文中作了确说明。本声明法律结果由本人承担。学摘要智能规划是人工智能研究领域近年来发震起来个热门分支，由于其广泛实用性，受到研究者高度重视。尤其是具有不完全信息和不确定信息规划问题已经成为智能规划研究中重点。在各种研究方法中，由于概率方法能较准确地对不确定信息进行定量描述，因此研究动作具有概率输出概率规划方法体现了较强优越性，这个方法得到了研究者肯定，并在此基础上产生了大量算法。基于研算法是概率规划中较优秀款规划器。研印在图规划框架下利用动态规划算法找到随机规划解。但规划解是在“每个时间步只允许执行个非空动作假设下求得，这个假设存在使得在规划图中无法使用互斥信息，找到规划解相对冗长，浪费求解时间。并且算法只考虑概率信息，没有涉及状态效用值信息，不便于处理现实世界问题。本文针对概率规划中存在这两点不足之处，提出了新概率规划算法两勰。首先，我们通过添加结果结点，对经典规划圈进行了扩展，并定义了并行有效轨迹及各种结点互斥关系，尽可能多包含所有有效轨迹，使其在同时间步实现了并行，打破了原有概率规划算法中“每个时间步只允许执行个非空动作限制，弥补了原有算法不足，提高了靓划器运行速度和性能。其次，在并行概率规划中运用了效用理论，使所有目标都能以最大期望效用值去实现，从而提高了规划器求解质量。该算法更适合于求解现实世界中概率规划问题。本文在给出算法基础上，利用语言对该算法进行了实现，设计了可以处理带有最大期望效用值并行概率规划系统翟坤娩。实验证翡该系统可以达到理论预期效果，实现了概率规划算法中动作并行执行，可以找到成功概率较大且具有最大期望效用值规划解。提高了概率规划器求解质量，使得概率规划器更适合于处理现实世界闯题。关键词智能规划错并行有效轨迹，印衙铲柏册印垂硫旬，访南“锄印南血向旬锄印巧矾，南，印，玛句订矾旬南肌幽乏旬独创性声明本人郑重声明所提交学位论文是本人在导师指导下独立进行研究工作所取得成果。据我所知，除了特别热以标注和致谢地方外，论文中不包含其他入已经发表或撰写过研究成果。对本人研究做出重要贡献个人和集体，均已在文中作了确说明。本声明法律结果由本人承担。学位论文作者签名查日期五琏螋学位论文使用授权书本学位论文作者完全了解东北师范大学有关保留使用学位论文规定，即东北师范大学有权保留并向国家有关部门或机构送交学位论文复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以采用影印缩印或其它复制手段保存汇编本学位论文。同意将本学位论文收录到巾匿优秀博硕士学位论文全文数据库中国学术期刊光艋版电子杂志社中豳学位论文全文数据库中国科学技术信息研究所等数据库中，并以电子出版物形式出版发行和提供信息服务。保密学位论文在解密后适用本授权书学位论文作者签名簿圜期趁呈吐乏方学位论文作者毕业后去向工作单位通讯地址指导教师签名日期电话邮编东北师范大学硕士学位论文课题研究背景第章引言智能规划是当前人工智能领域中极为活跃个研究热点，近十年来，有关智能规划研究在润题攒述和阍题求解两方面得到了新突破。相对于早期智能规划系统，现代规巅系统无论