基于图规划和启发式搜索的一致性规划求解

发布时间：2016-09-27 19:09

  本文关键词：基于启发式搜索的灵活规划的算法研究，由笔耕文化传播整理发布。

《吉林大学》 2013年

基于图规划和启发式搜索的一致性规划求解

李大为  

【摘要】：智能规划是人工智能研究领域的一个非常重要的分支，是人工智能领域内较早的研究方向之一。智能规划依据对领域内知识的和所给目标的分析，对资源约束和可供选择的操作进行推理，最终得出到达目标的动作序列。智能规划的研究早期，为了简化问题和加强对规划问题的针对性，对智能规划的问题做出了若干假设，即所谓经典规划。不过这些假设对于现实世界的问题过于严格，为了使智能规划能够得到更为广泛的应用，破除这些限制的诸多类型的规划，如：一致性规划，，概率规划，灵活规划等便随之产生。 一致性规划任务是指在初始状态和动作效果存在不确定性条件下，并且在规划执行过程中智能体没有任何感知能力的规划任务。生成的规划解应该在任何可能的初始状态下都能达到规划目标。一致性规划可以转化成信念状态空间下的搜索问题。其中信念状态空间包含的元素包含任何可能的真实世界状态。 在经典规划中，应用松弛规划图作为启发式的方法的FF经典规划器被证明是成功的，这里的松弛指的是忽略动作的删除效果，即删除表为空。然后对初始状态和没有删除效果的动作，进行正向搜索，得到一个松弛规划解，解的长度即我们要得到的启发值。对于一致性规划，由于不确定性的存在和规划复杂度的提高，Conformant-FF规划器对于FF规划器中的“松弛”做了进一步的扩展，对于每个规划动作的CNF范式只保留2个命题，即2-CNF，虽然这种表示忽略了松弛的正确性，不过最终的整个的规划算法是完备且健全的。这种松弛虽然保证了基于图规划的启发式的产生的时间效率，不过由于范式中命题选择的盲目性和命题数量的大幅度减少，导致启发式的产生质量存在很大的问题。 根据A*算法的性质，我们知道如果一个可采纳的启发式方法得到的启发解越接近最优解，则含有的信息的启发能力越强，反之则启发能力越弱。本文通过对Conformant-FF中松弛规划图启发式的分析，提出了求解一致性规划问题的一种新的解决办法，通过降低conformant-FF中对动作的松弛程度，将对动作的松弛改进成3-CNF,4-CNF来提高启发式的质量，并将这种启发式应用于信念状态空间的搜索过程当中，通过实验对这种启发式的启发值的准确程度和搜索效率与C-FF规划器相比较,并对这种基于松弛规划图的启发式方法的一些建议。实验结果表明采用3-CNF,4-CNF的动作松弛方法得到的启发值更接近真实解，说明这两种启发式得到启发值的启发能力要强于conformant-FF中的2-CNF动作松弛方法。

【关键词】：
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP18;O221
【目录】：

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【参考文献】

中国期刊全文数据库 前1条

1 丁德路;姜云飞;;智能规划及其应用的研究[J];计算机科学;2002年02期

【共引文献】

中国期刊全文数据库 前10条

1 孙伟;;智能规划与规划识别在网络教学技术中的应用研究刍议[J];长春大学学报;2010年02期

2 谷文祥,孙铁利,吕英华;智能规划中互斥动作延迟算法[J];东北师大学报(自然科学版);2003年03期

3 谷文祥;刘科成;;带有规划库的规划器设计模型研究[J];东北师大学报(自然科学版);2007年04期

4 刘日仙;袁利永;谷文祥;;智能规划学习和学习型智能规划系统架构研究[J];东北师大学报(自然科学版);2010年02期

5 李杨;宋克非;;用智能规划解空间树法生成测试数据[J];光学精密工程;2011年07期

6 黄平;李晖;韩丰;冯建雷;;电网智能规划系统技术[J];华东电力;2012年01期

