作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

求强规划解的快速状态分层算法

汪 泉,文中华,伍 选   

  1. (湘潭大学信息工程学院,湖南 湘潭 411105)
  • 收稿日期:2012-12-12 出版日期:2014-02-15 发布日期:2014-02-13
  • 作者简介:汪 泉(1989-),男,硕士研究生,主研方向:云计算,智能规划;文中华,副教授、博士;伍 选,硕士研究生
  • 基金资助:
    国家自然科学基金资助项目(61070232, 61272295)

Fast Hierarchical States Algorithm for Solving Strong Planning

WANG Quan, WEN Zhong-hua, WU Xuan   

  1. (College of Information Engineering, Xiangtan University, Xiangtan 411105, China)
  • Received:2012-12-12 Online:2014-02-15 Published:2014-02-13

摘要: 在求强规划解时,通过状态分层可以大幅减少问题规模,提高搜索效率,并能得到规划路径较短的强规划解。但现有分层算法本身有一定的复杂度,在状态较多时开销较大。为此,通过改进已有分层算法,设计一种适用于求强规划解的快速状态分层算法。采用链式双向图结构保存数据,在分层时修改已遍历的状态动作序偶,并根据修改结果直接进行分层判断,使得分层时只需要判断前一层状态而不是所有已分层状态,避免对非必要状态转移的搜索以及对必要状态转移的重复搜索。实验结果表明,该算法的分层速度优于已有的矩阵乘分层算法。

关键词: 不确定规划, 强规划, 状态分层, 智能规划, 状态动作序偶

Abstract: When solving strong plan, through using hierarchical states, it can sharply reduce the scale of the problem, boost search, and it can get the solution of shorter path. But existing hierarchy algorithms are still complex in some extent, and when the number of states is big, it costs large. Based on the ideal of hierarchy, it designs a fast hierarchy algorithm. It uses bidirectional chain graph to save data. In hierarchy, it directly modifies traversed state-action pair, and according to the modified results to make decision directly. With that, only one previous hierarchy is needed to judge rather than all hierarchical states. And it avoids searching the state transition of unnecessary and avoids repeat searching on necessary state transition. Experimental result shows that this algorithm runs more quickly than similar algorithms such as the matrix multiplication hierarchy algorithm.

Key words: nondeterministic planning, strong planning, hierarchical states, intelligent planning, state-action pair

中图分类号: