1、近二十年來，智能規(guī)劃方法在求解速度和求解范圍上取得了飛躍，其主要的推動是基于啟發(fā)式搜索的規(guī)劃方法。學(xué)界對該類方法中的啟發(fā)函數(shù)進行了大量研究，設(shè)計了很多有效的啟發(fā)函數(shù)。啟發(fā)函數(shù)的作用是引導(dǎo)搜索算法在狀態(tài)空間上經(jīng)過較少的狀態(tài)即能發(fā)現(xiàn)目標(biāo)狀態(tài)。本文研究運用新的搜索方式來降低搜索算法所需經(jīng)歷的狀態(tài)數(shù)量。
　　本文運用的搜索方式包含狀態(tài)空間的普通擴展和狀態(tài)空間的“前瞻”式擴展兩種策略。在普通擴展策略下，每次擴展使用單個動作；在“前瞻”式擴展

2、策略下，每次擴展使用多個動作構(gòu)成的“動作串”。動作串稱為“宏動作”（Macro Action）。不同于傳統(tǒng)的搜索過程，增加了“前瞻”策略的搜索過程不僅能以單步方式向前擴展而且能以相當(dāng)于兩步以上的連續(xù)多步方式向前擴展。因此，該搜索過程有望通過更少的狀態(tài)訪問發(fā)現(xiàn)目標(biāo)狀態(tài)、完成規(guī)劃求解。
　　本研究的關(guān)鍵是計算宏動作的新方法。不同于學(xué)界已有的僅僅利用“松弛規(guī)劃圖”信息構(gòu)造宏動作的方法，本文提出了結(jié)合松弛規(guī)劃圖和“Landmark知識”兩

3、類信息的新方法。本方法依據(jù)“松弛規(guī)劃解”確定宏動作的候選動作和候選順序，依據(jù)“Landmark知識”調(diào)整候選順序，采用增量構(gòu)建的方式計算盡可能長的宏動作。本方法的特色在于，松弛規(guī)劃圖反映了在不考慮動作的“刪除效果”情況下的動作順序，Landmark知識反映了在考慮動作的“刪除效果”情況下的動作順序，兩類信息的結(jié)合有望構(gòu)造長度更大的宏動作，從而引導(dǎo)搜索算法以更多的等價步數(shù)向前搜索。
　　本文在總結(jié)啟發(fā)式搜索方面相關(guān)概念與進展的基礎(chǔ)上