路标计数启发式引导的分解规划方法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61272208, 61133011, 60973089, 61003101, 61170092, 61300049); 吉林省科技发展计划(20101501, 20100185, 201101039); 国家教育部博士点专项基金(20100061110031, 20120061120059); 博士后科学基金面上资助项目(2011M 500612); 浙江省自然科学基金(Y1100191); 浙江师范大学计算机软件与理论省级重中之重学科开放基金(ZSDZZZZXK12)


Decomposed Planning Guided by Landmark Counting Heuristic
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    路标信息能够准确描述智能规划问题解空间的基本形态.提出由路标信息引导的分解规划方法,求解过程由路标计数启发式引导增强爬山算法向目标方向进行,根据路标的完成情况分段求出规划解.从全局范围上看,爬山过程逐渐实现更多的路标,路标计数启发式估值的降低引发规划任务的分解,当搜索过程遇到估值更低的状态时,提取一段爬山路径.如此反复执行“搜索-提取”过程,直至路标计数启发式的估值降低为0,各段爬山路径构成最终的规划解.采用最新国际通用的标准测试问题进行实验测试,结果表明:由路标计数启发式引导的分解规划方法能够更好地发挥路标信息的优势,实现了搜索范围的压缩,可更快地生成规划解.

    Abstract:

    Landmarks can capture the features of the solution space of planning tasks precisely. In this paper, a decomposed planning method guided by landmark information is proposed. The method executes an enforced hill-climbing procedure guided by the landmark-counting heuristic towards the goal, searching for a plan along with completions of the landmarks. Globally the hill-climbing procedure achieves the landmarks one after another. A decrease in the landmark counting heuristic estimation causes task decomposition and whenever the search encounters a state with a lower estimation, a hill-climbing fragment is extracted. Such "search-extract" procedure is repeated until the estimation of the landmark counting heuristic decreases to zero eventually, and then all the extracted fragments are connected into the final plan. Experiment results show that the decomposed planning method guided by landmark-counting heuristic makes use of the landmark information in a more flexible way, usually cutting down the search space dramatically and find the plan much faster.

    参考文献
    相似文献
    引证文献
引用本文

魏唯,欧阳丹彤,吕帅.路标计数启发式引导的分解规划方法.软件学报,2013,24(10):2327-2339

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2012-07-04
  • 最后修改日期:2013-02-04
  • 录用日期:
  • 在线发布日期: 2013-10-12
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号