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

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

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

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