帶有回溯和有用動作排序的FF規(guī)劃算法研究.pdf

1、智能規(guī)劃是人工智能的一個重要領(lǐng)域。近年來，有關(guān)智能規(guī)劃的研究在問題描述和問題求解兩方面得到了新的突破，使得智能規(guī)劃已成為一個熱門的人工智能研究領(lǐng)域。對智能規(guī)劃算法的研究主要集中在規(guī)劃算法性能的提高和規(guī)劃算法求解問題的范圍的擴展?；谝?guī)劃圖原理和啟發(fā)式狀態(tài)空間搜索的智能規(guī)劃算法在眾多的智能規(guī)劃算法中表現(xiàn)十分突出。FF規(guī)劃器將規(guī)劃圖和啟發(fā)式狀態(tài)空間搜索原理進行了很好的結(jié)合，在兩屆IPC(InternationalPlanningCompet

2、ition)中取得了優(yōu)異的成績。但是FF規(guī)劃算法所采用的搜索方法和規(guī)劃圖的使用上都存在很大不足，使得FF規(guī)劃算法在某些規(guī)劃問題域中，特別是含有死點狀態(tài)的問題域中表現(xiàn)不夠理想。 本文通過對規(guī)劃圖原理、啟發(fā)式狀態(tài)空間搜索原理和FF規(guī)劃算法的研究，提出了一種更適合FF規(guī)劃器使用的搜索方法——帶有回溯的加強爬山搜索算法，同時在規(guī)劃圖的使用中加入了有用動作排序并且探索了多種排序標(biāo)準(zhǔn)。帶有回溯的加強爬山算法在加強爬山算法失敗時，通過回溯使規(guī)

3、劃器可以利用前一步的搜索結(jié)果來繼續(xù)進行加強爬山搜索。有用動作排序使規(guī)劃圖和狀態(tài)空間搜索更好地結(jié)合在一起。以上兩種方法可以有效地解決死點問題?；谝陨蟽牲c，本文提出了一種新的規(guī)劃算法，即帶有回溯和有用動作排序的FF規(guī)劃算法。 本文將回溯應(yīng)用在規(guī)劃解的提取過程中，同時將規(guī)劃圖理論和狀態(tài)空間理論有機地結(jié)合在一起，很好地解決了死點狀態(tài)問題。基于新算法的BTFF規(guī)劃器相對于FF規(guī)劃器極大地提高了求解的效率和解決問題的范圍。因此本文具有很重