摘要： 在不确定规划中，可通过观察周围的信息来区分多个状态，但周围的观察信息较多，因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的，存在一定的局限性。在对观察信息约简研究中，为提高搜索效率，设计一种高效的不确定规划中观察信息约简算法。该算法将规划问题转化为求解0-1矩阵的覆盖问题，使用数据结构十字链表来表示0-1矩阵，通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明，该算法不仅能够找最小观察变量集，而且运行速度超过同类算法。

关键词: 不确定规划, 观察信息约简, 最小观察变量集, 人工智能规划, 十字链表, 启发式搜索

Abstract: In nondeterministic planning, it is feasible to distinguish some states through observation information, however, observation information is so much that it is significant how to select useful information from plenty of observation information. The previous algorithms use direct search algorithm that adds some cutting condition to achieve optimized objective, however, these methods have certain limitations. In research to observation information reduction, this paper designs a new algorithm which improves search efficiency. It converts the problem into cover problem in 0-1 matrix through abstract problem model, and replaces the 0-1 matrix using orthogonal list data structure and can get a minimal set of observation variable through maintaining the orthogonal list and using heuristic function. Experimental result shows that this algorithm not only finds a minimal set of observation variable, but also runs more quickly than similar algorithm.

Key words: nondeterministic planning, observation information reduction, minimal observation variable set, Artificial Intelligent(AI) planning, orthogonal list, heuristic search

中图分类号: 

• TP18