论文部分内容阅读
随着智能规划越来越多在实际问题中的应用,更多的学者开始关注和研究智能规划,人们从多个角度去完善,并提出了多种规划策略,其中,启发式规划方法作为智能规划领域的重要问题之一,在近十几年受到了众多学者的关注和研究。目前具有代表性的启发式规划器有:FF、LPG和Fast-Downward等。由于Fast-Downward将规划问题转化为一个多值规划任务,提出并采用了基于因果图的启发函数,得到了较高的搜索效率。但Fast-Downward的主要缺点在于其采用的基于因果图的启发函数将目标因子相互独立作为一个假设前提,然而在众多的规划问题中,各个目标因子之间往往存在相互依赖关系,造成计算出的启发代价比真实代价值大。针对Fast-Downward存在的不足,本文在充分考虑了因子间依赖关系的基础上,提出一种基于子目标排序和有利值提取的启发函数(HBSH)。
首先,根据目标因子间存在的依赖关系,依次从目标集中提取出子目标,得到一个有序的子目标序列,即目标因子合理的实现顺序。接下来以子目标序列中子目标的启发代价依次作为启发值来引导搜索,以达到提高启发函数准确性、加快启发函数计算速度的目的;其次,通过对目标因子间存在的有利依赖关系的分析,结合Fast-Downward中的域转移图技术,提出一种计算目标集在某一状态下存在的有利值的算法,在启发函数每次计算启发代价时都加入有利值提取技术,这样可得到更加准确的启发代价;最后采用最佳优先贪心算法来进行规划求解。
在Linux平台下,采用C++语言对给出的启发函数进行了实现,并将其嵌入到Fast-Downward规划器进行搜索求解,通过对国际规划大赛2008标准领域问题的实验,结果表明新启发函数在规划解质量和规划效率上都有一定的提高。