基于前瞻策略的自動規(guī)劃方法研究.pdf

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

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

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