计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (3): 55-58.

• 大数据与云计算 • 上一篇    下一篇

不确定规划领域中带权值的观察信息约简

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

  1. 湘潭大学 信息工程学院,湖南 湘潭 411105
  • 出版日期:2016-02-01 发布日期:2016-02-03

Weighted observation information reduction in uncertain planning domain

WANG Jinzong, WEN Zhonghua, TANG Jie, LONG Feng   

  1. College of Information Engineering, Xiangtan University, Xiangtan, Hunan 411105, China
  • Online:2016-02-01 Published:2016-02-03

摘要: 现实的规划问题中,观察信息的获取所需的代价是不同的,并且在规划解执行过程中,并非所有的观察信息都是有意义的,因此为了减少执行过程中的开销而对大量的带权值的观察信息进行约简就显得十分重要。首次针对带权值的观察信息约简问题做出研究,定义了带权值的最优观察集的概念,设计了SOWOS算法。该算法找出所有需要区分的状态对,用贪心的思想使搜索按指定顺序选择观察变量,并在搜索的过程中增加剪枝,减少了大量不必要的搜索,最终求得总花费最小的观察集,达到了减少执行成本的目的。实验结果表明,SOWOS算法可以高效地求得带权值的最优观察集,对减少规划执行中的开销贡献明显。

关键词: 智能规划, 不确定规划, 带权值的规划信息约简, 区分状态对, 区分集合, 带权值的最优观察集

Abstract: In the planning problem of reality, the cost to obtain the observation information is different, and in the plan implementation process, not all of the observed information is significant, so the huge weighted observation information reduction to reduce the execution overhead is very important. For the first time to observe the information reduction problem with weights to make research, this paper puts forward the concept of the set of optimal weighted, and designs the SOWOS algorithm. It finds out all state pairs needed to be distinguished, builds an observation matrix, backtracking and pruning, and obtains the optimal observation of total cost minimum set to reduce the execution cost. The experimental results show that, SOWOS algorithm can efficiently find the optimal weighted observation set.

Key words: artificial intelligent planning, uncertain planning, weighted observation information reduction, division state pairs, division set, optimal weighted observation set