7 李丽;沈湘衡;魏颖;任佳阅;王大勇;;一种改进的规划器算法在军用软件GUI测试用例自动生成中的应用[J];解放军理工大学学报(自然科学版);2010年03期

8 李杨;陈佳豫;韩诚山;孙焱;谷文祥;;基于启发式搜索的灵活规划的算法研究与系统实现[J];计算机科学;2008年04期

9 史晶晶;刘大有;蔡敦波;吕帅;江鸿;;基于多值表示的并行规划方法[J];计算机科学;2009年09期

10 江鸿;刘大有;吕帅;蔡敦波;史晶晶;;命题编码中公理的组合与设计[J];计算机科学;2009年10期

中国博士学位论文全文数据库 前2条

1 刘伟;对地观测卫星任务规划模型与算法研究[D];中国科学院研究生院（空间科学与应用研究中心）;2008年

2 李丽;航天相机主控软件测试用例自动生成技术的研究[D];中国科学院研究生院（长春光学精密机械与物理研究所）;2010年

中国硕士学位论文全文数据库 前10条

1 刘鸿亮;基于启发值的图规划算法[D];吉林大学;2011年

2 程爽;联合启发式求解优先约束问题[D];东北师范大学;2011年

3 高志升;基于多Agent的语义Web服务自动组合方法的研究[D];西华大学;2006年

4 蔡增玉;图规划框架下创建/删除对象规划的研究及实现[D];东北师范大学;2006年

5 董轶群;一种基于目标驱动理论的应对规划方法[D];东北师范大学;2007年

6 王艳;带有并行动作的概率规划算法的研究[D];东北师范大学;2007年

7 冯宇轩;基于分层规划的柔性和一致性规划求解[D];吉林大学;2008年

8 温立红;前向状态空间搜索中并行规划算法的研究及实现[D];东北师范大学;2008年

9 苏卫华;增量式动态概率规划的研究[D];东北师范大学;2008年

10 尹吉丽;基于完全目标图的对手规划识别方法[D];东北师范大学;2008年

【相似文献】

中国期刊全文数据库 前10条

1 李德仁,肖平;利用人工智能方法进行粗差的启发式搜索[J];测绘学报;1990年04期

2 张志明,王越,陶然,阎飞,周思永;基于时间Petri网和启发式搜索的资源分配(英文)[J];Journal of Beijing Institute of Technology;2000年02期

3 吉艳霞;;一种基于遗传算法的北京公共交通选乘问题的启发式算法[J];运城学院学报;2008年05期

4 张伟;基于多项式逼近的学习式搜索[J];辽宁大学学报(自然科学版);1995年S1期

5 杨勇;刘弘;杨峰;;一种优化排料方法及其数学描述[J];山东科学;2006年04期

6 张伟;洪声贵;;学习式搜索:一种新的搜索策略[J];辽宁大学学报(自然科学版);1992年04期

7 张燕,袁书卿,鲁汉榕;一种使用启发式搜索优化的模糊规则分类方法[J];计算机工程与应用;2004年01期

8 王德忠,刘红,王鲁川;一种启发式的自适应图像边缘检测方法[J];辽宁大学学报(自然科学版);1999年03期

9 许福永,梅中磊;基于现代超启发式搜索方法的计算机通信网络中路由选择优化的研究[J];兰州大学学报(自然科学版);2001年02期

10 刘润,戎建刚;自动布线中的一种有效的搜索算法[J];哈尔滨工业大学学报;1987年02期

中国重要会议论文全文数据库 前10条

1 赵庆杞;杨东升;张化光;;基于地理信息系统的配电检修最优路径的算法研究[A];2004中国控制与决策学术年会论文集[C];2004年

2 黄宇纯;王树青;王骥程;;间歇生产过程规划问题的智能优化模型[A];1995年中国智能自动化学术会议暨智能自动化专业委员会成立大会论文集（下册）[C];1995年

