计算机工程 ›› 2015, Vol. 41 ›› Issue (1): 196-199.doi: 10.3969/j.issn.1000-3428.2015.01.036

• 人工智能及识别技术 • 上一篇    下一篇

不确定规划中可达关系的快速求解算法

龙凤,文中华,唐杰,王进宗   

  1. 湘潭大学信息工程学院,湖南 湘潭 411105
  • 收稿日期:2013-12-30 修回日期:2014-03-26 出版日期:2015-01-15 发布日期:2015-01-16
  • 作者简介:龙 凤(1989-),女,硕士研究生,主研方向:智能规划;文中华,教授、博士生导师;唐 杰、王进宗,硕士研究生。
  • 基金项目:
    国家自然科学基金资助项目(61070232,61272295)

Fast Solving Algorithm of Reachability Relation in Uncertain Planning

LONG Feng,WEN Zhonghua,TANG Jie,WANG Jinzong   

  1. College of Information Engineering,Xiangtan University,Xiangtan 411105,China
  • Received:2013-12-30 Revised:2014-03-26 Online:2015-01-15 Published:2015-01-16

摘要: 在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。

关键词: 不确定规划, 可达关系, 智能规划, 模型检测, 不确定性, 不确定状态转移系统

Abstract: In uncertain planning field,it is frequent to solve many planning problems over a nondeterministic state-transition system in uncertain planning.So getting the state reachability for the nondeterministic state-transition system can make solving planning problems easier.However,the existing solution matrix multiplication of relations exist the problem of high algorithm complexity.Therefore,this paper presents a fast solving algorithm of reachability relation between the states in uncertain planning.The algorithm determines the certainly action and uncertainty actions separately.It determines the relationships between the certainty action,then solves relations between uncertain actions with lists and queues.Experimental result shows that the algorithm not only can get a more comprehensive relationship,but also has higher efficiency than the matrix multiplication algorithm.

Key words: uncertain planning, reachability relation, intelligent planning, model checking, uncertainty, uncertain state-transition system

中图分类号: