基于有序爬山法的前向启发式搜索规划

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于有序爬山法的前向启发式搜索规划

梁瑞仕, 姜云飞, 杨会志

文章导航 > 电子科技大学学报 > 2013 > 42(3): 464-469

梁瑞仕, 姜云飞, 杨会志. 基于有序爬山法的前向启发式搜索规划[J]. 电子科技大学学报, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

引用本文:

梁瑞仕, 姜云飞, 杨会志. 基于有序爬山法的前向启发式搜索规划[J]. 电子科技大学学报, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

LIANG Rui-shi, JIANG Yun-fei, YANG Hui-zhi. Forward Heuristic Search Planning Based on Ordered Hill Climbing Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

Citation:

LIANG Rui-shi, JIANG Yun-fei, YANG Hui-zhi. Forward Heuristic Search Planning Based on Ordered Hill Climbing Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

基于有序爬山法的前向启发式搜索规划

doi: 10.3969/j.issn.1001-0548.2013.03.028

1.
电子科技大学中山学院计算机学院广东中山 528402;
2.
中山大学信息科学与技术学院广州 510275

基金项目:

国家自然科学基金(60773201,60970042);广东省自然科学基金(S2012040011123)

作者简介:
梁瑞仕(1982-)，男，博士，主要从事智能规划、启发式搜索等方面的研究.

中图分类号: TP18

Forward Heuristic Search Planning Based on Ordered Hill Climbing Algorithm

1.
School of Computer,Zhongshan Institute,University of Electronic Science and Technology of China Zhongshan Guangdong 528402;
2.
School of Information Science & Technology,Sun Yat-Sen University Guangzhou 510275

摘要: 根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系，定义了状态适用度函数的概念，可对后继扩展状态的启发式估值进行快速近似的比较。在此基础上，结合增强型爬山法搜索后继状态的贪婪选择机制，提出了一种改进的局部搜索算法——有序爬山法，即根据状态适应度函数对所有待扩展的后继状态进行排序，并加入到扩展优先队列。在启发式估值阶段，适应度高的状态将被优先计算评估，有利于更快地发现较优状态，从而减少调用启发式估值程序的次数。通过在国际规划大赛基准测试领域的实验结果表明，该方法减少了搜索节点的数目和搜索时间，有效地提高了启发式搜索效率，而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略，因此整体规划性能比FF有显著的提升。
- 智能规划 /
- 启发式搜索 /
- 有序爬山法 /
- 状态适应度函数
Abstract: According to the relationship between relaxed planning graph and helpful actions in forward heuristic search planner FF, the notion of state adaptive function is defined, which is used to fast compare heuristic evaluations for expanded successor states approximately. Integrating with greedy selection mechanism in enforced hill climbing search, we propose an improved local search algorithm named ordered hill climbing search algorithm based on state adaptive function. The core idea of our algorithm is to order all expanded successor states according to their state adaptive functions, and then insert them into an expanded priority queen. In heuristic evaluation stage, a state with higher adaptive value will be computed earlier, as a result, better state can be found earlier and the frequency of calling heuristic evaluation procedure will be cut down. Experiments in Depots and FreeCell domains of IPC show that the proposed algorithm reduces search nodes and search time significantly and therefore improves the search efficiency effectively.
- AI planning /
- heuristic search /
- ordered hill climbing algorithm /
- state adaptive function

