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

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

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

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