3 蔡阳波;邓一贵;王康;;并发启发式搜索蛙跳算法[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

4 王家廞;;生产调度的冲突对排序方法[A];1995年中国智能自动化学术会议暨智能自动化专业委员会成立大会论文集（下册）[C];1995年

5 盛颖璞;毛卫宁;;基于启发式搜索的线谱跟踪技术[A];水下声系统会议论文集[C];2006年

6 董银文;王航宇;李鹏;;噪声图象中提取边缘的边缘分段自增强算法[A];第十三届全国图象图形学学术会议论文集[C];2006年

7 陈媛媛;施鹏飞;;基于启发式搜索的运动图像匹配[A];第十一届中国体视学与图像分析学术会议论文集[C];2006年

8 马春红;叶继昌;王小平;杨兵;;前视红外图像中机场的自动识别[A];2006年全国光电技术学术交流会会议文集（D 光电信息处理技术专题）[C];2006年

9 杨淮清;闵亚东;张琳琳;;一种基于橡皮筋拉紧的全国公路网行车分层规划研究[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

10 耿沿锋;康凯;王宏;;基于启发式搜索的半导体集束设备调度[A];2007'仪表，自动化及先进集成技术大会论文集（一）[C];2007年

中国重要报纸全文数据库 前8条

1 程鸿兴 张宇;[N];中国计算机报;2008年

2 内蒙古建设银行包头分行 薛志强;[N];网络世界;2002年

3 ;[N];计算机世界;2001年

4 本报记者 筱林;[N];中国信息报;2000年

5 陈翔;[N];中国计算机报;2007年

6 ;[N];中国计算机报;2001年

7 本报记者 汪挺;[N];中国商报;2009年

8 金红;[N];国际商报;2009年

中国博士学位论文全文数据库 前10条

1 刘洋;成像侦察卫星动态重调度模型、算法及应用研究[D];国防科学技术大学;2004年

2 孙小猛;基于模态观测的结构健康监测的传感器优化布置方法研究[D];大连理工大学;2009年

3 蔡敦波;基于启发式搜索的智能规划方法研究[D];吉林大学;2009年

4 雍爱霞;仿人机器人关节用永磁球形步进电机的转子位置检测及控制策略[D];合肥工业大学;2007年

5 殷明浩;自动推理和智能规划中若干问题研究[D];吉林大学;2008年

6 廖胜利;面向省级电网的跨流域水电群优化建模与应用研究[D];大连理工大学;2009年

7 朱永宣;基于模式识别的入侵检测关键技术研究[D];北京邮电大学;2006年

8 任小龙;基于Petri网的FMS调度问题研究[D];西安电子科技大学;2010年

9 龙云利;天基红外监视系统目标检测与跟踪技术研究[D];国防科学技术大学;2012年

10 Okafor Ekene Gabriel;复杂系统失效率评估与多目标优化方法研究[D];南京航空航天大学;2012年

中国硕士学位论文全文数据库 前10条

1 王改革;一种基于启发式搜索的感知图规划算法的研究与实现[D];东北师范大学;2010年

2 李大为;基于图规划和启发式搜索的一致性规划求解[D];吉林大学;2013年

3 解瑞飞;基于启发式搜索的生物特征辨识算法研究[D];杭州电子科技大学;2012年

4 董程玲;遗传连锁群中分子标记排序研究[D];南京林业大学;2011年

5 王宗原;基于电子地图的路径规划的设计与实现[D];哈尔滨工程大学;2005年

6 李杨;基于启发式搜索的灵活规划的算法研究[D];东北师范大学;2006年

7 蔡敦波;基于延迟部分推理的快速前向规划系统[D];东北师范大学;2006年

8 韩军伟;景物边缘提取技术的研究与应用[D];西北工业大学;2001年

9 郑朝明;配电网故障恢复系统的研究[D];华北电力（北京）大学;2002年

10 高彦明;蚁群算法并行化研究[D];苏州大学;2005年

  本文关键词：基于启发式搜索的灵活规划的算法研究，由笔耕文化传播整理发布。

本文编号：124864