[1]	杨骏, 敬思远, 钟勇. 面向时间序列有序分类的Shapelet抽取算法 . 电子科技大学学报, 2023, 52(6): 887-896. doi: 10.12178/1001-0548.2022278
[2]	张辰逸, 尚涛, 刘建伟. 基于交换门的前瞻启发式量子线路映射算法 . 电子科技大学学报, 2023, 52(4): 489-497. doi: 10.12178/1001-0548.2022339
[3]	王一竹, 李渊, 杨宇. 基于人眼亮度感知的S型函数图像对比度增强算法 . 电子科技大学学报, 2022, 51(4): 600-607. doi: 10.12178/1001-0548.2020383
[4]	何选森, 徐丽, 许莹. 启发式联合PCD快速降噪算法 . 电子科技大学学报, 2021, 50(3): 360-367. doi: 10.12178/1001-0548.2020053
[5]	韦顺军, 张晓玲, 师君, 蒲羚. 基于最大锐度半正定规划的线阵SAR自聚焦三维成像 . 电子科技大学学报, 2019, 48(1): 1-7. doi: 10.3969/j.issn.1001-0548.2019.01.001
[6]	周文辉, 钟伟锋, 余荣. 智能电网中电动汽车充电的自适应电价控制方法 . 电子科技大学学报, 2015, 44(4): 636-640. doi: 10.3969/j.issn.1001-0548.2015.04.028
[7]	李少波, 王继奎, 杨观赐. 基于模糊偏序关系支持度模型的真值发现算法 . 电子科技大学学报, 2014, 43(6): 893-897. doi: 10.3969/j.issn.1001-0548.2014.06.017
[8]	施侃晟, 刘海涛, 白英彩, 宋文涛, 洪亮亮. 余弦度量和适应度函数改进的聚类方法 . 电子科技大学学报, 2013, 42(4): 621-624. doi: 10.3969/j.issn.1001-0548.2013.04.017
[9]	唐聃, 黄健. 流水车间调度问题的启发式算法研究 . 电子科技大学学报, 2013, 42(6): 921-925. doi: 10.3969/j.issn.1001-0548.2013.06.021
[10]	张聪, 沈惠璋. 网络自然密度社团结构模块度函数 . 电子科技大学学报, 2012, 41(2): 185-191. doi: 10.3969/j.issn.1001-0548.2012.02.003
[11]	董彬虹, 唐诚, 李少谦. 基于状态网格图的差分跳频G函数构造方法研究 . 电子科技大学学报, 2011, 40(4): 497-500.
[12]	甄雁翔, 苏放, 寇明延, 徐惠民. 异构网络中丢包隶属度函数的构建方法 . 电子科技大学学报, 2010, 39(6): 845-849. doi: 10.3969/j.issn.1001-0548.2010.06.009
[13]	汪忠来, 黄洪钟, 王贵宝. 综合的结构可靠度函数预测模型 . 电子科技大学学报, 2010, 39(6): 952-955,960. doi: 10.3969/j.issn.1001-0548.2010.06.031
[14]	蒋毅, 刘章文, 古天祥. MUSIC法的有限域单向快速频率搜索 . 电子科技大学学报, 2008, 37(2): 241-243.
[15]	张继红, 黄大贵. 基于AHP法的智能制造CNC资源的优选 . 电子科技大学学报, 2006, 35(4): 514-517.
[16]	李刚俊. 冗余度机器人的运动规划碰撞算法 . 电子科技大学学报, 2005, 34(6): 828-831,864.
[17]	张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法 . 电子科技大学学报, 2005, 34(3): 359-362.
[18]	虞红芳, 詹柔莹, 李乐民. 一种启发式的计算机局域网故障诊断方法 . 电子科技大学学报, 2002, 31(2): 151-155.
[19]	唐小我. 非线性需求函数条件下二度价格歧视研究 . 电子科技大学学报, 1999, 28(1): 78-83.
[20]	何光宗, 陈华富. 线性规划的梯度投影算法 . 电子科技大学学报, 1997, 26(5): 549-551.

WeChat

点击查看大图

计量

文章访问数: 3616
HTML全文浏览量: 115
PDF下载量: 224
被引次数: 0

基于有序爬山法的前向启发式搜索规划

doi: 10.3969/j.issn.1001-0548.2013.03.028

1. 电子科技大学中山学院计算机学院广东中山 528402;

2. 中山大学信息科学与技术学院广州 510275

基金项目:

国家自然科学基金(60773201,60970042);广东省自然科学基金(S2012040011123)

作者简介:
梁瑞仕(1982-)，男，博士，主要从事智能规划、启发式搜索等方面的研究.

收稿日期: 2011-08-15
修回日期: 2011-12-20
刊出日期: 2013-06-15

中图分类号: TP18

关键词:

摘要: 根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系，定义了状态适用度函数的概念，可对后继扩展状态的启发式估值进行快速近似的比较。在此基础上，结合增强型爬山法搜索后继状态的贪婪选择机制，提出了一种改进的局部搜索算法——有序爬山法，即根据状态适应度函数对所有待扩展的后继状态进行排序，并加入到扩展优先队列。在启发式估值阶段，适应度高的状态将被优先计算评估，有利于更快地发现较优状态，从而减少调用启发式估值程序的次数。通过在国际规划大赛基准测试领域的实验结果表明，该方法减少了搜索节点的数目和搜索时间，有效地提高了启发式搜索效率，而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略，因此整体规划性能比FF有显著的提升。

English Abstract

梁瑞仕, 姜云飞, 杨会志. 基于有序爬山法的前向启发式搜索规划[J]. 电子科技大学学报, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

引用本文:

梁瑞仕, 姜云飞, 杨会志. 基于有序爬山法的前向启发式搜索规划[J]. 电子科技大学学报, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

LIANG Rui-shi, JIANG Yun-fei, YANG Hui-zhi. Forward Heuristic Search Planning Based on Ordered Hill Climbing Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

Citation:

LIANG Rui-shi, JIANG Yun-fei, YANG Hui-zhi. Forward Heuristic Search Planning Based on Ordered Hill Climbing Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发