智能规划是人工智能的一个重要领域。近年来,有关智能规划的研究在问题描述和问题求解两方面得到了新的突破,使得智能规划已成为一个热门的人工智能研究领域。对智能规划算法的研究主要集中在规划算法性能的提高和规划算法求解问题范围的扩展。基于规划图原理和启发式状态空间搜索的智能规划算法在众多的智能规划算法中表现十分突出。FF规划器将规划图和启发式状态空间搜索原理进行了很好的结合,在两届IPC(International Planning Competition)中取得了优异的成绩。但是,FF规划算法所采用的搜索方法和规划图的使用上都存在很大不足,使得FF规划算法在某些规划问题域中,特别是含有死点状态的问题域中表现不够理想。本文通过对规划图原理、启发式状态空间搜索原理和FF规划算法的研究,提出了一种更适合FF规划器使用的搜索方法——带有回溯的加强爬山搜索算法,同时在规划图的使用中加入了有用动作排序并且探索了多种排序标准。带有回溯的加强爬山算法在加强爬山算法失败时,通过回溯使规划器可以利用前一步的搜索结果来继续进行加强爬山搜索。有用动作排序使规划图和状态空间搜索更好地结合在一起。以上两种方法可以有效地解决死点问题。基于以上两点,本文提出了一种新的规划算法BTFF,即带有回溯和有用动作排序的FF规划算法。本文将回溯应用在规划解的提取过程中,同时将规划图理论和状态空间理论有机地结合在一起,很好地解决了死点状态问题。基于新算法的BTFF规划器相对于FF规划器,极大地提高了求解效率和解决问题的范围,具有很重要的学术意义和研究价值。